MC 906 – Inteligência Artificial Seminário Resolvendo o problema das N-Rainhas Vitor Salvucci Ricci RA: 083052 1º semestre de 2.011 Universidade Estadual de Campinas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Roteiro Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Roteiro Apresentação do problema Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Roteiro Apresentação do problema Táticas para a resolução Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Roteiro Apresentação do problema Táticas para a resolução Software Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Apresentação do problema Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Enunciado Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Enunciado O problema consiste em dispor N rainhas em um tabuleiro N x N, de tal modo que nenhuma rainha ataque outra, seguindo as regras do xadrez. Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Enunciado O problema consiste em dispor N rainhas em um tabuleiro N x N, de tal modo que nenhuma rainha ataque outra, seguindo as regras do xadrez. Um exemplo de solução para N=5 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas História Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas História Século XIX : primeiros relatos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas História Século XIX : primeiros relatos Proposto por um jogador de xadrez e estudado por vários matemáticos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas História Século XIX : primeiros relatos Proposto por um jogador de xadrez e estudado por vários matemáticos Gauss dedicou-se ao problema das 8-rainhas Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Características Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Características Quebra - cabeça Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Características Quebra - cabeça Não há adversários Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Características Quebra - cabeça Não há adversários Problemas semelhantes Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Características Quebra - cabeça Não há adversários Problemas semelhantes Torres de Hanói Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Características Quebra - cabeça Não há adversários Problemas semelhantes Torres de Hanói Cobertura total Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Características Quebra - cabeça Não há adversários Problemas semelhantes Torres de Hanói Cobertura total Combinações com outras peças Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Codificação Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Codificação Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Codificação A solução pode ser representada por: S=[1,3,5,2,4] Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Equivalência entre soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Número de soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Número de soluções N 1 2 3 4 5 6 7 8 Soluções 1 0 0 2 10 4 40 92 Vitor Salvucci Ricci Soluções Independentes 1 0 0 1 2 1 6 12 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Número de soluções N 1 2 3 4 5 6 7 8 Soluções 1 0 0 2 10 4 40 92 Vitor Salvucci Ricci Soluções Independentes 1 0 0 1 2 1 6 12 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Número de soluções N 1 2 3 4 5 6 7 8 Soluções 1 0 0 2 10 4 40 92 Vitor Salvucci Ricci Soluções Independentes 1 0 0 1 2 1 6 12 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Número de soluções Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Número de soluções N 9 10 . . . 25 26 Soluções 352 724 . . . 2.207.893.435.808.352 22.317.699.616.364.044 Vitor Salvucci Ricci Soluções Independentes 46 92 . . . 275.986.683.743.433 2.789.712.466.510.289 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Soluções Número de soluções N 9 10 . . . 25 26 Soluções 352 724 . . . 2.207.893.435.808.352 22.317.699.616.364.044 Vitor Salvucci Ricci Soluções Independentes 46 92 . . . 275.986.683.743.433 2.789.712.466.510.289 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Por que é um problema de I.A.? Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Por que é um problema de I.A.? Podemos identificar no problema: Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Por que é um problema de I.A.? Podemos identificar no problema: Agente racional Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Por que é um problema de I.A.? Podemos identificar no problema: Agente racional Espaço de estados Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Por que é um problema de I.A.? Podemos identificar no problema: Agente racional Espaço de estados Objetivo Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Táticas para a resolução Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Táticas escolhidas Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Táticas escolhidas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Táticas escolhidas Força bruta Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Táticas escolhidas Força bruta Busca local Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Táticas escolhidas Força bruta Busca local Satisfação de restrições Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Busca pela solução de forma recursiva Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Busca pela solução de forma recursiva O tabuleiro inicialmente está vazio Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Busca pela solução de forma recursiva O tabuleiro inicialmente está vazio Rainhas são colocadas uma – a – uma Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Sempre vai encontrar uma solução Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Sempre vai encontrar uma solução E o tempo? Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Sempre vai encontrar uma solução E o tempo? Passa por muitos estados Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Força bruta Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local O caminho é irrelevante Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local O caminho é irrelevante A configuração final é o que importa Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Formulação de estados completos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Formulação de estados completos Estado Atual Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Formulação de estados completos Estado Atual Vitor Salvucci Ricci Estado Vizinho Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Formulação de estados completos Estado Atual Estado Vizinho Objetivo: N rainhas no tabuleiro e não há ataques entre elas Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Função de custo da heurística (h) : número de ataques entre rainhas no tabuleiro Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Função de custo da heurística (h) : número de ataques entre rainhas no tabuleiro Objetivo: atingir um estado X tal que h(X) = 0 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 8 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 8 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 6 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 8 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 6 8 6 8 8 8 Vitor Salvucci Ricci 10 4 8 4 12 4 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 4 4 4 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 4 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 6 4 2 6 4 4 Vitor Salvucci Ricci 10 8 4 8 4 8 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local 2 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Usa pouca memória Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Usa pouca memória Frequentemente encontra soluções razoáveis em grades espaços de estados Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Problema : mínimos locais Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Busca local Problema : mínimos locais Tentativa de solução : Hill – climbing com reinício aleatório Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Método construtivo Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Método construtivo Minimum Remaining Values (MRV) Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Método construtivo Minimum Remaining Values (MRV) Least Constraining Value (LCV) Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 12 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 12 12 12 12 12 12 14 14 14 12 12 14 14 12 12 14 14 14 12 12 12 12 12 12 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 12 12 12 12 12 12 14 14 14 12 12 14 16 14 12 12 14 14 14 12 12 12 12 12 12 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 12 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 7 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 7 7 6 9 7 6 Vitor Salvucci Ricci 6 7 9 6 7 7 Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 6 6 6 6 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 6 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 0 0 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições 0 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Busca local para satisfação de restrições Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Busca local para satisfação de restrições Formulação de estados completos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Busca local para satisfação de restrições Formulação de estados completos O que importa é a configuração final Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Função de custo da heurística (h) : número de ataques de uma rainha Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Função de custo da heurística (h) : número de ataques de uma rainha Objetivo: atingir um estado X tal que h(X) = 0 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 2 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 2 2 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 2 2 1 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 2 2 1 2 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 0 2 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 0 2 2 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 0 2 2 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 0 2 2 3 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 2 1 2 1 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos 2 1 3 0 Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Conflitos mínimos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Software Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Primeiro protótipo Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Primeiro protótipo Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Primeiro protótipo Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Primeiro protótipo N Força Bruta 8 10 20 30 40 17 s Busca Local Mínimo de Máximo de tentativas tentativas 1 22 Conflitos Mínimos Mínimo de Máximo de tentativas tentativas 3 76 1 77 29 475 2 130 2 segundos 115 14 segundos 167 1 min 18 s 204 47.000 7 segundos 20 2 segundos 32 15 s Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Próximos protótipos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Próximos protótipos Reestruturação das classes Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Próximos protótipos Reestruturação das classes Otimizar as funções utilizadas Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Próximos protótipos Reestruturação das classes Otimizar as funções utilizadas Melhorar a interface Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Futuramente... Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Futuramente... Permitir a combinação de algoritmos Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Futuramente... Permitir a combinação de algoritmos Implementar o jogo Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Futuramente... Permitir a combinação de algoritmos Implementar o jogo Evoluir para o problema das N2 - rainhas Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas Apresentação do Problema Táticas para a resolução Software Seminário Resolvendo o problema das N-rainhas Referências [1] Material de aula disponibilizado pelo Professor Anderson Rocha no site da disciplina [2] Russell, Stuart & Norvig, Peter – Artificial Intelligence, 2ª edição, Pearson Education Vitor Salvucci Ricci Resolvendo o problema das N-Rainhas
Download
