DOCUMENTACIÓ TORRES DE HANOI


Descripció

Tenim "n" discos de diferents mides amb un forat al centre i 3 pals. Comencem amb tots els discos apilats de més gran a més petit en el primer pal i volem posar-los al tercer pal en el mateix ordre. Cal tenir en compte, que un disc només es pot posar sobre un altre disc si aquest segon és més gran. I només podem moure un disc si no en té cap més a sobre.

Enumerem cada disc amb un nombre, de manera que aquests nombres representin les mides dels discos. O sigui, el disc x és més gran que el disc y si x>y.

Exemple (torres de 4 discs):

Les torres A, amb un sol moviment poden generar B, C o D.

A

3

4

1

2

B

4

1

2

3

C

1

3

4

2

D

3

4

2

1

Per evitar cicles, utilitzem el mateix sistema que en el 8-puzzle (la llista amb tots els nodes oberts).

Heurístiques i Cost

- Heurístiques:

- Cost: Nombre de passos per arribar a aquestes torres des de les torres inicials.

- Exemples (torres de 8 discs):

1

2

3

4

5

6

7

8

3

4

5

6

7

8

1

2

4

5

6

7

8

2

1

3

Primer exemple:

Segon exemple:

Tercer exemple:

Inici Anterior