Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Backtracking

Prof. Gustavo Soares

Backtracking

Prof. Gustavo Soares 1 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Roteiro

1. Introdução

2. Algoritmo de Backtracking

3. Gerando Permutações

5. Problema das N-Rainhas

4. Problema do Circuito Hamiltoniano

6. Problema da Soma do Subconjunto

Prof. Gustavo Soares 2 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Busca Combinatória

I Problemas de busca combinatória podem ser abordados por

busca exaustiva:
1. Listar o espaço de busca.
2. Examinar cada possibilidade.
3. Retornar as soluções que satisfazem o problema.

I Ineficiente quando o espaço de busca é grande.

I Como fazer melhor?

Prof. Gustavo Soares 2 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Por que Backtracking?

I Aborda problemas complexos de busca combinatória.

I Utilizada para encontrar conjuntos que satisfaçam algumas
restrições.
I Mais eficiente que busca exaustiva: só gera soluções
candidatas promissoras.

Prof. Gustavo Soares 3 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Formulação do Problema

Os problemas abordados por Backtracking possuem a seguinte

forma:

Problemas Abordados por Backtracking

Ache uma n-tupla (x1 , x2 , . . . , xn ), tal que cada coordenada xi é
um elemento de algum Si linearmente ordenado. A dupla pode ter
que satisfazer algumas restrições.

Prof. Gustavo Soares 4 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Ideia Geral

I As soluções são construı́das um componente por vez.

I Cada solução parcial é avaliada como promissora ou não
promissora.
I Se uma solução parcial é promissora, selecionamos o próximo
componente da solução.
I Senão, o algoritmo retrocede (backtrack) e substitui o último
componente da solução parcial por sua próxima opção.

Prof. Gustavo Soares 5 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Árvore de Estados
I Backtracking induz uma árvore do espaço de soluções:
I A raiz corresponde ao estado inicial (antes do inı́cio da busca
por uma solução).
I Um nó interno corresponde à uma solução parcial.
I Um nó folha corresponde a uma solução parcial não promissora
ou à solução final.
I A busca é feita em profundidade (DFS).

Prof. Gustavo Soares 6 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Roteiro

1. Introdução

2. Algoritmo de Backtracking

3. Gerando Permutações

5. Problema das N-Rainhas

4. Problema do Circuito Hamiltoniano

6. Problema da Soma do Subconjunto

Prof. Gustavo Soares 7 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Estrutura Geral do Algoritmo

1. Defina a representação da solução (normalmente um array).

2. Estabeleça os conjuntos S1 , . . . , Sn e a ordem em que seus

elementos são processados.

3. Estabeleça as condições que tornam uma solução parcial

válida.

4. Estabeleça um critério para identificar a solução final.

Prof. Gustavo Soares 7 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Estrutura Geral do Algoritmo

I O algoritmo induz uma árvore do espaço de estados.

I Cada nó representa enuplas parciais com os primeiros i
componentes da solução parcial.
I Para cada (x1 , x2 , . . . , xi ) válida, o algoritmo acha o próximo
elemento que é consistente com
I os valores de (x1 , x2 , . . . , xi );
I as restrições do problema;

I e o adiciona à (x1 , x2 , . . . , xi ) como seu (i + 1) componente.

Prof. Gustavo Soares 8 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Algoritmo de Backtracking

Para iniciar um algoritmo de backtracking, o seguinte pseudo-código

pode ser chamado para i = 0 (X [1 . . 0] representa a enupla vazia).

Backtrack(X [1 . . i])
1 // Input: X [1 . . i] (i primeiros componentes da solução)
2 // Output: todas as enuplas representando as soluções do problema
3 if X [1 . . i] == solução
4 write X [1 . . i]
5 else for each x ∈ Ai+1 consistente com as restrições
6 X [i + 1] = x
7 Backtrack(X [1 . . i + 1])

Prof. Gustavo Soares 9 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Roteiro

1. Introdução

2. Algoritmo de Backtracking

3. Gerando Permutações

5. Problema das N-Rainhas

4. Problema do Circuito Hamiltoniano

6. Problema da Soma do Subconjunto

Prof. Gustavo Soares 10 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Gerando Permutações

Use Backtracking para gerar todas as permutações de {1, 2, 3}.

I Restrições: sj 6= sk para todo sj , sk ∈ S e todo j 6= k

Prof. Gustavo Soares 10 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Gerando Permutações

Use Backtracking para gerar todas as permutações de {1, 2, 3}.

I Restrições: sj 6= sk para todo sj , sk ∈ S e todo j 6= k

Prof. Gustavo Soares 10 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Gerando Permutações

1. Representação da solução: um array

X [1 . . n] satisfazendo X [i] 6= X [j] para todo i 6= j

2. Condições de continuação: qualquer solução parcial X [1 . . i]

deve satisfazer

X [i] 6= X [j] para todo j < i

3. Critério solução final: i == n.

Prof. Gustavo Soares 11 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Gerando Permutações

Perm(X [1 . . i], A)
// A == conjunto a ser permutado
1 if i == n
2 write X [1 . . n]
3 else for each a ∈ A
4 X [i + 1] = a
5 if valid(X [1 . . i + 1])
6 Perm(X [1 . . i + 1], A)

Valid(X [1 . . i])
1 for j = 1 to i − 1
2 if X [j] == X [i]
3 return false
4 return true

Prof. Gustavo Soares 12 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Roteiro

1. Introdução

2. Algoritmo de Backtracking

3. Gerando Permutações

5. Problema das N-Rainhas

4. Problema do Circuito Hamiltoniano

6. Problema da Soma do Subconjunto

Prof. Gustavo Soares 13 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Problema das N-Rainhas

Ache todas as possibilidades de colocar n rainhas num tabuleiro de

xadrez n × n tal que elas não possam se atacar:

I cada linha pode conter apenas uma rainha.

I cada coluna pode conter apenas uma rainha.
I cada diagonal pode conter apenas uma rainha.

Prof. Gustavo Soares 13 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Problema das Quatro Rainhas

I Quantos candidatos terı́amos por busca exaustiva para n = 4?

Prof. Gustavo Soares 14 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Problema das Quatro Rainhas

I Quantos candidatos terı́amos por busca exaustiva para n = 4?

I 16! = 37440 possı́veis formas de dispor 4 rainhas no tabuleiro.
12!

Prof. Gustavo Soares 14 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Problema das Quatro Rainhas

I Quantos candidatos terı́amos por busca exaustiva para n = 4?

I 16! = 37440 possı́veis formas de dispor 4 rainhas no tabuleiro.
12!

I Uma busca exaustiva mais eficiente, põe uma rainha em cada

linha e coluna portanto 4! = 24 possibilidades de dispor 4
rainhas no tabuleiro.

Prof. Gustavo Soares 14 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Preliminares

1. Representação da solução: um array

X [1 . . n] onde os indı́ces representam linhas e valores colunas

2. Condições de continuação: qualquer solução parcial X [1 . . i]

deve satisfazer
I rainhas devem estar em colunas diferentes.
I rainhas não podem estar na mesma diagonal.

3. Critério solução final: i == n.

Prof. Gustavo Soares 15 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Backtracking para n = 4

Prof. Gustavo Soares 16 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Algoritmo

N-Queens(X [1 . . i])
1 if i == n
2 write X [1 . . n]
3 else for j = 1 to n
4 X [i + 1] = j
5 if valid(X [1 . . i + 1])
6 N-Queens(X [1 . . i + 1])

Valid(X [1 . . i])
1 for j = 1 to i − 1
2 if (X [j] == X [i]) or (|X [i] − X [j]| == |i − j|)
3 return false
4 return true

Prof. Gustavo Soares 17 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Exercı́cio 2

Explique como a simetria do tabuleiro pode ser usada para achar a

segunda solução do problema das 4-rainhas. Abaixo encontra-se a
primeira solução mostrada no slide anterior.

Prof. Gustavo Soares 18 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Roteiro

1. Introdução

2. Algoritmo de Backtracking

3. Gerando Permutações

5. Problema das N-Rainhas

4. Problema do Circuito Hamiltoniano

6. Problema da Soma do Subconjunto

Prof. Gustavo Soares 19 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Definição do Problema

Circuito Hamiltoniano
Um circuito hamiltoniano em um grafo não direcionado G = (V , E )
é um ciclo simples que passa por todos vértices uma única vez.

I Entrada: grafo G com n vértices.

I Saı́da: ciclo Hamiltoniano.

Prof. Gustavo Soares 19 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Restrições

I Solução será uma tupla de n+1 elementos

Si = {x1 , x2 , x3 , x4 , x5 , x6 }
I Restrições:

Prof. Gustavo Soares 20 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Restrições

I Solução será uma tupla de n+1 elementos

Si = {x1 , x2 , x3 , x4 , x5 , x6 }
I Restrições:
I xi 6= xj para todo xi , xj ∈ S e todo i 6= j com 1 < i, j ≤ n + 1
I xi = xn+1
I (xk , xk−1 ) ∈ E para todo 1 ≤ k ≤ n + 1 (cada novo
componente deve ter uma aresta com o componente anterior).

Prof. Gustavo Soares 20 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Circuito Hamiltoniano

Ham(X [1 . . i], V , E , s)
// Input: vertice V , aresta E e origem s ∈ V
1 if i == n + 1
2 write X [1 . . n]
3 else for each v ∈ V
4 X [i + 1] = v
5 if valid(X [1 . . i + 1], E )
6 Ham(X [1 . . i + 1], V , E , s)

Valid(X [1 . . i])
1 for j = 2 to i − 1
2 if (X [j] = = X [i]) or ((X [1] and X [n + 1]) 6= s)
3 return false
4 if (X [i], X [i − 1]) ∈ E
5 return true
6 else return false

Prof. Gustavo Soares 21 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Exercı́cio 1

Desenhe a árvore de busca do backtracking para o grafo abaixo até

encontrar a primeira solução.

Prof. Gustavo Soares 22 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Roteiro

1. Introdução

2. Algoritmo de Backtracking

3. Gerando Permutações

5. Problema das N-Rainhas

4. Problema do Circuito Hamiltoniano

6. Problema da Soma do Subconjunto

Prof. Gustavo Soares 23 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Problema da Soma do Subconjunto

Definição
Achar o subconjunto de um dado conjunto B = {b1 , . . . , bn } de n
inteiros positivos cujo a soma de seus elementos é igual a um dado
inteiro positivo d.

Por exemplo, para B = {1, 2, 5, 6, 8} e d = 9, há duas soluções:

{1, 2, 6} e {1, 8}

É conveniente ordenar os elementos do conjunto em ordem crescente

b1 ≤ b2 ≤ . . . bn

Prof. Gustavo Soares 23 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Problema da Soma do Subconjunto

I O espaço de estados é representado por uma árvore binária onde:

I a raiz marca o inı́cio (nenhum elemento escolhido);
I nós a direita e esquerda representam inclusão e exclusão de
elementos resp.
I Caminhos da raiz até o i-ésimo nı́vel indicam os elementos
escolhidos.
I As somas parciais s 0 são armazenadas nos nós.
I O algoritmo retrocede quando:

s 0 + si+1 > d soma muito grande

X n
s0 + sj < d soma muito pequena
j=i+1

Prof. Gustavo Soares 24 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Backtracking para uma instância do problema

Abaixo a árvore de busca para B = {3, 5, 6, 7} e d = 15.

Prof. Gustavo Soares 25 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Exercı́cio 3

Dê um algoritmo em pseudo-código para resolver o problema da

soma do subconjunto.

Prof. Gustavo Soares 26 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Considerações Finais

I Adequado a problemas complexos de busca combinatória.

I No pior caso pode ter que gerar todos os candidatos (igual
força bruta).
I A melhora depende da capacidade de poda de soluções não
promissoras.
I Muito difı́cil de analisar assintoticamente (depende do
tamanho da árvore de estados).

Prof. Gustavo Soares 27 / 28 UFCG CEEI

Introdução Algoritmo Permutações N-Rainhas Circuito Hamiltoniano Soma do Subconjunto

Referências

Anany Levitin. Introduction to the Design and Analysis of

Algorithms. Segunda Edição. Pearson International Edition,
2007.

Prof. Gustavo Soares 28 / 28 UFCG CEEI