Tutorial: Procuras Construtivas

Algoritmos Cegos › 📖 Leitura 👓 Procura Cega 👓 Algoritmos Aspirador › 💻 Parte 1 💻 Parte 2 Puzzle 8 › ✏️ Profundidade ✏️ Iterativa ✏️ Largura 💻 Testar Partição › ✏️ Profundidade ✏️ Largura 💻 Testar Damas › ✏️ Profundidade ✏️ Largura 💻 Testar Algoritmos Informados › 📖 Leitura 👓 Procura Informada Puzzle 8 › ✏️ Melhor Primeiro ✏️ A-star ✏️ BnB 💻 Testar

Execução de exemplo com base no problema do Puzzle 8. Pode acompanhar o teste executando as ações localmente.

No Visual Studio, selecione o projeto TProcuraConstrutiva, e execute. No Linux na pasta .../TProcura/Construtiva/Teste$ execute make seguido de ./bin/Release/TProcuraConstrutiva

Nota: ao executar no terminal, os parâmetros, indicadores e outros elementos, aparecem com realce de cor para facilitar a leitura.

Sumário

┌─ Teste TProcuraConstrutiva ──┐
│ 1 - Aspirador                │
│ 2 - Puzzle 8                 │
│ 3 - 8 Damas                  │
│ 4 - Partição                 │
└──────────────────────────────┘
Opção: 2

Puzzle 8 - movimentar uma das peças para o espaço vazio

Ação 1 - Ver instâncias

Vamos entrar no problema Puzzle 8, introduza: 2.

Puzzle 8
┌─ ⚙ Parâmetros ──────────────────────────────────────────────────────
│ P1(ALGORITMO): Largura Primeiro | P2(NIVEL_DEBUG): NADA | P3(SEMENTE): 1
│ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 0 | P6(VER_ACOES): 4 | P7(LIMITE): 0
│ P8(ESTADOS_REPETIDOS): ascendentes | P11(BARALHAR_SUCESSORES): 0
└──────────────────────────────────────────────────────────────────────
 │  3  1  2 
 │  4  7  5 
 │  6  8  . 
┌─ ☰ Menu ─────────┬────────────────┬─────────────────────┬──────────────┐
│ 1 📄   Instância  │ 2 🔍  Explorar │ 3 ⚙   Parâmetros    │ 4 ✔  Solução │
│ 5 ⚖   Indicadores │ 6 ►   Executar │ 7 🛠️  Configurações │ 8 🧪  Teste  │
└───────────────────┴────────────────┴─────────────────────┴──────────────┘
Opção:

Aparece uma instância do Puzzle 8. Poderiamos procurar resolver manualmente. No entanto esta instância está distante da solução, pelo que vamos ver outra instância. Introduza: 1;4.

Opção: 1
┌─ 📄 Instância ───────────────────────────────────────────────────────
│ ID atual: 40  Intervalo: [1–1000]  
│ Prefixo atual: 'instancia_' 
└──────────────────────────────────────────────────────────────────────
Novo ID (ENTER mantém) ou novo prefixo (texto): 4
Puzzle 8
...
 3  1  2 
 6  4  5 
 7  8  . 
...
Opção:

Estavamos na instância 40, e existem instâncias de 1 a 1000. Como as instâncias são construídas com base em movimentos aleatórios em quantidade igual ao ID da instância, ao escolher um ID de 4 garantimos que estamos a uma distância de 4 ou menos da solução.

Ação 2 - Resolver manualmente

Vamos então resolver a instância manualmente. Introduza: 2; dir dir baixo baixo; ENTER.

Opção: 2
═╤═ 💰 g:0 🎯 h:4 ⚖  1|2|3 ═══
 │  3  1  2 
 │  6  4  5 
 │  7  8  . 
 │ └─ ⚡  ──── baixo dir
🔍 Sucessor [1-2, ação(ões), exe]: dir dir baixo baixo
┌─ ✔  ────────────────
│ Executadas 4 ações. 
└─────────────────────
═╤═ 💰 g:0 ⚖  6|14|6 ═══
 │  .  1  2 
 │  3  4  5 
 │  6  7  8 
 │ └─ ⚡  ──── cima esq
🔍 Sucessor [1-2, ação(ões), exe]: ↵
Puzzle 8
...
 │  .  1  2 
 │  3  4  5 
 │  6  7  8 
...
Opção:

A instância está resolvida. Vamos agora ver o caminho gravado. Introduza 4.

Opção: 4
Parte 1, ações: dir dir baixo baixo
(3) 1  2 
(6) 4  5 
(7)(8) . 
Puzzle 8
...
 │  .  1  2 
 │  3  4  5 
 │  6  7  8 
...
Opção:

Vemos agora a solução num formato compacto. Num só tabuleiro, vemos as peças que mudam. Ou se se quiser, vemos o percurso do espaço. Existe uma só parte, com as ações que demos manualmente. Caso o caminho intersecte, existiriam mais partes.

Esta forma de ver soluções é específica do Puzzle 8 porque foi redefinido o método MostrarSolucao(). Assim temos uma forma compacta mais cómoda de ver soluções.

Ação 3 - Procura em Largura

Começamos pela procura em largura nesta instância, colocando debug a 4. Introduza: 1; 4; 3; 2; 4; ENTER; 6

