Quali sono gli algoritmi k-best short-path che dovrei prendere in considerazione?

12

Sto risolvendo un problema di ottimizzazione della ricerca di grafici. Ho bisogno di trovare i k migliori percorsi aciclici più brevi attraverso un grafico ponderato diretto.

So che ci sono un certo numero di algoritmi k-best esatti e approssimativi, ma la maggior parte della ricerca recente sembra orientata verso grafici molto ampi e molto scarsamente connessi (ad es. routing e indicazioni stradali), e il mio grafico non è né .

Distinguere aspetti del mio problema:

  • Il grafico consiste di circa 160 vertici.

  • Il grafico è quasi completamente connesso (bidirezionalmente, quindi ~ 160 ^ 2 ~ = 25k bordi)

  • k sarà piuttosto piccolo (probabilmente meno di 10)

  • La lunghezza massima del percorso sarà probabilmente limitata e molto piccola (ad esempio 3-5 bordi)

  • Ho detto "aciclico" sopra, ma solo per ribadire: le soluzioni non devono includere i cicli. Questo non è un problema per il 1-best path più breve, ma diventa un problema per k-best - per esempio, considera un routing su strada - il 2o percorso più breve da A a B potrebbe essere lo stesso di 1-best, con un rapido giro per un isolato da qualche parte. Questo potrebbe essere matematicamente ottimale, ma non una soluzione molto utile. ; -)

  • Potremmo aver bisogno di ri-pesare i bordi al volo per ogni calcolo. Un costo limite consiste in una somma ponderata di diversi fattori e i requisiti finali (ogni volta che li otteniamo) possono consentire all'utente di specificare la propria priorità di tali fattori di ponderazione, modificando i pesi dei bordi. Questo è un grafico relativamente piccolo (dovremmo essere in grado di rappresentarlo in poche centinaia di KB), quindi è probabilmente ragionevole clonare il grafico in memoria, applicare la riponderazione e quindi eseguire la ricerca sul grafico clonato. Ma se c'è un metodo più efficace per eseguire la ricerca mentre si calcolano i pesi al volo, sono interessato.

Sto osservando gli algoritmi descritti in Santos (algoritmi con il percorso più breve K), Eppstein 1997 (Trovare i k percorsi più brevi) e altri. L'algoritmo di Yen è interessante, principalmente a causa dell'attuale implementazione . Non ho paura di leggere i documenti di ricerca, ma ho pensato che valesse la pena buttare fuori i dettagli del mio problema e chiedere indicazioni per risparmiare un po 'di tempo di lettura.

E se hai dei riferimenti alle implementazioni Java, ancora meglio.

    
posta AaronD 09.01.2013 - 15:39
fonte

2 risposte

1

Direi che questa domanda può essere facilmente cercata su Google ed è anche un duplicato:

Detto questo, ho già usato e implementato Eppstein e lo consiglio. L'ho trovato abbastanza elegante. Se ricordo bene, potrebbe anche essere ottimale, e il seguente documento lo spiega molto bene:

link

    
risposta data 09.01.2013 - 16:35
fonte
1

Per rispondere parzialmente alla mia stessa domanda:

Da quando ho postato questa domanda, ho scoperto che abbiamo bisogno di gestire i contorni negativi e positivi (la limitazione ai percorsi aciclici / semplici / senza anello significa che la migliore soluzione è definita, mentre senza quella limitazione il percorso più breve attraverso un grafico con cicli a costi negativi non definito).

L'algoritmo di Yen, e la maggior parte degli altri che ho esaminato, dipendono da una serie di 1-migliori ricerche; la maggior parte usa Dijkstra per quelle ricerche intermedie. Dijkstra non supporta i pesi negativi, ma possiamo sostituire Bellman-Ford al suo posto (almeno in Yen, presumibilmente anche in Lawler o Eppstein). Ho sviluppato una modifica di Bellman-Ford con una limitazione della lunghezza del percorso (nei bordi) e un controllo ciclico esplicito durante la ricerca (al posto del rilevamento del ciclo di post-ricerca standard). La complessità computazionale è peggiore, ma ancora trattabile per le mie esigenze. Modificherò questa risposta e collegherò a un rapporto tecnico se ottengo il permesso di pubblicarlo.

    
risposta data 15.03.2013 - 22:40
fonte

Leggi altre domande sui tag