Algoritmo per labirinto tridimensionale

[paga92aren]

Problema: Trovare un algoritmo che ti permette di trovare l'uscita da un labirinto tridimensionale (grafo non piano) senza sapere la struttura del labirinto, ma a ogni crocevia (vertice) che raggiungi vedi quante strade partono (grado del vertice) e percorrendo una strada (arco) sai quali piazze unisce (vertici).

Possibile soluzione? posto la mia idea (banale) dimostrare se funziona o meno (la metto nascosta nel caso qualcuno voglia risolverlo per conto suo)

Testo nascosto:

Per ogni vertice numero le strade che partono da esso da 1 a n.
Algoritmo: ad ogni vertice prendo la prima strada successiva a quella in cui sono entrato (in senso ciclico) che non ho ancora preso da quel vertice

[Anér]

Potresti riformulare più dettagliatamente il problema? In particolare vorrei sapere cosa puoi ricordare e cosa no durante il percorso, e se le strade che partono da un vertice sono ordinate ciclicamente a priori o devo ordinarle io (questa domanda ha senso solo se ho la memoria corta).

[paga92aren]

Puoi ricordare tutto quello che hai visto, quindi non serve rispondere alla seconda domanda. (e' diverso da problema risolto a Brema....potremo proporre anche quello sul forum)

[FrancescoVeneziano]

Per trovare la via di uscita da un labirinto non vi è che un mezzo. A ogni nodo nuovo, ossia mai visitato prima, il percorso di arrivo sarà contraddistinto da tre segni. Se, a causa di segni precedenti su qualcuno dei cammini del nodo, si vedrà che quel nodo è già stato visitato, si porrà un solo segno sul percorso di arrivo. Se tutti i varchi sono già stati segnati allora bisognerà rifare la strada, tornando indietro. Ma se uno o due varchi del nodo sono ancora senza segni, se ne sceglierà uno qualsiasi, apponendovi due segni. Incamminandosi per un varco che porta un solo segno, ve ne apporteremo altri due, in modo che ora quel varco ne porti tre. Tutte le parti del labirinto dovrebbero essere state percorse se, arrivando a un nodo, non si prenderà mai il varco con tre segni, a meno che nessuno degli altri varchi sia ormai privo di segni.

[paga92aren]

Nonostante la lingua usata da Gulielmo da Baskerville credo di aver capito cosa fa...ma continua a mancare la dimostrazione che l'algoritmo funziona per tutti i grafi...se qualcuno prova potrebbe uscire un topic interessante.
Io in questo periodo ho molto da fare quindi non so se trovo tempo per dimostrare l'algoritmo di Gulielmo.

[fph]

Se preferite, nella lingua di Knuth e Dijkstra si chiama deep-first search.