2
$\begingroup$

I'm trying to figure out how to calculate the route cost on this graph (it's the missionaries and cannibals game)

I have my definition as:

Mi = Missionary on the initial side, C = Cannibal on the initial side, B = Boat [I = Boat in the Initial Side, F = Boat on the Final Side],
Mf = Missionary on the other side of the river, Cf = Cannibal on the other side of the river
State: (Mi, Ci, B, Mf ,Cf)
Initial Status: (3, 3, I, 0,0)
Final Status: (0, 0, F, 3,3)
Status Space (All the valid statuses): 
{(3,3,I,0,0),(3,2,F,0,1),(2,2,F,1,1),(3,1,F,0,2),(3,2,I,0,1),(3,0,F,0,3),(3,1,I,0,2),(1,1,F,2,2),(2,2,I,1,1),(0,2,F,3,1),(0,3,I,3,0),(0,1,F,3,2),(0,2,I,3,1),(2,2,I,1,1),(3,2,I,0,1),(0,0,F,3,3)}

Rules: 

1.  Bote can only carry two people
2.  One person has to drive the boat
3.  Cannibals can't outnumber the missionaries or they the missionaries will be eaten. 
Cost: 1 per crossing.

Exhaustive Search (or Brute Search):

(3, 3, I, 0, 0) -> (2, 2, F, 1, 1) -> (3,2,I,0,1), -> (3,2,I,0,1) -> (3,2,1,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,F,1,1) -> (0,2,F,3,1) -> (0,3,I,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (0,0,F,3,3)

According to me and the graph the route cost for Exhaustive Search would be 11.

How can I calculate the route cost for that graph for Breadth-first?

I do know that Breadth-first I have to separate the graphs on levels and it will test each node on that level against the final result (depending on the direction, clockwise, or counterclockwise) but I'm not sure if I should take each node as a crossing (I'm getting 14 as length of the solution). For instance in the image I take the crossing from (3,3,I,0,0) to (3,2,F,0,1) as 1 and then there isn't more child-nodes on that branch so I should get back to (3,3,I,0,0) in order to reach the branch of (2,2,F,1,1) this I don't know If I should count it too or not

To get 14 I'm doing. (3, 3, I, 0, 0) -> (3,2,F,0,1) -> (2,2,F,1,1) -> (3,1,F,0,2) -> (3,2,I,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,I,1,1) -> (0,2,F,3,1) -> (0,3,1,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (2,2,I,1,1) -> (0,0,F,3,3)

Because of this doubts I have troubles calculating the Length of the solution

graph

Improve this question
$\endgroup$
8
  • $\begingroup$ @Evil please let me know how you got 13 in breadth-first. Because I'm getting 14 now. $\endgroup$ – Splendonia Aug 11 '16 at 13:06
  • $\begingroup$ At your last picture - there are possible states, it looks now like the solution is 11 long, right? The first attempt as the left child of the root - it was dead end, so it was not longer expanded, so it is not the part of the solution. Center or the right child provides the same next step, but you count only one of them - in the solution you do not follow both possible moves just pick one, right? $\endgroup$ – Evil Aug 11 '16 at 19:16
  • $\begingroup$ @Evil It should go from the left child of the root to the center child and then to the right child (because as I have understood that's how BF algorithm works) then it will go the next shallow node which could be the child of both nodes and then the next shallow and so on $\endgroup$ – Splendonia Aug 11 '16 at 20:40
  • 1
    $\begingroup$ Yes. 11 is the (1) length of the solution, and (2) the cost of the algorithm is 14. $\endgroup$ – Evil Aug 12 '16 at 3:58
  • 1
    $\begingroup$ @evil thanks a lot, I finally understood it $\endgroup$ – Splendonia Aug 12 '16 at 12:53
3
$\begingroup$

I do not know how your sources define "route cost" (I've never heard that term).

There are two points of view I can imagine.

  1. Length of the solution

    Once you reach a fitting leaf you have found your solution and can abort. The length of the solution, i.e. the number of steps you have to perform to get everybody across, is the length of the path from the root to that leaf.

  2. Cost of the algorithm

    The number of steps the algorithm has to perform is different, of course; it may visit many nodes that are not part of the final solution. The details depend on the specific implementation at hand.

    Specifically, you seem to be concerned about backtracking out of dead ends. The usual way to implement BFS is using a queue which makes backtracking free since you don't actually do it; the next node to visit is already at the front of the queue.

    If you don't use a queue and backtrack explicitly, well, you get quadratic worst-case performance. Don't do it.

Improve this answer
$\endgroup$
0
1
$\begingroup$

If you want to calculate the distance between two nodes using BFS, you could use the algorithm as described in the Wikipedia.

Maybe it's easier to understand how this works if you think of BFS as working in waves:

wave <- starting node
set all distances to infinity
d = 0
while wave is not empty:
     set the distance of all nodes in wave to d
     next_wave = all neighbors of nodes in wave with infinite distance
     d = d + 1
     wave = next_wave

The wave-front travels over the graph very much like the wave in a pond after you throw a stone in it. In this formulation you don't explicitly traverse edges forwards or backwards, so it's harder to get confused when to increase distances.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.