wavee Posted October 23, 2006 at 11:43 AM Report #59600 Posted October 23, 2006 at 11:43 AM Olá a todos Bem não percebo muito de programação e precisava da vossa ajuda é um problema já conhecido por muitos que é este. 3 Missionários e 3 Canibais pretendem atravessar um rio só existe um barco de 2 lugares para fazer a travessia. Em circunstância nenhuma os canibais podem ficar em maioria, como executar a travessia? O que eu prentendia era só a estrutura disto num algoritmo tou com duvidas em como defenir a estrutura do barco e verificar se ele está cheio ou não se me pudessem ajudar agradecia. Obrigado desde já
brink@ero Posted October 23, 2006 at 12:36 PM Report #59608 Posted October 23, 2006 at 12:36 PM Olá a todos Bem não percebo muito de programação e precisava da vossa ajuda é um problema já conhecido por muitos que é este. 3 Missionários e 3 Canibais pretendem atravessar um rio só existe um barco de 2 lugares para fazer a travessia. Em circunstância nenhuma os canibais podem ficar em maioria, como executar a travessia? O que eu prentendia era só a estrutura disto num algoritmo tou com duvidas em como defenir a estrutura do barco e verificar se ele está cheio ou não se me pudessem ajudar agradecia. Obrigado desde já Antes de mais, benvindo ao fórum Por acaso não és do IST? Esse problema é referido na cadeira de IA. Bem na cadeira refere um espaço de estados que é do tipo (X,Y, Z, W) Onde X e Y é respectivamente o n.º de missionários e canibais numa margem, e Z e W é respectivamente o n.º de missionários e canibais noutra margem. Consideras a acção {A, B, C}, onde A e B é respectivamente o número de missionários e canibais no barco e C refere se o barco vai da margem 1 -> 2 ou 2 -> 1. Quando efectuas uma acção, há uma mudança de estado e em cada novo estado, verificas se é válido/não válido ou um estado repetido (que consideras como inválido, se não estás sempre às voltas). Agora o tipo de procura, tu é que escolhes (se calhar o melhor é a procura em largura ou profundidade limitada, apesar de gastar muita memória). Espero ter acendido umas luzes... Bem isto é um dúvida de algoritmia, por isso, tópico movido! Cumpr. bk@ero ? EDIT: Uma demostraçãozinha: O estado inicial -> (3,3,0,0) acções possíveis -> estado seguinte {2,0,1} -> (1,3,2,0) -> inválido {1,1,1} -> (2,2,1,1) -> próxima acção -> .... -> .... {0,2,1} -> (3,1,0,2) -> inválido ...
wavee Posted October 23, 2006 at 01:14 PM Author Report #59612 Posted October 23, 2006 at 01:14 PM Antes de mais, benvindo ao fórum Por acaso não és do IST? Esse problema é referido na cadeira de IA. Bem na cadeira refere um espaço de estados que é do tipo (X,Y, Z, W) Onde X e Y é respectivamente o n.º de missionários e canibais numa margem, e Z e W é respectivamente o n.º de missionários e canibais noutra margem. Consideras a acção {A, B, C}, onde A e B é respectivamente o número de missionários e canibais no barco e C refere se o barco vai da margem 1 -> 2 ou 2 -> 1. Quando efectuas uma acção, há uma mudança de estado e em cada novo estado, verificas se é válido/não válido ou um estado repetido (que consideras como inválido, se não estás sempre às voltas). Agora o tipo de procura, tu é que escolhes (se calhar o melhor é a procura em largura ou profundidade limitada, apesar de gastar muita memória). Espero ter acendido umas luzes... Bem isto é um dúvida de algoritmia, por isso, tópico movido! Cumpr. bk@ero ? EDIT: Uma demostraçãozinha: O estado inicial -> (3,3,0,0) acções possíveis -> estado seguinte {2,0,1} -> (1,3,2,0) -> inválido {1,1,1} -> (2,2,1,1) -> próxima acção -> .... -> .... {0,2,1} -> (3,1,0,2) -> inválido ... Obrigado pela resposta 😁 Não não sou do Ist estudo no Porto. Eu tava a pensar resolver por vectores mas vou tentar ir pelo caminho que me deste obrigado
Warrior Posted October 23, 2006 at 07:08 PM Report #59661 Posted October 23, 2006 at 07:08 PM O caminho do brinkaero tambem usa vectores. Eu resolveria usando um DFS, visto serem poucas as combinações.
jintonico Posted October 23, 2006 at 11:28 PM Report #59739 Posted October 23, 2006 at 11:28 PM Em q linguagem e q vais fazer o jogo? Do modo como tou a imaginar o jogo, vou usar posições fixas para cada 1 dos componentes (Missionários , Canibais e barco) Se o barco esta na posição direita Se o missionario1 estiver na posição inicial // isto serve para mover o padre para o barco Se o lugar esquerdo do barco nao estiver ocupado Move o missionario1 para o lugar esquerdo do barco Definie o lugar esquerdo do barco como ocupado Senao Se o lugar direito do barco nao estiver ocupado Move o missionario1 para o lugar direito do barco Da o lugar direito do barco como ocupado Senao // aqui move do barco para terra Se o missionario1 estiver na posicao esquerda do barco Move o missionario1 para a posicao inicial Da o lugar esquerdo como livre Se o missionario1 estiver na posicao direita do barco Move o missionario1 para a posicao inicial Da o lugar direito como ocupado Senao // o barco esta no lado esquerdo Se o missionario1 esta na terra (no lado esquerdo) // tamos a tentar colocar 1º o missionario no barco Se o lugar esquerdo do barco n tiver ocupado Move o missionario1 para o lugar esquerdo do barco Da o lugar esquerdo do barco como ocupado Senao Se o lugar direito do barco n tiver ocupado Move o missionario1 para o lugar direito Da o lugar direito do barco como ocupado Senao // salta do barco para a terra Se o missionario1 esta na posicao esquerda do barco Move o missionario1 para a sua posicao em terra Da o lugar esquerdo do barco como ocupado Se o missionario1 esta na posicao direita do barco Move o missionario1 para a sua posicao em terra Da o lugar direito do barco como ocupado Como n sei a linguagem q vais usar, nem como n sei se vais fazer em modo texto ou grafico.... fica so + esta pequena ajuda... isto move os padres e demonios (1 codigo destes para cada 1) para as 4 posicoes possiveis do jogo. Para mover o barco de um lado para outro: Se o lugar esquerdo do barco estiver ocupado OU o lugar direito Se o barco estiver na posicao direita Mover o barco para a posicao esquerda Dizer q o barco esta no lado esquerdo Se o missionario1 estiver no lado esquerdo do barco Mover o missionario1 para o lado esquerdo do barco qdo este esta na posicao esquerda (o barco) Decrementar a quantidade de missionarios no lado esquerdo Incrementar a quantidade de missionarios no lado direito Se o missionario2..... // Isto e igual para cada 1 dos bonecos, inclusive o lado direito do barco Senao Se o barco estiver na posicao esquerda // fazer exctamente ao contrario do if acima //condicao de vitoria Se a quantidade de canibais no lado esquerdo for maior que a quantidade de missionarios do lado esquerdo Se a quantidade de missionarios for maior que 0 PERDEU Se a quantidade canibais no lado direito for maior que a quantidade de missionarios do lado direito Se a quantidade de padres no lado direito for maior que 0 PERDEU Eficaz? N sei... Simples? Axo q sim... isto da para implementar somente com variaveis O caminho do brinkaero tambem usa vectores. Eu resolveria usando um DFS, visto serem poucas as combinações. O q são DFS?
wavee Posted October 24, 2006 at 09:19 AM Author Report #59749 Posted October 24, 2006 at 09:19 AM Eficaz? N sei... Simples? Axo q sim... isto da para implementar somente com variaveis Bem muito obrigado era mesmo isto que eu queria, isto vai ser para implementar em C# com a ajuda que me deste já fiquei com a 1ªa fase do trabalho resolvido. Obrigado desde já a todos.
Chinês Posted October 24, 2006 at 08:35 PM Report #59858 Posted October 24, 2006 at 08:35 PM Já fiz um trabalho identico e posso te ajudar com mais umas ideias! -Criei uma variavel do tipo string com 3 caracteres, ou seja com 3 posições desde o 0 ao 2. -Inicializei a variavel a d00 ( "d" = que equivale a ter o barco na margem esquerda e , "00" que são as posições em cima do barco. -Sempre que uma figura sobe para o barco incremento um 1 na primeira posição ou na segunda se esta já estiver preenchida! Exemplos: Se o barco estiver da margem direita e tem o 1º lugar cheio com uma figura vou ter a seguinte string "d10" Se o barco estiver da margem direita e tem o 2º lugar cheio com uma figura vou ter a seguinte string "d01" Se o barco estiver da margem direita e tem os 2º lugar cheio s com duas figuras vou ter a seguinte string "d11" Assim sendo, temos o mesmo para o lado esquerdo da margem: Se o barco estiver da margem esquerda e tem o 1º lugar cheio com uma figura vou ter a seguinte string "e10" Se o barco estiver da margem esquerda e tem o 2º lugar cheio com uma figura vou ter a seguinte string "e01" Se o barco estiver da margem esquerda e tem os 2º lugar cheio s com duas figuras vou ter a seguinte string "e11" Com esta pequena string podes gerir o resto do codigo com um simples case que verifica a posição do barco na posição 0 da string ou seja a primeira! Se quiseres mais alguma ajuda envia mensagem privada que eu facilito o email do msn para ajudar, na boa!
Warrior Posted October 24, 2006 at 08:50 PM Report #59864 Posted October 24, 2006 at 08:50 PM O q são DFS? DFS = depth first search, busca em profundidade. Basicamente, vais testas todos os movimentos possíveis recursivamente, e escolhes o "correcto". Começas com 3 padres e 3 canibais, tentas mover 2 padres, ele dá erro (margem esquerda com mais canibais do que padres), volta um passo atras, tenta mover 2 canibais. Na margem direita, tenta mover um padre para a esquerda, dá erro, porque não há padres na margem direita, volta atras. Move um canibal. E volta ao inicio, desta vez com 3 padres e 2 canibais. Se implementado correctamente eu diria que nao iria além das 10 linhas (claro que posso estar enganado).. Atenção: A solução que apontaram é muitíssimos mais eficiente, porque limita-se a arranjar a resposta correcta, e não a testar todas as respostas possíveis para verificar se são correctas ou não.
jintonico Posted October 24, 2006 at 10:09 PM Report #59893 Posted October 24, 2006 at 10:09 PM Ok, obrigado pelo esclarecimento, o DFS cheira-me a algoritmo para IA... ainda n fiz a cadeiramas tb so tenho essa este semestre 🙂
Guest Marine Posted October 26, 2006 at 07:28 PM Report #60264 Posted October 26, 2006 at 07:28 PM Já joguei um jogo com essa mesma mecânica. O jogo foi desenvolvido em flash!😉
jintonico Posted October 30, 2006 at 03:32 PM Report #60894 Posted October 30, 2006 at 03:32 PM Já joguei um jogo com essa mesma mecânica. O jogo foi desenvolvido em flash!😄 Existem resmas de jogos do genero na net, quem quiser dar uma vista de olhos e ganhar alguns cabelos brancos 😁 http://www.gamegarage.co.uk/puzzles-games/priests-n-devils/play/
avelnunes Posted December 14, 2006 at 06:33 PM Report #70570 Posted December 14, 2006 at 06:33 PM Olá Pessoal. Alguem sabe de alguma implementação do algoritmo A* para o problema dos três canibais e três missionários que pretendem atravessar um rio. Eles dispõem de um barco que só pode levar duas pessoas. Os missionários têm de ter cuidado para que o número de canibais nunca exceda o número de missionários numa margem, senão os canibais comem os missionários. Se por acaso, for em C#, melhor. Espero que alguem me ajude. O meu email é avelnunes@hotmail.com. Xau, pessoal.
gerx Posted November 21, 2007 at 07:06 AM Report #149068 Posted November 21, 2007 at 07:06 AM boas ! eu tenho um bastante parecido. "Um grupo de 3 missionários e de 3 canibais pretende atravessar um rio. Para esse efeito existe um barco com 2 lugares. Como efectuar a travessia do grupo de 6 pessoas de forma a garantir (por uma questão de segurança para os missionários) que o número de canibais, em qualquer das margens, nunca é superior ao número de missionários? Apresentar a solução com um algoritmo escrito em linguagem corrente." Se alguem se quiser aventurar ! 🙂 força
mogers Posted November 21, 2007 at 08:58 PM Report #149209 Posted November 21, 2007 at 08:58 PM Eu vou dar o algoritmo A* em Inteligencia Artificial no próximo semestre... desconheço o algoritmo... mas pensava que era vocacionado para linguagens como o prolog e não C# "What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.
Triton Posted November 21, 2007 at 09:53 PM Report #149221 Posted November 21, 2007 at 09:53 PM Eu vou dar o algoritmo A* em Inteligencia Artificial no próximo semestre... desconheço o algoritmo... mas pensava que era vocacionado para linguagens como o prolog e não C# O algoritmo A* é usado em todas as linguagens mesmo, normalmente para path finding em jogos. <3 life
mogers Posted November 21, 2007 at 10:15 PM Report #149229 Posted November 21, 2007 at 10:15 PM Esclarecido 😛 "What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.
antónioramos Posted January 23, 2008 at 07:28 PM Report #161785 Posted January 23, 2008 at 07:28 PM Alguém tem a resolução em C deste jogo precisava mesmo para fazer um trabalho de programação mas nem sei como vou começar alguém pode ajudar-me, por favor, agradecia mesmo muito.
mogers Posted January 23, 2008 at 08:21 PM Report #161800 Posted January 23, 2008 at 08:21 PM Alguém tem a resolução em C deste jogo precisava mesmo para fazer um trabalho de programação mas nem sei como vou começar alguém pode ajudar-me, por favor, agradecia mesmo muito. O trabalho é sobre este jogo? Já tens muitas ajudas nos posts anteriores sobre o algoritmo a usar para resolver o problema, leste-os bem ? Analisar soluções já feitas não ajuda muito a aprender a sério, eventualmente, só alguns truques... "What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.
valter Posted July 22, 2009 at 03:24 PM Report #280557 Posted July 22, 2009 at 03:24 PM boas pessoal.. as voltas pela net para peskisa para um trabalho de inteligencia artificial encontrei este topico k eh mto identico ao k eu necessito.. no meu caso o jogo eh a travessia do rio (http://www.aulavaga.com.br/jogos/raciocinio/travessia-do-rio/).. sera k alguem tem alguma ideia de um algoritmo para este joguinho??..
pedrosorio Posted July 22, 2009 at 07:26 PM Report #280597 Posted July 22, 2009 at 07:26 PM É como já foi dito. Lê o tópico. Vais ter que usar um algoritmo de procura. Se tiveres dúvidas, pergunta. Não respondo a dúvidas por mensagem.
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now