reset password
Author Message
rabbott
Posts: 1649
Posted 17:15 Oct 27, 2012 |

Here is my breadth-first wolf, goat, cabbage code.

Can you use it (or your own) to create the other searches?

Last edited by rabbott at 17:15 Oct 27, 2012.
ummata
Posts: 68
Posted 20:43 Oct 28, 2012 |

My code is in the dropbox folder Amata/experiment.
It is just a breadth-first search. Some more are coming.
 

rkjc
Posts: 61
Posted 17:20 Nov 01, 2012 |

I've got a BFS 3-way and assorted versions of the 5-way  searches in my dropbox.

The BFS and DFS searches appear to be working just fine.

I'm not as sure about the Dijkstra BFS search though and was wondering if anyone else had results I could compare it to.


Here are outputs from the different searches:


There seems to be some kind of randomizing factor in the eclipse runtime environment.
These results will sometimes vary in order and selection between runs.

f = farmer
w = wolf
g = goat
c = cabbage
s = stick
r = fire

------------------------------------------------
FarmerBoat 5-way version puzzle - Breadth First Search

frwscg||
rsg||fwc
rsc||fwg
rwc||fsg
frsg||wc
frwsg||c
frscg||w
frwsc||g
frwc||sg
frwcg||s
sg||fwrc
rg||fwcs
rs||fwcg
g||fwrcs
s||fwrcg
r||fwcsg
rw||fcsg
sc||fwrg
rc||fwsg
wc||frsg
c||fwrsg
w||frscg
fsg||wrc
fwsg||rc
fscg||wr
fwscg||r
frwg||cs
fwg||rcs
fwcg||rs
fwsc||rg
fwc||rsg
||fwrcsg
--- the end state sequence ---
  ->  frwscg||  ->  rsg||fwc  ->  frsg||wc  ->  sg||fwrc  ->  fsg||wrc  ->  ||fwrcsg

-------------------------------------------------

FarmerBoat 5-way version puzzle - Depth First Search

rsfcgw||
rsg||fcw
rsfgw||c
rs||fcgw
rsfcw||g
rc||fsgw
rfcgw||s
rfcw||sg
r||sfgcw
rfgw||sc
g||rsfcw
fgcw||rs
fsgw||rc
s||rfcgw
sfcw||rg
fsgc||rw
fgw||rsc
||rsfcgw
--- the end state sequence ---
  ->  rsfcgw||  ->  rsg||fcw  ->  rsfgw||c  ->  rs||fcgw  ->  rsfcw||g  ->  rc||fsgw  ->  rfcw||sg  ->  r||sfgcw  ->  rfgw||sc  

->  g||rsfcw  ->  fgw||rsc  ->  ||rsfcgw

-------------------------------------------------

FarmerBoat 5-way version puzzle - Dijkstra Breadth First Search

wrsgcf||
rsc||wgf
rsg||wcf
wrc||sgf
rsgf||wc
wrsgf||c
rsgcf||w
wrcf||sg
wrscf||g
wrgcf||s
g||wsrcf
r||wsgcf
rg||wscf
s||wrgcf
sg||wrcf
rs||wgcf
rc||wsgf
sc||wrgf
c||wsrgf
w||srgcf
wc||srgf
wr||sgcf
sgcf||wr
sgf||wrc
wrgf||sc
wsgf||rc
wgf||src
wcf||srg
wsgcf||r
wscf||rg
wgcf||sr
||wrsgcf
--- the end state sequence ---
  ->  wrsgcf||  ->  rsg||wcf  ->  rsgf||wc  ->  g||wsrcf  ->  sgf||wrc  ->  ||wrsgcf

-------------------------------------------------
 

rkjc
Posts: 61
Posted 18:29 Nov 01, 2012 |

I'm thinking I have a problem in my Dijkstra algorithms.

I expected the DFS version (pull from the top of the openSet queue) to give the shortest route. It doesn't.

FarmerBoat 5-way version puzzle - Dijkstra Depth First Search
fscwgr||
scr||fwg
fscgr||w
sc||fwgr
fscg||wr
c||fswgr
fcwr||sg
cw||fsgr
fcwgr||s
fcwg||sr
fcswr||g
fcswg||r
fcsw||gr
fcw||sgr
||fscwgr
fwg||scr
fsg||cwr
s||fcwgr
fsgr||cw
sr||fcwg
fswgr||c
r||fcswg
fwgr||cs
gr||fcsw
sgr||fcw
fswg||cr
g||fcswr
sg||fcwr
w||fscgr
wr||fscg
cwr||fsg
cr||fswg
--- the end state sequence ---
  ->  fscwgr||  ->  scr||fwg  ->  fscgr||w  ->  sc||fwgr  ->  fscg||wr  ->  c||fswgr  ->  fcwr||sg  ->  cw||fsgr  ->  fcw||sgr  ->  ||fscwgr

rkjc
Posts: 61
Posted 23:33 Nov 01, 2012 |

Ahh Haa!

The Dijkstra is not finding the shortest route, it is finding the cheapest route.