Aplicacao de um algoritmo de backtracking

UNIVERSIDADE FEDERAL DE ITAJUBÁ CAMPUS ITABIRA

Disciplina: Complexidade de Algoritmos – ECO014

Trabalho prático 1

Alunos: Daniel Luis M. Timponi Diego Cordeiro Brioshi

RA: 16607 RA: 16.609

Professor: Rafael Francisco dos Santos

Itabira, 7 de maio de 2010

Sumário

1

DESCRIÇÃO DAS CLASSES................................................................................. 3

2

TENTATIVAS BEM SUCEDIDAS ........................................................................ 5

3

TENTATIVAS MAL SUCEDIDAS ........................................................................ 6

4

RESULTADOS E ANÁLISE DOS RESULTADOS ............................................... 7

1 DESCRIÇÃO DAS CLASSES public class Projeto3
Variáveis Random random =new Random(); //Variável randômica int matriz[][]; //matriz equivalente ao centro de BH int vet_pos[], // vetor que armazena o percurso do Jorge vet[]; //vetor que armazena o numero de vezes que cada esquina é visitada int e=0; //numero de quarteirões percorridos int topo; //auxiliar do vet_pos (vetor de percurso) int k=9; //auxiliar na impressão Métodos public Projeto3() Construtor da classe. Inicia os atributos declarados Pré-define a posição inicial do Jorge e a posição da casa do Jorge e do James Espalha randomicamente os bandidos public boolean movimento(int x , int y) Controla o percurso do Jorge evitando caminhos em direção a esquinas ocupadas por bandidos, esquinas já visitadas e mantendo o Jorge dentro dos limites do centro de BH eliminando o erro array out of bounds exception. public boolean movimento2(int x, int y) Controla o caminho reverso do Jorge evitando o cruzamento com ladrões public boolean sucesso(int x, int y) Função booleana referente a posição de tentativa de fuga bem sucedida public boolean Fuga(int x, int y) Função recursiva que executa o percurso do Jorge no centro de BH Pré-define os movimentos (um quarteirão acima ,ou abaixo, ou a direita, ou a esquerda) public void