Appetito aracnide (tecla)


#1

Qualcuno è capace di spiegarmi una volta per tutte come si risolve questo problema? :tired_face:

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 :scream:


Territoriali 2017 Tecla 30/100
#2

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 …


#3

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


#4

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.