Inteligência Artificial - Atividade Prática

Inteligência Artificial - Atividade Prática

Descreva os termos a seguir em termos de seus elementos.

1. Problema do caixeiro viajante.

Um caixeiro viajante tem de viajar por “n” cidades diferentes, iniciando e encerrando sua viajem na primeira cidade, não importando a ordem que elas são visitadas e de cada uma delas, pode-se ir diretamente a qualquer outra.

Cidades: A, B, C, D.

Estado Inicial: Caixeiro viajante posicionado na cidade A e o conjunto de rotas possíveis que ele pode escolher.

Operadores: sair da cidade A e ir até uma cidade de sua escolha (B, C ou D), ir para outra cidade (diferente da anterior), novamente ir para outra cidade (diferente das anteriores) e voltar para cidade A.

Espaço de Estado: conjunto de “n” caminhos que o caixeiro pode escolher, saindo da cidade A, percorrendo todas as cidades e encerrando a viajem na cidade que iniciou.

Estado de Término: Ter percorrido todas as cidades uma única vez, retornando para cidade que iniciou.

Custo do Caminho:

(A, B) = 1c; (A, C) = 2c; (B, C) = 1c; (C, D) = 3c; (A, D) = 3c.

1. Problema da Mochila.

Problema em que é necessário preencher uma mochila que possui uma capacidade “x” com “n” objetos de diferentes pesos. O objetivo é que se preencha a mochila com o maior valor possível (soma dos pesos dos objetos), não ultrapassando a capacidade máxima da mochila.

Estado Inicial: Mochila com a capacidade disponível totalmente e um conjunto de objetos com seus respectivos pesos e um valor associado.

Operadores: Formar conjuntos possíveis de objetos, de modo que o valor total desse conjunto não ultrapasse a capacidade da mochila. O conjunto com maior valor e que caiba na mochila, será colocado dentro da mesma.

Espaço de Estado: conjunto de itens com valor mais aproximado possível à capacidade da mochila.

Estado de Término: conjunto de objetos alocados dentro da mochila, com o máximo de valor carregado, sem exceder a capacidade da mochila.

Custo do Caminho: Valor do conjunto igual à que a capacidade da mochila = 5c; Valor do conjunto menor que a capacidade da mochila = 10c; Valor do conjunto maior que a capacidade da mochila = 20c.

1. Problema da Detecção de Loops em redes de computadores.

Estado Inicial:

Operadores:

Espaço d Estado:

Estado de Término:

Custo do Caminho:

1. Problema de Escalonamento de voos em um aeroporto.

Nesta pesquisa propõe-se um sistema para sincronização e gerenciamento de fluxo de tráfego aéreo que combina tecnologias de Inteligência Artificial cuja finalidade é otimizar o fluxo de tráfego aéreo sem, contudo ferir os princípios de segurança estabelecidos para a área de transportes aéreos.

Estado Inicial: Conjunto de horários dos voos programado para certo aeroporto.

Operadores: Fazer com que cada voo não choque com outro para evitar acidente.

Espaço de Estado: Conjuntos de passageiros e das empresas aéreas.

Estado de Término: Ter a certeza que cada voo ocorrera de forma programada, acrescentando ainda uma taxa de atraso, para não ocorrer colisões de voos.

Custo do Caminho: Depende do custo monetário, do tempo de espera, do tempo de voo, da hora do dia, do tipo de aeronave.

1. Problema das “n” rainhas.

Colocar um número N de rainhas em um tabuleiro NxN (tipo xadrez) de forma que elas não se ataquem. Por ataque entendemos que quaisquer duas rainhas não podem compartilhar a mesma linha, coluna ou diagonal.

...