PROLOG is Left Wall Hugging!

[Graham Cooper]

Consider the P=NP problem:

How many ways are there to get from LA to DETROIT?

a---b---c---d

A more accurate graph might have roads between close proximity
waypoints.

Each town you have 3 choices:

LEFT STRAIGHT or RIGHT

In general going RIGHT then LEFT
will get to the same location as STRAIGHT STRAIGHT.


c2--d2
/ \/
/ /\
b1--c1--d1
/ \/ \/
/ /\ /\
a0--b0--c0--d0
\ \/ \/
\ /\ /\
bm1-cm1-dm1
\ \/
\ /\
cm2-dm2



rd(a0,b1).
rd(a0,b0).
rd(a0,bm1).

rd(b1,c2).
rd(b1,c1).
rd(b1,c0).

rd(b0,c1).
rd(b0,c0).
rd(b0,cm1).

rd(bm1,c0).
rd(bm1,cm1).
rd(bm1,cm2).

rd(c2,d2).
rd(c2,d1).

rd(c1,d2).
rd(c1,d1).
rd(c1,d0).

rd(c0,d1).
rd(c0,d0).
rd(c0,dm1).

rd(cm1,d0).
rd(cm1,dm1).
rd(cm1,dm2).

rd(cm2,dm1).
rd(cm2,dm2).


path(A,B,go(A,B)) :- rd(A,B).

path(A,C,go(A,S)) :- rd(A,B),path(B,C,S).

?-path(a0,d0,P).

P = go(a0, go(b1, go(c1, d0)))
P = go(a0, go(b1, go(c0, d0)))
P = go(a0, go(b0, go(c1, d0)))
P = go(a0, go(b0, go(c0, d0)))
P = go(a0, go(b0, go(cm1, d0)))
P = go(a0, go(bm1, go(c0, do)))
P = go(a0, go(bm1, go(cm1, d0)))

NO PROBLEM!

Guess what the Run Time was?

About 3 seconds per path, 20 seconds!

Note: VTPROLOG is written with linked lists in Pascal 3.

But try that 10 cities deep and PROLOG will hang!

Herc
--
www.microPROLOG.com

[Graham Cooper]

> ?-path(a0,d0,P).
>
> P = go(a0, go(b1, go(c1, d0)))
> P = go(a0, go(b1, go(c0, d0)))
> P = go(a0, go(b0, go(c1, d0)))
> P = go(a0, go(b0, go(c0, d0)))
> P = go(a0, go(b0, go(cm1, d0)))
> P = go(a0, go(bm1, go(c0, do)))
> P = go(a0, go(bm1, go(cm1, d0)))
>
> NO PROBLEM!
>
> Guess what the Run Time was?
>
> About 3 seconds per path, 20 seconds!
>
> Note: VTPROLOG is written with linked lists in Pascal 3.
>
> But try that 10 cities deep and PROLOG will hang!

OK let's extend from 4 regions a, b, c, d to 5 regions.






e4
/
/
d3--e3
/ \/
/ /\
c2--d2--e2

/ \/ \/
/ /\ /\

b1--c1--d1--e1
/ \/ \/ \/
/ /\ /\ /\
a0--b0--c0--d0--e0
\ \/ \/ \/
\ /\ /\ /\
bm1-cm1-dm1-em1
\ \/ \/
\ /\ /\
cm2-dm2-em2
\ \/
\ /\
dm3-em3
\
\
em4


You can go LEFT, STRAIGHT or RIGHT from a to e.

e.g.

?- rd(a0,b0).
YES

?-path(a0,b0,P).
P = go(a0,b0). << PROLOG'S ANSWER

To add 3 roads branching out from D3

e4 LEFT
/
d3--e3 STRAIGHT
/ \
/ e2 RIGHT

SIMPLY ADD
rd(d3,e4).
rd(d3,e3).
rd(d3,e2).


?-path(a0,e4,P).
P = go(a0, go(b1, go(c2, go(d3, e4)))) 5 secs

?-path(a0,e3,P).
P = go(a0, go(b1, go(c2, go(d2, e3)))) 5 secs

?-path(a0,e2,P).
P = go(a0, go(b1, go(c2, go(d2, e2)))) 5 secs

?-path(a0,e1,P).
P = go(a0, go(b1, go(c2, go(d2, e1)))) 5 secs

?-path(a0,e0,P).
P = go(a0, go(b1, go(c2, go(d1, e0)))) 10 secs

?-path(a0,em1,P).
P = go(a0,b1,c1,d0,em1) 30 secs

?-path(a0,em2,P).
P = go(a0,b1,c0,dm1,em2) 50 secs

?-path(a0,em3,P).
P = go(a0,b0,cm1,dm2,em3) 100 secs (1 min 40s)

?-path(a0,em4,P).
P = go(a0,bm1,cm2,dm3,em4) 150 secs (2 min 30s)


SUMMARY
a0-e4 LLLL 5s
ao-e3 LLSL 5s
a0-e2 LLSS 5s
a0-e1 LLSR 5s
a0-e0 LLRR 10s
a0-em1 LSRR 30s
a0-em2 LRRR 50s
a0-em3 SRRR 100s
a0-em4 RRRR 150s

You can see how PROLOG hugs the LEFT BRANCHES
(or the FACTS that are entered 1st into it's Database)


-------paths.pro------

rd(a0,b1).
rd(a0,b0).
rd(a0,bm1).

rd(b1,c2).
rd(b1,c1).
rd(b1,c0).

rd(b0,c1).
rd(b0,c0).
rd(b0,cm1).

rd(bm1,c0).
rd(bm1,cm1).
rd(bm1,cm2).

rd(c2,d3).

rd(c2,d2).
rd(c2,d1).

rd(c1,d2).
rd(c1,d1).
rd(c1,d0).

rd(c0,d1).
rd(c0,d0).
rd(c0,dm1).

rd(cm1,d0).
rd(cm1,dm1).
rd(cm1,dm2).

rd(cm2,dm1).
rd(cm2,dm2).

rd(cm2,dm3).

rd(d3,e4).
rd(d3,e3).
rd(d3,e2).

rd(d2,e3).
rd(d2,e2).
rd(d2,e1).

rd(d1,e2).
rd(d1,e1).
rd(d1,e0).

rd(d0,e1).
rd(d0,e0).
rd(d0,em1).

rd(dm1,e0).
rd(dm1,em1).
rd(dm1,em2).

rd(dm2,em1).
rd(dm2,em2).
rd(dm2,em3).

rd(dm3,em2).
rd(dm3,em3).
rd(dm3,em4).