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.

\r\n
\r\n\r\n

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.

\r\n\r\n\r\n
\r\n
\r\n
\r\n

Receba nossas actualizações por email

\r\n
\r\n \r\n \r\n
\r\n

Ver Campanhas anteriores.

\r\n
\r\n \r\n \r\n
\r\n
\r\n
\r\n
\r\n
\r\n
\r\n
(Visited 58 times, 2 visits today)
Share