Resolvendo o problema do percurso entre cidades em prolog

Temos várias cidades marcadas com letras de A até F e percursos marcados com números. Por exemplo, poderiamos ter a seguinte situação:

Para sair da cidade A para cidade B temos o percurso 1
B–>C==2
C–>D==3
D–>F==4

já não recordo bem o exercício, mas é algo parecido com isto, e estes percursos estão indicados num diagrama, e não posso apresentar aqui agora, talvez mais tarde edite o artigo.

Agora a resolução que eu encontrei foi a seguinte:
Primeiro vamos definir as regras para sair de uma cidade para outra, tal como vem no enunciado. Vamos chamar de estrada esta regra, que pode ser assim: estrada(M,N,Y), que deve ser lida: Para sair da cidade M para cidade N usa-se o caminho Y. Teremos regras de acordo com o número de estradas, veja:

estrada(A,B,1).
estrada(B,C,2).
estrada(C,D,3).

Ja podemos sair de uma cidade para outra com as regras acima, desde que as cidades sejam vizinhas. Mas a ideia do exercício é encontrar uma regra que permita sair de uma cidade para qualquer outra mesmo que não sejam vizinhas. Então vamos definir uma nova regra que será: caminho(M,N,Y):-estrada(M,Z,_),caminho(Z,N,K).  Aqui estamos a dizer que existe um caminho de M até N não vizinhos, se for possível sair de uma cidade M até a sua cidade vizinha Z e depois de Z até N. parece estranho, mas se você se lembrar que prolog é recursivo verá a lógica. Por exemplo, usando as estradas definidas acima teriamos o seguinte se quisessemos sair de A para D:

  • -É possivel sair de A para D se for possível sair de A para B usando a estrada A e depois de B para D usando outro caminho;
  • -É possível sair de B para D se for possível sair de B para C usando a estrada 2 e depois de C para D usando outro caminho. Aqui nota-se a recursividade!
  • -É possível sair de C para D se for possível sair de C para D usando a estrada 3, e depois de D para D usando outro caminho; Mais uma vez recursividade!

Até aqui está tudo bom mas quando chegarmos a cidade D, o que nos dirá que já terminamos o exercício? Ai temos de criar uma nova regra, que dirá que já terminamos o exercício. Em prolog chamammos esta regra condição de paragem. Esta regra pode ser: caminho(M,M,0), que quer dizer que o caminho da cidade M até ela mesmo é zero. Assim, sempre que quisermos sair de D para D no caso do exercício anterior a recursividade para.
Então, resumindo, teremos as seguintes regras, depois de definidas as de estrada:

 caminho(M,M,0).
caminho(M,N,Y):-caminho(M,Z,_),caminho(Z,N,T).

Talvez seria interessante ter a lista de estradas usadas para percorrer de M até N. Na verdade era isso que o exercício pedia(Só agora me lembrei disso!!!). Então vou modificar um pouco a resolução anterior:

caminho(M,M,[]).
caminho(M,N,[T|Y]):-estrada(M,Z,T),caminho(Z,N,[Y]).

Agora complicou? Nada disso! Estamos  somente a dizer que para sair de uma cidade para ela mesmo não usamos nenhum caminho na primeira regra. Na segunda regra dissemos que a lista de estradas de M até N é a lista de estradas de Z, até N mais a estrada de M até Z, sendo M vizinha de Z. Agora está tudo claro. Tenta seguir o pensamento lógico do prolog que você verá a lógica do exercício.

Receba nossas actualizações por email

Ver Campanhas anteriores.

(Visited 103 times, 1 visits today)
Share