Fórum dos alunos

Falei com a Cris hoje no fim da aula de geocomp sobre o nosso problema (ela está dando distância entre pontos no plano em geometria computacional) e ela sugeriu que usássemos alguns algoritmos em grafos pra resolver nosso problema.

Pensamos em fazer da seguinte forma:

1. Transformamos uma metade do tabuleiro em um digrafo, onde os pinos e as águas são vértices
2. Usamos um algoritmo de pareamento de menor custo para conectar os pinos às respectivas águas (minimizando a distância entre o pino e a água correta)
3. 1. Teremos como resultado um grafo em que só há arestas indo do conjunto de pinos para o conjunto de águas
   2. 
4. Para cada água, criamos uma aresta para cada pino do lado oposto, onde o custo da aresta é a distância da água ao pino
5. 1. Essas são as arestas azuis da figura. Era pra ter aresta azul indo do B7 até todos os pinos (e depois de cada vértice de agua para todos os vértices de pinos), mas ia dar muito trabalho pra desenhar e o desenho ia ficar poluído... Mas acho que dá pra entender a idéia geral: ficará um grafo bipartido, onde cada vértice de água consegue acessar todos os vértices de pinos.
   2. 
   3. A cada aresta desse grafo resultante será associado um custo, e teremos, então, um grafo com peso nas arestas.
6. Aplicamos um algoritmo que percorre o grafo minimizando o custo (djkstra?)
7. Obtemos assim o percurso total do robô pra conseguir colocar todos os pinos percorrendo a menor distância possível

Um problema com isso é que estamos considerando só uma metade do tabuleiro. Precisaríamos pensar em como fazer com a outra metade (principalmente no caso em que o pino desejado se encontra do outro lado do rio). Aí poderíamos embutir a cooperação entre os robôs...

Bom, é isso,

Abraços!