4.2. Példák problémaredukciós reprezentációra

4.2.1. Hanoi tornyai

A legenda szerint egy szerzetesek lakta távol-keleti kolostor udvarán áll három rúd, amelyeken 64 különböző átmérőjű aranykorong található. Eredetileg mind a 64 korong egyetlen rúdra volt rárakva úgy, hogy minden korong alatt egy nála nagyobb volt. A szerzeteseknek az a feladatuk, hogy a korongokat helyezzék át az első rúdról a harmadik rúdra, egyszerre mindig csak egyet mozgatva úgy, hogy sohase rakjanak nagyobb korongot kisebbre. Amint mind a 64 korongot átpakolják a harmadik rúdra, eljön majd a világvége.

A legenda szerint a szerzetesek a munka elvégzésével a legidősebb társukat bízták meg. Sokat törte a fejét, gondolkodott, meditált, majd hirtelen világosság töltötte el: a feladatot három lépésben meg tudja oldani!

  1. lépés: Át kell vinni az első rúdon lévő felső 63 korongból álló tornyot a második rúdra.

  2. lépés: Át kell vinni az első rúdon lévő utolsó, legnagyobb korongot a harmadik rúdra.

  3. lépés: Át kell vinni a második rúdon lévő 63 korongból álló tornyot a harmadik rúdra.

A szerzetes másnap kiszögezte a templom kapujára az algoritmus leírását:

Módszer és út arra vonatkozóan hogy hogyan vigyünk át egy korongból álló tornyot az rúdról az -ra a felhasználásával:

  1. Abban az esetben, ha a torony egynél több korongból áll, bízd meg a legöregebb tanítványodat, hogy a szóban forgó torony felső korongját vigye át az rúdról a -re, miközben az -t használhatja.

  2. Vidd át magad az rúdon maradt egyetlen korongot az -ra.

  3. Abban az esetben, ha a torony egynél több korongból állt, bízd meg a legöregebb tanítványodat, hogy a szóban forgó torony felső korongját vigye át a rúdról az -ra, miközben az -t használhatja.

A legenda szerint tehát a hanoi szerzetesek problémaredukcióval próbálták megoldani az előttük álló feladatot. Adjuk meg most az elképzelésüknek megfelelő reprezentációt a módosított feladatra. A megoldandó feladat tehát: mindhárom az rúdon levő korong átvitele a rúdra ( felhasználásával). Ezt jelölhetjük a következőképpen:

Equation 4.. 


A megoldandó feladathoz hasonló feladatok a következők: az rúdon levő felső valahány korong átvitele a rúdra ( felhasználásával):

Equation 4.. 


Ezek közül egyszerűen megoldhatók, ha a felső korongot kell áthelyezni az rúdról egy olyan rúdra, amelyiken nincs ennél kisebb átmérőjű: s Minden nem egyszerű problémát három, az eredetinél egyszerűbb részre bonthatunk: