Qualcuno è capace di spiegarmi una volta per tutte come si risolve questo problema?
Ho letto molto sull’algoritmo di dijkstra; l’idea l’ho ben capita, i programmi che ho visto molto meno.
Ciò che mi preoccupa e che almeno 1 dei 3 problemi della gara territoriale si basa sui percorsi, nella maggior parte dei casi si risolve con questo algoritmo
Qui gli archi non sono pesati, si può anche mettere da parte dijkstra, va bene una BFS o una DFS leggermente ritoccate.
Va tenuto presente che un percorso tipo 0 1 7 3 4 7 1 0 è una soluzione; una parte del percorso può essere un avanti e indietro purchè tra l’avanti e l’indietro ci sia un tratto che …
Ci riprovo, anche se sui percorsi non mi avvio nemmeno.
Comunque quel che mi chiedo è
nell’esempio riportato dal testo del problema non è un per
Quel che non capisco è questo:
Ragionando sul problema mi accorgo sempre che ci sono più percorsi funzionali al buon appetito, ad esempio 0 1 2 3 4 2 3 0
Quindi non riesco ad un algoritmo generale
Un qualunque percorso che parte dal nodo 0 e torna al nodo 0 composto da un numero di archi dispari è una soluzione valida e a seconda dell’algoritmo utilizzato si possono ottenere soluzioni diverse pur con gli stessi dati di input.
In una BFS o in una DFS si marcano i nodi già visitati per evitare di ripassarci qui si marcano ma per vedere se ritornando indietro da uno di questi si ottiene un percorso con numero di archi dispari se è così abbiamo terminato di andare a spasso per il grafo. In sostanza una volta arrivati al nodo x può bastare trovare un percorso chiuso dispari da questo nodo (es.se x=5 un percorso 5-2-3-5).
Se per andare da 0 a x si percorrono y archi altrettanti se ne faranno a tornare indietro e quindi
y+y+3 (o un qualsiasi altro percorso dispari) sarà dispari.