CIC 110Análise e Projeto de Análise e Projeto de

Algoritmos IAlgoritmos I

Universidade Federal de Itajubá

Prof. Roberto Affonso da Costa Junior

AULA 05AULA 05

– Pesquisa Completa (Força Bruta)

Pesquisa CompletaPesquisa Completa

A pesquisa completa é um método geral que pode ser usado para resolver quase qualquer problema de algoritmo. A ideia é gerar todas as soluções possíveis para o problema usando a força bruta, e depois selecionar a melhor solução ou contar o número de soluções, dependendo do problema.

A pequisa completa é uma boa técnica se houver tempo suficiente para passar por todas as soluções, porque a pesquisa geralmente é fácil de implementar e sempre dá a resposta correta. Se a pesquisa completa for muito lenta, outras técnicas, como algoritmos gananciosos ou programação dinâmica, podem ser necessárias.

Gerando SubconjuntosGerando SubconjuntosConsideramos primeiro o problema de gerar todos os subconjuntos de um conjunto de n elementos. Por exemplo, os subconjuntos de {0, 1, 2} são; {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2} e {0, 1, 2}.

Existem dois métodos comuns para gerar subconjuntos: podemos realizar uma pesquisa recursiva ou explorar a representação de bits de números inteiros.

Método 1Método 1Uma maneira de passar por todos os subconjuntos de um conjunto é usar a recursão. A busca de função a seguir gera os subconjuntos do conjunto {0, 1,. . . , n - 1}. A função mantém um subconjunto vetorial que conterá os elementos de cada subconjunto. A pesquisa começa quando a função é chamada com o parâmetro 0. void search(int k)

{if (k == n) {

// process subset} else {

search(k+1);subset.push_back(k);search(k+1);subset.pop_back();

}}

Método 1Método 1Quando a busca de função é chamada com o parâmetro k, ele decide se deve incluir o elemento k no subconjunto ou não e, em ambos os casos, se chama com o parâmetro k + 1 No entanto, se k = n, a função percebe que todos os elementos foram processados e um subconjunto foi gerado.

A seguinte árvore ilustra as chamadas de função quando n = 3. Podemos sempre escolher o ramo esquerdo (k não está incluído no subconjunto) ou o ramo direito (k está incluído no subconjunto).

Método 1Método 1

ImplementaçãoImplementaçãovector <vector <int> > getsubsets(vector <int> set, int index){

vector < vector <int> > allsubsets;sort (allsubsets.begin(), allsubsets.end());if(index != set.size()){

allsubsets=getsubsets(set,index+1); //obter subconjuntos para set [index + 1: n]

int item=set[index]; vector <vector <int> > moresubsets;vector<vector<int> >::iterator i=allsubsets.begin();do {

vector<int> newsubset;for(vector<int>::iterator j=(*i).begin();j<(*i).end();j++){

newsubset.push_back(*j); //faça uma cópia de cada um dos subconjuntos obtidos para set [index + 1: n]

}

ImplementaçãoImplementaçãonewsubset.push_back(item);

//adicione set [index] a cada um delesmoresubsets.push_back(newsubset);i++;

} while(i<allsubsets.end());for(vector<vector<int> >::iterator i = moresubsets.begin();

i < moresubsets.end();i++){

allsubsets.push_back(*i); //agora este é o novo conjunto de subconjuntos !!

}return allsubsets;

}vector<int> empty;allsubsets.push_back(empty);

//O valor vazio atua como NULL para subconjuntosreturn allsubsets;

}

ImplementaçãoImplementaçãonewsubset.push_back(item);

//adicione set [index] a cada um delesmoresubsets.push_back(newsubset);i++;

} while(i<allsubsets.end());for(vector<vector<int> >::iterator i = moresubsets.begin();

i < moresubsets.end();i++){

allsubsets.push_back(*i); //agora este é o novo conjunto de subconjuntos !!

}return allsubsets;

}vector<int> empty;allsubsets.push_back(empty);

//O valor vazio atua como NULL para subconjuntosreturn allsubsets;

}

ImplementaçãoImplementação

for(vector<vector<int> >::iterator i=k.begin();i<k.end();i++){

printf("{");for(vector<int>::iterator j=(*i).begin();j<(*i).end();j++){

if (j != (*i).end() - 1){

printf("%d, ", *j);} else {

printf("%d", *j);}

}

ImplementaçãoImplementaçãoif (i != k.end() - 1){

printf("},");} else {

printf("}");}

}printf("}\n");return 0;

}

Exercício:Exercício:

Implemente o programa e coloque na entrada:3

1 2 3A saída será:

