Trovare il percorso minimo con ritorno?

Question

Trovare il percorso minimo con ritorno?

#1 da (1 voti)

1

Ho difficoltà a comprendere una domanda del quiz precedente che ho ricevuto:

Bobby lavora a Starbucks a San Mateo (V). Sta facendo test di garanzia della qualità e deve visitare i negozi di Palo Alto (B), Tenderloin (C) e San Jose (S) - e poi tornare a San Mateo per un incontro.

Le distanze tra i negozi sono:

V → B = 2
V → C = 3
V → S = 6
B → C = 1
B → S = 5
C → S = 4

Qual è il primo negozio che visita nella soluzione ottimale a questo problema?

Come approveresti a risolvere questo problema? Mi ricorda un po 'l'algoritmo di Djistra ma sospetto che ci sia un modo più semplice se non provare tutte le combinazioni poiché il limite di tempo è breve.

La mia interpretazione:

  B__1__C
  |     |
2 |     | 4
  |__6__|
  V     S

Affinché Bobby possa visitare tutti e 4 i negozi e tornare a V, inizia semplicemente a V e percorre i bordi della casella sopra. Ma la domanda è chiedere qual è il primo negozio? Entrambe le direzioni daranno un totale di 13, quindi come è la risposta giusta?

algorithms

posta theintellects 05.02.2014 - 00:02

fonte

1 risposta

Leggi altre domande sui tag algorithms

MVC Ottimizzazione dei widget durante l'accesso a CSS e risorse Aggiunta trasparente di un livello di interfaccia del database

score 1 · Accepted Answer

La risposta giusta è quel percorso che ha il minor costo. Anche se questo è tecnicamente un commesso viaggiatore e una soluzione esatta è molto difficile da raggiungere rapidamente, in genere è possibile ottenere un percorso ottimale o quasi ottimale utilizzando un algoritmo avido e novità affamato.

L'algoritmo è quindi:

Per il nodo corrente seleziona il percorso con il minor costo a condizione che porti a un nodo che non hai visitato in precedenza. Viaggia al nuovo nodo e ripeti fino a quando tutti i nodi, ma l'origine sono stati visitati. Quindi visita l'origine per percorso di costo minimo.

Iniziamo con un grafico vuoto:

Quindicontrassegniamoilnodocorrentecome"visitato" (in grassetto) e seguiamo il percorso di costo minimo per un nodo non visitato:

Continuiamoquestoschemaperiprossimiduenodi:

Oranonabbiamonuovinodidavisitaremaabbiamoilnododiorigineconnesso,cosìprendiamoquelpercorso:

Così arriviamo alla nostra soluzione. Questo algoritmo è il più ottimale per i grafici completamente connessi con bordi chiaramente ponderati. Ovviamente abbiamo usato una forma dell'algoritmo di Dijkstra che conferma ciò che sospettavi. Il miglior costo possibile è 13.