Opção: 6
═╤═ ►  Execução iniciada ═══
 ├■═╤═ 💰 g:0  ═══ { }
 │  3  1  2 
 │  6  4  5 
 │  7  8  . 
 │ └─ ⚡  ──── baixo dir { 🔖 1 🔖 2 } 
 ├■═╤═ 🔖 1 💰 g:1 ⚖  1|2 ═══ { 🔖 2 } 
 │  3  1  2 
 │  6  4  . 
 │  7  8  5 
 │ └─ ⚡  ──── baixo dir { 🔖 3 🔖 4 } 
 ├■═╤═ 🔖 2 💰 g:1 ⚖  2|4 ═══ { 🔖 3 🔖 4 } 
 │  3  1  2 
 │  6  4  5 
 │  7  .  8 
 │ └─ ⚡  ──── baixo dir { 🔖 5 🔖 6 } 
 ├■═╤═ 🔖 3 💰 g:2 ⚖  3|6 ═══ { 🔖 4 🔖 5 🔖 6 } 
 │  3  1  . 
 │  6  4  2 
 │  7  8  5 
 │ └─ ⚡  ──── dir { 🔖 7 } 
 ├■═╤═ 🔖 4 💰 g:2 ⚖  4|7 ═══ { 🔖 5 🔖 6 🔖 7 } 
 │  3  1  2 
 │  6  .  4 
 │  7  8  5 
 │ └─ ⚡  ──── baixo cima dir { 🔖 8 🔖 9 🔖 10 } 
 ├■═╤═ 🔖 5 💰 g:2 ⚖  5|10 ═══ { 🔖 6 🔖 7 🔖 8 🔖 9 🔖 10 } 
 │  3  1  2 
 │  6  .  5 
 │  7  4  8 
 │ └─ ⚡  ──── baixo dir esq { 🔖 11 🔖 12 🔖 13 } 
 ├■═╤═ 🔖 6 💰 g:2 ⚖  6|13 ═══ { 🔖 7 🔖 8 🔖 9 🔖 10 🔖 11 🔖 12 🔖 13 } 
 │  3  1  2 
 │  6  4  5 
 │  .  7  8 
 │ └─ ⚡  ──── baixo { 🔖 14 } 
 ├■═╤═ 🔖 7 💰 g:3 ⚖  7|14 ═══ { 🔖 8 🔖 9 🔖 10 🔖 11 🔖 12 🔖 13 🔖 14 } 
 │  3  .  1 
 │  6  4  2 
 │  7  8  5 
 │ └─ ⚡  ──── cima dir { 🔖 15 🔖 16 } 
 ├■═╤═ 🔖 8 💰 g:3 ⚖  8|16 ═══ { 🔖 9 🔖 10 🔖 11 🔖 12 🔖 13 🔖 14 🔖 15 🔖 16 } 
 │  3  .  2 
 │  6  1  4 
 │  7  8  5 
 │ └─ ⚡  ──── dir esq { 🔖 17 🔖 18 } 
 ├■═╤═ 🔖 9 💰 g:3 ⚖  9|18 ═══ { 🔖 10 🔖 11 🔖 12 🔖 13 🔖 14 🔖 15 🔖 16 🔖 17 🔖 18 } 
 │  3  1  2 
 │  6  8  4 
 │  7  .  5 
 │ └─ ⚡  ──── dir esq { 🔖 19 🔖 20 } 
 ├■═╤═ 🔖 10 💰 g:3 ⚖  10|20 ═══ { 🔖 11 🔖 12 🔖 13 🔖 14 🔖 15 🔖 16 🔖 17 🔖 18 🔖 19 🔖 20 } 
 │  3  1  2 
 │  .  6  4 
 │  7  8  5 
 │ └─ ⚡  ──── baixo cima { 🔖 21 🔖 22 } 
 ├■═╤═ 🔖 11 💰 g:3 ⚖  11|22 ═══ { 🔖 12 🔖 13 🔖 14 … 🔖 20 🔖 21 🔖 22 } #11
 │  3  .  2 
 │  6  1  5 
 │  7  4  8 
 │ └─ ⚡  ──── dir esq { 🔖 23 🔖 24 } 
 ├■═╤═ 🔖 12 💰 g:3 ⚖  12|24 ═══ { 🔖 13 🔖 14 🔖 15 … 🔖 22 🔖 23 🔖 24 } #12
 │  3  1  2 
 │  .  6  5 
 │  7  4  8 
 │ └─ ⚡  ──── baixo cima { 🔖 25 🔖 26 } 
 ├■═╤═ 🔖 13 💰 g:3 ⚖  13|26 ═══ { 🔖 14 🔖 15 🔖 16 … 🔖 24 🔖 25 🔖 26 } #13
 │  3  1  2 
 │  6  5  . 
 │  7  4  8 
 │ └─ ⚡  ──── baixo cima { 🔖 27 🔖 28 } 
 ├■═╤═ 🔖 14 💰 g:3 ⚖  14|28 ═══ { 🔖 15 🔖 16 🔖 17 … 🔖 26 🔖 27 🔖 28 } #14
 │  3  1  2 
 │  .  4  5 
 │  6  7  8 
 │ └─ ⚡  ──── baixo esq { 🔖 29 🔖 30 } 
 │  🎯  Solução encontrada! 💰 g:4
 │  .  1  2 
 │  3  4  5 
 │  6  7  8 
 ├─ Parâmetros ─ P1=1 P2=4 P3=1 P4=10 P5=0 P6=4 P7=0 P8=2 P11=0
═╧═ 🏁  Execução terminada ⏱    ═══
Puzzle 8
┌─ ⚙ Parâmetros ──────────────────────────────────────────────────────
│ P1(ALGORITMO): Largura Primeiro | P2(NIVEL_DEBUG): COMPLETO | P3(SEMENTE): 1
│ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 0 | P6(VER_ACOES): 4 | P7(LIMITE): 0
│ P8(ESTADOS_REPETIDOS): ascendentes | P11(BARALHAR_SUCESSORES): 0
└──────────────────────────────────────────────────────────────────────
 .  1  2 
 3  4  5 
 6  7  8 
