Como uma Pesquisa de Largura Primeira funciona ao procurar o Caminho Mais Curto?

129

Eu fiz algumas pesquisas e parece que falta uma pequena parte desse algoritmo. Entendo como uma Pesquisa de Largura Primeiro funciona, mas não entendo exatamente como ela me levará a um caminho específico, em vez de apenas me dizer para onde cada nó individual pode ir. Acho que a maneira mais fácil de explicar minha confusão é fornecer um exemplo:

Por exemplo, digamos que eu tenha um gráfico como este:

insira a descrição da imagem aqui

E meu objetivo é ir de A a E (todas as arestas não têm peso).

Começo em A, porque essa é minha origem. Enfileiro em A, seguido de desenfileirar imediatamente A e explorá-lo. Isso produz B e D, porque A está conectado a B e D. Assim, enfileiramos B e D.

Retirar a fila de B e explorá-la, e descobrir que ela leva a A (já explorada) e C, então enfileirar C. Em seguida, desenfileirar D e descobrir que isso leva a E, meu objetivo. Em seguida, retiro a fila de C e acho que isso também leva a E, meu objetivo.

Sei logicamente que o caminho mais rápido é A-> D-> E, mas não tenho certeza de como exatamente a primeira pesquisa ajuda - como devo gravar caminhos de modo que, quando terminar, possa analisar os resultados e ver que o caminho mais curto é A-> D-> E?

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

Jake
fonte
2
"Além disso, observe que eu não estou usando uma árvore, portanto, não há nós" pais ", apenas filhos" - bem, obviamente, você precisará armazenar o pai em algum lugar. Para o DFS, você está fazendo isso indiretamente através da pilha de chamadas; para o BFS, é necessário fazê-lo explicitamente. Nada que você possa fazer sobre isso temo :)
Voo

Respostas:

85

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

Algoritmo de Dijkstra adapta o BFS para permitir encontrar os caminhos mais curtos de fonte única.

Para recuperar o caminho mais curto da origem para um nó, é necessário manter dois itens para cada nó no gráfico: a menor distância 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. No seu exemplo, você define a distância de A como zero e 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 da borda 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 estiver vazia, escolha um nó (no seu exemplo, é E) e retorne seus predecessores de volta à origem.

Se isso parecer um pouco confuso, a wikipedia possui uma boa seção de pseudocódigo sobre o tópico.

dasblinkenlight
fonte
Obrigado! Eu tinha lido sobre o pseudocódigo anteriormente, mas foi incapaz de compreendê-lo, a sua explicação tornou clique para mim
Jake
46
Gostaria de fazer a seguinte observação para as pessoas que olharem para esta postagem no futuro: Se as arestas não forem ponderadas, não será necessário armazenar a "menor distância atual" para cada nó. Tudo o que precisa ser armazenado é o pai de cada nó descoberto. Assim, enquanto você estiver examinando um nó e enfileirando todos os seus sucessores, simplesmente defina o pai desses nós como o nó que está examinando (isso será o dobro da marcação de "descoberto"). Se esse ponteiro pai for NUL / nil / None para qualquer nó, significa que ele ainda não foi descoberto pelo BFS ou é o próprio nó de origem / raiz.
Shashank
@ Shanks Se não mantivermos a distância, como saberíamos a distância mais curta, por favor, explique mais.
Gaurav Sehgal
12
@gauravsehgal Esse comentário é para gráficos com arestas não ponderadas. O BFS encontrará a menor distância simplesmente por causa de seu padrão de busca radial, que considera os nós na ordem da sua distância do ponto inicial.
precisa saber é o seguinte
13
Uma dica para os leitores do comentário de @ Shashank: não ponderados e uniformemente ponderados (por exemplo, todas as arestas têm peso = 5) são equivalentes.
TWIStErRob 30/11/2015
54

Como apontado acima, o BFS pode ser usado apenas 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 é iniciar a partir da fonte e realizar uma primeira pesquisa abrangente e parar quando encontrar o Nó de destino. A única coisa adicional que você precisa fazer é ter uma matriz anterior [n] que armazene o nó anterior para cada nó visitado. O anterior da origem pode ser nulo.

