BUsca Cega E Heuristica

Resumo

Este relatório indroduzirá alguns conceitos de Inteligência Artificial (IA) e mostrará a diferença na solução de problemas desta utilizando-se dois diferentes métodos de resolução, sendo eles a Busca cega e heurística e a Busca Ótima.

1. Introdução

Da definição de Winston, “Inteligência Artificial é o estudo das computações” que tornam possível perceber, raciocinar e agir.”

Dentre um dos usos de IA está: saber representar o conhecimento e utilizar métodos que o manipule, entende-se por isso o estudo de diferentes maneiras pelas quais a informação é armazenada e manipulada na memória humana e como IA pode utilizar tais modos de armazenamento.

Em toda representação do conhecimento é desejavel:

- Expressividade;

- Auto-consistência;

- Robustez;

- Capacidade de ser completa;

- Tratabilidade;

- Ausência de ambigüidade

Assim, um dos melhores métodos para representação de como o conhecimento é armazenado em nossa memória é através de Redes Semânticas, as quais descrevem relações entre objetos e propriedades, e são compostas por:

- Nós: cada um representa um objeto ou uma propriedade

de um objeto;

- “Links”: Cada um representa a relação entre dois objetos.

Um exemplo simples de Rede Semântica seria sobre animais, descritos pelo que se é conhecido deles por:

- Animais comem;

-Mamíferos e pássaros são animais;

-Mamíferos têm pelo;

- Cachorros são mamíferos.

Um exemplo simples de Rede Semântica referente ao exemplo seria dado na figura 1:

Figura 1 - Rede Semântica simples

 

2. Métodos e Discussões

Após a utilização das redes semânticas representando o conhecimento e, muitas vezes, modelando problemas, foram desenvolvidos métodos para que estes problemas pudessem ser resolvidos.

Estes métodos, baseiam-se na busca da solução para o problema proposto através do uso da Rede Semântica.

No problema dado em laboratório, foram utilizadas as estratégias de busca: Métodos de Busca cega e heurística e a Busca Ótima.

Métodos de Busca cega são caracterizados por uma busca sistemática sem orientação da melhor maneira de realizá-la e estes métodos são:

1) Busca em Profundidade (Depth-first search), a qual parte do princípio de que todos os caminhos têm importâncias idênticas.

2) Busca em Amplitude (Breath-first search), onde considera todas as opções em um mesmo nível hierárquico antes de mudar de nível.

Métodos de Busca Heuristicamente informados são buscas sistemáticas onde as opções a serem exploradas são ordenadas, investigando-se inicialmente caminhos mais promissores. Dentre estes, pode-se destacar o Método Subida de encosta (Hill-Climbing), o qual é semelhante ao método de busca em profundidade, exceto no detalhe de ordenamento das escolhas do caminho de busca, no qual considera-se alguma medida heurística de distância ao objeto e as menores distâncias guiam a busca.

Por fim, tem-se as outras quatro métodos de busca que foram utilizados, que são:

• Busca em Feixe (beam search), semelhante a busca em amplitude porém quando em um nível o método só considera os w melhores nós em cada nível para prosseguir.

• Busca pela Melhor Escolha (best-first search), combina as vantagens das buscas em profundidade e em amplitude.

• Busca Ótima, onde foram implementados os métodos branch-and-bound e Pesquisa A*, baseados em programação dinâmica, na qual o melhor caminho através de um caminho específico entre dois lugares é o melhor caminho para o objetivo do lugar onde se inicia, seguido pelo melhor caminho de onde se está para o objetivo.

O problema a ser resolvido em laboratório era o de criar uma rede semântica que estabelecesse um sistema de comunicação entre 15 cidades, sendo elas: Rio de Janeiro, São Paulo, Belo Horizonte, Porto Alegre, Curitiba, Brasília, Cuiabá, Manaus, Fortaleza, Salvador, Recife, Natal, Chicago, Tóquio e Madri, com a limitação de que cada cidade só poderia se comunicar com duas outras, exceto Rio de Janeiro que poderia se comunicar com quatro.

A solução do problema foi implementada na linguagem Lisp, utilizando-se de um programa feito por ex-alunos da Escola de Engenharia de São Carlos (EESC-USP). Para tanto, deveríamos alterar alguns arquivos do programa padrão, baixado e instalado em cada máquina do laboratório, adaptando assim os arquivos padrões para o problema em questão.

3. Resultados

Primeiramente, na implementação para a solução de Busca Cega e Heuristica, o arquivo padrão a ser alterado era o “cidades.lsp”, dado abaixo:

;;;; -*- mode:Lisp; syntax:Common-Lisp; package:user -*- ;;;;

;;;; Copyright 1992 Patrick H. Winston. All rights reserved.

;;;; Version 1.1.1, copied from master file on 23 Apr 93

;;;;

;;;; This software is licensed by Patrick H. Winston (licensor) for

;;;; instructional use with the textbooks ``Artificial Intelligence,'' by

;;;; Patrick H. Winston, and ``Lisp,'' by Patrick H. Winston and Berthold

;;;; K. P. Horn. Your are free to make copies of this software and

;;;; modify it for such instructional use as long as:

;;;; 1. You keep this notice intact.

;;;; 2. You cause any modified files to carry a prominent notice stating

;;;;