Técnica de backtracking

Agenda
•• •• •• •• Conceitos Básicos Conceitos Básicos O Problema das Rainhas O Problema das Rainhas Template Genérico Template Genérico Mochila Binária Mochila Binária

Análise e Técnicas de Algoritmos
Jorge Figueiredo

Backtracking and Branch-and-Bound Backtracking and Branch-and-Bound

Análise e Técnicas de Algoritmos – 2005.1

© Jorge Figueiredo, DSC/UFCG

Análise e Técnicas de Algoritmos – 2005.1

© Jorge Figueiredo, DSC/UFCG

Jogo da Troca de Bolas
•• n bolas vermelhas e n bolas pretas n bolas vermelhas e n bolas pretas •• Tabuleiro (uma linha) com 2n + 1 posições Tabuleiro (uma linha) com 2n + 1 posições •• Bolas com a mesma cor em extremidades diferentes, e um Bolas com a mesma cor em extremidades diferentes, e um espaço vazio separando o conjunto de bolas diferentes. espaço vazio separando o conjunto de bolas diferentes. •• Movimentos possíveis: Movimentos possíveis: – Bola vermelha para a esquerda e preta para a direita – Bola vermelha para a esquerda e preta para a direita – Mover um espaço se o espaço está vazio – Mover um espaço se o espaço está vazio – Pular sobre exatamente uma bola de cor diferente, se o – Pular sobre exatamente uma bola de cor diferente, se o espaço logo após a bola estiver vazio espaço logo após a bola estiver vazio

Jogo da Troca de Bolas

Análise e Técnicas de Algoritmos – 2005.1

© Jorge Figueiredo, DSC/UFCG

Análise e Técnicas de Algoritmos – 2005.1

© Jorge Figueiredo, DSC/UFCG

Problema do Labirinto

Problema do Labirinto

Análise e Técnicas de Algoritmos – 2005.1

© Jorge Figueiredo, DSC/UFCG

Análise e Técnicas de Algoritmos – 2005.1

© Jorge Figueiredo, DSC/UFCG

1

Jogo do “Resta Um”

O Que Estes Problemas Têm em Comum?
•• Tomar uma série de decisões entre várias opções. Tomar uma série de decisões entre várias opções. •• Cada decisão leva a um novo conjunto de decisões. Cada decisão leva a um novo conjunto de decisões. •• Alguma(s) seqüência(s) de decisões pode(m) conduzir