Inteligencia Artificial

ATPS: ( Etapa 1 )

Passo 1

Grafos e suas Aplicações

Definição:

“Um grafo é um conjunto de pontos, chamados vértices, conectados por linhas, chamadas de arestas” [Wikipedia 2008], é uma abstração que permite codificar relacionamentos entre pares de objetos. Então um grafo é uma representação de um conjunto no qual cada um de seus elementos estabelece conexões com um ou mais elementos contidos nesse conjunto., é usado também como estruturas de dados para a programação de computadores.

Representação de Grafos

Um grafo pode ser representado de diversas maneiras. Apresentaremos as

três maneiras mais utilizadas:

1-Matriz de adjacência;

2-Lista de Adjacência;

3- Matriz de incidência.

1) Matriz de Adjacência

Seja G=(V,E) um grafo com n vértices. A matriz de adjacência para G é uma matriz

bidimensional nxn, que denotaremos por A, onde A(i,j)=1 se a aresta (i,j) está presente

em G.

2) Lista de Adjacência

Nesta representação, a linha i da matriz contém os vértices adjacentes ao vértice i.

Cada vértice i tem uma variável d[i] que guarda o grau do vértice i.

3) Matriz de Incidência

Seja G=(V,E) um grafo com n vértices e m arestas. A matriz de incidência para G é

uma matriz bidimensional nxm, que denotaremos por A, onde A(i,j)=1 se a aresta j

incide no vértice i em G.

Passo 2

Relatório do Agente de Resolução de Problemas

Objetivo: Desenvolver um programa capaz de definir para o viajante um caminho mais rápido em seu deslocamento de Arad à Bucharest.

Problema: Se deslocar de Arad até Bucharest através do melhor caminho usando as estradas descritas na ATPS.

Estado Inicial: Arad.

Estado Final: Bucharest.

Ações: Ir (Cidade1, Cidade2).

Espaço de Estados:

Rota 1: Arad, Timisoara, Lugoj, Mehadia, Giurgia, Bucharest.

Rota 2: Arad, Sibiu, Fagaras, Bucharest.

Rota 3: Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest.

Rota 4: Arad, Zerind, Oradea, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest.

Rota 5: Arad, Zerind, Oradea, Sibiu, Fagaras, Bucharest.

Custo dos caminhos:

Rota 1: Arad – 118, Timisoara –

111, Lugoj – 70, Mehadia – 200, Giurgia – 90, Bucharest = 589.

Rota 2: Arad – 140, Sibiu – 90, Fagaras – 211, Bucharest = 441.

Rota 3: Arad – 140, Sibiu – 80, Rimnicu Vilcea – 97, Pitesti – 101, Bucharest = 418.

Rota 4: Arad – 75, Zerind – 71, Oradea – 151, Sibiu – 80, Rimnicu Vilcea – 97, Pitesti – 101, Bucharest = 575.

Rota 5: Arad – 75, Zerind – 71, Oradea – 151, Sibiu – 90, Fagaras – 211, Bucharest = 598.

Teste do estado objetivo: estado_atual = Bucharest?

Caminho: O mais curto: Arad – 140, Sibiu – 80, Rimnicu Vilcea – 97, Pitesti – 101, Bucharest = 418.

Passo 3

Função Heurística

O programa foi elaborado com o objetivo de ajudar ao viajante a sair da Cidade de Arad e chegar até a Cidade de Bucharest utilizando a rota mais curta possível (sendo 5 rotas possíveis), passando por várias cidades no caminho.

No final aparecerá qual é a rota mais curta da Cidade de Arad até a Cidade de Bucharest.

Passo 4

Código fonte

Todo o código do sistema encontra-se na linguagem C# e foi desenvolvido seguindo o paradigma de Orientação a Objetos.

Classe Cidade

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ATPS_IA

{

class Cidade

{

private string nome;

private List vizinhos;

public Cidade()

{

vizinhos = new List();

}

public Cidade(string nome)

{

this.Nome = nome;

vizinhos = new List();

}

public string Nome

{

get { return nome; }

set { nome = value; }

}

public void addVizinho(Vizinho vizinho)

{

vizinhos.Add(vizinho);

}

public Vizinho getVizinho(int indice)

{

return vizinhos[indice];

}

public