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.
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:
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.
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.
/********************************************************/
/* Fulano de Tal e Beltrano de Tal */
/* Exercicio-Programa xx */
/* Disciplina yy Professor: Ciclano de Tal */
/********************************************************/