Pode ser feito em turmas de 4 pessoas

data de entrega: 31/3 ate meia noite via moodle: https://moodle.ggte.unicamp.br/

Exercício 1 versão 1

Essencialmente o exercício 3.7 do livro texto

Faça um programa que le um conjunto de polígonos no espaço 2D, um ponto de saida (S) e um ponto de chegada (G), e computa de diferente forma o caminho de S para G passando pelos vertices dos polígonos.

Considere que o problema é um problema de roteamento de um robo microscopico e voce quer achar o caminho mais curto de S para G. Ou existe um caminho direto (uma linha) ou o caminho sairá de S ate um dos vertices de algum dos polígonos, e recursivamente, ou dai ha um caminho direto ate G ou um caminho direto ate um outro vertice, e assim por diante.

O custo de de ir de um ponto A para B é a distancia euclidiana de A para B.

Pense no que seria uma heurística apropriada para estimar o custo de sair de cada ponto e chegar em G.

Implemente as buscas

• BFS - Best first search (busca em largura ordenada pelo g)

• ID - iterative deepening ou aprofundamento iterativo (busca em profundidade limitada por valores crescentes da profundidade até achar UMA solução (nao necessariamente a melhor)

• A*

• IDA*

Para cada busca imprima:

• o caminho encontrado e o custo deste caminho

• o número de vertices explorados na busca

Dicas

As implementações dos 4 algoritmos de busca não precisam ser eficientes. Por exemplo, BFS em principio precisaria de uma implementação de lista de prioridades, onde obter o nó com menor g demoraria tempo O(1) (constante) mas voce pode implementar com uma lista e a função min que obtém o menor elemento da lista (que tem complexidade O(n)).

As buscas que são essencialmente em profundidade (ID e IDA*) provavelmente são mais fáceis de implementar usando recursão em vez de uma pilha explicita.

A parte mais difícil do projeto é descobrir que são os vertices/estados descendentes de cada vertice (sao so vertices visíveis de cada vertice.

Dois vertices que estão numa mesma aresta são visíveis entre si. Mas vertices que estão de “lados diferentes do mesmo poligono não são. Da mesma forma que vertices que estão”atras” de poligono também não são.

Vertices que estão “atras” de um poligono são mais facies de determinar: se o segmento de reta que liga A e B cruza dom um dos lados de algum poligono, então A nao é visível de B e vice versa. (E note que na entrada dos dados os lados dos polígonos são explícitos).

Mas vertices que estão no mesmo polígono mas “do outro lado” me parece mais difícil de determinar. O problema seria mais facil se os polígonos fossem convexos (parecidos com circulos). Neste caso, 2 vertices de um mesmo poligono só são visíveis entre si se eles estão numa mesma aresta. Mas isso nao é verdade se o poligono é concavo (com “barriga para dentro”). Na primeira versão deste projeto voce NÃO deve assumir que os polígonos serão convexos.

Entrada de dados

os dados de entrada estão organizados da seguinte forma;

vertices

poligonos

ponto-de-saida 
ponto-de-chegada

vertices contem linhas no formato

nome-do-vertice  x   y

que indica o nome e a posição x e y de cada vertice. Nome é uma sequencia de letras e números, e as posições x e y sao números float.

poligonos contem dados no formato

n v1  v2  v3  ... v7 v1

que indica o número do poligono, e que ele é composto dos vertices v1 (o nome do vertice), v2 , v3 etc, ate v7 e volta a v1.

Finalmente as duas ultimas linhas contem as coordenadas x e y do ponto de saida (S) e o ponto de chegada (G).

Ha uma linha vazia separando a seção de vertices, dos polígonos e dos pontos de saida e chegada.

Em cada linha os dados estão separados por um ou mais brancos.

Voce pode mudar o formato dos dados se isso tornar a sua leitura de dados mais simples.

Exemplo

O arquivo ex1-dados.txt) contem a entrada de dados que representa o problema ilustrado na figura figex1.pdf. Note que um dos polígonos não é convexo e que nesse poligono, os pontos p e s sao visíveis entre si mas nao estão na mesma aresta.

Entrega

submeta um arquivo PDF com o seu programa e com o resultado de roda-lo no exemplo acima.

Discuta brevemente os resultados (qual algoritmo gerou o caminho mais curto, qual visitou menos vertices, etc).