Qual é a diferença entre as versões de pesquisa de gráfico e de pesquisa em árvore em relação às pesquisas DFS, A * em inteligência artificial ?

A julgar pelas respostas existentes, parece haver muita confusão sobre esse conceito.

O problema é sempre um gráfico

A distinção entre pesquisa em árvore e pesquisa em gráfico não está enraizada no fato de o gráfico do problema ser uma árvore ou um gráfico geral. Sempre presume-se que você está lidando com um gráfico geral. A distinção está no padrão de percurso usado para pesquisar o gráfico, que pode ser em forma de gráfico ou de árvore.

Se você estiver lidando com um problema em forma de árvore , ambas as variantes do algoritmo levam a resultados equivalentes. Portanto, você pode escolher a variante de pesquisa em árvore mais simples.

Diferença entre pesquisa em gráfico e árvore

Seu algoritmo de pesquisa de gráfico básico se parece com o seguinte. Com um nó inicial start, arestas direcionadas successorse uma goalespecificação usada na condição de loop. openmantém os nós na memória, que estão atualmente sob consideração, a lista aberta . Observe que o seguinte pseudocódigo não está correto em todos os aspectos (2).

Tree Search

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

Dependendo de como você implementa select from open, você obtém diferentes variantes de algoritmos de pesquisa, como pesquisa em profundidade (DFS) (escolha o elemento mais novo), pesquisa em amplitude (BFS) (escolha o elemento mais antigo) ou pesquisa de custo uniforme (escolha o elemento com o custo de caminho mais baixo ), a popular pesquisa A-star escolhendo o nó com o menor custo mais valor heurístico e assim por diante.

O algoritmo declarado acima é na verdade chamado de pesquisa em árvore . Ele visitará um estado do gráfico do problema subjacente várias vezes, se houver vários caminhos direcionados para o enraizamento no estado inicial. É até possível visitar um estado um número infinito de vezes se ele estiver em um loop direcionado. Mas cada visita corresponde a um nó diferente na árvore gerada por nosso algoritmo de pesquisa. Essa aparente ineficiência às vezes é desejada, conforme explicado posteriormente.

Pesquisa de gráfico

Como vimos, a pesquisa em árvore pode visitar um estado várias vezes. E, como tal, explorará a "subárvore" encontrada após esse estado várias vezes, o que pode ser caro. A pesquisa gráfica corrige isso mantendo o controle de todos os estados visitados em uma lista fechada . Se um sucessor recém-encontrado de nextjá for conhecido, ele não será inserido na lista aberta:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

Comparação

Percebemos que a pesquisa gráfica requer mais memória, pois mantém registro de todos os estados visitados. Isso pode ser compensado pela lista aberta menor, o que resulta em maior eficiência de pesquisa.

Soluções ótimas

Alguns métodos de implementação selectpodem garantir o retorno de soluções ótimas - ou seja, um caminho mais curto ou um caminho com custo mínimo (para gráficos com custos associados às arestas). Isso basicamente ocorre sempre que os nós são expandidos em ordem crescente de custo, ou quando o custo é uma constante positiva diferente de zero. Um algoritmo comum que implementa esse tipo de seleção é a pesquisa de custo uniforme ou, se os custos da etapa forem idênticos, BFS ou IDDFS . O IDDFS evita o consumo agressivo de memória do BFS e geralmente é recomendado para pesquisa desinformada (também conhecida como força bruta) quando o tamanho do passo é constante.

UMA*

Além disso, o (muito popular) algoritmo de pesquisa A * tree oferece uma solução ótima quando usado com uma heurística admissível . O algoritmo de busca do gráfico A * , entretanto, só dá essa garantia quando usado com uma heurística consistente (ou "monotônica") (uma condição mais forte do que a admissibilidade).

(2) Falhas do pseudo-código

Para simplificar, o código apresentado não:

• lidar com buscas com falha, ou seja, só funciona se uma solução puder ser encontrada

Uma árvore é um caso especial de gráfico; portanto, tudo o que funciona para gráficos gerais também funciona para árvores. Uma árvore é um gráfico onde existe precisamente um caminho entre cada par de nós. Isso implica que ele não contém nenhum ciclo, como afirma uma resposta anterior, mas um gráfico direcionado sem ciclos (um DAG, gráfico acíclico direcionado) não é necessariamente uma árvore.

