Trovare una buona euristica per una ricerca *

Question

Sto cercando di trovare la soluzione ottimale per un gioco di puzzle poco chiamato Twiddle (un applet con il gioco può essere trovato qui ). Il gioco ha una matrice 3x3 con il numero da 1 a 9. L'obiettivo è quello di portare i numeri nell'ordine corretto utilizzando la minima quantità di mosse. In ogni mossa è possibile ruotare un 2x2 piazza in senso orario o antiorario.

vale a dire. se si dispone di questo stato

6 3 9
8 7 5
1 2 4

e si ruota la 2x2 in alto a sinistra in senso orario quadrato si ottiene

8 6 9
7 3 5
1 2 4

Io sto usando un A * cercare di trovare la soluzione ottimale. La mia f () è semplicemente il numero di rotazioni necessarie. La mia funzione euristica già porta alla soluzione ottimale (se ho modificarlo, vedere l'avviso di t alla fine), ma non credo che sia il migliore che si può trovare. Il mio euristica corrente assume ogni angolo, guarda il numero di all'angolo e calcola la distanza Manhattan alla posizione di questo numero avrà nello stato risolto (che mi dà il numero di rotazione necessaria per portare il numero a questo postion) e le somme tutte questi valori. Cioè Si prende l'esempio precedente:

6 3 9
8 7 5
1 2 4

e questo stato finale

1 2 3
4 5 6
7 8 9 

quindi l'euristica fa il seguente

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 and should by at index 0: 2 rotations needed
4 is currently at index 8 and should by at index 3: 3 rotations needed

h = 3 + 2 + 2 + 3 = 10

Inoltre, se h è 0, ma lo stato non è completamente ordinato, di h = 1.

Ma c'è il problema, che si ruota 4 elementi in una sola volta. lì così un raro caso in cui si possono fare due (minerale di più) di tesi di rotazioni in una mossa stimati. Questo mezzo tesi euristica sovrastime la distanza alla soluzione.

La mia soluzione attuale è, semplicemente escluso uno degli angoli del calcolo che risolve questo problema, almeno per i miei test-casi. Ho fatto alcuna ricerca se davvero risolve il problema o se questo sovrastima ancora euristiche in alcuni edge-casi.

Quindi la mia domanda è: Qual è il miglior euristica che si può trovare con

(Disclaimer: Questo è per un progetto universitario, quindi questo è un po 'di compiti a casa, ma io sono liberi di utilizzare qualsiasi risorsa se può venire con, quindi è bene chiedere voi ragazzi anche io credito StackOverflow per.. mi aiuta;))

Answer 1

Simplicity is often most effective. Consider the nine digits (in the rows-first order) as forming a single integer. The solution is represented by the smallest possible integer i(g) = 123456789. Hence I suggest the following heuristic h(s) = i(s) - i(g). For your example, h(s) = 639875124 - 123456789.

Answer 2

All elements should be taken into account when calculating distance, not just corner elements. Imagine that all corner elements 1, 3, 7, 9 are at their home, but all other are not.

It could be argued that those elements that are neighbors in the final state should tend to become closer during each step, so neighboring distance can also be part of heuristic, but probably with weaker influence than distance of elements to their final state.

Answer 3

You can get an admissible (i.e., not overestimating) heuristic from your approach by taking all numbers into account, and dividing by 4 and rounding up to the next integer.

To improve the heuristic, you could look at pairs of numbers. If e.g. in the top left the numbers 1 and 2 are swapped, you need at least 3 rotations to fix them both up, which is a better value than 1+1 from considering them separately. In the end, you still need to divide by 4. You can pair up numbers arbitrarily, or even try all pairs and find the best division into pairs.