Backtracking

[TamiresLelis 0]

olá!

 

Gostaria de saber se alguém de candidata a me ajudar a desenvolver o algoritmo a seguir:Observações:

 

 

Backtracking

Uma área muito interessante de projeto de algoritmos é quando se quer achar soluções para problemas que não se

conhece uma regra fixa de computação. Nesse caso, uma possível alternativa é a técnica de tentativa e erro. Nesse tipo de

problema, a abordagem mais comum é decompor o processo em um número finito de tarefas parciais. Geralmente as

tarefas são expressas naturalmente em termos recursivos e devem ser exploradas de forma exaustiva. A construção de

uma solução é obtida através de tentativas (ou pesquisas) da árvore de sub-tarefas. Muitas vezes as tentativas crescem

exponencialmente e, nesses casos, deve-se usar heurísticas para evitar uma pesquisa exaustiva. Uma heurística não

garante a solução ótima mas tende a ser rápida. O objetivo aqui é estudar como essa técnica recursiva funciona e não

heurísticas, que em geral são dependentes do tipo de problema que se está estudando.

A técnica de tentativa e erro pode ser melhor explicada através de um exemplo: O Passeio do Cavalo (Knight’s

Tour ). Seja um tabuleiro n x n com n2 posições e um cavalo que se move seguindo as regras do xadrez. O cavalo é

colocado em uma posição inicial (x0; y0). O objetivo do problema é encontrar, se existir, um passeio do cavalo com

n2 - 1 movimentos tal que todas as posições do tabuleiro são visitadas uma única vez.

Algoritmos que usam a técnica de tentativa e erro não seguem uma regra fixa de computação. Em geral, os passos

em direção à solução final são tentados e registrados em uma estrutura de dados. Caso esses passos tomados não levem à

solução final do problema, eles podem ser retirados e apagados do registro. Neste problema, os oito movimentos possíveis

de um cavalo, considerando um tabuleiro 5 x 5 e o cavalo posicionado inicialmente no centro desse tabuleiro, estão

representados a seguir:

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS

CAMPUS VII - UNIDADE TIMÓTEO

TPD – Trabalho Prático da Disciplina

Disciplina: MD – Matemática Discreta

Prof.: Bruno R. Silva

Curso: Engenharia de Computação 2° Período

Data: 19/08/2011 Valor: 20 pts Nota: ...............................

Cada número representa um movimento válido do cavalo. Assim, o movimento 7, por exemplo, significa avançar uma

coluna para a direita e descer duas linhas.

Uma possível solução para um tabuleiro 5 x 5 seria:

Para o exemplo acima, o cavalo, ao começar na posição indicada por 1, pode fazer qualquer um dos oito

movimentos acima. O movimento 7 é executado e o número dois é colocado nessa posição. Nesse momento, os

movimentos de 5 a 8 levariam o cavalo à uma posição inexistente. Assim, somente os movimentos 2 e 4 podem ser

executados e um deles deve ser escolhido. Note que o movimento 3 levaria o cavalo à posição inicial, que já foi visitada.

Esse processo deve continuar até possivelmente se chegar a uma solução.

Objetivo: Este trabalho tem como objetivo a implementação do Passeio do Cavalo e sua avaliação para um tabuleiro 8 x

8. Pede-se:

1. O possível Passeio do Cavalo começando na posição (1; 1) (canto superior esquerdo do tabuleiro)

2. Suponha a geração do Passeio do Cavalo, cada um começando em uma das 64 casas do tabuleiro.

Deseja-se calcular:

(a) a profundidade que se consegue alcançar na árvore de possibilidades até a primeira vez que se chega a

uma posição que não seja possível caminhar mais e deve ser feito um retrocesso;

(B) o número de possibilidades até esse momento.

Por exemplo, para um tabuleiro 4 x 4, começando na posição (1; 1) e sempre tentando as posições na

ordem de 1 a 8, temos o seguinte passeio:

Legenda: Casa visitada no n-ésimo passo {Identificação (n°) dos movimentos válidos}, sendo que o primeiro movimento

(n°) que aparece é o que foi escolhido.

Neste caso, a primeira casa visitada (que tem o número 1) está no canto superior esquerdo. A partir dessa casa, só é

possível executar dois movimentos: 7 e 8. Como o primeiro movimento é escolhido, a segunda casa visitada recebe o

número 2 e foi alcançada executando o movimento 7. Ao se chegar à 14 a casa visitada, não é possível prosseguir. Até

esse momento, temos a seguinte quantidade de possibilidades:

2 x 3 x 2 x 2 x 2 x 2 x 2 x 2 x 1 x 1 x 2 x 1 x 2 = 29 x 3 = 1536:

Ao não ser possível continuar, teríamos que retornar até à 13a casa, escolher o movimento 7 e tentar prosseguir. Se ainda

assim não for possível prosseguir, teríamos que retornar até à 11a casa, escolher o movimento 5 e tentar continuar. Veja

que nesse exemplo só existe uma alternativa na 12a casa, fazendo com que seja necessário retornar até a primeira casa

onde haja mais de uma possibilidade de movimento, que nesse momento é a 11a casa.

 

 

Qual quer dúvida entre em contado comigo:@tamireslelis__

e e-mail:tamiresslelis@gmail.com

 

OBSERVAÇÕES:Eu agora tenho o programa pronto preciso modificá-lo alguém se cantidata?

[quitZAUMMM 18]

Opa,

vamo que vamo.

 

[]s