Quarto Exercício-Programa

Entrega: 30 de junho (pelo panda)

Este EP pode ser feito em dupla. Ele pode ser entregue também no dia 1/7 até às 13 horas em papel e disquete na minha sala.

Wumpus - Cálculo de um Passeio mais Curto

Esse EP usa como dados de entrada a saída gerada pelo EP3. Não é necessário no entanto que você tenha feito o EP3 para fazer este EP. Os dois programas são independentes e você pode inclusive gerar os seus próprios dados de entrada sem precisar do EP3.

Os dados de entrada deste EP deverão ser lidos de um arquivo. O nome do arquivo é dado pelo usuário, ou seja, o seu programa deve pedir que o usuário digite o nome do arquivo de entrada e então prosseguir com a leitura deste arquivo. Um arquivo de entrada deve ter exatamente o formato de um arquivo de saída do EP3:

• na primeira linha, deve haver um inteiro k.
• cada uma das k próximas linhas contém um par de inteiros, representando uma posição. Algumas posições tem (pelo menos) uma das suas coordenadas negativas.
• nas k linhas seguintes, é dada uma matriz kxk com a distância entre as posições dadas.

Chamemos de essenciais as posições com as duas coordenadas não-negativas.

O objetivo desse EP é calcular uma ordem em que as posições devem ser visitadas que corresponda a um passeio de comprimento mínimo que passe por todas as posições essenciais e por pelo menos uma (se houver alguma) posição não-essencial.

Para calcular tal passeio, utilize um algoritmo de enumeração. Ou seja, enumere todos os possíveis passeios e escolha um mais curto. Algoritmos de enumeração podem se tornar muito lentos. Sinta-se a vontade de "otimizar" o seu algoritmo, evitando enumerar passeios que você esteja certo que não levarão a um passeio mais curto. Cuidado para não "perder o melhor passeio" nessa otimização. Ou seja, certifique-se e explique em comentários no seu programa porque as suas otimizações garantidamente não cortam passeios mais curtos.

Evite também, dentro do possível, a geração de passeios "equivalentes". Por exemplo, um passeio e o seu inverso correspondem a um mesmo passeio. Teste apenas passeios começando da primeira posição dada, pois estamos interessados em passeios "circulares", ou seja, que começam e terminam no mesmo lugar, e portanto podemos fixar a ponta inicial.

A sua nota neste EP dependerá, entre outras coisas, da qualidade das suas otimizações. Assim, mesmo que seu EP calcule um passeio de comprimento mínimo, ele pode não receber nota máxima, por estar muito lento e não ter nenhum tipo de otimização implementada.

Saída do seu programa

Competição

Como vocês verão, o algoritmo implementado no EP4 é bastante lento para uma matriz de tamanho não tão grande. Assim, fará bastante diferença na qualidade do produto final as otimizações implementadas neste EP.

Na competição, escolheremos o melhor EP3 e, independente desse, o melhor EP4. O melhor EP3 é o que gera a matriz mais "enxuta", que servirá de dado para o EP4. O melhor EP4 é o que, dada uma matriz, identifica o melhor passeio o mais rapidamente possível.

Um par EP3+EP4 será considerado satisfatório para ser incluído no projeto do Laboratório Virtual de Inteligência Artificial se calcular rapidamente (instantaneamente do ponto de vista do usuário) o valor do limitante superior para dados do tamanho dos labirintos do jogo.

Avisos

• Seu EP deverá ser entregue pelo panda. Não serão aceitos EPs entregues no papel ou em disquete.
• Não serão aceitos EPs atrasados.
• EPs com erros de sintaxe (ou seja, erros de compilação) receberão nota ZERO.
• Seu programa deve ser o mais eficiente possível. Se você implementar algoritmos desnecessariamente ineficientes, você poderá perder pontos.
• Seu programa deve estar bem indentado, bem documentado e organizado. Isso será fortemente levado em conta na sua nota.
• Se você decidir fazer o seu EP em dupla, não se esqueça de enviar até o dia 22/6 um mail para a professora avisando quem é a sua dupla.
• Todos os exercícios-programas devem ter um cabeçalho do seguinte tipo:

      /********************************************************/
      /* Fulano de Tal e Beltrano de Tal                      */
      /* Exercicio-Programa xx                                */
      /* Disciplina yy            Professor:  Ciclano de Tal  */
      /********************************************************/
  

• Guarde com você atê o final do semestre, em seus disquetes, os arquivos de seus programas, pois eles podem ser solicitados pelo professor caso surja alguma dúvida. Guarde também a avaliação do seu EP, que você receberá através do panda.
• EPs copiados receberão nota zero: fonte e cópia. Assim, não copie o EP de outra pessoa nem empreste seu EP ou parte dele para ninguém. Seja cuidadoso para que alguém não copie seu EP sem a sua permissão.