Please enable JavaScript.
Coggle requires JavaScript to display documents.
423-440 Lidando com as limitações de poder Algorítmicas - Coggle Diagram
423-440 Lidando com as limitações de poder Algorítmicas
Backtracking
A ideia principal é construir soluções com um componente por vez e avaliar os candidatos à participar da solução checando se eles não tem algo contra as restrições do problema caso não tenham o algoritmo busca a primeira legitima opção como próximo componente e move-se para ele caso essa próxima opção não tenha nenhum caminho válido se retorna para o ultimo estado valido e checa-se o proximo válido possivel.
Arvore espacial de estados
Raiz representa um estado inicial antes da busca por solução
Os nodos do primeiro nivel na arvore representam as escolhas feitas para o primeiro componente da solução, os nodos do segundo nivel são o mesmo em relação ao primeiro componente e assim por diante
Problema das n-Rainhas
colocar n rainhas em um tabuleiro nxn onde 2 rainhas não consigam atacar umas as outras estando na mesma linhas,diagonal ou coluna
Problema do Circuito Hamiltoniano
Problema do Subconjunto-Soma
Achar um subconjunto de dado um conjunto A com n elemento inteiros e positivos no qual a soma é igual a um dado inteiro
branch and bound
Aplicado somente a problemas de otimização
Ordem de geração da árvore é feita normalmente por melhor primeiro
Adicional que difere em relação ao backtracking
Para cada nó se tem um limite (bound) para o melhor valor da função objetivo (considerando os descendentes deste nó)
Conhecer a melhor solução até um dado momento
Expande a partir do melhor limite possível
Se um nó possui um limite pior do que a melhor solução atual, ele é ignorado (pruned / podado)
Problema da atribuição de tarefas
Atribuir n pessoas a n tarefas minimizando o custo de execução
Problema da mochila
Encontrar o subconjunto de itens mais valioso que cabe na mochila
Problema do caixeiro viajante
Encontrar o menor circuito Hamiltoniano para um grafo G