Le mosse di un cavallo per ricoprire tutta la scacchiera
Salve a tutti!
Stavo cercando di implementare un algoritmo che, data una scacchiera quadrata di n caselle, scriva su un file tutti possibili tragitti che un cavallo potrebb fareper ricoprire tutta la scacchiera senza passare per due volte sulla stssa casella. La prima soluzione, ovvia, è una funzione ricorsiva con backtracking, solo che ha complessità esponenziale!!! Ammettendo che il suo tempo di calcolo sia proporzionale a $k^n$, trova su una scacchiera di 25 caselle (5*5) 1728 soluzioni in 9 secondi. Su una scacchiera di 36 caselle impiegherà circa $k^36 = 9*k^11$ secondi (ho provato a lasciarlo girare per tutto il pomeriggio e non ha finito come previsto).
Ho pensato che si potrebbe ripensare il problema come se ogni casella fosse il nodo di un grafo e le mosse del cavallo dei ponti trai nodi, ma comunque questo non i aiuterebbe a diminuire la complessità dell'algoritmo, al massimo potrebbe diventare più veloce il ciclo interno della funzione.
C'è qualcuno che mi può aiutare? Penso che il problema abbia anche altre applicazione perchè si può anche riformulare come trovare il massimo percorso possibile in un grafo senza passare due volte per lo stesso nodo.
Stavo cercando di implementare un algoritmo che, data una scacchiera quadrata di n caselle, scriva su un file tutti possibili tragitti che un cavallo potrebb fareper ricoprire tutta la scacchiera senza passare per due volte sulla stssa casella. La prima soluzione, ovvia, è una funzione ricorsiva con backtracking, solo che ha complessità esponenziale!!! Ammettendo che il suo tempo di calcolo sia proporzionale a $k^n$, trova su una scacchiera di 25 caselle (5*5) 1728 soluzioni in 9 secondi. Su una scacchiera di 36 caselle impiegherà circa $k^36 = 9*k^11$ secondi (ho provato a lasciarlo girare per tutto il pomeriggio e non ha finito come previsto).
Ho pensato che si potrebbe ripensare il problema come se ogni casella fosse il nodo di un grafo e le mosse del cavallo dei ponti trai nodi, ma comunque questo non i aiuterebbe a diminuire la complessità dell'algoritmo, al massimo potrebbe diventare più veloce il ciclo interno della funzione.
C'è qualcuno che mi può aiutare? Penso che il problema abbia anche altre applicazione perchè si può anche riformulare come trovare il massimo percorso possibile in un grafo senza passare due volte per lo stesso nodo.
Risposte
Non so se c'entra ma un problema simile è quello di passare per tutti i vertici passando al più una volta su tutti gli spigoli. Tali cammini sono detti hamiltoniani ma al momento non sono note condizioni necessarie perchè un grafo ne possegga.
In rete ho trovato 2 risorse interessanti.
[url]
http://www.matematicaeliberaricerca.com ... cacchi.htm[/url]
Mentre il secondo è orientato ai grafi
http://xoomer.alice.it/vdepetr/t18/Text18.htm
[url]
http://www.matematicaeliberaricerca.com ... cacchi.htm[/url]
Mentre il secondo è orientato ai grafi
http://xoomer.alice.it/vdepetr/t18/Text18.htm
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo