Encontrar o caminho mais curto em um gráfico que visitas certos nós

Question

I têm um gráfico não dirigida com cerca de 100 e cerca de 200 nodos bordas. Um nó é rotulado 'start', é 'final', e há cerca de uma dúzia rotulados 'mustpass'.

Eu preciso encontrar o caminho mais curto através deste gráfico que começa em 'start', termina no 'fim', e passa por todos os nós 'mustpass' (em qualquer ordem).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt é o gráfico em questão - que representa um labirinto de milho em Lancaster, PA)

Answer 1

Toda a gente comparar isso ao Caixeiro Viajante problema provavelmente não leu a pergunta cuidadosamente. Em TSP, o objetivo é encontrar o ciclo mais curto que as visitas todas os vértices (um ciclo hamiltoniano) - corresponde a ter todas nó rotulado 'mustpass'

No seu caso, dado que você tem apenas cerca de uma dúzia rotulados 'mustpass', e dado que 12! é bastante pequena (479001600), você pode simplesmente tentar todas as permutações de apenas o 'mustpass' nós, e olhar para o caminho mais curto de 'start' para 'final' que as visitas a 'mustpass' nós nessa ordem - ele vai simplesmente ser a concatenação dos caminhos mais curtos entre cada dois nós consecutivos na lista.

Em outras palavras, primeiro, encontrar a menor distância entre cada par de vértices (você pode usar o algoritmo de Dijkstra ou outros, mas com esses pequenos números (100 nós), mesmo o mais simples-a-código Floyd-Warshall algoritmo será executado no tempo). Então, uma vez que você tem isso em uma mesa, tente todas as permutações de seus nós 'mustpass', eo resto.

Algo parecido com isto:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(É claro que isso não é o código real, e se você quiser que o caminho real que você terá que manter o controle de quais permutação dá a distância mais curta, e também o que os todos os pares caminhos mais curtos são, mas você começa a idéia. )

Ele será executado em no máximo alguns segundos em qualquer idioma razoável :)
[Se você tem n nós e k 'mustpass' nós, o seu tempo de execução é O (n ³ ) para a parte Floyd-Warshall, e O (k! N) para a parte todas as permutações e 100 ^ 3 + (12!) (100) é praticamente amendoim menos que você tenha algumas restrições muito restritivas.]

Answer 2

Djikstra para encontrar os caminhos mais curtos entre todos os nós críticos (início, fim e deve-pass), então um percurso em profundidade deve dizer-lhe o caminho mais curto através da subgráfico resultante que toca todos os nós começar ... mustpasses ... end

Answer 3

Na verdade, o problema que você postou é semelhante ao caixeiro-viajante, mas acho mais perto de um problema pathfinding simples. Em vez de precisar visitar cada nó, você simplesmente precisa visitar um determinado conjunto de nós no menor tempo (distância) possível.

A razão para isso é que, ao contrário do problema do caixeiro viajante, um labirinto de milho não vai permitir que você viajar diretamente de qualquer ponto a qualquer outro ponto no mapa sem a necessidade de passar por outros nós para chegar lá.

Eu realmente recomendo A * pathfinding como uma técnica a considerar. Você configurar isso por decidir quais nós têm acesso a quais outros nós diretamente, e que o "custo" de cada hop de um nó particular é. Neste caso, parece que cada "salto" poderia ser de igual custo, uma vez que seus nós parecem relativamente espaçados. A * pode usar esta informação para encontrar o caminho de menor custo entre quaisquer dois pontos. Desde que você precisa para ir do ponto A ao ponto B e visita cerca de 12 inbetween, mesmo uma abordagem de força bruta usando pathfinding não faria mal em tudo.

Apenas uma alternativa a considerar. Ele faz olhar notavelmente como o problema caixeiro-viajante, e esses são bons papéis para ler sobre, mas olhar mais atento e você verá que suas coisas só complicar. ^ _ ^ Isso vindo da mente de um programador de jogos de vídeo que lidou com esses tipos de coisas antes.

Answer 4

Este é dois problemas ... Steven Lowe apontou isso, mas não deu o devido respeito à segunda metade do problema.

Você deve primeiro descobrir os caminhos mais curtos entre todos os seus nós críticos (início, fim, mustpass). Uma vez que estes caminhos são descobertos, é possível construir um gráfico simplificado, em que cada aresta no novo gráfico é um caminho de um nó para outro crítico no gráfico original. Há muitos algoritmos pathfinding que você pode usar para encontrar o caminho mais curto aqui.

