Esta aplicação web permite-lhe ver uma representação gráfica de uma gama de diferentes algoritmos de pesquisa gráfica, enquanto resolve a sua escolha de problemas de 8-puzzle.
Arrancar
No lado esquerdo desta aplicação, verá o Painel de Controlo. Usando o Painel de Controle, você pode configurar os seguintes aspectos da aplicação:
- Initial State and Goal State
- Which Search Algorithm to use
- Which Heuristic Function to use, if using an Informed Search Algorithm
- And whether to use single-step or burst mode
A cada uma destas opções será descrita em mais detalhes abaixo.
Estados iniciais e Goal
Para definir os estados Inicial ou Goal, você pode clicar no botão ‘Edit state’ ou na representação gráfica do estado.
Você deve ver um popup como o seguinte:
Para mudar um tile, basta clicar no tile que você gostaria de substituir, então digite o novo valor no seu teclado. Isto irá trocar o tile com aquele que anteriormente tinha esse valor.
Search Algorithm
N-Puzzle suporta cinco diferentes Algoritmos de Pesquisa baseados em gráficos. Os três primeiros são Algoritmos de Pesquisa Desinformados:
- Primeira pesquisa
- Primeira pesquisa de profundidade
- Profundamento iterativo de Pesquisa
Os outros dois são Algoritmos de Pesquisa Informados:
- A* Pesquisa
- Pesquisa Grisalha
Se você escolher um Algoritmo de Pesquisa Informada, então você também precisará selecionar uma Função Heurística.
Função Heurística
N-Puzzle suporta três diferentes Funções Heurísticas:
- Distância Euclideana
- Distância Manhattan (City-Block distance)
- Tiles Out-of-place
Modo único passo ou Burst Mode
N-Puzzle pode ser usado em dois modos. O modo padrão é o modo Single-Step, que lhe permite ‘rebobinar’ uma busca, um passo de cada vez. Isto é útil para entender melhor como funciona um Algoritmo de Busca.
O outro modo é o Modo Burst. Uma vez iniciado, o Modo Burst continua a executar uma pesquisa até que o estado de objectivo seja encontrado. Uma busca no modo de explosão pode ser pausada, mas não pode ser ‘rebobinada’.
A árvore de busca
Representação do estado
Enquanto uma busca estiver ativa, você será capaz de ver uma representação visual da árvore de busca. Cada nó nesta árvore de busca representa um arranjo de telhas (ou estado), e é desenhado como uma caixa que é dividida em 4 seções.
O diagrama seguinte mostra um nó retirado de uma busca Gananciosa:
A maior seção é o estado do enigma. Abaixo disso você verá duas seções menores.
Below the puzzle state são duas seções. A seção da esquerda é a profundidade do nó. A seção da direita é a pontuação heurística. A pontuação heurística só é usada com Algoritmos de Busca Informada, então se você estiver usando Breadth-first, Depth-first ou Iterative Deepening Search, a pontuação heurística será omitida.
A última seção registra a ordem em que os nós foram expandidos. Por exemplo, o nó raiz será sempre ‘#1’, e o próximo nó a ser expandido será marcado como ‘#2’.
Cores do Nó
Para ajudar a tornar a Árvore de Busca mais ‘legível’, a borda de cada nó é codificada por cores com base no seu estado atual.
O diagrama seguinte mostra o algoritmo A* (com a heurística de distância euclidiana) aplicado a um problema que pode ser resolvido em apenas dois movimentos:
As cores podem ser interpretadas da seguinte forma:
| Cor | Meaning |
|---|---|
| Azul | Se um nó estiver na Lista Aberta, então ele será realçado em azul. |
| Vermelho | Após cada iteração de um algoritmo de busca, o nó que será expandido em seguida será destacado em vermelho. Isto se aplica mesmo quando o nó objetivo for encontrado. |
| Cinza | Se um estado tiver sido explorado, ele será destacado em cinza. Por exemplo, no passo 2) do diagrama acima, o estado inicial foi colorido de cinza para indicar que ele foi explorado. No passo 3), um nó representando o estado inicial é redescoberto mas não será expandido uma vez que o estado inicial foi expandido através do nó raiz. |
| Verde | Após o estado de objetivo ter sido encontrado, ele será destacado em verde. |
| Ouro | Após ter sido encontrado um nó representando o estado de objetivo, quaisquer nós no caminho de volta ao nó raiz serão destacados em dourado. |
| Púrpura | Ao usar a Busca Iterativa de Aprofundamento, nós não explorados que excedam a profundidade máxima não serão adicionados à lista aberta. Estes nós serão coloridos em roxo. |
Listas Abertas e Fechadas
Aquando os algoritmos de busca estão sendo executados, duas listas são mantidas. A primeira é a Lista Aberta – esta é usada para manter registro de nós que foram descobertos, mas ainda não explorados.
A segunda é a Lista Fechada – esta é usada para manter registro de nós que foram explorados, ou nós que não serão explorados porque representam estados que já foram explorados através de outros nós.
Quando uma pesquisa está ativa, o número de nós nas Listas Aberta e Fechada será visível no canto superior esquerdo:
