Search Problems

Introduction

1. completeness: a estratégia irá encontrar uma solução sempre que ela existir;
2. optimality: a solução encontrada é a melhor dentre todas as possíveis;
3. space complexity: a memória necessária para encontrar a solução; e
4. time complexity: o tempo necessário para encontrar a solução.

Generic Search

$\text{algorithm search}(A, v)$
1.$\qquad m \leftarrow \text{memory}()$
2.$\qquad m\cdot\text{insert}(v)$
3.$\qquad \text{while not empty}(m) \text{ do}$
4.$\qquad|\qquad w \leftarrow m\cdot\text{remove}()$
5.$\qquad|\qquad \text{if not } (w\cdot\text{visited}) \text{ then}$
6.$\qquad|\qquad|\qquad w\cdot\text{visited} \leftarrow \text{true}$
7.$\qquad|\qquad|\qquad \text{for each } z \in A(w) \text{ do}$
8.$\qquad|\qquad|\qquad|\qquad m\cdot\text{insert}(z)$

Depth-first Search

O algoritmo de Busca em Profundidade (do inglês, Depth-First Search, ou DFS) é um algoritmo utilizado para percorrer ou buscar soluções em árvores ou grafos. Usa uma estratégia de memória do tipo pilha (FIFO).

Breadth-first Search

O algoritmo de Busca em Largura (do inglês, Breadth-First Search, ou BFS) é um algoritmo utilizado para percorrer ou buscar soluções em árvores ou grafos. Usa uma estratégia de memória do tipo fila (LIFO).

Exemplo

graph LR;
    a((A));
    b((B));
    c((C));
    d((D));
    a ---|w| b;
    a ---|x| c;
    b ---|y| d;
    c ---|z| d;

Loading

Trivial Graph Format (TGF)

1 A
2 B
3 C
4 D
#
1 2 w
1 3 x
2 4 y
3 4 z