Trovare un euristico A * per un grafico diretto

Lascia che h(x) sia la tua euristica per il nodo x e h*(x) l'euristica perfetta (dove conosci la distanza ESATTA del tuo obiettivo da x ), se 0 < h(x) <= h*(x) per ogni nodo del grafico quindi l'euristica è ammissibile.

• Se h(x) = 0 non hai informazioni e A * degenera in Algoritmo di Dijkstra .
• Se h(x) = h*(x) conosci la risposta e quindi non c'è alcun problema da risolvere.
• Il più vicino h(x) è a h*(x) , il più breve A * impiegherà per trovare il percorso più breve.
• Se h(x) > h*(x) , la tua soluzione non è garantita come ottimale (cioè il percorso trovato potrebbe non essere il percorso di costo minore).

Alcune euristiche ben conosciute che soddisfano questi criteri sono Distanza euclidea e Distanza Manhattan .

Se h(x) <= d(x,y) + h(y) per ogni margine x, y del grafico, dove d(x,y) è la distanza effettiva tra i nodi, l'euristica è detta monotona (o coerente) e nessun nodo deve essere elaborato più di una volta .

Detto questo, qualsiasi euristica che non sopravvaluta la distanza andrà bene. Non importa se i tuoi nodi hanno pesi diversi, fa parte di d(x) (la distanza effettiva del tuo percorso percorso), non h(x) che è solo una stima approssimativa per favorire alcuni percorsi prima degli altri. Fintanto che h(x) (ricorda, è solo una stima) è < h*(x) otterrai il percorso ottimale.

In un caso normale, userei semplicemente lo stesso modo in cui ho ottenuto l'obiettivo di tornare indietro, ma dal momento che una delle strade avrebbe potuto essere a senso unico, potrebbe non essere possibile.

Non importa se hai strade a senso unico. Il tuo grafico può essere diretto e semplicemente non permetti al tuo algoritmo di generare quella rotta. Non è necessario tornare indietro durante l'esecuzione di A *, perché diventerebbe un percorso più lungo che se non avessi intrapreso quel percorso in primo luogo. Se vuoi tornare da GOAL a NODE è solo una nuova ricerca nel tuo spazio di ricerca, non un singolo problema.

Per quanto riguarda l'avviso di MSalters, non penso che tu possa ricavare un'euristica in un grafico con solo pesi. Hai bisogno di un problema che soddisfi alcuni criteri che offrono ulteriori informazioni da cui indovinare. Se hai solo pesi, non puoi farlo meglio di Dijkstra's perché ti mancano ulteriori informazioni. Dipende interamente dal dominio del problema, quindi non è possibile fornire una risposta ampia adatta a qualsiasi grafico.

L'euristica non deve essere perfetta. Mentre A * correva in un tempo ridicolmente breve se h(node) era uguale al percorso ottimale da quel nodo all'obiettivo, questo è ovviamente irrealistico. Tuttavia, per euristiche ragionevoli, devono essere solo la distanza minima possibile, ovvero non può esserci alcun percorso che raggiunga l'obiettivo da x di peso inferiore rispetto a h(x) , ma può sicuramente sarà più grande. Le euristiche comuni sono la distanza euclidea e la distanza di Manhattan. Nessuno di questi è perfetto, ma entrambi soddisfano i requisiti di A *.

Il caso delle strade a senso unico non cambia necessariamente l'euristica. Non dovresti semplicemente generare percorsi non validi nell'algoritmo A * stesso. Ad esempio, in termini di pseudocode di Wikipedia ,

neighbor_nodes(current)

dovrebbe generare solo nodi (giunzioni) che possono essere effettivamente raggiunti di un passo da current e non provare a percorrere una strada a senso unico nella direzione sbagliata.

La funzione euristica A *, tuttavia, dovrebbe essere sottostimare della distanza dall'obiettivo, e supponendo che le strade a senso unico possano essere attraversate in entrambe le direzioni ti darà esattamente questo.

(Potresti essere in grado di prendere in considerazione le strade a senso unico in un'euristica più intelligente, ma non hai bisogno di.)

Trovare il ciclo più lungo è un nuovo concetto di analisi del ciclo di feedback biochimico in biologia dei sistemi. Le reti biochimiche sono spesso rappresentate come grafici diretti in cui i vertici rappresentano composti chimici e i bordi rappresentano le reazioni chimiche tra i composti. Pertanto, un ciclo di retroazione biochimico più lungo può essere formulato come il ciclo più lungo in un grafico diretto. Poiché trovare il ciclo più lungo in un grafico diretto è NP-difficile, in questo documento abbiamo proposto un algoritmo euristico intelligente per trovare il ciclo più lungo in un grafico diretto. Abbiamo testato l'algoritmo su reti complesse generate casualmente e reti biochimiche reali estratte dal database KEGG. I risultati hanno mostrato che il nostro algoritmo è in grado di trovare oltre il 70% dei cicli più lunghi reali nelle 200 reti complesse generate casualmente e può anche trovare il ciclo di feedback nel percorso più lungo. Rispetto al tradizionale algoritmo di ricerca del percorso di ricerca, l'efficienza di ricerca dell'algoritmo proposto è stata migliorata notevolmente. Tra i feedback trovati dal database KEGG utilizzando l'algoritmo proposto, il feedback più lungo include 8 composti, 9 reazioni e 6 percorsi tra diversi moduli.

L'euristica si basa sul costo del volo diretto dell'uccello di raggiungere il tuo obiettivo con il minor peso possibile (e..g correre in una super autostrada senza limiti di velocità, se esistono nel tuo contesto).

Non ha molto a che fare con il tuo grafico a parte il peso minimo per unità di distanza che potrebbe contenere.