Depois de ter este novo gráfico, porém, você tem exatamente o problema de vendedor de viagem (bem, quase ... Não há necessidade de retornar ao seu ponto de partida). Qualquer uma das mensagens relativas a este, mencionados acima, será aplicada.

Answer 5

Andrew Top tem a idéia certa:

1) Algoritmo de Djikstra 2) Alguns heurística TSP.

Eu recomendo a heurística de Lin-Kernighan: é um dos mais conhecidos para qualquer problema NP completo. A única outra coisa a lembrar é que depois que você expandiu o gráfico novamente após a etapa 2, você pode ter laços em seu caminho expandido, por isso você deve ir ao redor curto-circuito aqueles (olhar para o grau de vértices ao longo de seu caminho).

Estou realmente não sei como boa esta solução será em relação ao ideal. Há provavelmente alguns casos patológicos para fazer com curtos-circuitos. Afinal, este problema parece muito com Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree e você definitivamente não pode aproximar Steiner árvore por apenas contrair seu gráfico e funcionando Kruskal do por exemplo.

Answer 6

Esta é não um problema TSP e não NP-difícil, porque a pergunta original não exige que-pass obrigação nodos são visitados apenas uma vez. Isso faz com que a resposta muito, muito mais simples de força bruta apenas depois de compilar uma lista de caminhos mais curtos entre todos os nós passa-must via algoritmo de Dijkstra. Pode haver uma maneira melhor de ir, mas um simples seria a de simplesmente trabalhar um binário para trás das árvores. Imagine uma lista de nós [START, a, b, c, fim]. Somar as distâncias simples [iniciar-> a-> b-> c-> FIM] esta é a sua nova distância do alvo a bater. Agora tente [iniciar-> a-> c-> b-> final] e se isso é melhor conjunto que como o alvo (e lembre-se que ela veio de que o padrão de nós). para trás trabalho ao longo dos permutações:

• [iniciar-> a-> b-> c-> fim]
• [iniciar-> a-> c-> b-> end]
• [iniciar-> b-> a-> c-> fim]
• [iniciar-> b-> c-> a-> end]
• [iniciar-> c-> a-> b-> end]
• [iniciar-> c-> b-> a-> end]

Uma delas será mais curto.

(onde estão os nós 'visitado várias vezes, se existir? Eles estão apenas escondidos na etapa de inicialização do caminho mais curto. O caminho mais curto entre a e b podem conter c ou até o ponto final. Você não necessidade de cuidados)

Answer 7

Considerando a quantidade de nós e arestas é relativamente limitado, provavelmente você pode calcular todos os caminhos possíveis e tomar a um menor.

Geralmente este conhecido como o problema do caixeiro viajante, e tem um tempo de execução polinomial não-determinístico, não importa o que o algoritmo que você usar.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Answer 8

nós Que tal usar a força bruta na dúzia 'deve visitar'. Você pode cobrir todas as possíveis combinações de 12 nós com bastante facilidade, e isso deixa você com um circuito ideal que você pode seguir para cobri-los.

Agora o problema é simplificado para um de encontrar as melhores rotas a partir do nó de início ao circuito, que você siga ao redor até que você cobriu eles, e, em seguida, encontrar a rota de que até o fim.

caminho final é composta de:

Iniciar -> caminho para o circuito * -> circuito de nós deve visitar -> caminho para a final * -> end

Você encontra os caminhos que marcados com * como este

Faça um A * busca a partir do nó começo para cada ponto no circuito para cada um deles fazer um A * busca do próximo e anterior nó no circuito até o fim (porque você pode seguir a rodada de circuito em qualquer direção) O que você acabar com um monte de caminhos de pesquisa, e você pode escolher aquele com o menor custo.

Há muito espaço para a otimização de cache as buscas, mas eu acho que isso vai gerar boas soluções.

Não ir a qualquer lugar próximo à procura de uma solução ideal, porém, porque isso poderia envolver deixando circuito de visita do mosto dentro da pesquisa.

Answer 9

Uma coisa que não é mencionado em qualquer lugar, é se é ok para o mesmo vértice a ser visitado mais de uma vez no caminho. A maioria das respostas aqui assumir que é ok para visitar a mesma borda várias vezes, mas a minha opinião dada a questão (a caminho não deve visitar o mesmo vértice mais de uma vez!) É que é não ok para visitar o mesmo vértice duas vezes.

Assim, uma abordagem de força bruta ainda se aplica, mas você teria que remover vértices já utilizadas quando você tenta calcular cada subconjunto do caminho.