Calcolare il percorso più breve attraverso un negozio di alimentari

Question

Sto cercando un modo per trovare il percorso più breve attraverso un negozio di alimentari, visitando un elenco di località (lista della spesa). Il percorso dovrebbe iniziare in una posizione di partenza specificata e terminare a più posizioni finali (ci sono più contatori di cassa). Inoltre, ho alcuni vincoli predefiniti sul percorso, come "l'articolo x sulla lista della spesa deve essere l'ultimo, il penultimo o il terzo ultimo elemento sul percorso". Esiste una funzione che restituirà true o false per un determinato percorso. Infine, questo deve essere calcolato con potenza CPU limitata (su uno smartphone) e entro un secondo circa. Se questo non è possibile, allora anche un'approssimazione al percorso ottimale è ok.

È possibile? Finora penso di dover iniziare calcolando la distanza tra ogni elemento della lista usando qualcosa come A * o Dijkstra. Dopo, dovrei trattarlo come il problema del commesso viaggiatore? Perché nel mio problema c'è un nodo iniziale specificato, nodi finali specificati e alcuni vincoli, che non sono nel problema del commesso viaggiatore.

Answer 1

Beh, in fondo si tratta di un problema di commesso viaggiatore, ma con le vostre esigenze si limita lo spazio di ricerca piuttosto bene. Se non ci sono troppe location, puoi provare a calcolare tutte le opzioni possibili, ma se ciò non è fattibile, devi limitare ancora di più lo spazio di ricerca.

È possibile limitare il tempo di ricerca in modo da restituire il percorso più breve che è possibile trovare in 1 secondo, ma che potrebbe non essere il più breve di tutti, ma comunque piuttosto breve.

si potrebbe applicare anche Greedy algorithm per trovare la posizione più vicina successivo, quindi utilizzando Backtracking selezionare la posizione più vicina successivo ecc

Pseudo codice per possibile soluzione:

 
def find_shortest_path(current_path, best_path): 
    if time_limit() 
    return 

    if len(current_path) == NUM_LOCATIONS: 
     # destionation reached 
     if calc_len(current_path) < calc_len(best_path): 
      best_path = current_path 
     return 

    # You need to sort the possible locations well to maximize your chances of finding the 
    # the shortest solution 
    sort(possible_locations) 

    for location in possible_locations: 
     find_shortest_path(current_path + location, best_path) 

Answer 2

Beh, si potrebbe limitare la ricerca -space utilizzando le informazioni sul layout del negozio. Ad esempio, un negozio tipico (almeno qui in Germania) ha molti scaffali che possono essere considerati per formare delle corsie. In mezzo ci sono delle corsie ortogonali che collegano le corsie degli scaffali. Ora definisci le traversine come nodi e le corsie come bordi in un grafico. I bordi sono etichettati con tutti gli articoli nei ripiani di quella sezione di corsia. Ora, anche per un grande negozio questo grafico sarebbe piuttosto piccolo. Dovresti ora trovare il percorso più breve che include tutte le etichette bordo (elementi) di cui hai bisogno. Ciò dovrebbe essere possibile utilizzando l'approccio avido/backtracking Tuomas Pelkonen suggested.

Questa è solo un'idea, e non so se funziona davvero, ma forse puoi prenderla da qui.

Answer 3

Solo la ricerca per ampiezza prima farà in modo di non "perdere" un percorso attraverso lo store che è migliore della soluzione "migliore" corrente, ma non è necessario cercare ogni nodo nel percorso. Nodi che sono "ovviamente" più lunghi dell'attuale soluzione "migliore" possono essere espansi successivamente.

Ciò significa che il problema si avvicina come una ricerca "breath first", ma modifica l'espansione dei nodi in base alla distanza percorsa corrente. Alcuni rami dell'albero di ricerca si espandono più velocemente di altri, poiché riescono a visitare più nodi nello stesso intervallo di tempo.

Quindi, se l'espansione del nodo non è veramente mozzafiato, perché continuo a usare quella parola? Perché dopo aver trovato una soluzione, è necessario espandere ancora il set corrente di "nodi considerati" fino a quando ognuno di quei percorsi di ricerca supera la soluzione. Ciò evita di perdere un percorso che richiede molto tempo per le gambe iniziali, ma termina più velocemente rispetto alla soluzione attuale perché l'ultimo passaggio è l'illuminazione veloce.

Answer 4

Il requisito di un nodo di avvio è fittizio. Usando il TSP ti ritroverai con un tour in cui puoi scegliere il nodo iniziale che vuoi senza alterare il costo della soluzione.

È piuttosto complicato quando si tratta dei contatori: ciò di cui si ha bisogno è risolvere il problema su un grafico diretto con alcuni archi mancanti (o, che è lo stesso, dove alcuni archi hanno un costo molto alto).

A partire dal grafo orientato completo è necessario modificare i costi degli archi appropriate al fine di:

1. negare che va dagli elementi al nodo di partenza
2. negare che va dai contatori agli elementi
3. negare che va dal nodo di partenza per i contatori
4. permettono va dai contatori al nodo di partenza a costo zero (questo sono necessarie solo per chiudere il percorso)
5. dopo aver disegnato t egli cosa giù, dimmi se ho perso qualcosa :)

HTH

Answer 5

Sembra che la visione come un problema TSP rende più difficile. Qualcuno ha sottolineato che le storie alimentari non sono così complicate. Nei negozi di alimentari con cui ho familiarità (negli Stati Uniti), non ci sono molti percorsi ragionevoli. Soprattutto se hai un determinato punto di partenza. Penso che un'euristica ben ponderata probabilmente farà il trucco.

Ad esempio: in genere inizio ad una estremità, se è un grande viaggio, mi assicuro di passare per ultimo i cibi surgelati, ma spesso non importa e inizierò più vicino a dove entro nel negozio . Generalmente vado in giro per l'esterno, scendendo solo nei corridoi individuali se ho bisogno di qualcosa in quello. Una volta che vai in un corridoio, raccogli tutto in quello. Con alcuni corridoi è meglio cadere in un'estremità, afferrare l'oggetto e tornare al punto di partenza, mentre altri si limitano a passare all'intero corridoio: è una funzione dell'ultimo elemento di cui si ha bisogno in quel corridoio e dove è necessario per essere il prossimo-- come uscire dal corridoio dipende dal prossimo elemento necessario-- potrebbe o meno comportare un ritorno alla storia-- ma il computer può facilmente calcolare il percorso più breve per gli oggetti successivi.

Quindi sono d'accordo con i suggerimenti utili degli altri problemi di cui sopra, ma forse funzionerà un algoritmo meno generale. E probabilmente funzionerà meglio con risorse limitate. TSP ci dice, tuttavia, non è possibile dimostrare che sia l'approccio ottimale ma sospetto che non sia davvero necessario ...