Gráfico algoritmo de busca

Question

Eu estou procurando um algoritmo gráfico com algumas propriedades incomuns.

Cada aresta no grafo é uma "cópia" de borda ou "para baixo" de borda.

Um caminho válido pode ir de um número indefinido de "up"s seguido por um número indefinido de "para baixo"'s, ou vice-versa.No entanto, ele não pode mudar de direção mais de uma vez.

E. g., um caminho válido pode ser Um "até" B"," C "para baixo" E "para baixo" F um caminho inválido pode ser Um "até" B "para baixo" C "até" D

O que é um bom algoritmo para encontrar o menor caminho válido entre dois nós?Que tal encontrar todos de igual comprimento do caminho mais curto?

Answer 1

Supondo que você não tem qualquer heurística, uma variação de o algoritmo de dijkstra deve bastar-nos muito bem.Cada vez que você pensar em um novo borda, armazenar informações sobre seus "antepassados".Em seguida, verifique se o invariante (apenas uma mudança de direção), e recuar, se ela for violada.

Os antepassados aqui estão todas as arestas que foram percorridos para chegar ao nó atual, ao longo do caminho mais curto.Uma boa maneira de armazenar a informação do antepassado seria como um par de números.Se U e D é baixo, uma borda específica antepassados poderia ser UUUDDDD, o que seria o par 3, 4.Você não vai precisar de um terceiro número, devido invariável.

Desde que nós temos utilizado o algoritmo de dijkstra, a encontrar vários caminhos mais já é tomado cuidado de.

Answer 2

Talvez você pode transformar o seu gráfico em um normal dirigido gráfico e, em seguida, utilizar algoritmos.

Uma forma seria a de dividir o gráfico em dois gráficos, um com todas as bordas e, com todas as bordas para baixo e com dirigido arestas entre todos os nós em um gráfico e o nó correspondente no gráfico dois.

Primeiro resolver para iniciar no gráfico e terminando no gráfico dois e, em seguida, a outra maneira ao redor, em seguida, verifique a menor solução.

Answer 3

Pensar-se-ia o seu padrão de BFS deve funcionar aqui.Sempre que você adicionar um nó para abrir a lista, você pode envolvê-lo em uma estrutura que detém a direção que ele está usando (para cima ou para baixo) e um sinalizador booleano indicando se ele trocou de direções ainda.Estes podem ser usados para determinar quais arestas de saída do nó são válidas.

Para encontrar todos os caminhos mais de igual comprimento, incluem o número de arestas percorridas até agora em sua estrutura.Quando você encontrar o seu primeiro caminho mais curto, anote o comprimento do caminho e parar de adicionar nós ao abrir a lista.Continuar através de nós restantes na lista até que você tenha verificado que todos os caminhos de comprimento actual e, em seguida, parar.

Answer 4

Um* especialmente criado custo (G pontuação) e heurística (H pontuação) função pode lidar com isso.

O custo que você pode manter o controle do número de mudanças de direcção no caminho e adicione custo infinito na segunda alteração (ie.cortar a pesquisa para os ramos).

A heurística leva mais algum pensamento, especialmente quando você deseja manter a heurística admissível (nunca superestima distância mínima para a meta) e monotônica.(Única forma de garantir Um* encontrar uma solução ótima.)

Talvez haja mais informações sobre o domínio disponíveis para criar a heurística?(ie.coordenadas x,y dos nós no gráfico?)

É claro que, dependendo do tamanho do gráfico que você deseja resolver, você pode tentar primeiro o mais simples algoritmos como largura de pesquisa ou de Dijkstra o algoritmo de:basicamente, cada algoritmo de busca vai fazer, e para cada um, você vai precisar de uma função de custo (ou similar) de qualquer maneira.

Answer 5

Se você tem um padrão gráfico de função de busca, dizer Graph.shortest(from, to) em uma biblioteca, você pode fazer um loop e minimizar, em C#/pseudocódigo:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

Se você precisa se lembrar do caminho mínimo/caminhos e acontece que o padrão de função retorna os dados, você também pode pronunciar

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

onde myMin deve comparar dois [fst, nxt, C, AC, BD] tuplas e deixar o que tem a menor distância, ou ambos, e supondo que reduce é um smart função.

Este tem alguma sobrecarga de memória se nossos gráficos são grandes e não usa memória (o que é possível se eles são gerados dinamicamente), mas não realmente qualquer velocidade, sobrecarga, imho.