No entanto, se você sabe que seu gráfico tem algumas restrições, por exemplo, que é uma árvore ou um DAG, geralmente você pode encontrar algum algoritmo de pesquisa mais eficiente do que um gráfico irrestrito. Por exemplo, provavelmente não faz muito sentido usar A *, ou sua contraparte não heurística "algoritmo de Dijkstra", em uma árvore (onde há apenas um caminho para escolher de qualquer maneira, que você pode encontrar por DFS ou BFS) ou em um DAG (onde um caminho ideal pode ser encontrado considerando vértices na ordem obtida por classificação topológica).

Quanto ao gráfico direcionado vs não direcionado, um gráfico não direcionado é um caso especial de um direcionado, a saber, o caso que segue a regra “se houver uma aresta (ligação, transição) de u para v, há também uma aresta de v para u .

Atualização : Observe que se o que interessa é o padrão de percurso da pesquisa, e não a estrutura do gráfico em si, essa não é a resposta. Veja, por exemplo, a resposta de @ziggystar.

A única diferença entre um gráfico e uma árvore é o ciclo . Um gráfico pode conter ciclos, uma árvore não. Portanto, quando você vai implementar um algoritmo de busca em uma árvore, não precisa considerar a existência de ciclos, mas ao trabalhar com um gráfico arbitrário, você precisa considerá-los. Se você não manipular os ciclos, o algoritmo pode eventualmente cair em um loop infinito ou em uma recursão infinita.

Outro ponto a se pensar são as propriedades direcionais do gráfico com o qual você está lidando. Na maioria dos casos, lidamos com árvores que representam relacionamentos pai-filho em cada borda. Um DAG (gráfico acíclico direcionado) também mostra características semelhantes. Mas os gráficos bidirecionais são diferentes. Cada aresta em um gráfico bidirecional representa dois vizinhos. Portanto, as abordagens algorítmicas devem diferir um pouco para esses dois tipos de gráficos.

GRÁFICO VS ÁRVORE

• Gráficos têm ciclos
• Árvores não têm ciclos "Por exemplo, imagine qualquer árvore em sua cabeça, ramos não têm conexões diretas com a raiz, mas ramos têm conexões com outros ramos, para cima"

Mas no caso de AI Graph-search vs Tree-search

A pesquisa de grafos tem uma boa propriedade que é sempre que o algoritmo explora um novo nó e o marca como visitado, "Independentemente do algoritmo usado", o algoritmo normalmente explora todos os outros nós que são acessíveis a partir do nó atual.

Por exemplo, considere o seguinte gráfico com 3 vértices AB e C, e considere o seguinte as arestas

AB, BC e CA, bem, há um ciclo de C para A,

E ao fazer DFS a partir de A, A irá gerar um novo estado B, B irá gerar um novo estado C, mas quando C for explorado o algoritmo tentará gerar um novo estado A mas A já foi visitado, portanto será ignorado. Legal!

Mas e as árvores? bem o algoritmo das árvores não marca o nó visitado como visitado, mas as árvores não têm ciclos, como ficaria em loops infinitos?

Considere esta Árvore com 3 vértices e considere as seguintes arestas

A - B - C enraizado em A, para baixo. E vamos supor que estamos usando o algoritmo DFS

A irá gerar um novo estado B, B irá gerar dois estados A e C, porque as Árvores não têm "Marcar um nó visitado se for explorado", portanto, talvez o algoritmo DFS explore A novamente, gerando um novo estado B, portanto estamos entrando em um loop infinito.

Mas você notou algo, estamos trabalhando em bordas não direcionadas, ou seja, há uma conexão entre AB e BA. claro que isso não é um ciclo, porque o ciclo implica que os vértices devem ser> = 3 e todos os vértices são distintos, exceto o primeiro e o último nós.

ST A-> B-> A-> B-> A não é um ciclo porque viola a propriedade de ciclagem> = 3. Mas de fato A-> B-> C-> A é um ciclo> = 3 nós distintos Verificado, o primeiro e o último nó são o mesmo verificado.

Considere novamente as arestas da árvore, A-> B-> C-> B-> A, claro que não é um ciclo, porque há dois Bs, o que significa que nem todos os nós são distintos.

Por último, você pode implementar um algoritmo de busca em árvore, para evitar explorar o mesmo nó duas vezes. Mas isso tem consequências.

Em palavras simples, a árvore não contém ciclos e onde o gráfico pode. Portanto, quando fazemos pesquisas, devemos evitar ciclos nos gráficos para não entrarmos em loops infinitos.

Outro aspecto é que a árvore normalmente terá algum tipo de classificação topológica ou uma propriedade como a árvore de pesquisa binária que torna a pesquisa tão rápida e fácil em comparação com os gráficos.