Chapter 4. Problémamegoldás redukcióval

Gyakran előfordul, hogy egy problémát úgy próbálunk megoldani, hogy több külön-külön megoldandó részproblémára bontjuk. Ha a részproblémákat megoldjuk, az eredeti probléma megoldását is megkapjuk. A részproblémák megoldását további részek megoldására vezetjük vissza, egészen addig, amíg csupa olyan problémához nem jutunk, amelyeket egyszerűségüknél fogva már könnyedén meg tudunk oldani. A probléma megoldásnak ezt a módját problémaredukciónak nevezzük.

4.1. Problémaredukciós reprezentáció

  • Először is le kell írni az eredeti problémát, jelöljük ezt most -vel.

  • Egy probléma részproblémákra bontása során a nyert részek az eredeti problémához hasonló, de annál egyszerűbb problémák.

    Jelöljük az így nyert problémahalmazt -vel. Természetesen .

  • problémáinak összegyűjtése során törekszünk arra, hogy legyenek közöttük olyanok, melyeket meg tudunk oldani, vagy ismerjük a megoldásukat. Ezek a problémák az ún. egyszerű problémák.

    Az egyszerű problémák halmazát -vel jelöljük.

    , hiszen , különben nincs megoldandó feladat.

  • Meg kell még adni a problémákat egyszerűsítő, illetve részekre bontó redukciós operátorokat. Egy redukciós operátor egy problémához azokat a (rész)problémákat rendeli hozzá, melyek egyenkénti megoldásával a probléma megoldása is előáll. Jelöljön a redukciós operátorok véges halmazából egy operátort. Ekkor

    Equation 4.. 


    Tehát egy redukciós operátor egy-egy problémához egy-egy részhalmazát rendeli, így értékkészlete hatványhalmazának valamely részhalmaza.

Definíció:

Legyen egy probléma. Azt mondjuk, hogy a problémát problémaredukciós reprezentációval írtuk le, ha megadtuk a négyest, azaz

  • a megoldandó problémát,

  • a halmazt, a problémához hasonló problémák halmazát,

  • az egyszerű problémák halmazát és

  • a redukciós operátorok véges halmazát.

Jelölése: .

Definíció:

Legyen a probléma a reprezentációval leírva és legyenek

Equation 4.. 


Equation 4.. 


egy-egy problémahalmaz (). Azt mondjuk, hogy a problémahalmaz egy lépésben vagy közvetlenül redukálható a problémahalmazzá, ha van olyan redukciós operátor, melyre , és

Equation 4.. 


Ennek jelölése: , illetve ha fontos, hogy az redukciós operátor segítségével állítottul elő -ból a -t, akkor .

Definíció:

Legyen a probléma reprezentációja , és . A -ból a redukálható, ha van olyan véges problémahalmaz-sorozat, hogy

Equation 4.. 


és minden esetén. Jelölése: .

Definíció:

Nyilvánvaló, hogy ha minden esetén, akkor van olyan redukciós operátorsorozat, hogy . Ilyenkor azt mondjuk, hogy a problémahalmazt a problémahalmazzá az redukciós operátorsorozat segítségével redukáltuk. Jelölve: .

Definíció:

Legyen a probléma problémaredukciós reprezentációja . A probléma megoldható ebben a reprezentációban, ha csupa egyszerű problémából álló problémahalmazzá redukálható, azaz

Equation 4.. 


Ekkor az redukciós operátorsorozatot tekinthetjük a probléma megoldásának.

A feladatunk lehet

  • annak eldöntése, hogy megoldható-e a probléma az adott problémaredukciós reprezentációban,

  • egy (esetleg az összes) megoldás előállítása,

  • valamilyen minősítés alapján jó megoldás előállítása (a megoldások között különbséget tehetünk, pl. a megoldás költsége alapján).

Jelölje az redukciós operátor problémára való alkalmazásának a költségét, és ha , akkor pedig a egyszerű probléma közvetlen megoldásának költségét.

Definíció:

A problémaredukciós reprezentációban a probléma megoldásának minimális költsége, ha

Equation 4.. 


A részproblémák párhuzamos megoldása esetén lehetőségünk van a legrövidebb idő alatt előállítható megoldás megkeresésére. Ekkor az redukciós operátor problémára való \textbf{alkalmazásának a végrehajtási idejét}, pedig a egyszerű probléma közvetlen megoldásának idejét jelenti.

Definíció:

A problémaredukciós reprezentációban a probléma megoldásának minimális ideje, ha

Equation 4..