Please enable JavaScript.
Coggle requires JavaScript to display documents.
Técnicas de Design de Algoritmos - Coggle Diagram
Técnicas de Design de Algoritmos
Backtracking
Construir soluções, um componente por vez, e avaliar. Se a solução parcial não violar as restrições do problema, pegar a primeira solução legítima que resta para o próximo componente. Se não tem opção legítima pro próximo componente, não precisa considerar nenhum dos componentes restantes
State-space tree: raiz é o estado inicial, primeiros nós são as escolhas pro primeiro componente e assim vai
Construída como DFS
Problemas
n-Queens Problem
Colocar n rainhas num tabuleiro n x n, sem que duas rainhas possam se atacar estando na mesma linha, coluna ou diagonal
Circuito Hamiltoniano
Assume que existe resposta com raiz da state-space tree sendo um vértice aleatório
Soma do subconjunto
Achar um subconjunto de um conjunto de inteiros em que a soma seja igual a x
Não é um algoritmo eficiente, pode ter que passar por todas as possibilidades possíveis
Geralmente aplicado a problemas difíceis de combinatória
Branch-and-Bound
Um jeito de oferecer, pra cada nó da state-space tree, um limite no melhor valor do objetivo, que qualquer solução pode ser obtida adicionando componentes ao já encontrado
O valor da melhor solução atual
Podemos comparar o limite do valor de um nó com o valor da melhor solução atual, se o valor do primeiro nó não for melhor que o limite, podemos ignorar essa solução
Problemas
Assignment Problem
Atribuir n pessoas pra n trabalhos, de forma que o custo da atribuição seja o menor possível
Best-first branch-and-bound
Knapsack Problem
Dado n itens de peso w, valores de 1 até n, e uma mochila de capacidade W, qual o subconjunto mais valioso de itens que cabem na mochila
Traveling Salesman Problem
Achar um limite: para cada cidade achar a soma das distâncias dessa pras duas cidades mais próximas. Computar a soma desses n números, dividir por 2, o limite é o teto dessa divisão