Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lidando com as limitações dos algoritmos - Coggle Diagram
Lidando com as limitações dos algoritmos
Maneiras de lidar com problemas que são difíceis de serem resolvidos algoritmicamente
Backtracking e Branch-and-bound
Baseadas na construção de uma
árvore de estado de espaço
Os nós da árvore simbolizam escolhas feitas em busca de um componente da solução
Concluem um nó quando não é mais possível obter uma solução para o problema a partir de escolhas que correspondam aos descendentes do nó
Branch-and-bound
Aplicável apenas para problemas de otimização
Backtracking
É mais comumente usada para problemas que não são de otimização
Variação da busca exaustiva
Construir um componente da solução por vez e os avaliar
Se a solução parcial construída pode ser desenvolvida sem desobedecer às restrições do problema, isso é feito utilizando a primeira opção restante como próximo componente
Se não houver uma opção para o próximo componente, nenhuma alternativa para nenhum componente restante precisa ser considerada
O algoritmo retrocede para substituir o último componente da solução parcial com a próxima opção
Construir uma árvore com as decisões feitas
Árvore de estado de espaço
A
raiz
representa o estado antes do início da busca por uma solução
Os nós no primeiro nível representam as escolhas feitas para o primeiro componente de uma solução e assim segue
Um nó é
promissor
se ele representa uma solução parcial que pode levar a uma solução total
Caso contrário, ele não é promissor
Folhas
representam ou finais não-promissores ou soluções completas
Similar ao DFS
Problema das
n-rainhas
Colocar n rainhas em um tabuleiro \(n \times n\) de forma que as rainhas não possam se atacar duas a duas
Considerando o problema com 4 rainhas
Cada rainha deve ser colocada em uma linha, além de que cada rainha terá sua própria coluna
Cada solução para \(n \ge 4\) pode ser achada em tempo linear
Problema do circuito Hamiltoniano
Se um circuito existe, então ele começa em um vértice \(a\)
\(a\) será a raiz da árvore de estado de espaço
O primeiro componente da solução será um primeiro vértice intermediário de um circuito hamiltoniano
Se o algoritmo encontrar um ponto sem saída que ainda não é uma solução, ele retrocede
Problema da soma de subconjuntos
Achar um subconjunto de um dado conjunto \(A\) com \(n\) inteiros positivos cuja soma é igual a um dado inteiro \(d\)
Ordenar os elementos do conjunto em ordem crescente
A árvore de estado de espaço pode ser feita como uma árvore binária
O filho direito representa a inclusão do próximo elemento do conjunto no subconjunto procurado
O filho esquerdo representa a exclusão do próximo elemento do conjunto no subconjunto procurado
Geralmente, o resultado de um algoritmo de backtracking é uma n-upla em que cada coordenada é um elemento de um conjunto finito linearmente ordenado
Não é, necessariamente, eficiente
Branch-and-bound
Dois itens adicionais em relação ao backtracking
Uma maneira de limitar uma função ao seu melhor valor para cada nó da árvore que pode vir a ser uma solução
O valor da melhor solução encontrada até o momento
É possível comparar o valor limite de um nó com o valor da melhor solução encontrada até o momento
Se o valor do limite não for melhor que o da melhor solução, então o nó não é promissor
No geral, existem 3 razões para um nó de uma árvore
O valor do limite não é melhor que o da melhor solução encontrada
O nó não representa uma solução possível, pois as restrições do problema foram violadas
O subconjunto de soluções possíveis representado pelo nó consiste de apenas um ponto
Não é possível mais fazer outras escolhas
Problema da atribuição
Atribuir n trabalhos para n pessoas de forma que o custo total das atribuições é o menor possível
Matriz \(n \times n\)
Selecionar um elemento em cada linha de forma que quaisquer dois elementos selecionados não estejam na mesma coluna e que a soma seja a menor possível
Gerar todos os filhos do nó mais promissor dentre as folhas não concluídas da árvore
Comparar os limites inferiores dessas folhas para saber qual o nó mais promissor
Branch-and-bound
de melhor início
Problema da mochila
Dados \(n\) itens de pesos\(w_i\) e valores \(v_i\), com \(i=1, 2, ..., n\), e uma mochila com capacidade \(W\), achar o subconjunto com valor mais alto que cabe na mochila
Ordenar os itens em ordem decrescente das razões entre os valores e os pesos
Na árvore, o filho à esquerda indica a inclusão do próximo item
O filho à direita indica a exclusão do próximo item
Problema do vendedor viajante
Limite inferior para o tamanho das viagens