Passeio do cavalo: técnicas de força bruta. No Exercício 6.24, desenvolvemos uma solução para o problema do Passeio do Cavalo. A técnica usada, chamada ‘heurística de acessibilidade’, gera muitas soluções e é executado de modo eficiente. À medida que os computadores continuarem crescendo em potência, poderemos resolver muitos problemas com o imenso poder da computação e de algoritmos relativamente pouco sofisticados. Vamos chamar essa técnica de solução do problema pela ‘força bruta’.

  1. Use a geração de número aleatório para permitir que o cavalo se movimente pelo tabuleiro de xadrez aleatoriamente (logicamente, em seus movimentos legítimos em forma de L). Seu programa deverá executar um passeio e imprimir o tabuleiro final. Até onde o cavalo conseguiu chegar?
  2. Provavelmente, o programa anterior produziu um passeio relativamente curto. Agora, modifique seu programa para tentar 1000 passeios. Use um array de subscrito único para registrar o número de passeios de cada extensão. Quando seu programa terminar de experimentar os 1000 passeios, ele deverá mostrar essa informação em formato tabular. Qual foi o melhor resultado?
  3. Provavelmente, o programa anterior lhe ofereceu alguns passeios ‘respeitáveis’, mas não passeios completos. Agora, ‘retire todas as restrições’, e simplesmente deixe que seu programa seja executado até que produza um passeio completo. [Cuidado: essa versão do programa poderia ser executada por horas em um computador poderoso.] Mais uma vez, mantenha uma tabela dos números de passeios de cada extensão e imprima essa tabela quando o primeiro passeio completo for encontrado. Quantos passeios seu programa fez até produzir um passeio completo? Quanto tempo ele levou para fazer isso?
  4. Compare a versão força bruta do Passeio do Cavalo com a versão da heurística de acessibilidade. Qual das duas versões exigiu um estudo mais cuidadoso do problema? Qual algoritmo foi mais difícil de desenvolver? Qual exigiu mais poder do computador? Poderíamos estar certos (antecipadamente) de obter um passeio completo com a técnica de heurística de acessibilidade? Poderíamos estar certos (antecipadamente) de obter um passeio completo com a técnica de força bruta? Argumente os prós e os contras da solução geral do problema pela força bruta.

Passo 1

Beleza pessoal, espero que todos estejam bem e dispostos a continuar mais um dia de estudos. Hoje iremos realizar essa atividade de C que é bem extensa, então é bom estarem ligados. Abram seu compilador para podermos começarmos.

  1. Vamos modificar a função makeMoves para selecionar um movimento aleatório, se houver um disponível.
  2. A função modificada:

    Passo 2

  3. Vamos precisar adicionar uma nova variável:
  4. int movePerTour[64] = {0};

    E modifique a função principal:

    Passo 3

  5. Modificando main para ser executado até que ocorra um tour completo:
  6. O programa tentou 9827291 tours, levou 1 hora e 33 minutos.

  7. A abordagem heurística exigia um estudo mais aprofundado do programa, também era mais difícil de implementar.

O programa de força bruta requer mais poder de computação e leva muito tempo para encontrar um tour completo.

A abordagem heurística exigiu muito pouco tempo para encontrar um passeio completo. Não podemos ter certeza com uma abordagem heurística de que encontraremos um passeio completo. Isso foi comprovado quando testamos a partir de todos os quadrados possíveis. Alguns passeios não chegariam a 63 movimentos. Com uma solução de força bruta, temos ainda menos certeza de encontrar um tour completo.

Resposta

Ver o desenvolvimento!