Ho questo layout di un labirinto per cui ho problemi a pensare a come implementare una soluzione per:
So che ci sono molte risorse per gli algoritmi di risoluzione dei labirinti, ad es. http://www.astrolog.org/labyrnth/algrithm.htm ma non sono sicuro di quale algoritmo sia più adatto per un determinato labirinto.
Ci sono tre aree etichettate come "*" che sono le posizioni a cui MazeSolver deve recarsi prima di poter uscire dal labirinto dall'ingresso nella parte superiore della mappa.
Gradirei lo pseudo codice per risolvere ilparte delle isole labirinto. Vorrei cercare una soluzione semplice e il tempo ottimale non è davvero un problema. Il fatto è che anche se al risolutore viene fornita una panoramica del labirinto, potrebbe non essere del tutto preciso quando il risolutore del labirinto esegue effettivamente il labirinto, quindi è un po 'più complicato di codificarlo prima o usare un algoritmo che usa onnisciente vista del labirinto e ha bisogno di "metà" umana / fattibile se capisci cosa intendo ...
Mentre al programmatore robot / robot verrà fornita una mappa della miniera per ogni salvataggio, la mappa potrebbe non essere aggiornata a causa di nuove attività di mining o a causa di danni causati dall'evento.
Per questa applicazione è richiesto il robotprima di tutto individuare tutte le aree di salvataggio e determinare se sono occupate. Il robot dovrà essere totalmente autonomo. Quando questi sono stati studiati, il robot dovrebbe quindi controllare tutti i passaggi per gli esseri umani.
Il robot dovrebbe anche essere auto-navigante. Sebbene un sistema GPS sia una scelta naturale, in questo caso non può essere utilizzato a causa dello spessore del controsoffitto roccioso che impedisce qualsiasi segnale GPS, pertanto è anche necessario progettare un sistema di navigazione per il robot. A tal fine, al robot possono essere aggiunte piccole modifiche hardware, come sensori aggiuntivi o radiofari dispiegabili. Si noti che almeno uno dei rifugi si trova in un'isola.
risposte:
0 per risposta № 1Supponendo che non stai cercando un percorso più breve per uscire dal labirinto - qualsiasi percorso, crea un certo ordine per le tue Isole: island1,island2,...,islandk.
Ora, supponendo che tu sappia come risolvere un labirinto "normale", devi trovare percorsi da:
start->island1, island1->island2, ...., islandk->end
Alcuni commenti:
- La risoluzione del labirinto "normale" può essere fatta usando BFS, o DFS (il secondo non è ottimale però).
- Se stai cercando una soluzione più efficiente, puoi usare percorso più breve per tutti piuttosto che la risoluzione multipla di labirinti "regolari".
- Se stai cercando un percorso più breve, questa è una variante di Problema del commesso viaggiatore. Si discute della possibile soluzione Qui.
- Se vuoi passare anche attraverso tutti i passaggi, puoi farlo usando a DFS che continua fino a quando non vengono scoperti tutti i nodi. Ancora una volta, questo non sarà il percorso più breve, ma trovare il percorso più breve sarà NP-Hard.
0 per risposta № 2
Questo problema è legato al Problema del commesso viaggiatore problema, che è NP-Hard, quindi non mi aspetterei soluzioni rapide per un numero maggiore di isole.
Per un piccolo numero di isole, puoi farlo: per ogni 2 isole (compresa la posizione iniziale), calcola il percorso più breve tra di loro. Dato che sei interessato a distanze tra una frazione relativamente bassa di vertici, ti consiglio di usare il L'algoritmo di Dijkstra, poiché è relativamente semplice e può essere fatto a mano (per graf abbastanza grandi).
Ora hai le distanze più brevi tra tuttepunti di interesse ed è quando è necessario trovare il percorso ottimale hamiltoniano tra di loro. Fortunatamente, le distanze soddisfano una metrica, quindi puoi avere algoritmi di approssimazione 2 (facile, anche a mano) o anche di approssimazione 3/2 (non così facile), ma non sono noti algoritmi polinomiali.
Per una soluzione perfetta con 3 isole devi controllare solo 6 modi per visitarle (facile), ma per 6 isole puoi visitarle in 720 modi, e per n in n! così buona fortuna con quello.