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.