Please enable JavaScript.
Coggle requires JavaScript to display documents.
Coping with the Limitations of Algorithm Power - Coggle Diagram
Coping with the Limitations of Algorithm Power
Backtracking
Construir soluções (sendo um componente por vez) e avaliar.
Caso a solução parcial não viole as restrições do problema, pegar a primeira solução legítima que resta para o próximo componente.
Caso não tenha opção legítima para o próximo componente, não precisa considerar nenhum dos componentes restantes
State-space tree
O estado inicial é raiz, as escolhas para o primeiro componente são os nós e assim por diante
É construída como DFS
Soma do subconjunto
n-Queens Problem
Circuito hamiltoniano
Eficiência
Não é eficiente, já que pode ter que
passar por todas as possibilidades possíveis.
Branch-and-Bound
Uma maneira de oferecer, para 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.
Pode-se comparar o limite do valor de um nó ao valor da melhor solução atual. Caso o valor do primeiro nó não seja melhor que o limite, pode-se ignorar essa solução.
Problemas
Knapsack Problem
Traveling Salesman Problem
Encontra um limite: para cada cidade acha a
soma das distâncias dessa para as duas cidades mais próximas.
Computa a soma desses n
números, divide por 2. Assim, o limite é o teto da divisão
Assignment Problem
Atribue n pessoas pra n trabalhos.