Előadó: Dr. Várterész Magdolna

2.3. Probléma-redukciós reprezentáció

2.3.1. Probléma-redukció

Nagyon gyakori a feladat egyszerűsítése, részproblémákra bontása.

p: a megoldandó probléma. Ezt valahogy le kell írni. Ez akár az állapottérrel
  is leírható, de most nem az a fontos. Ehhez a problémához hasonló problémákat keresünk.
P: probléma-halmaz (ebbe gyűjtjük össze őket)
   
p P ennek a mi problémánk is eleme lesz
e E P egy ismert probléma is legyen benne! Ez az egyszerű probléma.
  e: 1. meg tudjuk oldani, ismerjük a megoldását
    2. meg tudjuk mondani, hogy nem megoldható
     
Az induló problémát addig kellene gyúrni, alakítani, míg csupa egyszerű probléma nem állna elő.
     
r R redukciós operátor

  dom(r) P (egy problémaosztálybeli problémát tud egyszerűsíteni)
    van előfeltétele is!
  r: P 2P P részhalmazainak a halmazába képez tehát
  r(p) = {p1,...,pn} részproblémákra bont, egyszerű részekre bont (n 1)
     
<P,p,E,R> ezzel a négyessel tudjuk megadni a probléma probléma-redukciós
  reprezentációját
   

 


Def.:

P1 = {p1,...,pi-1,pi,pi+1,...,pn}
P2 = {p1,...,pi-1,q1,q2,...,qm,pi+1,...,pn}

P1-ből egy lépésben (közvetlenül) redukálható P2, ha van:

r R: pi dom(r) és r(pi) = {q1,...,qm}
   P1 P2

Def:

A P' problémahalmazból a P'' redukálható, ha van:

 

Mikor megoldható? Ha a kezdőproblémából (mint 1 elemű problémahalmazból) csupa megoldható egyszerű problémát tartalmazó halmazt redukálhatunk.

Megoldás: az azt megvalósító ri redukciós operátorsorozat.

Megint egy keresési feladattal állunk szemben: egy operátorsorozatot keresünk. Itt is lehet költség, redukciós operátor alkalmazási költsége.

Megoldás költsége: a megoldásban szereplő operátorsorozat alkalmazási költségeinek összege.

2.3.2. Szemléltetése

Problémánk probléma-redukciós reprezentációját a <P,p,E,R> négyessel tudjuk megadni.

  q P
n N egy problémát egy csúccsal jelölünk
  p P
s N start-csúcs
  e E P
t T N terminális csúcsok

 


 

r R    
r(q) = {q1,...,qk} k 1
   
r'(q) = {z1,z2,...,zl}    
     

1 csúcsból annyi élköteg indul, ahány redukciós operátort alkalmazunk, s egy élköteg annyi élből áll, ahány részprobléma állt elő.

ÉS, AND élköteg minden részproblémát egy élkötegben kell megoldani
VAGY, OR élköteg vagy az egyik redukció segítségével bontom
  részproblémákra, vagy a másikkal
<G,s,T> és/vagy problémaredukciós (reprezentációs) gráf, ahol:
  G: gráf
 

s:  start csúcs
  T: terminális csúcs(ok)
hiperút: olyan összefüggő része az és/vagy gráfnak, melyben minden
  csúcsból legfeljebb 1 ÉS-élköteg indul ki.
  (Ha 1 ÉS-élköteget 1-nek veszünk, akkor az út fogalmához
  jutunk).

A hiperút a start csúcsból indul, s a levelek: csupa megoldható terminális levelek.
A megoldást egy olyan hiperút szemlélteti, mely a start csúcsból indul, s levelei csupa megoldható terminális csúcsok. A megoldáskeresés során egy általánosabb gráfban egy részgráfot keresünk.

k(n, {n1,...,nk}) redukciós operátor alkalmazási költsége
     
,ahol K - csúcshalmaz  


     
 
æ
 0, ha n K
g(n,K) =
í
  
 
è
     
 
æ
 c(n) , ha n E megoldható
k(n,{}) =
í
  
 
è
 ,ha n nem megoldható


 

Tiszta ÉS-VAGY gráf: olyan gráf, amelyben minden csúcsból csak ÉS vagy csak VAGY élkötegek indulnak ki.

Például adott a következő ÉS-VAGY gráf:

Elérhető, hogy csak ÉS vagy csak VAGY élkötegeket tartalmazzon:

Fiktív csúcsokat kell beiktatni. Annyi kell, ahény VAGY élköteg indul ki. Mellette feltüntetve: melyik redukciós operátorral kaptuk.

 

Megoldáskereső módszerek:

  1. nem-módosítható megoldáskeresők (nem foglalkozunk velük)
  2. módosítható keresők
    1. visszalépéses (backtrack)
    2. keresőgráffal