Para imprimir o caminho, faça um loop simples através da matriz [] anterior da origem 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 for mais complexo, contendo arestas e loops ponderados, precisamos de uma versão mais sofisticada do BFS, ou seja, o algoritmo de Dijkstra.

javaProgrammer
fonte
1
Dijkstra se nenhum pesos-ve outra ford uso carregador algo se pesos-ve
shaunak1111
O BFS trabalha para encontrar todos os caminhos mais curtos entre dois nós?
Maria Ines Parnisari
35
@javaProgrammer, não está certo. O BFS também pode ser usado para encontrar o caminho mais curto em um gráfico cíclico não ponderado. Se um gráfico não for ponderado, o BFS poderá ser aplicado ao SP, independentemente de haver loops.
Andrei Kaigorodov 21/01
3
To print the path, simple loop through the previous[] array from source till you reach destination.Mas anterior da fonte é nulo. Eu acho que o que você quis dizer é backtrace from destination using the previous array until you reach the source.
aandis
2
Por que você diz que o DFS funcionará sob condições semelhantes? Não é possível para o DFS seguir uma rota ingênua para obter os nós start-> end e, portanto, fornecer um caminho que não seja o mais curto?
James Wierzba
26

Do tutorial aqui

"Tem a propriedade extremamente útil de que, se todas as arestas de um gráfico não tiverem peso (ou o mesmo peso), a primeira vez que um nó for visitado é o caminho mais curto para o nó a partir do nó de origem"

acheron55
fonte
Isso é bom para o nó diretamente acessível (1-> 2) (2 é alcançado diretamente de 1). Para o nó não diretamente alcançável, há mais trabalho (1-> 2-> 3, 3 não é alcançado diretamente de 1). Obviamente, ainda é verdade considerando individualmente, ou seja, 1-> 2 e 2-> 3 individualmente são os caminhos mais curtos.
Manohar Reddy Poreddy
11

Eu perdi 3 dias
finalmente resolvi uma questão gráfica
usada para
encontrar a menor distância
usando o BFS

Deseja 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

Perdi três dias tentando todas as alternativas acima, verificando e revendo novamente e novamente acima,
elas não são o problema.
(Tente gastar tempo procurando outros problemas, se não encontrar nenhum problema acima de 5).


Mais explicações do comentário abaixo:

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

Suponha que acima é o seu gráfico
seja descendente.
Para A, os adjacentes são B e C.
Para B, os adjacentes são D e E.
Para C, os adjacentes são F e G

digamos, o nó inicial é A

  1. quando você alcança A, para, B e C, a menor distância entre B e C de A é 1

  2. quando você alcança D ou E, através de B, a distância mais curta de A e D é 2 (A-> B-> D)

da mesma forma, A-> E é 2 (A-> B-> E)

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

Portanto, agora, em vez de 1 distância entre nós, se for 6, basta multiplicar a resposta por 6
exemplo,
se a distância entre cada um for 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 seguir qualquer caminho
mas estamos calculando para todos os caminhos

se você tem que ir de A a Z, então nós viajamos todos os caminhos de A a um intermediário I, e uma vez que haverá muitos caminhos que descartar tudo, mas caminho mais curto até que eu, em seguida, continuar com o caminho mais curto à frente para o próximo nó J
novamente se existem vários caminhos de I a J, tomamos apenas o menor
exemplo,
suponha,
A -> eu temos a distância 5
(STEP) assuma, I -> J temos vários caminhos, das distâncias 7 e 8, já que 7 é o menor
tomamos A -> J como 5 (A-> eu menor) + 8 (menor agora) = 13,
então A-> J é agora 13
, repetimos agora acima (STEP) para J -> K e assim por diante, até chegarmos para Z

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


