Qual è il modo più efficiente di trovare un percorso attraverso un piccolo grafico mondiale?

https://stackoverflow.com/questions/221311

03-07-2019
|

Domanda

Ho un mare di nodi ponderati con bordi che collegano insieme gruppi di nodi. Questo grafico segue il tipico layout del piccolo mondo.

Vorrei trovare un algoritmo di ricerca del percorso, che non è costoso per la potenza del processore, per trovare un percorso lungo il percorso migliore in cui i nodi hanno il peso più favorevole, il percorso più veloce non è il fattore più importante. Questo algoritmo prende in considerazione anche il carico portante e il reinstradamento del traffico.

(sidenote: le reti neurali potrebbero essere utilizzate qui?)

Grazie

Sto guardando ACO . C'è qualcosa di meglio di ACO per questo tipo di problema?

Proprio l'algoritmo A * trova il minor costo o percorso più veloce, senza bilanciamento del carico.

Diciamo che il percorso più veloce o più breve non è il percorso più importante, ciò che è più importante è seguire un percorso in cui i nodi ponderati hanno un certo valore. no1.

no2. Se si utilizza A *, il traffico su quella rotta viene sovraccaricato, quindi improvvisamente quel percorso è ridondante. Così bello come A *, non ha alcune caratteristiche che ACO, ovvero il bilanciamento del carico intrinseco.

- A meno che non sia sbagliato e frainteso A *

Quindi cosa batte ACO?

Sembra davvero uno show down tra ACO e A *, ci sono stati così tanti discorsi positivi su A *, che sicuramente approfondirò.

In primo luogo in risposta a David; Posso eseguire la simulazione ACO nella parte posteriore e trovare il percorso migliore, quindi sì, c'è un costo iniziale di avvio, ma fortunatamente l'avvio non è essenziale. Quindi posso permettermi di eseguire una simulazione più volte. L'unico vero problema è trovare nodi di origine e destinazione collegati. Considerando che A * sarà in grado di farlo abbastanza facilmente. Ora cosa succede quando questa rete diventa tremendamente grande come in milioni di nodi. A * sarà in grado di ridimensionarsi facilmente?

Ricercherò ulteriormente A *. Ma ti lascio con un'ultima domanda!

Sarà possibile ridimensionare A * e Antnet (ACO)?

Soluzione

Note generali

L'algoritmo di Dijkstra e la variante ottimizzata A * trovano il percorso con "quot" costo minimo attraverso il tuo grafico. Le cose importanti sono a) definire correttamente il grafico eb) definire una funzione di costo appropriata.

Di fronte a una funzione di costo che cambia Dijksta richiede di ricalcolare la soluzione.

Per il bilanciamento del carico estenderei Dikstra non solo per calcolare il percorso ottimale, ma usare un qualche tipo di comportamento di riempimento per creare un insieme di possibili percorsi (ordinati per costo) per trovare alternative. Solo la conoscenza del problema specifico e della funzione di costo può rispondere se e come potrebbe funzionare.

Ottimizzazione delle colonie di formiche sembra invece molto più flessibile nell'adattarsi a un cambiamento funzione di costo, continuando l'iterazione dopo / mentre la funzione di costo cambia.

Efficienza

