ti-enxame.com

Como funciona uma pesquisa de largura de canal ao procurar o caminho mais curto?

Fiz algumas pesquisas e pareço estar perdendo uma pequena parte desse algoritmo. Eu entendo como funciona uma pesquisa Breadth-First, mas não entendo exatamente como isso me levará a um caminho específico, em vez de apenas me dizer para onde cada nó individual pode ir. Eu acho que a maneira mais fácil de explicar minha confusão é fornecer um exemplo:

Então, por exemplo, digamos que eu tenha um gráfico como este:

enter image description here

E meu objetivo é ir de A para E (todas as arestas não são ponderadas).

Eu começo em A, porque essa é minha origem. Eu enfileirei A, seguido imediatamente dequeuinging e explorando isto. Isso produz B e D, porque A está conectado a B e D. Portanto, enfileirar B e D.

Desfaço B e explora-o, e descubro que isso leva a A (já explorado), e C, então eu coloco C. então desqualifico D e descubro que isso leva a E, meu objetivo. Eu então dequeue C e descubra que isso também leva a E, meu objetivo.

Eu sei logicamente que o caminho mais rápido é A-> D-> E, mas não tenho certeza de como exatamente a pesquisa inicial ajuda - como eu deveria estar gravando caminhos que, quando terminar, possa analisar os resultados e ver que o caminho mais curto é A-> D-> E?

Além disso, observe que não estou realmente usando uma árvore, portanto, não há nós "pai", apenas filhos.

108
Jake

Tecnicamente, a pesquisa de largura de banda (BFS) por si só não permite encontrar o caminho mais curto, simplesmente porque o BFS não está procurando um caminho mais curto: o BFS descreve uma estratégia para pesquisar um gráfico, mas não diz que você deve procurar alguma coisa em particular.

O algoritmo de Dijkstra adapta o BFS para permitir que você encontre caminhos mais curtos de fonte única.

Para recuperar o caminho mais curto da Origem para um nó, você precisa manter dois itens para cada nó no gráfico: sua distância mais curta atual e o nó anterior no caminho mais curto. Inicialmente, todas as distâncias são definidas como infinito e todos os predecessores são definidos como vazios. Em seu exemplo, você define a distância de A como zero e depois prossegue com o BFS. Em cada etapa, você verifica se pode melhorar a distância de um descendente, ou seja, a distância da Origem ao predecessor mais o comprimento do Edge que você está explorando é menor que a melhor distância atual para o nó em questão. Se você puder melhorar a distância, defina o novo caminho mais curto e lembre-se do predecessor pelo qual esse caminho foi adquirido. Quando a fila BFS está vazia, escolha um nó (no seu exemplo, é E) e atravesse seus predecessores de volta para a Origem. Isso lhe daria o caminho mais curto.

Se isso soa um pouco confuso, a wikipedia tem um Nice seção de pseudocódigo sobre o tópico.

68
dasblinkenlight

Como apontado acima, o BFS pode somente ser usado para encontrar o caminho mais curto em um gráfico se:

  1. Não há loops

  2. Todas as arestas têm o mesmo peso ou nenhum peso.

Para encontrar o caminho mais curto, tudo o que você precisa fazer é começar a partir da fonte e realizar uma pesquisa de amplitude primeiro e parar quando encontrar seu nó de destino. A única coisa adicional que você precisa fazer é ter uma matriz anterior [n] que irá armazenar o nó anterior para cada nó visitado. O anterior da fonte pode ser nulo.

Para imprimir o caminho, faça um loop simples através do array [] anterior da fonte até chegar ao destino e imprimir os nós. O DFS também pode ser usado para encontrar o caminho mais curto em um gráfico em condições semelhantes.

No entanto, se o gráfico é mais complexo, contendo bordas e loops ponderados, então precisamos de uma versão mais sofisticada do BFS, ou seja, o algoritmo de Dijkstra.

42
javaProgrammer

De tutorial aqui

"Ele tem a propriedade extremamente útil de que, se todas as arestas em um gráfico não forem ponderadas (ou o mesmo peso), a primeira vez que um nó for visitado será o caminho mais curto para esse nó a partir do nó de origem"

20
acheron55

Eu perdi 3 dias
finalmente resolveu uma questão gráfica
usado para
encontrando a menor distância
usando o BFS

Quer compartilhar a experiência.

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges

#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)

#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path

#3
It does not matter what queue you use
   deque/queue(c++) or
   your own queue implementation (in c language)
   A circular queue is unnecessary

#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.

#5
Wikipedia BFS will work, and is sufficient.
    https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

Eu perdi 3 dias tentando todas as alternativas acima, verificando e re-verificando novamente e novamente acima
eles não são o problema.
(Tente passar o tempo procurando por outros problemas, se você não encontrar nenhum problema acima com 5).


Mais explicação do comentário abaixo:

      A
     /  \
  B       C
 /\       /\
D  E     F  G

Suponha que acima é o seu gráfico
gráfico vai para baixo
Para A, os adjacentes são B & C
Para B, os adjacentes são D & E
Para C, os adjacentes são F & G

digamos, o nó inicial é A

  1. quando você alcança A, para, B e C a distância mais curta para B & C de A é 1

  2. quando você alcança D ou E, até B, a menor distância para A & D é 2 (A-> B-> D)

similarmente, A-> E é 2 (A-> B-> E)

também, A-> F & A-> G é 2

Então, agora, em vez de uma distância entre os nós, se for 6, basta multiplicar a resposta por 6
exemplo,
se a distância entre cada um é 1, então A-> E é 2 (A-> B-> E = 1 + 1)
se a distância entre cada um é 6, então A-> E é 12 (A-> B-> E = 6 + 6)

sim, o bfs pode pegar qualquer caminho
mas estamos calculando para todos os caminhos

se você tiver que ir de A a Z, então viajaremos todos os caminhos de A até um intermediário I, e como haverá muitos caminhos, descartamos todos os caminhos, exceto o mais curto, até que eu continue com o caminho mais curto até o próximo nó J
novamente, se houver vários caminhos de I a J, só tomamos o menor
exemplo,
assumir,
A -> Eu temos a distância 5
(STEP) presuma, eu -> J temos vários caminhos, das distâncias 7 e 8, desde que 7 é o mais curto
tomamos A -> J como 5 (A-> I mais curto) + 8 (menor agora) = 13
então A-> J é agora 13
repetimos agora acima (STEP) para J -> K e assim por diante, até chegarmos a Z

Leia esta parte, 2 ou 3 vezes, e desenhe no papel, você certamente vai conseguir o que eu estou dizendo, boa sorte


8
Manohar Reddy Poreddy

Com base em acheron55 resposta Eu postei uma possível implementação aqui .
Aqui está um breve verão:

Tudo o que você precisa fazer é acompanhar o caminho pelo qual o alvo foi atingido. Uma maneira simples de fazer isso é enviar para o Queue o caminho inteiro usado para alcançar um nó, em vez do próprio nó.
O benefício de fazer isso é que quando o alvo é alcançado, a fila mantém o caminho usado para alcançá-lo.
Isso também é aplicável a gráficos cíclicos, em que um nó pode ter mais de um pai.

1
c0der