Gioco del 15 e formalizzazione matematica

Caroncino
Salve,

Nel famoso gioco del 15 dovrei riuscire a portare la casella 1 al suo posto (cioè in alto a sinistra), da qualunque posizione essa si trovi, con il minor numero di spostamenti di caselle possibili. Ho scoperto sperimentalmente che risolvo il problema spostando la casella 1 diagonalmente a "zig zag" e poi eventualemte spostandomi in orizzontale o in verticale se incontro il lato superiore o sinistro del quadrato. In tal modo gni volta che muovo la casella 1 ho uno spostamento complessivo di 3 caselle in totale (compresa la 1), quando mi muovo a zig zag, e 5 postamenti di caselle quando mi muovo orizzontalmente o verticalmente. Ora questo dovrebbe essere l' "algoritmo ottimo di risoluzione". Ora il mio problema sta nel trovare una formalizzazione matematica che mi giustifichi tale algoritmo. Come posso fare?

Risposte
TomSawyer1
Se andassi solo orizzontalmente e verticalmente (cioe' se per esempio ti spostassi a sinistra fino a toccare il bordo, poi in alto) , allora dovresti spostare ogni volta 5 caselle, per far avanzare la 1. Invece, andando a zig-zag, come hai detto tu, sposti due caselle in meno che seguendo la prima strada. Non c'e' uno studio complicato sotto.

motorhead
lo trovi su wikipedia anche in italiano , ricordo di averlo visto

Caroncino
Se invece del quadrato avessi un rettangolo, magari fortemente sbilanciato, come posso giustificare che il mio caso peggiore è quando la casella 1 è in fondo a destra e il posto vuoto deve essere in alto a sinistra? Inoltre posso formalizzare un algoritmo che mi indichi qual è il percorso che nel minor tempo (e quindi con il minor numero di spostamenti di caselle) mi porti la casella 1 al suo posto?
Grazie :?

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.