O Problema dos peões da Maratona 2003

… é ???

Paulo, você poderia disponibilizar também a solução de vocês para os outros programas que vocês fizeram?

infelizmente a gente soh imprimiu esse, que foi o que a gente nao passou… mas a gente esta pensando em criar um repositorio de solucoes desses problemas em java, para o ano que vem.

Paulo,

O link para o pdf está quebrado? Removeram o arquivo?

Já tentei algumas vezes ver o problema e não consegui.

Gustavo GUilherme BacK

pelo que vi estava fora o ar, mas ja voltou:
http://maratona.ime.usp.br/problem_set.pdf

Paulo, você chegou a ver oque no seu programa ficou lento? Fazer algum profiling?
Me parece que se você tivesse utilizado um heap no lugar de uma lista-ligada para representar os próximos tabuleiros o programa poderia rodar mais rápido.
Outra coisa, vcs chegaram a pensar em resolver de outra forma? Em vez de simplesmente fazer o cavalo ir andando, pq não ir selecionando lista de alvos e testando a viabilidade delas?
Caramba, aqui rodou rápido pacas com a entrada que voce proveu, alguns milisegundos! Foi por tempo mesmo?

louds! exatamente os pensamentos que voce teve a gente teve la na hora. hehehe, voce entendeu esse codigo que esta uma zona hein?

bem, o heap nao adianta muito nao, a gente ateh tinha feito com TreeSet que tambem removia em O(logn). a remocao na lista ligada eh super rapido, mesmo sendo O(n), ja que a gente usa A* (pode ver que tem um comparator que usa uma heuristica) e tem poucos caras na fila. Mas vc tem razao, eh um lugar que da pra melhorar em vez de ficar pegando min/max.

parece que nao eh por tempo certo? a gente acha que tem algum caso particular que entra em loop infinito, por causa do nosso while true ai.

e acredite se quiser, o pessoal que conseguiu passar esse ai fez busca em PROFUNDIDADE exaustiva! fez TODAS as jogadas e escolheu a mais curta. Brincadeira??? nao eh possivel que uma busca exaustiva em C seja mais rapida que A* em java, nao mesmo…

de qualquer maneira, estamos esperando as solucoes dos juizes, junto com os testes deles…

sobre a ideia de fazer ele cacar os peoes, tentamos, mas ele dava resposta errada se a gente soh considerasse as posicoes que poderiam comer.

bizarro em…
O espaço total de pesquisa não me parece ser suficientemente grande para valer a pena usar A*, vejamos:

São no máximo 8 passos, com 8 possibilidades por passo, isso gera um pior caso de 2^24 testes, porem isso dificilmente vai acontecer se voce colocar 1 pouco de heuristica.

Vou implementar usando busca em profundidade e ai comparamos os resultados.

a gente fez alguns testes.
fazendo uma busca em largura secona, sem cache nem nada, mas fazendo um pruning que percebe que aquele tabuleiro ja esta perdido, a gente teve de visitar 2500 tabuleiros para resolver o problema com 6 peoes comiveis.

usando o A*, isso diminui para 25!!!

louds, posta seus resultados pra gente depois por favor! testa com aqueles caras e posta quantos tabuleiros visitados.

Estava estudando o capítulo de array do Java Como Programar e acabei fazendo uma versão “jogável” do Passeio do Cavalo. É fora do tópico, mas quem estiver afim de dar uma conferida: .

muda o while(true) para while(lista.size()!=0)
mas deveria dar na mesma, pq o while(true) so ficaria em loop caso os objetos da lista nao estivessem sido removidos ou nao existisse um fim de profundidade (8 passos)