┌─ ⚖ Indicadores ─────────────────────────────────────────────────────
│ I1(IND_CUSTO): 4 | I2(Tempo(ms)): 0 | I3(Iterações): 0 | I4(IND_EXPANSOES): 15 | 
│ I5(IND_GERACOES): 30 | I6(IND_LOWER_BOUND): 0
└──────────────────────────────────────────────────────────────────────
...
Opção:

Foi encontrada uma solução de distância 4. Podemos ver a ordem das expansões, houve estados expandidos que em nada contribuiam para a solução, mas serviram para garantir que não havia outra solução mais curta.

Vemos a lista de estados gerados não expandidos, vai cada vez aumentando, e na geração 14 já tinha 14 elementos. A partir de 10 elementos, em vez de colocar todos os elementos da lista, colocamos apenas os primeiros e últimos, acompanhado com a quantidade de elementos.

Esta instância era fácil, mas e a instância inicial? Vamos ver, mas reduzindo o debug para 2, e a semente para 2. Introduza: 3; 2; 2; 3; 2; ENTER; 1; 40; 6.

Opção: 6
═╤═ ►  Execução iniciada ═══
 ├■═╤═ 💰 g:0  ═══ { }
 ├■═╤═ 🔖 1 💰 g:1 ⚖  1|4 ═══ { 🔖 2 🔖 3 🔖 4 } 
 ├■═╤═ 🔖 2 💰 g:1 ⚖  2|6 ═══ { 🔖 3 🔖 4 🔖 5 🔖 6 } 
 ├■═╤═ 🔖 3 💰 g:1 ⚖  3|8 ═══ { 🔖 4 🔖 5 🔖 6 🔖 7 🔖 8 } 
 ├■═╤═ 🔖 4 💰 g:1 ⚖  4|10 ═══ { 🔖 5 🔖 6 🔖 7 🔖 8 🔖 9 🔖 10 } 
 ├■═╤═ 🔖 5 💰 g:2 ⚖  5|12 ═══ { 🔖 6 🔖 7 🔖 8 🔖 9 🔖 10 🔖 11 🔖 12 } 
 ├■═╤═ 🔖 6 💰 g:2 ⚖  6|13 ═══ { 🔖 7 🔖 8 🔖 9 🔖 10 🔖 11 🔖 12 🔖 13 } 
 ├■═╤═ 🔖 7 💰 g:2 ⚖  7|14 ═══ { 🔖 8 🔖 9 🔖 10 🔖 11 🔖 12 🔖 13 🔖 14 } 
 ├■═╤═ 🔖 8 💰 g:2 ⚖  8|15 ═══ { 🔖 9 🔖 10 🔖 11 🔖 12 🔖 13 🔖 14 🔖 15 } 
 ├■═╤═ 🔖 9 💰 g:2 ⚖  9|16 ═══ { 🔖 10 🔖 11 🔖 12 🔖 13 🔖 14 🔖 15 🔖 16 } 
 ├■═╤═ 🔖 10 💰 g:2 ⚖  10|17 ═══ { 🔖 11 🔖 12 🔖 13 🔖 14 🔖 15 🔖 16 🔖 17 } 
 ├■═╤═ 🔖 11 💰 g:2 ⚖  11|18 ═══ { 🔖 12 🔖 13 🔖 14 🔖 15 🔖 16 🔖 17 🔖 18 } 
 ├■═╤═ 🔖 12 💰 g:2 ⚖  12|19 ═══ { 🔖 13 🔖 14 🔖 15 🔖 16 🔖 17 🔖 18 🔖 19 } 
 ├■═╤═ 🔖 13 💰 g:3 ⚖  13|20 ═══ { 🔖 14 🔖 15 🔖 16 🔖 17 🔖 18 🔖 19 🔖 20 } 
 ├■═╤═ 🔖 14 💰 g:3 ⚖  14|22 ═══ { 🔖 15 🔖 16 🔖 17 🔖 18 🔖 19 🔖 20 🔖 21 🔖 22 } 
 ├■═╤═ 🔖 15 💰 g:3 ⚖  15|24 ═══ { 🔖 16 🔖 17 🔖 18 🔖 19 🔖 20 🔖 21 🔖 22 🔖 23 🔖 24 } 
 ├■═╤═ 🔖 16 💰 g:3 ⚖  16|26 ═══ { 🔖 17 🔖 18 🔖 19 🔖 20 🔖 21 🔖 22 🔖 23 🔖 24 🔖 25 🔖 26 } 
 ├■═╤═ 🔖 17 💰 g:3 ⚖  17|28 ═══ { 🔖 18 🔖 19 🔖 20 … 🔖 26 🔖 27 🔖 28 } #11
...
 ├■═╤═ 🔖 1273 💰 g:11 ⚖  1273|2107 ═══ { 🔖 1274 🔖 1275 🔖 1276 … 🔖 2105 🔖 2106 🔖 2107 } #834
 ├■═╤═ 🔖 1274 💰 g:11 ⚖  1274|2109 ═══ { 🔖 1275 🔖 1276 🔖 1277 … 🔖 2107 🔖 2108 🔖 2109 } #835
 ├■═╤═ 🔖 1275 💰 g:11 ⚖  1275|2111 ═══ { 🔖 1276 🔖 1277 🔖 1278 … 🔖 2109 🔖 2110 🔖 2111 } #836
 ├■═╤═ 🔖 1276 💰 g:11 ⚖  1276|2113 ═══ { 🔖 1277 🔖 1278 🔖 1279 … 🔖 2111 🔖 2112 🔖 2113 } #837
 ├■═╤═ 🔖 1277 💰 g:11 ⚖  1277|2115 ═══ { 🔖 1278 🔖 1279 🔖 1280 … 🔖 2113 🔖 2114 🔖 2115 } #838
 ├■═╤═ 🔖 1278 💰 g:11 ⚖  1278|2117 ═══ { 🔖 1279 🔖 1280 🔖 1281 … 🔖 2115 🔖 2116 🔖 2117 } #839
 ├■═╤═ 🔖 1279 💰 g:11 ⚖  1279|2119 ═══ { 🔖 1280 🔖 1281 🔖 1282 … 🔖 2117 🔖 2118 🔖 2119 } #840
 ├■═╤═ 🔖 1280 💰 g:11 ⚖  1280|2121 ═══ { 🔖 1281 🔖 1282 🔖 1283 … 🔖 2119 🔖 2120 🔖 2121 } #841
 ├■═╤═ 🔖 1281 💰 g:11 ⚖  1281|2123 ═══ { 🔖 1282 🔖 1283 🔖 1284 … 🔖 2121 🔖 2122 🔖 2123 } #842
 ├■═╤═ 🔖 1282 💰 g:11 ⚖  1282|2125 ═══ { 🔖 1283 🔖 1284 🔖 1285 … 🔖 2123 🔖 2124 🔖 2125 } #843
 ├■═╤═ 🔖 1283 💰 g:11 ⚖  1283|2127 ═══ { 🔖 1284 🔖 1285 🔖 1286 … 🔖 2125 🔖 2126 🔖 2127 } #844
 ├■═╤═ 🔖 1284 💰 g:11 ⚖  1284|2129 ═══ { 🔖 1285 🔖 1286 🔖 1287 … 🔖 2127 🔖 2128 🔖 2129 } #845
 │  🎯  Solução encontrada! 💰 g:12
 │  .  1  2 
 │  3  4  5 
 │  6  7  8 
 ├─ Parâmetros ─ P1=1 P2=2 P3=2 P4=10 P5=0 P6=4 P7=0 P8=2 P11=0
═╧═ 🏁  Execução terminada ⏱   8ms  ═══
Puzzle 8
┌─ ⚙ Parâmetros ──────────────────────────────────────────────────────
│ P1(ALGORITMO): Largura Primeiro | P2(NIVEL_DEBUG): PASSOS | P3(SEMENTE): 2
│ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 0 | P6(VER_ACOES): 4 | P7(LIMITE): 0
│ P8(ESTADOS_REPETIDOS): ascendentes | P11(BARALHAR_SUCESSORES): 0
└──────────────────────────────────────────────────────────────────────
 .  1  2 
 3  4  5 
 6  7  8 
┌─ ⚖ Indicadores ─────────────────────────────────────────────────────
│ I1(IND_CUSTO): 12 | I2(Tempo(ms)): 8 | I3(Iterações): 0 | I4(IND_EXPANSOES): 1285 | 
│ I5(IND_GERACOES): 2131 | I6(IND_LOWER_BOUND): 0
└──────────────────────────────────────────────────────────────────────
,,,
Opção:

Foi encontrado um resultado com 12 movimentos, mas foram realizadas 1285 expansões, resultando em 2131 gerações. Notar que a lista de estados gerados não expandidos foi continuamente crescendo, e no momento em que foi encontrada a solução haviam 845 estados nesta lista.

Vamos confirmar a solução. Introduza 4.

Opção: 4
Parte 1, ações: baixo esq cima cima
 4 (7)(3)
 1  . (2)
 6  8 (5)
Parte 2, ações: dir baixo baixo dir
(4)(3) 2 
 1 (7) 5 
 6 (8) . 
Parte 3, ações: cima esq
 .  4  2 
(1)(3) 5 
 6  7  8 
Parte 4, ações: baixo dir
(1)(4) 2 
 3  .  5 
 6  7  8 
Puzzle 8
...
 .  1  2 
 3  4  5 
 6  7  8 
...
Opção:

Nesta instância foram precisas 4 partes para mostrar a solução com 12 ações.

Embora o estado inicial tenha sido obtido por 40 movimentos aleatórios desde o estado objetivo, alguns dos movimentos acabaram por se inverter resultando numa instância à distância 12 do objetivo.

Utilizamos P3(SEMENTE)=2, naturalmente que outra semente aleatória poderia gerar um puzzle de 0 a 40 movimentos da solução.

Ação 4 - Procura em Profundidade

Vamos ver a procura em profundidade na instância 40, que sabemos ter uma solução de 12. Vamos alterar o algoritmo, colocar a profundidade a 4, debug a completo e visualização de ações a 1, para ser ver todos os estados. Introduza: 1; 40; 3; 1; 3; 7; 4; 2; 4; 6; 1; ENTER; 6.

Opção: 6
═╤═ ►  Execução iniciada ═══
 ├■═╤═ 💰 g:0  ═══
 │  4  7  3 
 │  1  .  2 
 │  6  8  5 
 │  ├■═╤═ 🔖 1 💰 g:1 ⚖  1|4 ═══ ⚡ baixo
 │  │  4  .  3 
 │  │  1  7  2 
 │  │  6  8  5 
 │  │  ├■═╤═ 🔖 5 💰 g:2 ⚖  2|6 ═══ ⚡ dir
 │  │  │  .  4  3 
 │  │  │  1  7  2 
 │  │  │  6  8  5 
 │  │  │  └■═╤═ 🔖 7 💰 g:3 ⚖  3|7 ═══ ⚡ cima
 │  │  │     1  4  3 
 │  │  │     .  7  2 
 │  │  │     6  8  5 
 │  │  │    🍃 🪜 
 │  │  └■═╤═ 🔖 6 💰 g:2 ⚖  3|7 ═══ ⚡ esq
 │  │     4  3  . 
 │  │     1  7  2 
 │  │     6  8  5 
 │  │     └■═╤═ 🔖 8 💰 g:3 ⚖  4|8 ═══ ⚡ cima
 │  │        4  3  2 
 │  │        1  7  . 
 │  │        6  8  5 
 │  │       🍃 🪜 
 │  ├■═╤═ 🔖 2 💰 g:1 ⚖  4|8 ═══ ⚡ cima
 │  │  4  7  3 
 │  │  1  8  2 
 │  │  6  .  5 
 │  │  ├■═╤═ 🔖 9 💰 g:2 ⚖  5|10 ═══ ⚡ dir
 │  │  │  4  7  3 
 │  │  │  1  8  2 
 │  │  │  .  6  5 
 │  │  │  └■═╤═ 🔖 11 💰 g:3 ⚖  6|11 ═══ ⚡ baixo
 │  │  │     4  7  3 
 │  │  │     .  8  2 
 │  │  │     1  6  5 
 │  │  │    🍃 🪜 
 │  │  └■═╤═ 🔖 10 💰 g:2 ⚖  6|11 ═══ ⚡ esq
 │  │     4  7  3 
 │  │     1  8  2 
 │  │     6  5  . 
 │  │     └■═╤═ 🔖 12 💰 g:3 ⚖  7|12 ═══ ⚡ baixo
 │  │        4  7  3 
 │  │        1  8  . 
 │  │        6  5  2 
 │  │       🍃 🪜 
 │  ├■═╤═ 🔖 3 💰 g:1 ⚖  7|12 ═══ ⚡ dir
 │  │  4  7  3 
 │  │  .  1  2 
 │  │  6  8  5 
 │  │  ├■═╤═ 🔖 13 💰 g:2 ⚖  8|14 ═══ ⚡ baixo
 │  │  │  .  7  3 
 │  │  │  4  1  2 
 │  │  │  6  8  5 
 │  │  │  └■═╤═ 🔖 15 💰 g:3 ⚖  9|15 ═══ ⚡ esq
 │  │  │     7  .  3 
 │  │  │     4  1  2 
 │  │  │     6  8  5 
 │  │  │    🍃 🪜 
 │  │  └■═╤═ 🔖 14 💰 g:2 ⚖  9|15 ═══ ⚡ cima
 │  │     4  7  3 
 │  │     6  1  2 
 │  │     .  8  5 
 │  │     └■═╤═ 🔖 16 💰 g:3 ⚖  10|16 ═══ ⚡ esq
 │  │        4  7  3 
 │  │        6  1  2 
 │  │        8  .  5 
 │  │       🍃 🪜 
 │  └■═╤═ 🔖 4 💰 g:1 ⚖  10|16 ═══ ⚡ esq
 │     4  7  3 
 │     1  2  . 
 │     6  8  5 
 │     ├■═╤═ 🔖 17 💰 g:2 ⚖  11|18 ═══ ⚡ baixo
 │     │  4  7  . 
 │     │  1  2  3 
 │     │  6  8  5 
 │     │  └■═╤═ 🔖 19 💰 g:3 ⚖  12|19 ═══ ⚡ dir
 │     │     4  .  7 
 │     │     1  2  3 
 │     │     6  8  5 
 │     │    🍃 🪜 
 │     └■═╤═ 🔖 18 💰 g:2 ⚖  12|19 ═══ ⚡ cima
 │        4  7  3 
 │        1  2  5 
 │        6  8  . 
 │        └■═╤═ 🔖 20 💰 g:3 ⚖  13|20 ═══ ⚡ dir
 │           4  7  3 
 │           1  2  5 
 │           6  .  8 
 │          🍃 🪜 
 ├─ Parâmetros ─ P1=3 P2=4 P3=2 P4=10 P5=0 P6=1 P7=4 P8=2 P11=0
═╧═ 🏁  Execução terminada ⏱    ═══
Puzzle 8
┌─ ⚙ Parâmetros ──────────────────────────────────────────────────────
│ P1(ALGORITMO): Profundidade Primeiro | P2(NIVEL_DEBUG): COMPLETO | P3(SEMENTE): 2
│ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 0 | P6(VER_ACOES): 1 | P7(LIMITE): 4
│ P8(ESTADOS_REPETIDOS): ascendentes | P11(BARALHAR_SUCESSORES): 0
└──────────────────────────────────────────────────────────────────────
 4  7  3 
 1  .  2 
 6  8  5 
┌─ ⚖ Indicadores ─────────────────────────────────────────────────────
│ I1(IND_CUSTO): -1 | I2(Tempo(ms)): 0 | I3(Iterações): 0 | I4(IND_EXPANSOES): 13 | 
│ I5(IND_GERACOES): 20 | I6(IND_LOWER_BOUND): 0
└──────────────────────────────────────────────────────────────────────
...
Opção:

Foram vistos todos os estados, e não se encontrou uma solução. No entanto todos os nós folha foram cortados devido ao limite, motivo pelo qual têm o ícon da escada. Vamos agora colocar o limite a 0, de modo a executar a iterativa, e debug no nível 2. Introduza: 1; 40; 3; 7; 0; 2; 2; ENTER; 6.

Opção: 6
═╤═ ►  Execução iniciada ═══
 ├─────────── 🌳 🪜 1 ⏱  ──────────── 
 ├■═╤═ 💰 g:0  ═══ ─── 🍃 🪜 
 ├─────────── 🌳 🪜 2 ⏱  ──────────── 
 ├■═╤═ 💰 g:0  ═══
 │  ├■═╤═ 🔖 1 💰 g:1 ⚖  1|4 ═══ ⚡ baixo ─── 🍃 🪜 
 │  ├■═╤═ 🔖 2 💰 g:1 ⚖  1|4 ═══ ⚡ cima ─── 🍃 🪜 
 │  ├■═╤═ 🔖 3 💰 g:1 ⚖  1|4 ═══ ⚡ dir ─── 🍃 🪜 
 │  └■═╤═ 🔖 4 💰 g:1 ⚖  1|4 ═══ ⚡ esq ─── 🍃 🪜 
 ├─────────── 🌳 🪜 3 ⏱  ──────────── 
 ├■═╤═ 💰 g:0 ⚖  1|4 ═══
 │  ├■═╤═ 🔖 5 💰 g:1 ⚖  2|8 ═══ ⚡ baixo
 │  │  ├■═╤═ 🔖 9 💰 g:2 ⚖  3|10 ═══ ⚡ dir ─── 🍃 🪜 
 │  │  └■═╤═ 🔖 10 💰 g:2 ⚖  3|10 ═══ ⚡ esq ─── 🍃 🪜 
 │  ├■═╤═ 🔖 6 💰 g:1 ⚖  3|10 ═══ ⚡ cima
 │  │  ├■═╤═ 🔖 11 💰 g:2 ⚖  4|12 ═══ ⚡ dir ─── 🍃 🪜 
 │  │  └■═╤═ 🔖 12 💰 g:2 ⚖  4|12 ═══ ⚡ esq ─── 🍃 🪜 
 │  ├■═╤═ 🔖 7 💰 g:1 ⚖  4|12 ═══ ⚡ dir
 │  │  ├■═╤═ 🔖 13 💰 g:2 ⚖  5|14 ═══ ⚡ baixo ─── 🍃 🪜 
 │  │  └■═╤═ 🔖 14 💰 g:2 ⚖  5|14 ═══ ⚡ cima ─── 🍃 🪜 
 │  └■═╤═ 🔖 8 💰 g:1 ⚖  5|14 ═══ ⚡ esq
 │     ├■═╤═ 🔖 15 💰 g:2 ⚖  6|16 ═══ ⚡ baixo ─── 🍃 🪜 
 │     └■═╤═ 🔖 16 💰 g:2 ⚖  6|16 ═══ ⚡ cima ─── 🍃 🪜 
 ├─────────── 🌳 🪜 4 ⏱  ──────────── 
 ├■═╤═ 💰 g:0 ⚖  6|16 ═══
 │  ├■═╤═ 🔖 17 💰 g:1 ⚖  7|20 ═══ ⚡ baixo
 │  │  ├■═╤═ 🔖 21 💰 g:2 ⚖  8|22 ═══ ⚡ dir
 │  │  │  └■═╤═ 🔖 23 💰 g:3 ⚖  9|23 ═══ ⚡ cima ─── 🍃 🪜 
 │  │  └■═╤═ 🔖 22 💰 g:2 ⚖  9|23 ═══ ⚡ esq
 │  │     └■═╤═ 🔖 24 💰 g:3 ⚖  10|24 ═══ ⚡ cima ─── 🍃 🪜 
 │  ├■═╤═ 🔖 18 💰 g:1 ⚖  10|24 ═══ ⚡ cima
 │  │  ├■═╤═ 🔖 25 💰 g:2 ⚖  11|26 ═══ ⚡ dir
 │  │  │  └■═╤═ 🔖 27 💰 g:3 ⚖  12|27 ═══ ⚡ baixo ─── 🍃 🪜 
 │  │  └■═╤═ 🔖 26 💰 g:2 ⚖  12|27 ═══ ⚡ esq
 │  │     └■═╤═ 🔖 28 💰 g:3 ⚖  13|28 ═══ ⚡ baixo ─── 🍃 🪜 
 │  ├■═╤═ 🔖 19 💰 g:1 ⚖  13|28 ═══ ⚡ dir
 │  │  ├■═╤═ 🔖 29 💰 g:2 ⚖  14|30 ═══ ⚡ baixo
 │  │  │  └■═╤═ 🔖 31 💰 g:3 ⚖  15|31 ═══ ⚡ esq ─── 🍃 🪜 
 │  │  └■═╤═ 🔖 30 💰 g:2 ⚖  15|31 ═══ ⚡ cima
 │  │     └■═╤═ 🔖 32 💰 g:3 ⚖  16|32 ═══ ⚡ esq ─── 🍃 🪜 
 │  └■═╤═ 🔖 20 💰 g:1 ⚖  16|32 ═══ ⚡ esq
 │     ├■═╤═ 🔖 33 💰 g:2 ⚖  17|34 ═══ ⚡ baixo
 │     │  └■═╤═ 🔖 35 💰 g:3 ⚖  18|35 ═══ ⚡ dir ─── 🍃 🪜 
 │     └■═╤═ 🔖 34 💰 g:2 ⚖  18|35 ═══ ⚡ cima
 │        └■═╤═ 🔖 36 💰 g:3 ⚖  19|36 ═══ ⚡ dir ─── 🍃 🪜 
 ├─────────── 🌳 🪜 5 ⏱  ──────────── 
...
 ├─────────── 🌳 🪜 13 ⏱ 6ms  ──────────── 
 ├■═╤═ 💰 g:0 ⚖  2699|4628 ═══
 │  ├■═╤═ 🔖 4629 💰 g:1 ⚖  2700|4632 ═══ ⚡ baixo
 │  │  ├■═╤═ 🔖 4633 💰 g:2 ⚖  2701|4634 ═══ ⚡ dir
 │  │  │  └■═╤═ 🔖 4635 💰 g:3 ⚖  2702|4635 ═══ ⚡ cima
 │  │  │     ├■═╤═ 🔖 4636 💰 g:4 ⚖  2703|4637 ═══ ⚡ cima
 │  │  │     │  └■═╤═ 🔖 4638 💰 g:5 ⚖  2704|4638 ═══ ⚡ esq
 │  │  │     │     ├■═╤═ 🔖 4639 💰 g:6 ⚖  2705|4640 ═══ ⚡ baixo
 │  │  │     │     │  ├■═╤═ 🔖 4641 💰 g:7 ⚖  2706|4643 ═══ ⚡ baixo
 │  │  │     │     │  │  ├■═╤═ 🔖 4644 💰 g:8 ⚖  2707|4645 ═══ ⚡ dir
 │  │  │     │     │  │  │  └■═╤═ 🔖 4646 💰 g:9 ⚖  2708|4646 ═══ ⚡ cima
 │  │  │     │     │  │  │     ├■═╤═ 🔖 4647 💰 g:10 ⚖  2709|4648 ═══ ⚡ cima
 │  │  │     │     │  │  │     │  └■═╤═ 🔖 4649 💰 g:11 ⚖  2710|4649 ═══ ⚡ esq
 │  │  │     │     │  │  │     │     ├■═╤═ 🔖 4650 💰 g:12 ⚖  2711|4651 ═══ ⚡ baixo ─── 🍃 🪜 
 │  │  │     │     │  │  │     │     └■═╤═ 🔖 4651 💰 g:12 ⚖  2711|4651 ═══ ⚡ esq ─── 🍃 🪜 
 │  │  │     │     │  │  │     └■═╤═ 🔖 4648 💰 g:10 ⚖  2711|4651 ═══ ⚡ esq
 │  │  │     │     │  │  │        ├■═╤═ 🔖 4652 💰 g:11 ⚖  2712|4654 ═══ ⚡ baixo
 │  │  │     │     │  │  │        │  ├■═╤═ 🔖 4655 💰 g:12 ⚖  2713|4656 ═══ ⚡ dir ─── 🍃 🪜 
...
 │  │  │                          └■═╤═ 🔖 5056 💰 g:11 ⚖  2942|5060 ═══ ⚡ esq
 │  │  │                             ├■═╤═ 🔖 5061 💰 g:12 ⚖  2943|5062 ═══ ⚡ baixo ─── 🍃 🪜 
 │  │  │                             └■═╤═ 🔖 5062 💰 g:12 ⚖  2943|5062 ═══ ⚡ cima ─── 🍃 🪜 
 │  │  └■═╤═ 🔖 4634 💰 g:2 ⚖  2943|5062 ═══ ⚡ esq
 │  │     └■═╤═ 🔖 5063 💰 g:3 ⚖  2944|5063 ═══ ⚡ cima
 │  │        ├■═╤═ 🔖 5064 💰 g:4 ⚖  2945|5065 ═══ ⚡ cima
 │  │        │  └■═╤═ 🔖 5066 💰 g:5 ⚖  2946|5066 ═══ ⚡ dir
 │  │        │     ├■═╤═ 🔖 5067 💰 g:6 ⚖  2947|5068 ═══ ⚡ baixo
 │  │        │     │  ├■═╤═ 🔖 5069 💰 g:7 ⚖  2948|5071 ═══ ⚡ baixo
 │  │        │     │  │  ├■═╤═ 🔖 5072 💰 g:8 ⚖  2949|5073 ═══ ⚡ dir
 │  │        │     │  │  │  └■═╤═ 🔖 5074 💰 g:9 ⚖  2950|5074 ═══ ⚡ cima
 │  │        │     │  │  │     ├■═╤═ 🔖 5075 💰 g:10 ⚖  2951|5076 ═══ ⚡ cima
 │  │        │     │  │  │     │  └■═╤═ 🔖 5077 💰 g:11 ⚖  2952|5077 ═══ ⚡ esq
 │  │        │     │  │  │     │     ├■═╤═ 🔖 5078 💰 g:12 ⚖  2953|5079 ═══ ⚡ baixo ─── 🍃 🪜 
 │  │        │     │  │  │     │     └■═╤═ 🔖 5079 💰 g:12 ⚖  2953|5079 ═══ ⚡ esq ─── 🍃 🪜 
 │  │        │     │  │  │     └■═╤═ 🔖 5076 💰 g:10 ⚖  2953|5079 ═══ ⚡ esq
 │  │        │     │  │  │        ├■═╤═ 🔖 5080 💰 g:11 ⚖  2954|5082 ═══ ⚡ baixo
 │  │        │     │  │  │        │  ├■═╤═ 🔖 5083 💰 g:12 ⚖  2955|5084 ═══ ⚡ dir
 │  │        │     │  │  │        │  │  🎯  Solução encontrada! 💰 g:12
 │  │        │     │  │  │        │  │  .  1  2 
 │  │        │     │  │  │        │  │  3  4  5 
 │  │        │     │  │  │        │  │  6  7  8  ─── 🎯 12 → 📈  ───  { 🔖 5084 }  ───  { 🔖 5081 🔖 5082 }  ───  { 🔖 5073 }  ───  { 🔖 5070 🔖 5071 }  ───  { 🔖 5068 }  ───  { 🔖 5065 }  ───  { 🔖 4630 🔖 4631 🔖 4632 } 
 ├─ Parâmetros ─ P1=3 P2=2 P3=2 P4=10 P5=0 P6=1 P7=0 P8=2 P11=0
═╧═ 🏁  Execução terminada ⏱   7ms  ═══
Puzzle 8
┌─ ⚙ Parâmetros ──────────────────────────────────────────────────────
│ P1(ALGORITMO): Profundidade Primeiro | P2(NIVEL_DEBUG): PASSOS | P3(SEMENTE): 2
│ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 0 | P6(VER_ACOES): 1 | P7(LIMITE): 0
│ P8(ESTADOS_REPETIDOS): ascendentes | P11(BARALHAR_SUCESSORES): 0
└──────────────────────────────────────────────────────────────────────
 .  1  2 
 3  4  5 
 6  7  8 
┌─ ⚖ Indicadores ─────────────────────────────────────────────────────
│ I1(IND_CUSTO): 12 | I2(Tempo(ms)): 7 | I3(Iterações): 0 | I4(IND_EXPANSOES): 2955 | 
│ I5(IND_GERACOES): 5084 | I6(IND_LOWER_BOUND): 0
└──────────────────────────────────────────────────────────────────────
...
Opção:

A procura em profundidade iterativa encontrou também a solução ótima, com 12 movimentos, na 13ª iteração. Foram realizadas 2955 expansões e 5084 gerações, um valor superior à procura em largura.

Notar no entanto no parâmetro P8(ESTADOS_REPETIDOS): ascendentes. Significa que não foram gerados estados, que num dado ramo, já tinham ocorrido anteriormente. Esta é a opção por omissão para este problema, já que foi redefinido CPuzzle8::ResetParametros().

Vamos repetir esta execução, com debug no nível 1, e ignorando repetidos. Introduza: 1; 40; 3; 2; 1; 8; 1; ENTER; 6.

Opção: 6
═╤═ ►  Execução iniciada ═══#########...###########
 ├■ 🎯  Solução encontrada! 💰 g:12
 │  .  1  2 
 │  3  4  5 
 │  6  7  8 
 ├─ Parâmetros ─ P1=3 P2=1 P3=2 P4=10 P5=0 P6=1 P7=0 P8=1 P11=0
═╧═ 🏁  Execução terminada ⏱   83ms  ═══
Puzzle 8
┌─ ⚙ Parâmetros ──────────────────────────────────────────────────────
│ P1(ALGORITMO): Profundidade Primeiro | P2(NIVEL_DEBUG): ATIVIDADE | P3(SEMENTE): 2
│ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 0 | P6(VER_ACOES): 1 | P7(LIMITE): 0
│ P8(ESTADOS_REPETIDOS): ignorar | P11(BARALHAR_SUCESSORES): 0
└──────────────────────────────────────────────────────────────────────
 .  1  2 
 3  4  5 
 6  7  8 
┌─ ⚖ Indicadores ─────────────────────────────────────────────────────
│ I1(IND_CUSTO): 12 | I2(Tempo(ms)): 83 | I3(Iterações): 0 | I4(IND_EXPANSOES): 156105 | 
│ I5(IND_GERACOES): 440523 | I6(IND_LOWER_BOUND): 0
└──────────────────────────────────────────────────────────────────────
...
Opção:

Podemos ver que o número de expansões e gerações é consideravelmente superior. O tempo foi idêntico mesmo com mais gerações, mas isso deve-se ao nível de debug utilizado.

A verificação dos estados repetidos, é portanto um parâmetro bastante importante neste problema, em que o mesmo estado pode surgir várias vezes. Vamos então testar a eliminação de todos os estados repetidos gerados. Introduza: 1; 40; 3; 8; 3; ENTER; 6.

Opção: 6
═╤═ ►  Execução iniciada ═══####
 ├■ 🎯  Solução encontrada! 💰 g:12
 │  .  1  2 
 │  3  4  5 
 │  6  7  8 
 ├─ Parâmetros ─ P1=3 P2=1 P3=2 P4=10 P5=0 P6=1 P7=0 P8=3 P11=0
═╧═ 🏁  Execução terminada ⏱   22ms  ═══
Puzzle 8
┌─ ⚙ Parâmetros ──────────────────────────────────────────────────────
│ P1(ALGORITMO): Profundidade Primeiro | P2(NIVEL_DEBUG): ATIVIDADE | P3(SEMENTE): 2
│ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 0 | P6(VER_ACOES): 1 | P7(LIMITE): 0
│ P8(ESTADOS_REPETIDOS): gerados | P11(BARALHAR_SUCESSORES): 0
└──────────────────────────────────────────────────────────────────────
 .  1  2 
 3  4  5 
 6  7  8 
┌─ ⚖ Indicadores ─────────────────────────────────────────────────────
│ I1(IND_CUSTO): 12 | I2(Tempo(ms)): 22 | I3(Iterações): 0 | I4(IND_EXPANSOES): 2647 | 
│ I5(IND_GERACOES): 4400 | I6(IND_LOWER_BOUND): 0
└──────────────────────────────────────────────────────────────────────
...
Opção:

Podemos ver que o número de exapansões e gerações é ligeiramente inferior à configuração inicial, de remover repetidos ascendentes.

Pergunta: o que acontecia se executarmos a procura em profundidade ilimitada, ao deixar limite com -1, e sem verificar estados repetidos?

Resposta

A procura não retorna, crasha devido a entrar num ciclo infinito.

◀ Passo anterior Próximo passo ▶