subconjuntos = {{},{3},{2},{3, 2},{1},{3, 1},{2, 1},{3, 2, 1}}

Seu trabalho é alterar o programa para sair da forma:subconjuntos = {{},{1},{2},{3},{1, 2},{1, 3},{2, 3},{1, 2, 3}}

Data de Entrega: 12/09/2017 no 12/09/2017 no e-mail: e-mail: rcosta62br@gmailrcosta62br@gmail.com.com

Implemente o programa e coloque na entrada:3

1 2 3A saída será:

subconjuntos = {{},{3},{2},{3, 2},{1},{3, 1},{2, 1},{3, 2, 1}}

Seu trabalho é alterar o programa para sair da forma:subconjuntos = {{},{1},{2},{3},{1, 2},{1, 3},{2, 3},{1, 2, 3}}

Data de Entrega: 12/09/2017 no 12/09/2017 no e-mail: e-mail: rcosta62br@gmailrcosta62br@gmail.com.com

Método 2Método 2Outra maneira de gerar subconjuntos é baseada na representação de bits de números inteiros. Cada subconjunto de um conjunto de n elementos pode ser representado como uma sequência de n bits, que corresponde a um número inteiro entre 0. . . 2n - 1. Os que estão na sequência de bits indicam quais elementos estão incluídos no subconjunto.

A convenção usual é que o último bit corresponde ao elemento 0, o segundo último bit corresponde ao elemento 1 e assim por diante. Por exemplo, a representação de bits de 25 é 11001, que corresponde ao subconjunto {0, 3, 4}.

Método 2Método 2O código a seguir passa pelos subconjuntos de um conjunto de n elementos:

O código a seguir mostra como podemos encontrar os elementos de um subconjunto que corresponde a uma sequência de bits. Ao processar cada subconjunto, o código cria um vetor que contém os elementos no subconjunto.

for (int b = 0; b < (1<<n); b++) { // process subset}

for (int b = 0; b < (1<<n); b++) { vector<int> subset; for (int i = 0; i < n; i++) { if (b&(1<<i)) subset.push_back(i); }}

Gerando PermutaçõesGerando PermutaçõesEm seguida, consideramos o problema de gerar todas as permutações de um conjunto de n elementos. Por exemplo, as permutações de {0, 1, 2} são (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0 , 1) e (2, 1, 0). Mais uma vez, existem duas abordagens: podemos usar a recursão ou passar pelas permutações iterativamente.

Método 1Método 1Como subconjuntos, permutações podem ser geradas usando recursão. A busca de função a seguir passa pelas permutações do conjunto {0, 1,. . . , n - 1}. A função cria uma permutação vetorial que contém a permutação e a pesquisa começa quando a função é chamada sem parâmetros.

Método 1Método 1

Cada chamada de função adiciona um novo elemento à permutação. A matriz escolhida indica quais elementos já estão incluídos na permutação. Se o tamanho da permutação for igual ao tamanho do conjunto, uma permutação foi gerada.

void search() {if (permutation.size() == n) {

// process permutation} else {

for (int i = 0; i < n; i++) {if (chosen[i]) continue;chosen[i] = true;permutation.push_back(i);search();chosen[i] = false;permutation.pop_back();

}}

}

Método 2Método 2Outro método para gerar permutações é começar com a permutação {0, 1,. . . , n - 1} e use repetidamente uma função que constrói a próxima permutação em ordem crescente. A biblioteca padrão C ++ contém a função next_permutation que pode ser usada para isso:

vector<int> permutation;for (int i = 0; i < n; i++) {

permutation.push_back(i);}do {

// process permutation} while (next_permutation(permutation.begin(),permutation.end()));

URI 1401URI 1401Gerar permutações sempre foi um problema importante na ciência da computação. Neste problema, você terá de gerar todas as permutações de uma dada string, em ordem lexicográfica crescente. Lembre-se que seu algoritmo deve ser eficiente.

Entrada:

A primeira linha da entrada contém um inteiro n, indicando o número de strings que seguem. As próximas n linhas contém uma string cada. Cada string conterá apenas caracteres alfanuméricos, e nunca conterá espaços. O tamanho máximo de uma string é 10.

URI 1401URI 1401Exemplo de Entrada Exemplo de Saída

3ababcbca

abba

abcacbbacbcacabcba

abcacbbacbcacabcba

URI 1401URI 1401#include <bits/stdc++.h>using namespace std;int main() {

int n;string line;scanf ("%d", &n);for (int t = 0; t < n; ++t){

cin >> line;sort(line.begin(), line.end());do {

printf("%s\n", line.c_str());} while (next_permutation(line.begin(), line.end()));printf("\n");

}return 0;

}

BacktrackingBacktrackingUm algoritmo de backtracking começa com uma solução vazia e amplia a solução passo a passo. A pesquisa recursivamente passa por todas as formas diferentes de como uma solução pode ser construída.

Como exemplo, considere o problema de calcular o número de maneiras em que as rainhas podem ser colocadas em um xadrez n × n para que nenhuma rainha se ataque. Por exemplo, quando n = 4, existem duas soluções possíveis: um algoritmo de backtracking começa com uma solução vazia e amplia a solução passo a passo. A pesquisa recursivamente passa por todas as formas diferentes de como uma solução pode ser construída.

BacktrackingBacktrackingComo exemplo, considere o problema de calcular o número de maneiras em que as rainhas podem ser colocadas em um xadrez n × n para que nenhuma rainha se ataque. Por exemplo, quando n = 4, existem duas soluções possíveis:

BacktrackingBacktrackingO problema pode ser resolvido usando backtracking colocando rainhas na linha da placa por linha. Mais precisamente, exatamente uma rainha será colocada em cada linha para que nenhuma rainha ataque qualquer das rainhas colocadas antes. Uma solução é encontrada quando todas as n rainhas foram colocadas na placa.

Por exemplo, quando n = 4, algumas soluções parciais geradas pelo algoritmo de backtracking são as seguintes:

BacktrackingBacktracking

BacktrackingBacktrackingNo nível inferior, as três primeiras configurações são ilegais, porque as rainhas se atacam. No entanto, a quarta configuração é válida e pode ser estendida para uma solução completa colocando mais duas rainhas na placa. Existe apenas uma maneira de colocar as duas rainhas restantes.

O algoritmo pode ser implementado da seguinte forma:

BacktrackingBacktracking

void search(int y){

if (y == n){

count++;return;

}for (int x = 0; x < n; x++){

if (column[x] || diag1[x+y] || diag2[x-y+n-1]) continue;column[x] = diag1[x+y] = diag2[x-y+n-1] = 1;search(y+1);column[x] = diag1[x+y] = diag2[x-y+n-1] = 0;

}}

BacktrackingBacktrackingA pesquisa começa com a busca por chamada (0). O tamanho do quadro é n, e o código calcula o número de soluções a contar.

O código assume que as linhas e as colunas da placa são numeradas de 0 a n - 1. Quando a busca da função é chamada com o parâmetro y, coloca uma rainha para fila y e então se chama com o parâmetro y + 1. Então, se y = n, uma solução foi encontrada e a contagem variável é aumentada em um.

BacktrackingBacktrackingA coluna da matriz acompanha as colunas que contêm uma rainha e as matrizes diag1 e diag2 acompanham as diagonais. Não é permitido adicionar outra rainha a uma coluna ou diagonal que já contém uma rainha. Por exemplo, as colunas e diagonais da placa 4 × 4 são numeradas da seguinte forma:

BacktrackingBacktrackingDeixe q(n) indicar o número de maneiras de colocar n rainhas em um xadrez n × n. O algoritmo de backtracking acima nos diz que, por exemplo, q (8) = 92. Quando n aumenta, a pesquisa rapidamente se torna lenta, porque o número de soluções aumenta exponencialmente. Por exemplo, calcular q (16) = 14772512 usando o algoritmo acima já leva cerca de um minuto em um computador moderno.

Observação: Não há nenhuma maneira conhecida de calcular com eficiência valores maiores de q(n). O valor atual é q (27) = 234907967154122528, calculada em 2016 [56].

URI 1682URI 1682As conexões entre Matemática e Biologia são complicadas. Na maioria das vezes, estas conexões não se dão por meio de ligações que alegremente se juntam à primeira vista, mas são abstratas e nem sempre facilmente estabelecidas.

O Lago Vostok - com cerca de 14 mil quilômetros quadrados de extensão, mais de 650 metros de profundidade e coberto por 3743 metros de gelo - foi descoberto recentemente no continente Antártico. O lago permanceu sob condições de alta pressão e desprovido de luz solar por milhares de anos. Acredita-se que a vida comum evoluiu para uma forma mais eficiente usando-se de um código genético composto unicamente por três bases (a Ciência atualmente diz haver quatro bases: adenina, citosina, guanina e timina). Até que nomes apropriados sejam encontrados, as três bases em questão serão identificadas por N, O e P.

URI 1682URI 1682Além disso, o genoma é de fita simples e dirigido, isto é, podemos percebê-lo como uma sequência do alfabeto {N,O,P}. A menos que apresente instabilidade, é necessário que o genoma seja uma sequência Thue, devido aos estudos do matemático norueguês A. Thue (1863 - 1922). Entenda por subsegmento de uma sequência, uma sequência a ser conectada, e entenda que dois subsegmentos são adjacentes, quando um é seguido imediatamente pelo outro em uma determinada sequência. Uma sequência-Thue é uma sequência onde nenhum subsegmento adjacente é igual. Por exemplo, NOPNO (é uma sequência-Thue) e NOPNPNO (não é uma sequência-Thue), logo o primeiro exemplo configura um genoma, enquanto o segundo, não.

Para sermos capazes de simular experiências com novos genomas, pedimos que você gere genomas de determinados comprimentos.

URI 1682URI 1682Entrada:

A entrada contém vários casos de testes. Cada caso de teste é composto por um inteiro n. Adimita que 1 ≤ n ≤ 5000. O último caso de teste deve ser zero, isto é, n = 0.

Saída:

Para cada caso de teste especificado por n imprima uma linha com qualquer genoma de comprimento n. Caso nenhum genoma de comprimento n exista, imprima uma linha em branco.

URI 1682URI 1682

Exemplo de Entrada Exemplo de Saída

1210200

NNONONPNOPNPONONPNOPNPONOPNONPNOP

URI 1682URI 1682#include <bits/stdc++.h>using namespace std;

char s[] = "NONPNOPNPONOPNONPNOPNPONON";

int main(){

int n = strlen(s);int m;

while (1){

scanf("%d", &m);if (!m) return 0;int i = 0 ;while (m--){

printf("%c", s[i]);i = (i + 1) % n;

}printf("\n");

}return 0;

}

Poder da BuscaPoder da BuscaMuitas vezes podemos otimizar backtracking podando a árvore de pesquisa. A ideia é adicionar "inteligência" ao algoritmo para que ele perceba o mais cedo possível se uma solução parcial não puder ser estendida a uma solução completa. Tais otimizações podem ter um tremendo efeito sobre a eficiência da pesquisa.

Consideremos o problema de calcular o número de caminhos em uma grade n × n do canto superior esquerdo para o canto inferior direito, de modo que o caminho visite cada quadrado exatamente uma vez. Por exemplo, em uma grade 7 × 7, existem 111712 caminhos desse tipo. Um dos caminhos é o seguinte:

Poder da BuscaPoder da Busca

Concentramo-nos no caso 7 × 7, porque o seu nível de dificuldade é adequado às nossas necessidades. Começamos com um algoritmo de retrocesso direto e, em seguida, otimizamos passo a passo usando observações de como a pesquisa pode ser podada. Após cada otimização, medimos o tempo de execução do algoritmo e o número de chamadas recursivas, para que vejamos claramente o efeito de cada otimização sobre a eficiência da pesquisa.

Algoritmo BásicoAlgoritmo BásicoA primeira versão do algoritmo não contém qualquer otimização. Nós simplesmente usamos backtracking para gerar todos os caminhos possíveis do canto superior esquerdo para o canto inferior direito e contamos o número desses caminhos.

tempo de execução: 483 segundos

número de chamadas recursivas: 76 bilhões

Otimização 1Otimização 1Em qualquer solução, primeiro movemos um passo para baixo ou para a direita. Há sempre dois caminhos que são simétricos sobre a diagonal da grade após o primeiro passo. Por exemplo, os seguintes caminhos são simétricos:

Otimização 1Otimização 1Por isso, podemos decidir que sempre movemos primeiro um passo para baixo (ou direita) e, finalmente, multiplicamos o número de soluções por dois.

tempo de execução: 244 segundos

número de chamadas recursivas: 38 bilhões

Otimização 2Otimização 2Se o caminho chegar ao quadrado inferior direito antes de ter visitado todos os outros quadrados da grade, fica claro que não será possível completar a solução. Um exemplo disso é o seguinte caminho:

Otimização 2Otimização 2Com esta observação, podemos encerrar a busca imediatamente se chegarmos ao quadrado inferior direito muito cedo.

tempo de execução: 119 segundos

número de chamadas recursivas: 20 bilhões

Otimização 3Otimização 3Se o caminho toca uma parede e pode girar à esquerda ou à direita, a grade se divide em duas partes que contêm quadrados não visitados. Por exemplo, na seguinte situação, o caminho pode girar à esquerda ou à direita:

Otimização 3Otimização 3Nesse caso, não podemos mais visitar todos os quadrados, para que possamos terminar a pesquisa. Essa otimização é muito útil:

tempo de execução: 1,8 segundos

número de chamadas recursivas: 221 milhões

Otimização 4Otimização 4A ideia de otimização 3 pode ser generalizada: se o caminho não pode continuar para a frente, mas pode girar para a esquerda ou para a direita, a grade se divide em duas partes que contêm quadrados não visitados. Por exemplo, considere o seguinte caminho:

Otimização 4Otimização 4É claro que não podemos mais visitar todos os quadrados, para que possamos terminar a pesquisa. Após esta otimização, a busca é muito eficiente:

tempo de execução: 0,6 segundos

número de chamadas recursivas: 69 milhões

OtimizaçãoOtimizaçãoAgora é um bom momento para parar de otimizar o algoritmo e ver o que conseguimos. O tempo de execução do algoritmo original foi de 483 segundos, e agora após as otimizações, o tempo de execução é de apenas 0,6 segundos. Assim, o algoritmo tornou-se quase 1000 vezes mais rápido após as otimizações.

Este é um fenômeno usual em backtracking, porque a árvore de pesquisa geralmente é grande e até observações simples podem efetivamente podar a pesquisa. Especialmente úteis são otimizações que ocorrem durante as primeiras etapas do algoritmo, isto é, na parte superior da árvore de pesquisa.

Conhecer no MeioConhecer no MeioConhecer no meio é uma técnica onde o espaço de busca é dividido em duas partes de tamanho igual. Uma pesquisa separada é realizada para ambas as partes e, finalmente, os resultados das pesquisas são combinados.

A técnica pode ser usada se houver uma maneira eficiente de combinar os resultados das pesquisas. Em tal situação, as duas pesquisas podem exigir menos tempo do que uma busca grande. Normalmente, podemos transformar um fator de 2n em um fator de 2n/2 usando a técnica de reunião na técnica do meio.

Conhecer no MeioConhecer no MeioComo exemplo, considere um problema em que nos é dada uma lista de n números e um número x, e queremos descobrir se é possível escolher alguns números da lista para que sua soma seja x. Por exemplo, dada a lista [2, 4, 5, 9] e x = 15, podemos escolher os números [2, 4, 9] para obter 2 + 4 + 9 = 15. No entanto, se x = 10 para o mesma lista, não é possível formar a soma.

Conhecer no MeioConhecer no MeioUm algoritmo simples para o problema é passar por todos os subconjuntos dos elementos e verificar se a soma de qualquer um dos subconjuntos é x. O tempo de execução de tal algoritmo é O (2n), porque existem 2n subconjuntos. No entanto, usando a reunião na técnica do meio, podemos conseguir um algoritmo de tempo O (2n/2) mais eficiente p. Note-se que O (2n) e O (2n/2) são complexidades diferentes porque 2n/2 é igual a .

OBSERVAÇÃOEssa ideia foi introduzida em 1974 por E. Horowitz e S. Sahni

√2n

Conhecer no MeioConhecer no MeioA ideia é dividir a lista em duas listas A e B, de modo que ambas as listas contenham cerca de metade dos números. A primeira pesquisa gera todos os subconjuntos de A e armazena suas somas para uma lista S

A. Correspondentemente, a segunda pesquisa

cria uma lista SB de B. Depois disso, basta verificar se

é possível escolher um elemento de SA e outro

elemento de SB, de modo que sua soma seja x. Isso é

possível exatamente quando há uma maneira de formar a soma x usando os números da lista original.

Conhecer no MeioConhecer no MeioPor exemplo, suponha que a lista seja [2, 4, 5, 9] e x = 15. Primeiro, dividimos a lista em A = [2, 4] e B = [5, 9]. Depois disso, criamos listas S

A = [0, 2, 4, 6] e S

B =

[0, 5, 9, 14]. Neste caso, a soma x = 15 é possível, uma vez que S

A contém a soma 6, S

B contém a soma 9 e 6 +

9 = 15. Isso corresponde à solução [2, 4, 9].

A complexidade do tempo do algoritmo é O (2n/2), porque ambas as listas A e B contêm cerca de n/2 números e leva O (2n/2) tempo para calcular as somas de seus subconjuntos para listas S

A e S

B. Depois disso,

é possível verificar o tempo O (2n/2) se a soma x pode ser criada a partir de S

A e S

B.

ExercícioExercícioUVa 154UVa 441UVa 639UVa 725UVa 10360UVa 10662UVa 11242UVa 11804UVa 193UVa 222UVa 524UVa 624UVa 628UVa 729UVa 750UVa 10496LiveArchive 4793

Você pode fazer eles nocodepit.ioCIC 110 5

senha: unifei

Você pode fazer eles nocodepit.ioCIC 110 5

senha: unifei