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.