Trovare un percorso hamiltonianico in un grafico

Question

Dichiarazione del problema

Dato un grafico di tutti i quadrati blu nella seguente immagine in cui ogni quadrato blu è collegato ad altri quadrati blu in tutte e 4 le direzioni cardinali.

Dato qualsiasi nodo iniziale.

Quale algoritmo permetterà di trovare il percorso più lungo (ISH).

Considerando che ogni nodo può essere visitato solo una volta.

Considerando che non ci interessa dove finisce il percorso.

Considerando che la velocità è più importante che visitare necessariamente ogni nodo.

Esempio

Ho rintracciato un esempio del risultato desiderato nell'immagine qui sotto.Come puoi vedere, il percorso non visita ogni nodo e questo va bene.Sto cercando un algoritmo veloce che mi darà uno dei sentieri più lunghi su questo grafico.80% copertura o più è ciò che sto riprendendo.

Answer 1

Ho finito per usare il UCT (MCTS con UCB1) Algoritmo ma con una svolta.

Normalmente, in UCT, la fase di simulazione è una riproduzione simulata di un gioco con mosse scelte a caso. Se il gioco simulato finisce in una vittoria, il punteggio del nodo, da dove è stato giocato la simulazione, e tutti i punteggi dei genitori sono tornati alla radice, vengono incrementati da 1.

Nella mia implementazione, il "gioco-through" simulato è in realtà solo una camminata casuale lungo l'albero delle piastrelle vicine che non sono state ancora visitate. Una volta che la simulazione raggiunge un nodo del terminale (vicolo cieco) assegna un punteggio di S= D / m dove D è la profondità del nodo del terminale nell'albero e M è la massima profondità possibile.

Su una griglia di 15 x 15 senza ostacoli, si imposta da M a 225 mentre il percorso più lungo visiterebbe ogni piastrella. Ho impostato il mio leggermente inferiore a quello che ho bisogno dell'algoritmo da generalizzare e lavorare su mappe generate a caso che di solito hanno 10-30 tessere occupate da ostacoli.

Invece di incrementare il punteggio dei genitori, l'algoritmo di backtracking imposta il punteggio di ciascun genitore al punteggio appena calcolato, se è superiore al loro punteggio corrente. In altre parole, il punteggio di un nodo rappresenta sempre la lunghezza del percorso più lungo raggiunto finora da questo nodo.

UCT utilizza UCB1 per selezionare il nodo da sfruttare o esplorare una volta che ogni figlio del nodo corrente sono stati ampliati e ho in gran parte tenuto con quello. L'unica modifica che ho fatto è il termine di sfruttamento. In UCB1, il termine di sfruttamento è w / v dove w è il punteggio accumulato del nodo e V è il numero di tempo il nodo è stato visitato. Questo funziona alla grande in un gioco in cui vuoi selezionare la mossa che massimizza le tue possibilità di vincere. Nel mio caso, dal momento che il punteggio non riflette una funzione binaria di win= 1 e perdere= 0 ma piuttosto una scala di 0= percorso super breve vs 1= il percorso più lungo possibile e voglio scendere il percorso più lungo trovato dall'algoritmo , Ho semplicemente impostato il termine di sfruttamento in S= Punteggio= percorso più lungo raggiungibile da questo nodo.

Il contesto in cui sto usando questo algoritmo mi consente di circa 40 ms di tempo di calcolo in un ambiente di nodejs prima di poter selezionare una mossa. Questo di solito offre circa 785 attraversali per alberi sulla mia macchina. In media, in quel periodo, e sulla mappa mostrava in OP, questo algoritmo troverà un percorso che è 70 nodi in profondità. Il che è più che sufficiente per i miei scopi che vedono mentre riesco ad eseguire nuovamente l'algoritmo il prossimo turno. In pratica, quando si utilizza questo algoritmo per selezionare le prossime mosse, finisco per viaggiare un percorso che è a 100-110 passi lunghi prima di colpire un vicolo cieco e copro una porzione molto grande delle piastrelle blu.

Per il divertimento ho eseguito l'algoritmo per molto più lungo e intorno a 300 000 attraversali (30 secondi sulla mia macchina), in media, in media sulla mappa mostrata in OP, trova un percorso che è 125 nodi profondi Vicino alla profondità massima su questa mappa.

Answer 2

Questo è il problema del percorso più lungo.È difficile trovare il percorso più lungo in un grafico generale.Puoi provare ad applicare qualsiasi algoritmo standard per trovare percorsi più lunghi.Cerca su questo sito per "percorso più lungo" e "percorso hamiltoniano" per trovare molti riferimenti.Dal momento che sei disposto ad accettare soluzioni suboppimali, potresti cercare un algoritmo euristico o approssimativo (ad esempio, utilizzando un algoritmo di ricerca locale).