Estou resolvendo um problema de otimização de pesquisa de gráficos. Preciso encontrar os k caminhos mais curtos acíclicos através de um gráfico ponderado direcionado.
Eu sei que existem vários algoritmos k-best exatos e aproximados, mas a maioria das pesquisas recentes parece estar orientada para gráficos muito grandes e muito pouco conectados (por exemplo, roteiros e direções), e meu gráfico não é.
Distinguindo aspectos do meu problema:
O gráfico consiste em aproximadamente 160 vértices.
O gráfico está quase totalmente conectado (bidirecionalmente, então ~ 160 ^ 2 ~ = 25k arestas)
k será bem pequeno (provavelmente menor que 10)
O comprimento máximo do caminho provavelmente também será limitado e muito pequeno (por exemplo, 3-5 arestas)
Eu disse 'acíclico' acima, mas apenas para reiterar - as soluções não devem incluir ciclos. Esse não é um problema para o melhor caminho mais curto, mas torna-se um problema para o k-best - por exemplo, considere um roteiro - o segundo caminho mais curto de A a B pode ser o mesmo que o 1, uma viagem rápida em torno de uma quadra em algum lugar. Isso pode ser matematicamente ideal, mas não é uma solução muito útil. ;-)
Talvez seja necessário ponderar novamente as arestas rapidamente para cada cálculo. Um custo de borda consiste em uma soma ponderada de vários fatores, e os requisitos finais (sempre que os obtemos) podem permitir que um usuário especifique sua própria priorização desses fatores de ponderação, alterando os pesos das bordas. Este é um gráfico relativamente pequeno (poderemos representá-lo em algumas centenas de KB); portanto, é provavelmente razoável clonar o gráfico na memória, aplicar a nova ponderação e executar a pesquisa no gráfico clonado. Mas se houver um método mais eficaz de realizar a pesquisa enquanto estiver computando pesos on-the-fly, estou interessado.
Estou olhando para os algoritmos descritos em Santos (algoritmos de caminho mais curto K), Eppstein 1997 (Finding the k Shortest Paths) e outros. O algoritmo de Yen é interessante, principalmente por causa da implementação Java existente . Não tenho medo de ler os trabalhos de pesquisa, mas achei que valia a pena jogar fora os detalhes do meu problema e pedir dicas para economizar tempo de leitura.
E se você tiver ponteiros para implementações Java, melhor ainda.
fonte
Respostas:
Para responder parcialmente a minha própria pergunta:
Desde que postei essa pergunta, descobri que precisamos lidar com pesos de borda negativos e positivos (a limitação aos caminhos acíclicos / simples / sem loop significa que a melhor solução é definida, enquanto sem essa limitação o caminho mais curto em um gráfico com valores negativos- ciclos de custo é indefinido).
O algoritmo de Yen, e a maioria dos outros que examinei, dependem de uma série de uma das melhores pesquisas; a maioria usa o Dijkstra para essas pesquisas intermediárias. Dijkstra não suporta pesos negativos, mas podemos substituir Bellman-Ford em seu lugar (pelo menos em ienes; presumivelmente em Lawler ou Eppstein também). Desenvolvi uma modificação do Bellman-Ford com uma limitação de comprimento do caminho (nas bordas) e verificação explícita do ciclo durante a pesquisa (no lugar da detecção padrão do ciclo pós-pesquisa). A complexidade computacional é pior, mas ainda é tratável para meus requisitos. Vou editar esta resposta e vincular a um relatório técnico se tiver permissão para publicá-lo.
fonte
Eu diria que esta pergunta pode ser facilmente pesquisada no Google e também é uma duplicata:
Dito isto, eu já usei e implementei o Eppstein e o recomendo. Eu achei bastante elegante. Se bem me lembro, pode ser ideal também, e o artigo a seguir explica muito bem:
http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf
fonte