Skip to content
Menu
CDhistory
CDhistory

N-Puzzle

Posted on Novembro 4, 2021 by admin

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
  • Estados iniciais e Goal
  • Search Algorithm
  • Função Heurística
  • Modo único passo ou Burst Mode
  • Representação do estado
  • Cores do Nó
  • Listas Abertas e Fechadas
  • Créditos

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:

Créditos

Deixe uma resposta Cancelar resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *

Artigos recentes

  • Acela está de volta: NYC ou Boston por $99
  • Entrada OMIM – # 608363 – CHROMOSOME 22q11.2 SÍNDROME DE DUPLICAÇÃO
  • Kate Albrecht’s Parents – Learn More About Her Father Chris Albrecht And Mother Annie Albrecht
  • Temple Fork Outfitters
  • Burr (romance)

Arquivo

  • Fevereiro 2022
  • Janeiro 2022
  • Dezembro 2021
  • Novembro 2021
  • Outubro 2021
  • Setembro 2021
  • Agosto 2021
  • Julho 2021
  • Junho 2021
  • Maio 2021
  • Abril 2021
  • DeutschDeutsch
  • NederlandsNederlands
  • SvenskaSvenska
  • DanskDansk
  • EspañolEspañol
  • FrançaisFrançais
  • PortuguêsPortuguês
  • ItalianoItaliano
  • RomânăRomână
  • PolskiPolski
  • ČeštinaČeština
  • MagyarMagyar
  • SuomiSuomi
  • 日本語日本語
©2022 CDhistory | Powered by WordPress & Superb Themes
Menu
CDhistory