Please enable JavaScript.
Coggle requires JavaScript to display documents.
Olavo Rangel da Conceição - MM 15 - Coggle Diagram
Olavo Rangel da Conceição - MM 15
Backtracking
Entrada Grande
Resolver
Problemas Intratáveis
Melhor do que Busca Exaustiva
No pior caso é Intratavel
Baseado em State-Space trees
State-Space Exploration
Depht-First
Problemas
n-Queens Problem
Conceito
Colocar n Rainhas em uma mesa de xadrez NxN de forma que duas rainhas não podem se atacar
Passo-a-Passo
Atribua uma linha(ou coluna) para cada rainha
Comece com o tabuleiro vázio
Tentar Colocar as Rainhas(uma por uma) nas primeiras posições possiveis
Se não for possivel tentar colocar numa posição diferente da anterior
Se possível solução encontrada, pode parar :D
Solução Trivial
N = 1
Não a solução
N = 2 ou N = 3
Encontrar Circuito Hamiltiano
Escolher
Vértice Arbitrário
Passar para os próximos até achar o primeiro
Não sendo possível tente o próximo vértice
Problema das Somas dos Conjuntos
Vamos supor que temos um Conjunto A
Positivo
Inteiro
Achar um A` contido no A
Tal que
A soma dos Elementos de A`
é igual a D pertecendo aos Naturais
Ordenar Elementos
Ordem Crescente
Outras Aplicações
Graph Colouring
Knight´s Tour
Resumindo
Tempo de Eficiência
Depende do Problema
Depende da Instancia
Otimizações
Explorar
Simetria
Problemas Combinatórios
Reorganizar Dados
Dependendo da Instância
Branch and Bound
Problema de Otimização
Minimizar
Maximizar
ou
Algum objetivo da Função
Solução Viavel
Satisfaz todas restrições
Ideal
Viabilizar o melhor valor da função objetivo
Cada Nó da state-space-tree
Limite
No melhor valor da função objetivo
O valor da melhor solução até agora
Best-First
Nó
Limite Inferior a Melhor Solução
Pruned
Não é a melhor opção
outras
AI: outras heuristicas
Problemas
Problema de Atribuição
Conceito
Atribuir para n pessoas, n trabalhos de forma que o custo total das atribuições sejam a menor possivel
Limite Inferior
Soma dos Menores Elementos em cada Linha
Algoritmo Polinomial(deterministico)
Hungarian Method
Problema do Caixeiro Viajante
Conceito
Achar o menor circuito hamiltoniano no grafo
Limite Inferior
Para cada cidade 1<=1 <=n
Achar a soma das distâncias de duas cidades vizinhas
Computar S = S1 + S2 + .... Sn
Computar o valor absoluto de S/2
Ajustar
Considerando as arestas selecionadas
Simplificações
Considerar apenas excursões que começam de um nó arbitrário
Depois de visitar n-1 cidades
Visitar o restante
Voltar para o ponto de partida
Grafo unidirecionado
Ignorar excursões simetricas
Desafio
Definir
Limite Inferior
Limite Superior
Precisa
Ser fácil de computar
Não pode ser muito simples