Manohar Reddy Poreddy
fonte
Você poderia, por favor, explicar como conseguiu encontrar o caminho mais curto com uma primeira pesquisa abrangente. Uma primeira pesquisa abrangente procura principalmente um nó; pode haver n caminhos para um nó de objetivo a partir do nó de origem e o bfs pode seguir qualquer caminho. Como você está determinando o melhor caminho?
underdog
i ter adicionado parte "mais explicação para resposta acima, deixe-me saber se isso satisfaz
Manohar Reddy Poreddy
1
Vejo que você está tentando executar um BFS no gráfico ponderado. Das distâncias 7 e 8, por que você escolheu 8? por que não 7? e se o nó 8 não tiver mais arestas para o destino? O fluxo terá que escolher 7 então.
underdog
boa pergunta, votada, sim, não estamos jogando fora, acompanhamos todos os nós adjacentes, até chegarmos ao destino. O BFS só funcionará quando houver apenas distâncias constantes, como todos os 7 ou 8. Dei um genérico com 7 e 8, que também é chamado de algoritmo de dijkstra.
Manohar Reddy Poreddy
desculpe, não sei o que você quer dizer, consulte en.wikipedia.org/wiki/Dijkstra's_algorithm
Manohar Reddy Poreddy
2

Com base na resposta acheron55 , 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 objetivo foi alcançado. Uma maneira simples de fazer isso é entrar no Queuecaminho inteiro usado para alcançar um nó, e não no próprio nó.
O benefício de fazer isso é que, quando o destino é atingido, a fila mantém o caminho usado para alcançá-lo.
Isso também é aplicável aos gráficos cíclicos, nos quais um nó pode ter mais de um pai.

c0der
fonte
0

Visitando este tópico após algum período de inatividade, mas como não vejo uma resposta completa, aqui estão meus dois centavos.

A busca pela largura da primeira sempre encontrará o caminho mais curto em um gráfico não ponderado. O gráfico pode ser cíclico ou acíclico.

Veja abaixo o pseudocódigo. Esse pseudocódigo pressupõe que você esteja usando uma fila para implementar o BFS. Ele também pressupõe que você pode marcar vértices como visitados e que cada vértice armazena um parâmetro de distância, que é inicializado para o infinito.

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
push the start vertex on the queue
while(queue is not empty)   
    dequeue one vertex (well call it x) off of the queue
    if the value of x is the value of the end vertex: 
        return the distance value of x
    otherwise, if x is not marked as visited:
        mark it as visited
        for all of the unmarked children of x:
            set their distance values to be the distance of x + 1
            enqueue them to the queue
if here: there is no path connecting the vertices

Observe que essa abordagem não funciona para gráficos ponderados - para isso, consulte o algoritmo de Dijkstra.

Matthew Russell
fonte
-6

A solução a seguir funciona para todos os casos de teste.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

   public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);

            int testCases = sc.nextInt();

            for (int i = 0; i < testCases; i++)
            {
                int totalNodes = sc.nextInt();
                int totalEdges = sc.nextInt();

                Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();

                for (int j = 0; j < totalEdges; j++)
                {
                    int src = sc.nextInt();
                    int dest = sc.nextInt();

                    if (adjacencyList.get(src) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(src);
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    }


                    if (adjacencyList.get(dest) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(dest);
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    }
                }

                int start = sc.nextInt();

                Queue<Integer> queue = new LinkedList<>();

                queue.add(start);

                int[] costs = new int[totalNodes + 1];

                Arrays.fill(costs, 0);

                costs[start] = 0;

                Map<String, Integer> visited = new HashMap<String, Integer>();

                while (!queue.isEmpty())
                {
                    int node = queue.remove();

                    if(visited.get(node +"") != null)
                    {
                        continue;
                    }

                    visited.put(node + "", 1);

                    int nodeCost = costs[node];

                    List<Integer> children = adjacencyList.get(node);

                    if (children != null)
                    {
                        for (Integer child : children)
                        {
                            int total = nodeCost + 6;
                            String key = child + "";

                            if (visited.get(key) == null)
                            {
                                queue.add(child);

                                if (costs[child] == 0)
                                {
                                    costs[child] = total;
                                } else if (costs[child] > total)
                                {
                                    costs[child] = total;
                                }
                            }
                        }
                    }
                }

                for (int k = 1; k <= totalNodes; k++)
                {
                    if (k == start)
                    {
                        continue;
                    }

                    System.out.print(costs[k] == 0 ? -1 : costs[k]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
}
user3819236
fonte
4
Voto por não responder à pergunta. Simplesmente colar um trecho de código não funcionará no SO.
Rishabh Agrahari