ELC1014 - Inteligência Artificial
Primeiro Semestre de 2011
Professora: Juliana Kaizer Vizzotto
Carga horária: 60h
Horários: Terças-feiras, das 8:30 às 10:30, e quintas-feiras, das 8:30 às 10:30
Sala: 368
Definindo sua própria heurística para o 8-puzzle
** Descrição do Trabalho **
- Você já implementou um programa para o jogo 8-puzzle usando duas heurísticas: h1 e h2 (Manhattan distance). Para esse trabalho você deve usar o seu código e o material da última aula (slides disponíveis no site da disciplina) sobre definição de heurísticas e definir sua própria heurística para o jogo 8-puzzle. Você deve tentar que a sua própria heurística tenha uma performance média melhor que a distância de Manhattan (i.e. menos nodos expandidos). A sua heurística não precisa ser melhor em todos os testes de caso. Você deve tentar com diferentes estados inciais e estados de objetivo. Explique porque sua heurística é admissível? Sua heurística é monotônica, por quê?
** Dicas **
- Tente implementar alguma heurística mais interessante ou mais inteligente que o número de tijolos fora do lugar
- Você é encorajado a projetar sua própria heurística - você pode criar alguma do zero ou também alguma variação de uma heurística já existente. Você pode pesquisar algumas heurísticas conhecidas também.
- Você deve fazer uma apresentação sobre a sua heurística. Ela deve conter: um nome, uma explicação da heurística (se ela é completamente original, uma variação de alguma heurística conhecida, ou alguma heurística conhecida diferente), uma breve explicação do código, os testes que você fez e se sua heurística é admissível e monotônica.
- Exemplos de algumas outras heurísticas são:
- Escore da Sequência de Nilson: h(n) = P(n) + 3 S(n). Onde P(n) é a distância de Manhattan de cada tijolo até a sua própria posição. A quantidade S(n) é um escore de sequência, obtido verificando nos tijolos na volta da posição central, adicionando dois para cada tijolo não seguido pelo seu próprio sucessor e 0 para todos os outros tijolos, exceto para o tijolo do centro que vale 1. (Não admissível)
- X-Y: decomponha o problema em dois problemas de uma dimensão, tal que o espaço em branco pode trocar com qualquer tijolo em uma linha/coluna adjacente. Adicione o número de passos dos dois subproblemas.
- n-MaxSwap: assuma que você pode trocar qualquer tijolo com o espaço em branco. Use o número de passos que leva para resolver este problema como valor da heurística.
- n-swap: represente o espaço em branco como um tijolo e assuma que você pode trocar qualquer dois tijolos. Use o número de passos que leva para resolver esse problemas como o valor da heurística.
Página criada em: Seg Mar 23 15:50:18 BRT 2011. Última atualização em: Tue May 24 00:07:50 2011. Autoria: Juliana Kaizer Vizzotto.