Migliore strategia di attraversamento / Guida logica necessaria

3

Sfondo: ecco lo scenario, immagina di avere un piccolo robot. Dò a questo robot una mappa, e voglio che lui attraversi la mappa, dopo averlo fatto, voglio che il robot mi dica il percorso più breve possibile sulla mappa. Quindi ecco un esempio di una mappa:

Difficoltà: Il robot riceve la mappa sotto forma di HashMap. Per la mappa di cui sopra sarà qualcosa di simile a questo:

A > B, E
B > A, C, E
C > B, E
D > E
E > A, B, C, D, F
F > E

Quindi il nodo [A] ha i vicini [B] e [E] e così via. Il robot può conoscere solo i vicini del nodo in cui si trova attualmente.

Quindi solo quando sul nodo [A] il Robot saprà che i vicini di [A] sono [B] e [E]. Il Robot non ha modo di sapere cosa hanno i vicini [B] a meno che non sia in [B], una volta lì, il Robot può chiamare il metodo getNeighbouringNodes () per scoprire i vicini (Returned to Robot as una lista).

Pensiero corrente: al momento la mia logica per ottenere il percorso più breve da Start a Exit è la seguente:

In sostanza, si tratta di una prima svolta di ampiezza. Una volta sul nodo di partenza [A], ottengo l'elenco dei nodi adiacenti, quindi visita il primo vicino nell'elenco [B].

Una volta in [B] chiamo il metodo isThisAnExitNode () per verificare che [B] sia un nodo di uscita, se sì, scrivi il mio percorso breve ed esisto la mappa. Se no, torno al nodo [A] e afferro il prossimo prossimo di [A] che è [E].

Fai lo stesso con [E], ora se non è stato trovato nessun nodo di uscita, passo a [B] per esplorare i suoi vicini.

Penso che tu abbia avuto l'idea.

La mia domanda è, lo sto facendo bene? Esiste un modo migliore, più efficiente del mio metodo di attraversamento?

Qualsiasi aiuto sarebbe molto apprezzato.

Grazie.

    
posta J86 20.01.2013 - 04:25
fonte

1 risposta

4

Se conosci il tuo nodo iniziale (che in questo caso lo fai), puoi usare Algoritmo di Dijkstra per trovare il percorso più breve. Sebbene tu non abbia specificato se ci sono pesi per i percorsi, ne tiene conto anche se non ci sono valori negativi consentiti nei pesi.

Questo presuppone che il robot abbia una qualche forma di memoria. Non è in grado di vedere parti della mappa a cui non è adiacente, ma memorizzare i vertici e i loro pesi è un must per qualsiasi tipo di algoritmo efficiente.

    
risposta data 20.01.2013 - 10:34
fonte

Leggi altre domande sui tag