Prolog - Labyrinth problem

Author

Labyrinth problem

Negator

2004-04-11, 10:32 am

The task is to find all ways from Start to Destination in a labirinth. The
labyrinth is defined as the quantity of facts as follows:

link(room1,room2).
link(room2,room3).
....
link(roomK,room1).
....
link(roomN,roomK).

where roomK are room numbers and link means that these rooms are connected.
The way can be layed in both directions (i.e. from room1 to room2 and from
room2 to room1).

The following predicate throws "out of stack" error because of recursion
caused by marked lines.

path(A,A,L):-length(L,1).
path(From,To,A):-A=[From|Rest],
Rest=[SecondInPair|_],
(pass(SecondInPair,From); /* recursion*/
pass(From,SecondInPair)),
path(SecondInPair,To,Rest).

The recursion looks like this:

?-path(room1,room2).

[room1,room2,room1,room2...]

How to get rid of recursion in this predicate?

Thanks in advance.

bart demoen

2004-04-11, 5:35 pm

Negator wrote:
> The task is to find all ways from Start to Destination in a labirinth. The
> labyrinth is defined as the quantity of facts as follows:
>
> link(room1,room2).
> link(room2,room3).
> ...
> link(roomK,room1).
> ...
> link(roomN,roomK).
>
> where roomK are room numbers and link means that these rooms are connected.
> The way can be layed in both directions (i.e. from room1 to room2 and from
> room2 to room1).
>
> The following predicate throws "out of stack" error because of recursion
> caused by marked lines.
>
> path(A,A,L):-length(L,1).
> path(From,To,A):-A=[From|Rest],
> Rest=[SecondInPair|_],
> (pass(SecondInPair,From); /* recursion*/
> pass(From,SecondInPair)),
> path(SecondInPair,To,Rest).
>
> The recursion looks like this:
>
> ?-path(room1,room2).
>
> [room1,room2,room1,room2...]
>
> How to get rid of recursion in this predicate?
>
> Thanks in advance.
>
>

Several things are not clear in what you ask:

how vould the query ?-path(room1,room2).
produce the list of answers [room1,room2,room1,room2...]

your program calls a predicate pass/2, but you
didn't give clauses for it

Finally, one answer to you question would be: get rid of recursive
calls. But I guess that's not what you want. Did you mean to ask:

How can I get rid of multiple answers ?
or
How can I get rid of an infinite loop ?

Please, more precise details about your program and your questions and
then the net can (maybe try to) answer your problem.

Cheers

Bart Demoen

Negator

2004-04-12, 7:33 am

> Several things are not clear in what you ask:
>
> how vould the query ?-path(room1,room2).
> produce the list of answers [room1,room2,room1,room2...]
>
> your program calls a predicate pass/2, but you
> didn't give clauses for it
>
> Finally, one answer to you question would be: get rid of recursive
> calls. But I guess that's not what you want. Did you mean to ask:
>
> How can I get rid of multiple answers ?
> or
> How can I get rid of an infinite loop ?
>
> Please, more precise details about your program and your questions and
> then the net can (maybe try to) answer your problem.

I'm sorry, I meant "link" instead of "pass" - that happend because of
different versions of the predicate. The right version looks like:

path(A,A,L):-length(L,1).
path(From,To,A):-A=[From|Rest],
Rest=[SecondInPair|_],
(link(SecondInPair,From); /* recursion*/
link(From,SecondInPair)),
path(SecondInPair,To,Rest).

but still doesn't work)
You are right - the qestion isn't correctly formulated. It isn't really a
Prolog qestion, but I'm sure, it can be solved here much easier than in any
other programming language.
How to make a rule, that will exclude the recursion. I.e.

?-path(room1,room2).

or

?-path(room2,room1).

if there is a

link(room1,room2).

instructs Prolog to find all paths between room1 and room2. Prolog finds the
first correct variant - [room1,room2], but we need all possible paths
between two roms, that's why it finds the next variant -
[room1,room2,room1,room2] - that is a correct variant too, but we don't need
it.
So the qestion is: how to exclude these variants, and infinite loops with
them?

Bill Spight

2004-04-12, 2:37 pm

Dear Negator,

>
> I'm sorry, I meant "link" instead of "pass" - that happend because of
> different versions of the predicate. The right version looks like:
>
> path(A,A,L):-length(L,1).
> path(From,To,A):-A=[From|Rest],
> Rest=[SecondInPair|_],
> (link(SecondInPair,From); /* recursion*/
> link(From,SecondInPair)),
> path(SecondInPair,To,Rest).
>
> but still doesn't work)

Are you sure that's rightthe right version?

At a glance it looks like the first clause should be

path(A,A,[]).

Best,

Bill

houdini

2004-04-12, 3:33 pm

Negator wrote:
>
>
> I'm sorry, I meant "link" instead of "pass" - that happend because of
> different versions of the predicate. The right version looks like:
>
> path(A,A,L):-length(L,1).
> path(From,To,A):-A=[From|Rest],
> Rest=[SecondInPair|_],
> (link(SecondInPair,From); /* recursion*/
> link(From,SecondInPair)),
> path(SecondInPair,To,Rest).
>
> but still doesn't work)
> You are right - the qestion isn't correctly formulated.

In Prolog and in logic programming generally, capturing the essence
of the problem in as few rules or axioms as possible is pretty much the
name of the game.

It isn't really a
> Prolog qestion, but I'm sure, it can be solved here much easier than in any
> other programming language.

[?]

> How to make a rule, that will exclude the recursion. I.e.
>
> ?-path(room1,room2).
>
> or
>
> ?-path(room2,room1).
>
> if there is a
>
> link(room1,room2).
>
> instructs Prolog to find all paths between room1 and room2. Prolog finds the
> first correct variant - [room1,room2], but we need all possible paths
> between two roms, that's why it finds the next variant -
> [room1,room2,room1,room2] - that is a correct variant too, but we don't need
> it.
> So the qestion is: how to exclude these variants, and infinite loops with
> them?
>
>

Suppose you had to explore a huge mansion that had hundreds of
interconnected rooms and you were not allowed to leave markers of any
kind and you didn't want to visit any room twice: put into words the
rule that governs the question of whether you are allowed to go from
room A to room B.

With no restrictions, you have

possible_to_go(A,B) if link(A,B).
possible_to_go(A,B) if link(B,A).

In these rules, the only factors that enter into consideration are
the respective names of the rooms. If there is another factor, it has to
be represented, maybe like

allowed_to_go(A,B,OtherFactor) if
possible_to_go(A,B)
and not rules_out(OtherFactor,A,B).

--
sequitur AT sonic DOT net

Sponsored Links