Questo dipende molto dal tuo dominio problematico. Se hai una buona euristica (consulta la sezione Complessità dell'articolo A * ) e raramente i costi cambiano, quindi il runtime polinomiale di A * potrebbe favorire re-calcoli ripetuti. L'ACO, d'altra parte, deve ripetere più volte prima di convergere su una soluzione approssimativa. Se i cambiamenti di costo si verificano molto frequentemente, continuare l'iterazione a un ritmo costante potrebbe essere più efficiente dell'aggiornamento della risoluzione A *, poiché le informazioni vengono conservate nello stato dell'algoritmo. ACO non promette la soluzione ottimale , tuttavia e probabilmente ha costi di avvio più elevati prima di convergere in un "buono" soluzione. Anche in questo caso dipende molto dal dominio specifico, dal grafico e dalla funzione di costo nonché dai requisiti di ottimalità.

Altri suggerimenti

Con A *, il costo del percorso non deve essere costante, quindi puoi iniziare con il seguente grafico:

A---1---B---1---C
|               |
\-------1-------/

dove vogliamo andare da A a C. Inizialmente, l'algoritmo di ricerca del percorso sceglierà il percorso A-C poiché A-B-C è 2 mentre A-C è 1. Possiamo aggiungere un termine aggiuntivo ai percorsi:

A---r---B---r---C
|               |
\-------r-------/

con

r(NM) = k(NM) + users(NM) / 10

dove

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

Man mano che gli utenti vengono aggiunti al sistema, la route AC diventerà più costosa della ABC con venti utenti (1 + 20/10) = 3, ABC è 2. Poiché gli utenti vengono rimossi dal sistema, la route AC diventerà di nuovo l'opzione migliore.

Il vero potere di A * è l'euristica che usi per calcolare il costo di ogni connessione.

L'algoritmo più comunemente usato per questo problema è A * (A Star) , che è una algoritmo di Dijkstra generalizzata con l'euristica aggiunta - lo scopo dell'euristica è di dirigere la ricerca verso l'obiettivo di ricerca in modo che le ricerche tipiche finiscano più velocemente.

Questo algoritmo ha molte varianti, versioni derivate e miglioramenti, la ricerca di Google o la pagina di Wikipedia dovrebbero essere un buon punto di partenza.

Sicuramente A *. Un * troverà il percorso migliore possibile o nessun percorso se non esiste alcun percorso. Per esempio. il percorso di questa barca è stato calcolato usando A *

_{(fonte: cokeandcode.com )}

Ecco una Demo Java interattiva con cui giocare. Si noti che questo algoritmo è rallentato dai sleep, quindi lo si vede funzionare. Senza questo rallentamento, troverebbe il percorso in meno di un secondo.

L'algoritmo è semplice ma potente. Ogni nodo ha 3 valori, g è il costo fino a questo nodo. h è il costo stimato da questo nodo al target e f è la somma di entrambi (è un'ipotesi per l'intero percorso). A * mantiene due elenchi, l'elenco Apri e l'elenco Chiuso. L'elenco Apri contiene tutti i nodi che non sono stati esplorati finora. L'elenco Chiuso elenca tutti i nodi che sono stati esplorati. Un nodo conta come esplorato se l'algoritmo ha già testato tutti i nodi collegati a questo nodo (connesso potrebbe significare solo in orizzontale e in verticale, ma anche in diagonale se sono consentiti spostamenti diagonali tra i nodi).

L'algoritmo potrebbe essere descritto come

Sia P il punto di partenza
Assegna i valori g, h e f a P
Aggiungi P alla lista aperta (a questo punto P è l'unico nodo in quella lista).
Sia B il nodo migliore dall'elenco Apri (migliore == valore f più basso)
- Se B è il nodo obiettivo - > esci, hai trovato il percorso
- Se l'elenco Apri è vuoto - > esci, non esiste alcun percorso
Sia C un nodo valido connesso a B
- Assegna g, h ef a C
- Controlla se C è nell'elenco aperto o chiuso
  - Se sì, controlla se il nuovo percorso è più efficiente (valore f inferiore)
    - In tal caso, aggiorna il percorso
  - Altrimenti aggiungi C all'elenco aperto
- Ripetere il passaggio 5 per tutti i nodi collegati a B
Aggiungi B all'elenco Chiuso (abbiamo esplorato tutti i vicini)
Ripeti dal passaggio 4.

Dai anche un'occhiata a Wikipedia per i dettagli di implementazione.

Ho sentito parlare di un'implementazione NN per gestire anche questo tipo di problema. Quindi se vuoi usare le NN alla fine troverai la tua strada ;-) ma devono essere inferiori rispetto a "algoritmi genetici".

Se il consumo computazionale / di tempo è un problema, suggerirei vivamente di utilizzare algoritmi genetici. Questo è esattamente il tipo di problemi a cui sono eccezionali.

I GA si basano su una funzione che descrive la tua soddisfazione per una determinata soluzione. È possibile modificare questa funzione in base alle proprie esigenze (ad es. È possibile includere non solo il costo del percorso ma qualsiasi fattore desiderato).

Un Dijkstra comune non sarebbe sufficiente?

http://improve.dk/generic-dijkstras-algorithm/

Algoritmo di Dijkstras, piccolo esempio per te

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow