Busca não informada e informada

Um problema de busca descreve as escolhas antes de um algoritmo começar a fazê-las. Sua formulação determina tanto o significado de uma solução quanto o número de possibilidades que o algoritmo deve considerar.

Defina o problema

Há seis componentes:

• Estados descrevem as situações possíveis.
• O estado inicial é onde a busca começa.
• Ações são as escolhas disponíveis em um estado.
• O modelo de transição, $\text{RESULT}(s,a)$, fornece o estado após a ação $a$.
• O teste de objetivo reconhece um estado aceitável.
• A função de custo da ação, $c(s,a,s^{\mathrm{\prime }})$, atribui um custo a cada passo.

Todos os custos de ação aqui são positivos. Uma solução para um problema de busca de caminhos é uma sequência de ações que leva a um objetivo. Some os custos de suas ações para obter seu custo do caminho. Uma solução ótima em custo minimiza essa soma. Apenas nomear o destino não informa a um agente como alcançá-lo.

Formule o quebra-cabeça de 8 peças

Um tabuleiro contém oito peças numeradas e um espaço vazio. Registre as nove posições como o estado. O estado inicial é a disposição fornecida; o objetivo é “1 2 3 / 4 5 6 / 7 8 vazio”. Uma ação move o espaço vazio para a esquerda, direita, cima ou baixo quando esse movimento permanece no tabuleiro. A transição troca o espaço vazio com a peça vizinha, e cada movimento custa 1. Um canto permite duas ações; o centro permite quatro.

Uma solução é uma sequência como “Esquerda, Cima, Direita”, se esses movimentos forem permitidos e alcançarem o objetivo. Como cada movimento tem o mesmo custo, minimizar o custo significa minimizar o número de movimentos.

Escolha o espaço de estados

Pense nos estados como vértices de um grafo direcionado e nas ações como arestas identificadas por custos. Uma estrada de mão dupla produz duas arestas direcionadas. Para a busca de rotas, um estado pode ser o local atual e o custo de um passo pode ser a distância da estrada em quilômetros.

A abstração deixa de fora detalhes irrelevantes. A música tocando em um carro não precisa fazer parte de um estado de rota. Uma solução abstrata ainda deve poder ser executada. Remover um detalhe que altera quais ações são permitidas mudaria o problema, não apenas simplificaria sua descrição.

A formulação pode economizar mais trabalho que uma fila mais rápida. Colocar oito rainhas em quaisquer casas vazias permite $64\times 63\times \cdots \times 57\approx \mathrm{1,8}\times {10}^{14}$ sequências ordenadas de posicionamento possíveis. Colocar cada próxima rainha na coluna vazia mais à esquerda, em uma casa não atacada, deixa 2.057 estados alcançáveis. Essas são construções diferentes da mesma condição de objetivo.

Gere possibilidades conforme necessário

O quebra-cabeça de 8 peças tem $9!\mathrm{/}2=181.440$ estados alcançáveis a partir de um início fixo. O quebra-cabeça de 15 peças tem $16!\mathrm{/}2\approx \mathrm{1,05}\times {10}^{13}$. Uma representação completa das 8 rainhas com uma rainha por coluna tem $8^8=\mathrm{16.777.216}$ estados.

Esses espaços geralmente são fornecidos implicitamente: a busca recebe um estado inicial e procedimentos para ações e transições. Ela gera a parte relevante durante a execução. Para um problema de caminho, mantenha a sequência de ações. Para um problema de otimização como o posicionamento de rainhas, a própria disposição final pode ser a resposta.

O espaço de estados descreve o que é possível. A árvore de busca registra os caminhos que o algoritmo tentou. Vários nós podem descrever o mesmo estado porque chegaram a ele por caminhos diferentes.

Armazene um caminho em um nó

Um nó armazena um estado, seu nó pai, a ação a partir desse pai e o custo do caminho $g(n)$. A profundidade também pode ser armazenada. A raiz não tem pai e tem custo do caminho 0. Expandir um nó aplica todas as ações permitidas a seu estado e gera seus filhos.

Em um mapa de mão dupla, os caminhos “S, A” e “S, B, C, A” terminam no mesmo estado, mas produzem nós diferentes. Mesmo um mapa finito pode gerar uma árvore de busca infinita: “S, A, S, A, …” continua produzindo caminhos cada vez mais longos.

A fronteira, também chamada de borda, contém nós gerados que aguardam expansão. O conjunto de estados alcançados registra os estados gerados e o melhor nó encontrado para cada um. Ele inclui estados que ainda estão na fronteira e estados já expandidos. Um conjunto fechado ou explorado geralmente se refere apenas aos estados expandidos.

Execute o procedimento geral de busca pela melhor escolha

1. Coloque a raiz na fronteira e na tabela de estados alcançados.
2. Se a fronteira estiver vazia, retorne falha.
3. Remova o nó com o menor valor de avaliação $f(n)$.
4. Se seu estado for um objetivo, retorne esse nó.
5. Expanda-o. Adicione cada novo estado; para um estado alcançado anteriormente, substitua seu nó armazenado apenas quando o novo caminho for mais barato.
6. Repita a partir do passo 2.

Um caminho mais barato até um estado já expandido pode exigir sua reabertura. Retornos de mesmo custo não trazem melhora. Com um heap, uma entrada antiga pode permanecer fisicamente presente; ela deve ser reconhecida como desatualizada e ignorada quando removida.

A regra da fronteira determina a estratégia. Uma fila FIFO seleciona nós de menor profundidade para a BFS. Uma pilha LIFO seleciona nós mais profundos para a DFS. Filas de prioridade ordenadas por $g$, $h$ e $g+h$ produzem as buscas de custo uniforme, gulosa pela melhor escolha e A*.

Acompanhe os nós do mapa rodoviário

Use estas estradas de mão dupla, com distâncias em quilômetros: S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 e D–G 2. Comece em S e busque G. Desfaça empates em ordem alfabética.

Expandir S gera A com custo 2, B com custo 3 e D com custo 9. Cada um tem S como pai. A fronteira contém A, B e D; a tabela de estados alcançados também contém S. Mais tarde, C pode ser alcançado por A com custo 6 ou por B com custo 4. São dois nós para um estado, e o mais barato deve representar C.

Para recuperar uma solução, siga os vínculos de pai do nó objetivo retornado para trás e inverta as ações. Atualizar o custo sem atualizar o pai deixaria um caminho que não corresponde ao custo informado.

Decida o que guardar

A busca em grafo guarda os estados alcançados para evitar trabalho repetido. A busca em árvore não tem uma tabela global de estados alcançados; ela pode apenas rejeitar ciclos no caminho atual. Ela economiza memória, mas pode gerar o mesmo estado por muitos caminhos.

O procedimento geral testa objetivos na remoção. A BFS pode testar na geração porque ela segue a ordem de profundidade. A busca baseada em custo deve esperar a remoção: o primeiro objetivo gerado pode ter um caminho mais caro que um objetivo encontrado depois.

Um algoritmo pode ser confiável e ainda assim ser caro demais para executar. Avalie suas garantias separadamente do uso de recursos e verifique se essas garantias correspondem ao problema que você realmente precisa resolver.

Faça quatro perguntas diferentes

Completude significa encontrar uma solução sempre que uma existe. Em um espaço alcançável finito, esgotar todas as possibilidades também pode comprovar a falha. Um espaço infinito sem solução pode ser explorado para sempre, mesmo por um algoritmo completo.

Otimalidade de custo significa retornar uma solução com o menor custo do caminho. Ela não diz nada sobre a velocidade de execução do algoritmo. Um método pode encontrar uma solução de forma confiável e ainda retornar uma rota cara.

Complexidade temporal conta os nós gerados ou expandidos. Indique qual contagem está sendo usada ao comparar medições. Complexidade espacial mede o número máximo de nós mantidos ao mesmo tempo, incluindo a fronteira e as informações de busca armazenadas.

Identifique os parâmetros

Para um espaço de busca implícito, use:

Para um grafo explícito já na memória, as contagens de vértices e arestas geralmente são mais úteis. Um limite de percurso em $\mathrm{\mid }V\mathrm{\mid }$ e $\mathrm{\mid }E\mathrm{\mid }$ responde a uma pergunta diferente de um limite para gerar uma árvore ainda não observada.

Veja por que a profundidade é cara

Uma árvore completa até a profundidade $d$ contém

nós para $b\mathrm{\ne }1$. Com fator de ramificação 10 e profundidade 5, são 111.111 nós, incluindo a raiz. Aumentar a profundidade em um acrescenta uma camada com dez vezes mais nós que a camada anterior.

A um milhão de nós por segundo e 1 quilobyte por nó, a escala muda rapidamente:

Essas são unidades decimais de armazenamento: 1 GB equivale a ${10}^9$ bytes. A memória pode inviabilizar uma busca muito antes de seu tempo de execução parecer excessivo.

Leia as garantias com suas condições

A BFS acaba alcançando toda profundidade finita quando a ramificação é finita. A DFS pode passar uma eternidade em um ramo infinito e nunca tentar um objetivo próximo. Essa diferença explica seus resultados de completude.

A BFS encontra um caminho com o menor número de ações. Se uma rota de dois passos custa 11 km e uma rota de três passos custa 9 km, a rota de menor profundidade não é ótima em custo. Custos de passo iguais fazem profundidade e custo concordarem; custos diferentes podem separá-los.

Um limite O grande de pior caso não prevê toda execução. Dois métodos com o mesmo limite podem diferir nas constantes, no tratamento de duplicatas e no número de ramos úteis. Uma heurística pode melhorar muito uma execução típica sem eliminar o pior caso exponencial.

A busca em largura explora em camadas. Sua próxima expansão é o nó de menor profundidade que ainda aguarda, então todo caminho de uma ação é considerado antes que qualquer caminho de duas ações seja expandido.

Mantenha a ordem da fila

A fronteira funciona por primeiro a entrar, primeiro a sair: remova da frente e acrescente os filhos ao fim. Registre os estados quando forem gerados. Se o estado de um filho já tiver sido alcançado, ignore-o; caso contrário, dois pais diferentes poderiam colocar o mesmo estado na fila.

Teste o estado inicial antes de iniciar a busca. Para os nós posteriores, a BFS pode usar um teste de objetivo na geração. O primeiro objetivo gerado tem profundidade mínima porque o algoritmo gera filhos camada por camada. A ordem dentro de uma camada pode escolher entre soluções de mesma profundidade, mas não pode fazer uma solução mais profunda aparecer primeiro.

Acompanhe a execução no mapa de exemplo

As estradas de mão dupla são S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 e D–G 2 km. Comece em S, busque G e gere vizinhos em ordem alfabética. Na tabela, o próximo nó a remover está à esquerda.

Quando B é expandido, C e D já foram alcançados. Eles não mudam para novas posições na fila. Quando D gera G, sua cadeia de pais é G–D–S. Inverta-a para recuperar S–D–G, com duas estradas e distância total $9+2=11$ km.

C já foi gerado, mas ainda não foi expandido. Sua rota até G teria três estradas. A BFS pode parar sem explorá-lo porque três estradas não podem melhorar o número de ações de uma solução com duas estradas.

Saiba o que o resultado minimiza

A BFS é completa para ramificação finita, mesmo se o espaço for infinito: cada camada finita é processada antes da próxima. Ela é ótima em custo quando todas as ações custam o mesmo. Em um quebra-cabeça deslizante com custo 1 por movimento, uma solução de menor profundidade também é uma solução de menor custo.

Nesse mapa rodoviário, S–B–C–G custa $3+1+5=9$ km. A BFS retorna a rota de 11 km porque a distância não é sua regra de ordenação. “Caminho mais curto”, portanto, precisa de uma unidade: menor número de estradas e menor número de quilômetros são objetivos diferentes.

Considere a memória

Com o teste de objetivo na geração, a BFS usa tempo e espaço $O(b^d)$. Ela pode gerar quase todos os nós até a profundidade do objetivo e manter a fronteira e as informações de estados alcançados. Se os objetivos forem testados apenas na remoção, expandir outros nós na profundidade $d$ pode gerar a profundidade $d+1$, produzindo o limite usual $O(b^{d+1})$ para essa versão.

Com fator de ramificação 10 e 1 quilobyte por nó, armazenar uma árvore até a profundidade 10 leva cerca de 11 TB. A BFS é útil para problemas de pouca profundidade e custos iguais quando há memória suficiente, como caminhos de rede com o menor número de saltos ou quebra-cabeças com o menor número de movimentos. Uma fila FIFO não usa os custos numéricos das arestas, mesmo quando eles estão escritos no grafo.

A busca de custo uniforme ordena caminhos pelo custo já pago. Ela pode deixar de lado um destino próximo, mas caro, enquanto investiga rotas mais longas compostas de passos baratos.

Remova o caminho mais barato

Defina $f(n)=g(n)$ e use uma fila de prioridade. Quando uma expansão encontrar um caminho mais barato até um estado alcançado, atualize tanto seu custo quanto seu pai. Um caminho de mesmo custo não melhora o registro. A UCS é a forma de busca do algoritmo de Dijkstra, que para quando remove um objetivo.

O teste de objetivo na remoção da fronteira é essencial. Gerar um objetivo prova que uma rota existe. Remover esse objetivo como o nó mais barato da fronteira prova que nenhuma rota inacabada mais barata pode superá-lo, considerando custos de ação positivos.

Acompanhe a execução no mapa de exemplo

Use as estradas de mão dupla S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 e D–G 2 km. Desfaça empates de custo em ordem alfabética. As entradas da fronteira abaixo mostram o estado e o custo do caminho.

A substituição de C é decisiva: $3+1=4$ é melhor que $2+4=6$. O pai de G é C, o pai de C é B e o pai de B é S. A rota retornada S–B–C–G custa 9 km. D é removido antes de G apenas porque a regra de desempate é alfabética.

Se uma estrada direta S–G de 12 km fosse acrescentada, S geraria um objetivo imediatamente. Um teste na geração retornaria 12 km antes de descobrir a rota de 9 km. A fila de prioridade não pode proteger a otimalidade se a regra de parada a contornar.

Explique a garantia

Com ramificação finita e todo custo de ação de pelo menos algum $ϵ>0$, apenas um número finito de passos de caminho pode caber abaixo de qualquer limite de custo fixo. A UCS, portanto, acaba removendo um objetivo sempre que um existe. Custos positivos garantem que estender um caminho não possa torná-lo mais barato, o que fundamenta a demonstração de otimalidade.

Custos zero exigem cuidado. A busca em árvore pode continuar percorrendo um ciclo de custo zero. A busca em grafo rejeita retornos de mesmo custo ao mesmo estado, mas uma cadeia infinita de estados distintos com custo acumulado limitado ainda pode atrasar um objetivo para sempre. Custos de passo negativos invalidam o argumento usual de otimalidade da UCS.

Entenda o custo

O limite padrão de pior caso para tempo e espaço é $O(b^{1+\lfloor C^{\ast }\mathrm{/}ϵ\rfloor })$. Nesse mapa, $C^{\ast }=9$ e $ϵ=1$, resultando em $O(b^{10})$. Esse é um limite pouco restritivo, não o número real de nós expandidos no mapa de seis estados.

Muitos caminhos baratos sem saída podem obrigar a UCS a realizar trabalho considerável antes de executar uma ação útil e cara. Quando todos os custos de passo são iguais, seu teste de objetivo na remoção fornece o conhecido limite $O(b^{d+1})$. A* com $h=0$ faz exatamente as mesmas comparações de prioridade que a UCS.

A busca em profundidade segue um ramo antes de tentar suas alternativas. Essa escolha pode reduzir muito o uso de memória, mas permite que um ramo desfavorável atrase todas as outras possibilidades.

Siga um ramo profundo

A DFS usa uma pilha em que o último a entrar é o primeiro a sair. Em uma versão de busca em árvore, rejeite estados que já estejam no caminho atual para evitar ciclos imediatos. Armazene o caminho atual e os irmãos não expandidos ao longo dele. Para tentar sucessores em ordem alfabética com uma pilha, empilhe-os em ordem alfabética inversa.

No mapa de mão dupla S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 e D–G 2 km, comece em S e busque G. Tentar vizinhos em ordem alfabética e testar objetivos na remoção produz S, A, C, B, D, G. Em C, B é o primeiro vizinho que ainda não está no caminho. A rota retornada S–A–C–B–D–G custa $2+4+1+6+2=15$ km.

A DFS não é ótima em custo. Ela é completa em um espaço finito com verificação de ciclos no caminho, mas pode seguir um ramo infinito para sempre. Seu tempo de pior caso é $O(b^m)$, e os caminhos e irmãos armazenados precisam de espaço $O(bm)$. O retrocesso que gera um filho por vez reduz o armazenamento para $O(m)$. Com ramificação 10 e profundidade máxima 12, o armazenamento de caminho e irmãos é de cerca de 120 nós, contra aproximadamente um trilhão para a BFS até a profundidade 12. Uma tabela global de estados alcançados usaria memória adicional.

Limite a profundidade

A busca em profundidade limitada para de expandir na profundidade $\mathrm{\ell }$. Um objetivo nessa profundidade ainda pode ser reconhecido. Ela distingue três resultados:

• Uma solução foi encontrada.
• Corte: o limite de profundidade impediu uma busca completa.
• Falha: as possibilidades relevantes foram esgotadas sem objetivo ou corte.

Um corte não prova que não existe solução. Se o objetivo de menor profundidade estiver na profundidade 7, um limite de 5 não poderá alcançá-lo. Tempo e espaço de pior caso são $O(b^{\mathrm{\ell }})$ e $O(b\mathrm{\ell })$.

Aumente o limite gradualmente

A busca com aprofundamento iterativo, ou IDS, executa buscas em profundidade limitada com limites 0, 1, 2 e assim por diante. Ela encontra uma solução de menor profundidade sem armazenar uma fronteira de busca em largura. Com ramificação finita, é completa; com custos de ação iguais, é ótima em custo. O tempo é $O(b^d)$ e o espaço é $O(bd)$.

A maioria dos nós de uma árvore larga está na última camada, então repetir as camadas superiores costuma ser pouco custoso. Para $b=10$ e $d=5$, conte os nós gerados abaixo da raiz:

A BFS gera 111.110 desses nós até a profundidade 5. A IDS gera cerca de 11% mais nós, mantendo apenas o armazenamento da busca em profundidade. As visitas repetidas à raiz são excluídas dessas duas contagens específicas.

Para fatores de ramificação maiores que 1, o trabalho adicional em uma árvore larga se aproxima do fator $b\mathrm{/}(b-1)$. Essa vantagem é menor em uma cadeia estreita, na qual os prefixos repetidos predominam. A IDS é uma escolha não informada útil quando a profundidade da solução é desconhecida e uma fronteira completa não cabe na memória. Em espaços com muitas rotas até o mesmo estado, a ausência de um conjunto global de estados alcançados pode causar uma regeneração considerável.

Uma estratégia útil corresponde ao resultado desejado e aos recursos disponíveis. A busca não informada usa a definição do problema sem uma estimativa da distância restante. Ainda assim, ela pode ser sistemática e cuidadosamente ordenada.

Compare nas mesmas condições

Suponha ramificação finita e as condições de custo positivo para a UCS. A linha da BFS usa o teste de objetivo na geração; a linha da DFS usa verificação de ciclos no caminho e não usa uma tabela global de estados alcançados.

A BFS e a IDS também minimizam o custo quando ele é uma função não decrescente apenas da profundidade. A palavra “apenas” importa: todos os caminhos de uma dada profundidade devem ter o mesmo custo para satisfazer essa condição mais ampla. Arestas positivas, por si só, não tornam a BFS ótima em custo.

Busque a partir das duas extremidades

A busca bidirecional avança a partir do início e retrocede a partir do objetivo. Se as buscas se encontrarem perto do meio, cada uma alcançará aproximadamente a profundidade $d\mathrm{/}2$. O trabalho será então aproximadamente $2b^{d\mathrm{/}2}$ em vez de $b^d$. Com fator de ramificação 10 e profundidade da solução 6, a comparação das camadas mais profundas é de cerca de 2.000 nós contra 1.000.000.

Ela precisa de um estado objetivo explícito e de uma forma de gerar predecessores. Estradas reversíveis de mão dupla facilitam a expansão para trás. Uma propriedade de objetivo como “todas as rainhas estão seguras” pode descrever estados objetivo demais para fornecer um ponto de partida inverso conveniente.

Com buscas em largura ou baseadas em custo, regras adequadas de encontro e término podem preservar a completude e a otimalidade. Em um mapa com pesos, pare apenas quando nenhuma conexão mais barata ainda for possível. A primeira sobreposição entre as duas buscas não precisa ser a conexão mais barata.

Escolha conforme o problema

Para o menor número de movimentos em um pequeno quebra-cabeça deslizante, custos de movimento iguais tornam a BFS adequada se houver bastante memória. Para percorrer a menor distância com estradas de comprimentos diferentes e sem heurística, escolha a UCS. Para um quebra-cabeça enorme de custo igual e profundidade da solução desconhecida, a IDS evita uma fronteira enorme. Em um espaço finito com muitos objetivos profundos, no qual qualquer solução é aceitável, a DFS pode ser prática. Um início e um objetivo conhecidos, com ações reversíveis, tornam a busca bidirecional uma opção a considerar.

O uso de memória deve incluir o que a versão escolhida armazena. A DFS com uma tabela global de estados alcançados deixa de ter o mesmo perfil de armazenamento da DFS em árvore. Uma execução da BFS com teste de objetivo na remoção não deve ser comparada a um limite de complexidade com teste na geração como se as versões fossem idênticas.

Mesmo a melhor escolha não informada pode enfrentar crescimento exponencial. Quando há conhecimento útil do domínio, uma heurística pode reduzir a exploração irrelevante. Quando apenas a configuração final importa, a busca local pode evitar manter uma árvore de busca.

Uma heurística atribui a um estado uma estimativa do menor custo restante até um objetivo. Escreva-a como $h(n)$ para o estado no nó $n$. Ela depende do estado, não do caminho usado para alcançá-lo, e é zero em um objetivo.

Estime o que falta

A distância em linha reta estima a distância restante por estrada. Em uma grade com movimentos unitários horizontais e verticais, a distância de Manhattan soma as diferenças entre as coordenadas:

Da célula (1,1) a (4,5), isso fornece $3+4=7$ movimentos. A distância em linha reta entre as mesmas coordenadas é $\sqrt{3^2+4^2}=5$. As estimativas respondem a perguntas diferentes sobre movimentos em problemas relaxados. Uma heurística deve usar as mesmas unidades do custo que estima; quilômetros não estimam diretamente o tempo de viagem sem um modelo de conversão adequado.

A busca informada usa uma estimativa para orientar a expansão. A estimativa não precisa dizer ao algoritmo qual ação executar. Ela avalia os estados produzidos pelas ações permitidas, e a regra da fronteira decide qual caminho pendente investigar em seguida.

Siga a menor estimativa

A busca gulosa pela melhor escolha define $f(n)=h(n)$. Sua fila de prioridade remove o estado que parece mais próximo do objetivo, ignorando o custo já pago.

Use as estradas de mão dupla S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 e D–G 2 km. As estimativas heurísticas até G são S 8, A 7, B 5, C 4, D 2 e G 0 km.

1. Expanda S. A fronteira tem A com estimativa 7, B com 5 e D com 2.
2. Remova D porque 2 é o menor valor. Expandir D gera G com estimativa 0. O custo do caminho até G é $9+2=11$ km.
3. Remova G e retorne S–D–G.

Apenas S e D foram expandidos. A rota S–B–C–G de 9 km estava disponível, mas a estimativa 5 de B parecia pior que a estimativa 2 de D. A busca gulosa nunca incluiu em sua comparação os 9 km já percorridos para alcançar D.

Separe orientação de garantias

Mesmo uma heurística que nunca superestima não torna a busca gulosa ótima em custo. As estimativas do exemplo são admissíveis, mas a rota retornada é cara demais. A busca gulosa usa apenas a estimativa restante, então pode pagar demais antes de alcançar um estado promissor.

A busca em grafo é completa em um espaço de estados finito quando trata duplicatas adequadamente. A busca gulosa em árvore pode entrar em ciclos em estados repetidos que parecem promissores, e um espaço infinito pode continuar oferecendo estimativas baixas e enganosas. Tempo e espaço de pior caso são $O(b^m)$, embora uma estimativa útil possa tornar curta uma execução real.

Um lugar pode estar próximo de um destino em linha reta, mas exigir um longo desvio em torno de um rio. Valores heurísticos pequenos não garantem boas rotas totais. Calcular a heurística também leva tempo: reduzir expansões só ajuda se a avaliação dessas estimativas não consumir a economia obtida.

A* avalia toda a jornada proposta: o custo já pago mais uma estimativa do que resta. Sua prioridade é

Use uma fila de prioridade, substitua caminhos mais caros e teste um objetivo quando ele for removido. Em um objetivo, $h=0$, então sua prioridade é o custo real de seu caminho.

Acompanhe a regra de custo mais estimativa

As estradas de mão dupla são S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 e D–G 2 km. As estimativas heurísticas até G são S 8, A 7, B 5, C 4, D 2 e G 0. Desfaça empates em ordem alfabética.

A é removido antes de G por causa da regra de desempate. A* expande quatro nós que não são objetivos e nunca expande D. A UCS no mesmo mapa também expande D. Definir todas as estimativas heurísticas como zero eliminaria essa orientação e reproduziria a UCS.

Explique por que uma estimativa otimista funciona

Uma heurística admissível nunca excede o custo restante real $h^{\ast }(n)$. Para A* com reabertura, a admissibilidade garante otimalidade de custo; A* em árvore tem a mesma garantia sob as condições de busca com custos positivos.

Suponha que um objetivo pior de custo $C>C^{\ast }$ estivesse prestes a ser removido. Algum nó em um caminho ótimo ainda deve estar pendente. Para seu prefixo no caminho ótimo,

A fila deve escolher esse nó antes do objetivo pior. Isso contradiz o ponto de parada proposto. A reabertura importa porque um prefixo mais barato descoberto depois deve poder continuar por um estado já expandido.

Uma heurística consistente faz $f$ ser não decrescente ao longo dos caminhos. Ela garante que a primeira expansão de um estado use um caminho de menor custo até ele. A* pode então fechar permanentemente os estados expandidos. Apenas com admissibilidade, um conjunto permanentemente fechado pode descartar uma melhora essencial.

Entenda a poda e seus limites

Com consistência, A* expande todo nó relevante cujo $f<C^{\ast }$, pode expandir nós empatados em $C^{\ast }$ e não expande nenhum acima desse valor antes de retornar. A prioridade 11 de D excede o custo da solução 9, então ele permanece sem expansão. Na classe de algoritmos que constroem caminhos para frente e usam as mesmas informações heurísticas, A* é otimamente eficiente, exceto em empates. Essa é uma comparação das expansões necessárias, não uma afirmação de que seu código sempre é executado mais rápido.

A superestimativa pode invalidar o argumento. Altere a estimativa de B para 9, embora seu custo restante real seja 6. B agora tem prioridade 12. A*, seguindo S, A, C e D, retorna S–A–C–G com custo 11 enquanto B ainda espera.

A* ainda tem um pior caso exponencial e armazena informações de busca geradas.

Quando a fronteira deixa de caber na memória ou uma resposta demora demais, escolha qual recurso ou garantia negociar. Variantes voltadas à velocidade mudam prioridades ou descartam candidatos. Variantes voltadas à memória geram novamente caminhos que não puderam manter.

Dê mais peso à estimativa

O A ponderado* usa $f=g+Wh$ com $W>1$. Ele geralmente favorece mais o progresso em direção a um objetivo. Com uma heurística admissível e as atualizações do melhor caminho e reaberturas do procedimento geral, o custo retornado é no máximo $W{C}^{\ast }$. Esse limite permite uma solução pior, mas não exige que ela seja pior.

No mapa rodoviário de referência, use as estimativas S 8, A 7, B 5, C 4, D 2 e G 0, e peso 2. A partir de S, as prioridades são B 13, D 13 e A 16. O desempate alfabético seleciona B. Seu filho C tem $4+2(4)=12$; C então gera G com prioridade 9. A rota de custo 9 é retornada após três expansões de nós que não são objetivos. A garantia permite até 18 km, embora essa execução encontre a solução ótima.

Na mesma fórmula, peso 0 produz UCS e peso 1 produz A*. À medida que o peso cresce, a estimativa domina cada vez mais as comparações, aproximando-se do comportamento guloso.

A busca em feixe mantém apenas os $k$ melhores nós pendentes e descarta os demais. A fronteira mantida é limitada, mas um candidato descartado pode conter a única solução. Portanto, ela não oferece garantia de completude nem de otimalidade.

Aprofunde por um limite de custo estimado

O IDA* executa busca em profundidade com um corte em $f=g+h$. O primeiro limite de corte é o valor da raiz. Pode qualquer nó acima dele, registrando o menor valor excedente. Esse valor se torna o próximo limite de corte; ele não é necessariamente o limite anterior mais 1. Use verificação de ciclos no caminho.

Para o mapa de exemplo, o primeiro limite de corte é 8. A em 9 e D em 11 são podados; B e C em 8 são explorados, mas G em 9 é podado. O próximo limite de corte é 9. Nessa iteração, o caminho por A produz C em 10, que é podado. O caminho S–B–C–G permanece dentro de 9 e tem sucesso.

Com admissibilidade, IDA* preserva a otimalidade de custo e precisa apenas do armazenamento de caminho da busca em profundidade. Suas passagens repetidas podem ser caras quando os custos produzem muitos limites distintos. Custos inteiros pequenos muitas vezes tornam o número de limites mais administrável.

Use a memória limitada de forma mais seletiva

A busca recursiva pela melhor escolha (RBFS) armazena a melhor prioridade alternativa em cada nível. Ela segue o ramo mais promissor até que essa alternativa se torne melhor e então retrocede. Usa memória linear, mas pode gerar novamente ramos esquecidos.

O SMA* usa a memória disponível, descarta a pior folha da fronteira quando ela está cheia e propaga seu valor para o pai. Esse registro permite regenerá-la depois. Com uma heurística admissível, ele é ótimo em custo se um caminho de solução ótima couber na memória. Caso contrário, pode retornar uma solução pior ou falhar se nenhum caminho de solução couber.

Escolha A* para uma resposta ótima quando o armazenamento for suficiente. Escolha IDA* ou uma variante adequada com memória limitada quando a otimalidade importar, mas a fronteira não couber. A* ponderado oferece um limite numérico de qualidade; a busca em feixe oferece poda agressiva sem esse limite.

Uma heurística pode ser otimista no conjunto e ainda assim variar abruptamente demais entre estados vizinhos. Admissibilidade e consistência representam essas verificações diferentes, e cada uma fundamenta uma versão diferente de A*.

Compare estimativas com custos reais

Uma heurística admissível satisfaz $0\le h(n)\le h^{\ast }(n)$ em todo estado. Em um objetivo, o custo restante real é zero, então sua estimativa também deve ser zero. Admissível não significa precisa: zero em todos os estados é seguro, mas não fornece orientação.

No mapa rodoviário de referência, as estimativas e as distâncias restantes exatas de menor custo até G são:

Toda estimativa é no máximo igual a seu custo real. Em um problema grande, calcular esses custos exatos pode ser tão difícil quanto a busca original. Uma demonstração a partir da estrutura do problema é então mais útil que uma tabela exaustiva.

Verifique cada ação

A consistência, também chamada de monotonicidade, exige $h(n)\le c(n,a,n^{\mathrm{\prime }})+h(n^{\mathrm{\prime }})$ para toda ação, além de zero nos objetivos. A estimativa atual não pode exceder o custo de um passo mais a estimativa do sucessor.

No mapa rodoviário, A→C fornece $7\le 4+4$, C→B fornece $4\le 1+5$ e D→G fornece $2\le 2+0$. Estradas de mão dupla exigem ambas as direções. Todas as 16 verificações direcionadas são satisfeitas para essas estimativas.

Somar as desigualdades ao longo de um caminho até um objetivo cancela as estimativas intermediárias. Isso fornece $h(n)\le h^{\ast }(n)$ em um caminho ótimo, então a consistência implica admissibilidade. Também fornece

As prioridades não podem diminuir ao longo de um caminho. A primeira expansão de um estado ocorre, portanto, por um caminho de menor custo, mesmo que sua primeira geração tenha sido mais cara.

Veja por que a admissibilidade sozinha exige reabertura

Considere as estradas de mão dupla S–A 1, A–C 1, S–B 1, B–C 2 e C–G 3. Sejam as estimativas S 0, A 4, B 1, C 1 e G 0. Elas não excedem os custos reais S 5, A 4, B 5, C 3 e G 0, então são admissíveis. Mas A→C viola a consistência: $4>1+1$.

A* expande S, depois B com prioridade 2 e depois C alcançado com custo 3 e prioridade 4. Em seguida, expande A com prioridade 5 e descobre um caminho mais barato até C, de custo 2. Rejeitar C permanentemente porque está fechado deixa um objetivo de custo 6. Reabrir C propaga a melhora e produz a solução ótima, de custo 5.

Considere o modelo de movimento

A distância de Manhattan é admissível e consistente para movimentos unitários horizontais e verticais. Se movimentos diagonais também custarem 1, ir de (0,0) a (3,3) leva apenas três movimentos, enquanto a distância de Manhattan indica 6. Para esse modelo de movimento, $\max (\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid },\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid })$ fornece a distância sem obstáculos. A garantia de uma heurística pertence a um modelo de ações específico.

Para elaborar uma estimativa segura, resolva uma versão mais fácil do problema. Um problema relaxado remove restrições de ação, então toda solução original continua disponível. Seu menor custo não pode exceder o menor custo original.

Remova restrições deliberadamente

Um custo relaxado exato é uma heurística admissível. Ele também é consistente quando as ações originais continuam disponíveis com seus custos: executar um passo original e depois uma rota relaxada ótima é uma rota relaxada possível, então o ótimo relaxado não pode custar mais.

No quebra-cabeça de 8 peças, uma peça só pode se mover para uma casa adjacente quando essa casa está vazia. Remova a exigência de que esteja vazia e as peças poderão passar por casas ocupadas. Cada peça numerada precisa então percorrer pelo menos sua distância horizontal mais a vertical até seu destino. A soma fornece a distância de Manhattan, $h_2$.

Remova também a adjacência e cada peça fora do lugar poderá saltar diretamente para seu destino em um movimento. O custo resultante é a contagem de peças fora do lugar, $h_1$. Ambas são fáceis de calcular sem buscar no quebra-cabeça original.

Calcule as duas estimativas

Para o objetivo “1 2 3 / 4 5 6 / 7 8 vazio”, considere “5 1 3 / 4 vazio 2 / 7 8 6”. Numere linhas e colunas a partir de 1.

As outras peças numeradas já estão corretas. Quatro estão fora do lugar, então $h_1=4$. Suas distâncias somam $2+1+2+1=6$, então $h_2=6$. A solução ótima leva 12 movimentos; os relaxamentos ignoram interações que criam trabalho adicional.

Não conte o espaço vazio. A um movimento do objetivo, uma peça numerada e o espaço vazio estão deslocados. Contar ambos produziria 2 quando o custo real é 1. O espaço vazio permite movimentos; ele não é uma peça adicional a ser cobrada.

Armazene subproblemas resolvidos

Um banco de dados de padrões registra custos exatos de um subproblema selecionado, como posicionar corretamente as peças 1 a 4 tratando as demais como intercambiáveis. Construa a tabela uma vez por busca para trás a partir do objetivo. Durante uma nova busca, use uma consulta em vez de resolver o subproblema novamente.

O subproblema não exige mais trabalho que o problema completo, fornecendo um limite inferior. No entanto, somar dois custos comuns de padrões pode cobrar o mesmo movimento real duas vezes. A soma é segura para padrões disjuntos quando cada banco conta apenas movimentos de suas próprias peças. Nomes de peças disjuntos, por si só, não estabelecem essa regra de contabilização de custos.

Combine estimativas seguras

O máximo de estimativas admissíveis é admissível:

Todo candidato permanece abaixo do custo restante real, então seu máximo também permanece. Ele é pelo menos tão informativo quanto cada estimativa individual. Uma soma simples não tem essa proteção.

Uma heurística aprendida a partir de exemplos resolvidos pode prever bem o custo restante em média. A precisão média não estabelece um limite inferior para todo estado. Ela mantém a garantia de A* com heurística admissível apenas quando se demonstra que suas estimativas nunca superestimam.

Uma estimativa mais próxima pode reduzir a exploração, mas uma estimativa custosa ainda pode tornar a busca mais lenta. Compare tanto as informações fornecidas quanto a computação total necessária.

Estabeleça a dominância em todo estado

Uma heurística admissível $h_2$ domina a heurística admissível $h_1$ se $h_2(n)\ge h_1(n)$ em todos os estados. Um tabuleiro favorável não é suficiente para demonstrar essa relação.

A distância de Manhattan domina a contagem de peças fora do lugar no quebra-cabeça de 8 peças. Cada peça fora do lugar deve percorrer pelo menos uma casa, então sua contribuição para a distância de Manhattan é pelo menos o 1 contado pela heurística mais fraca. Uma peça posicionada corretamente contribui com zero para ambas.

Com estimativas consistentes, A* deve expandir caminhos com $g+h<C^{\ast }$. Aumentar uma estimativa segura remove alguns caminhos dessa região obrigatória. Uma heurística consistente dominante não expande mais nós, exceto por diferenças em empates. Uma estimativa inadmissível pode ser ainda maior, mas perde a garantia de otimalidade e não se qualifica para essa comparação de dominância.

Resuma o esforço de busca

O fator de ramificação efetivo, $b^{\ast }$, descreve a largura de uma árvore uniforme equivalente. Conte $N$ nós gerados abaixo da raiz e seja $d$ a profundidade da solução. Resolva

O 1 adicional corresponde à raiz. Contar de forma consistente importa: se uma medição já inclui a raiz, não a adicione duas vezes.

Para 52 nós gerados abaixo da raiz e profundidade da solução 5, o total é 53 e $b^{\ast }\approx \mathrm{1,92}$. Para 1.000 nós gerados e profundidade 8, $b^{\ast }\approx \mathrm{2,20}$. Encontre esses valores numericamente, aumentando ou diminuindo um valor de teste até que sua soma geométrica corresponda ao total de nós.

Um valor próximo de 1 indica uma busca estreita. Compare resultados entre instâncias representativas, com a mesma regra de contagem e profundidades de solução comparáveis. O fator de ramificação efetivo pode ajudar a estimar o comportamento em escala maior, mas uma instância excepcionalmente fácil não é uma previsão confiável para toda uma família de problemas.

Meça o tempo de toda a computação

Suponha que um nó leve 10 microssegundos, incluindo 1 microssegundo para avaliar a heurística antiga. Uma substituta reduz a contagem de nós pela metade, mas leva 100 microssegundos por avaliação. O trabalho não heurístico ainda custa 9 microssegundos, então o novo total por nó é 109. A razão entre os tempos totais é

A busca fica cerca de 5,5 vezes mais lenta, apesar de visitar menos nós. Se a nova avaliação levar apenas 2 microssegundos, o total por nó passa a 11 e a razão entre os tempos é $\mathrm{0,5}\times 11\mathrm{/}10=\mathrm{0,55}$. Isso é cerca de 1,8 vez mais rápido.

Um banco de dados de padrões também tem custo de construção. Muitas buscas com o mesmo objetivo podem compartilhar esse investimento; uma busca pequena pode não compensá-lo. Meça separadamente o pré-processamento, o tempo de consulta, os nós gerados e a memória para que menos expansões não sejam confundidas com uma melhoria automática de velocidade.

A busca local altera repetidamente uma resposta candidata completa. Ela é adequada a tarefas nas quais a configuração final importa e a sequência usada para encontrá-la pode ser descartada.

Represente um candidato completo

Para as 8 rainhas, coloque uma rainha em cada coluna. Represente o estado pelos oito números de linha, lendo as colunas da esquerda para a direita. Todo estado tem as oito rainhas, inclusive os estados com conflitos. Um vizinho move uma rainha para outra linha em sua própria coluna.

Há $8^8=\mathrm{16.777.216}$ estados e $8\times 7=56$ vizinhos por estado. Um número fixo de estados atuais substitui a grande fronteira e os registros de pais da busca de caminhos. O armazenamento ainda depende do tamanho de um estado; manter uma tupla de oito entradas ocupa menos espaço que manter um enorme quadro de horários.

Elaborar horários, organizar componentes em chips e escolher um percurso completo por cidades seguem o mesmo padrão geral: cada estado é uma proposta completa. Um percurso é, por si só, uma disposição candidata, embora seu conteúdo descreva uma viagem. A busca local não precisa preservar a sequência de alterações usada para melhorar esse percurso.

Defina o que significa melhor

Uma função objetivo fornece a cada estado uma pontuação a maximizar. De modo equivalente, defina um custo a minimizar. Para as n rainhas, faça $h$ contar os pares de rainhas que se atacam. Conte cada par uma vez, incluindo ataques em linhas ou diagonais mesmo quando outra rainha estiver entre elas. Uma solução tem $h=0$.

Para quatro colunas, a tupla (1,2,3,4) coloca todas as rainhas em uma diagonal. Todos os seus $\left(\genfrac{}{}{0px}{}{4}{2}\right)=6$ pares se atacam. A tupla (2,1,3,4) tem dois pares que se atacam, enquanto (2,4,1,3) não tem nenhum. Aqui valores menores são melhores; a letra $h$ é um custo objetivo, não uma estimativa do custo restante do caminho usada por A*.

Interprete a paisagem

Imagine a qualidade do estado como altura. Para maximização:

• Um máximo global tem o melhor valor em todo o espaço.
• Um máximo local é melhor que seus vizinhos, mas pode ser pior que um estado distante.
• Um platô é uma região plana e conectada. Pode ser um máximo local plano sem saída ascendente ou um patamar do qual movimentos laterais podem alcançar uma saída ascendente.
• Uma crista pode subir em uma direção que os movimentos isolados disponíveis não conseguem seguir. Toda escolha imediata pode parecer pior.

Para minimizar o custo, inverta a altura: a busca procura mínimos e vales. Um mínimo local não prova que não exista um estado de custo menor em outro lugar. A vizinhança determina quais estados podem ser comparados em um passo, então alterar a modificação permitida pode mudar onde a busca fica presa.

Verifique se o caminho pode ser ignorado

Um agente de busca de rotas deve retornar ações permitidas a partir de seu início real. Um bom destino, sozinho, é insuficiente. A busca local geralmente retorna apenas o estado candidato, sem uma cadeia de pais que passe por todas as alterações anteriores.

Um método completo de busca local encontraria um objetivo sempre que um existisse; um método ótimo encontraria o melhor global. Métodos locais básicos não oferecem nenhuma das duas garantias gerais. Sua vantagem é que podem alcançar bons candidatos rapidamente quando armazenar uma árvore de busca sistemática é impraticável.

A subida de encosta faz a melhor melhora imediata que consegue encontrar. Para uma pontuação a maximizar, a ascensão mais íngreme escolhe o vizinho com maior pontuação. Para um custo a minimizar, escolhe o vizinho com menor custo. Ela para quando não existe melhora estrita.

Acompanhe uma execução com quatro rainhas

Faça um estado listar a linha da rainha em cada coluna e faça $h$ contar os pares que se atacam. Comece com (1,2,3,4), cujo custo é 6.

1. Avalie os movimentos de uma rainha. Um dos melhores vizinhos é (2,2,3,4), com custo 4.
2. A partir daí, um dos melhores vizinhos é (2,1,3,4), com custo 2.
3. Nenhum vizinho obtido pelo movimento de uma rainha tem custo abaixo de 2. A subida de encosta estrita para.

A disposição de custo zero (2,4,1,3) existe, mas não pode ser alcançada por um movimento de melhora imediata a partir do estado em que a busca parou. Isso é consequência da regra local, não evidência de que o programa contou os conflitos incorretamente.

Permita movimentos laterais úteis

Um movimento lateral mantém a mesma pontuação. Ele pode atravessar um patamar até uma saída que melhore o valor, mas também pode vaguear em um ótimo local plano. Limite os movimentos laterais consecutivos para evitar ciclos intermináveis.

No experimento com 8 rainhas relatado por Russell e Norvig, a ascensão mais íngreme a partir de inícios aleatórios tem sucesso em cerca de 14% das vezes, levando cerca de 4 passos no sucesso e 3 quando fica presa. Permitir até 100 movimentos laterais consecutivos eleva o sucesso relatado para cerca de 94%, com cerca de 21 passos por sucesso e 64 por falha. Esses são resultados desse experimento, não taxas universais de sucesso para a subida de encosta.

Mude a forma de escolher um vizinho

A subida de encosta estocástica seleciona aleatoriamente um vizinho que ofereça melhora, possivelmente favorecendo melhoras maiores. A subida de encosta por primeira escolha amostra vizinhos um por vez e escolhe a primeira melhora. Ela evita avaliar uma vizinhança enorme antes de cada movimento. Ambas continuam recusando movimentos piores.

A subida de encosta com reinícios aleatórios começa uma nova execução a partir de um estado recém-amostrado após uma execução malsucedida. Com execuções independentes de probabilidade de sucesso $p$, o número esperado de execuções até o primeiro sucesso é $1\mathrm{/}p$. Para $p=\mathrm{0,14}$, são cerca de 7 execuções. Usando as contagens de passos relatadas, o total esperado de passos é

As execuções malsucedidas também contribuem com trabalho. Com probabilidade positiva de sucesso e reinícios independentes, a probabilidade de acabar tendo sucesso se aproxima de 1 à medida que o número de execuções cresce.

Permita que vários candidatos compartilhem descobertas

A busca local em feixe mantém $k$ estados, gera seus vizinhos em conjunto e retém os $k$ melhores desse conjunto reunido. Um pai promissor pode contribuir com vários sobreviventes, enquanto outro não contribui com nenhum. Esse compartilhamento a distingue de reinícios independentes.

A reunião também pode fazer todos os candidatos se concentrarem em uma região. A busca em feixe estocástica amostra sobreviventes com probabilidade crescente conforme a qualidade para preservar mais variedade. A escolha entre movimentos laterais, reinícios e diversidade populacional depende do motivo pelo qual o progresso está falhando: uma passagem próxima de mesmo valor, uma região inicial ruim ou candidatos demais explorando a mesma área.

Algumas paisagens exigem uma perda temporária antes que um estado melhor se torne alcançável. O recozimento simulado permite esses movimentos com uma probabilidade controlada. Os algoritmos genéticos, por sua vez, exploram selecionando e combinando candidatos completos.

Aceite um movimento pior às vezes

O recozimento simulado amostra um vizinho aleatório. Aceite um movimento que melhore o resultado. Para uma função objetivo maximizada, escreva sua variação como $\mathrm{\Delta }E$. Se $\mathrm{\Delta }E<0$, aceite o movimento pior com probabilidade

Para minimização de custo, seja $\mathrm{\Delta }$ o aumento do custo. Um movimento pior tem então $\mathrm{\Delta }>0$ e probabilidade de aceitação $e^{-\mathrm{\Delta }\mathrm{/}T}$. Movimentos de valor igual têm probabilidade 1 em ambas as fórmulas. A temperatura e as variações da função objetivo devem usar uma escala numérica compatível.

Uma queda de 2 na pontuação é aceita com probabilidade de cerca de 0,819 na temperatura 10, 0,135 na temperatura 1 e 0,018 na temperatura 0,5. Na temperatura 10, uma queda maior, de 5, tem probabilidade de cerca de 0,607. Assim, a temperatura controla a tolerância, enquanto o tamanho da perda ainda importa para uma mesma temperatura.

Reduza a temperatura

Um cronograma de resfriamento define a temperatura ao longo do tempo. O resfriamento geométrico usa $T_{k+1}=\alpha T_k$ com um fator próximo de 1, como 0,95. Em temperatura alta, muitos movimentos piores são aceitos e a exploração se assemelha a um passeio aleatório. Perto de zero, movimentos piores se tornam raros e o comportamento se assemelha ao da subida de encosta.

Resfriar rápido demais pode prender a busca antes que ela escape de uma região ruim. Resfriar muito devagar aumenta a computação. O resultado assintótico de ótimo global exige resfriamento suficientemente lento e a possibilidade usual de alcançar estados pela vizinhança; uma execução geométrica finita comum não garante sucesso global. Usado para organização de componentes em chips e programação de tarefas desde a década de 1980, o método recebe seu nome do aquecimento e resfriamento lento de metal para que ele se acomode em uma estrutura de menor energia.

Construa uma nova população

Um algoritmo genético representa candidatos como sequências. Cada geração avalia sua aptidão, seleciona pais com preferência pelos de maior aptidão, cria filhos por cruzamento e aplica mutações ocasionais.

Para as 8 rainhas, oito dígitos de linha descrevem uma rainha por coluna. A aptidão pode contar pares que não se atacam, com 28 como máximo. Corte as sequências dos pais “64751517” e “64278273” após o quarto dígito. Combinar metades opostas produz “64758273” e “64271517”.

Os pais têm aptidão 23 e 24; os filhos têm aptidão 27 e 21. Um filho melhora em relação a ambos os pais, enquanto o outro é pior. O cruzamento oferece novas combinações, não uma garantia de melhora. Ele é útil quando bons blocos tendem a manter seu valor ao serem combinados. A mutação altera ocasionalmente uma posição e ajuda a introduzir variedade além dessas combinações.

Seleção, cruzamento e mutação têm papéis diferentes: a seleção favorece candidatos úteis, o cruzamento os recombina e a mutação altera posições individuais. Como a busca em feixe estocástica, o método mantém uma população, mas novos candidatos podem reunir material de dois pais. Nem um pai de alta aptidão nem uma temperatura final baixa, por si só, provam que o ótimo global foi encontrado.