Problema: riempi tutte le celle usando numeri distinti da < 1,25 > impostato, in modo che la somma di due celle adiacenti sia un numero quadrato.
(fonte:
Ho già risolto questo problema analiticamente e ora mi piacerebbe affrontarlo usando un algoritmo.
Mi piacerebbe sapere come dovrei affrontare questo tipo di problemi in generale (non una soluzione, solo un punto da cui iniziare)
La chiave è riconoscere che questo è in realtà un altro problema, il venditore ambulante.
Ogni numero compreso tra 1-25 è un vertice. Se x + y = quadrato, allora c'è un margine tra x e y. Per n numeri, puoi costruire questo grafico in O (n ^ 2). Ora visita ciascun nodo in modo che nessun nodo venga visitato più di una volta. Questo è NP-Complete e l'essenza di TSP.
Una volta riconosciuta questa variante, puoi iniziare adattando le soluzioni a TSP alla tua specifica istanza.
Leggi altre domande sui tag numbers algorithms