Q:

BFS traversing a desert graph under certain rules

I'm currently solving the question as shown at this link below:
http://www.expertsmind.com/questions/python-implementation-of-a-solver-for-the-desert-crossing-30144185.aspx
That requires Breadth-First-Search (BFS) algorithm to solve the problem. As per my understanding, modified BFS algo is used to find the shortest path connecting from source node to a destination. However, I have no idea of how to implement it in this scenario under the stated truck crossing formal rules.
Can anyone provide me a guide/idea how to use BFS to solve this? Your help is highly much appreciated.Thanks

A:

The first step is to try to formulate the problem in terms of a graph. In this case, each node (also called vertex) in the graph represents some possible configuration (position or state) of the desert, described by a truck location and the amount of gas in each camp. Since the desert is a fixed line, it makes sense to represent it as an array of gas amounts. With those details set, here's the start node of the graph:
  truck (gas: 3)
  v
 [0, 0, 0, 0, 0]
  ^           ^
start        goal

From this position, call it (A), what transitions (edges) to another node are possible? Here they are:
       (B)                  (C)                    (D)

     truck (gas: 0)          truck (gas: 0)           truck (gas: 0)
     v                       v                        v
 [0, 2, 0, 0, 0]      [0, 0, 1, 0, 0]       [0, 0, 0, 0, 0]

Here's how the transitions look in graph form:
      A
     /|\
    / | \
   B  C  D

Nodes (B), (C) and (D) are all of the child nodes of (A), their parent, meaning there is an available transition from the parent to the child. Exploring these children one by one is a BFS, whereas in a DFS, you'd pick the first child, (B), and keep exploring its first child until it reaches a leaf node with no children.
Clearly, (D) is a terminal leaf node because it has no children (it's not the goal, the truck has no gas and the camp it's at has no gas, so it's stuck; there are no available transitions to consider).
The next step is to inspect all of the possible child states available to nodes (B) and (C). Here are the children of (B):
       (E)                  (F)                   (G)

  truck (gas: 3)             truck (gas: 0)           truck (gas: 0)
  v                          v                        v
 [0, 1, 0, 0, 0]      [0, 0, 1, 0, 0]       [0, 0, 0, 0, 0]

       (H)   

        truck (gas: 0) 
        v         
 [0, 1, 0, 0, 0]   

Now the graph looks like:
         A
       / | \
      /  |  \
     /   |   \
    B    C    D
  /|\ \
 / | \ \
E  F  G H

Note that nodes (F) and (G) are identical to (C) and (D) and (E) is clearly the most promising route. In spite of that, (C) will be the next expansion, since this is a BFS rather than a DFS. I'll skip the diagram, but it should be clear that both children of (C) ((I) and (J)) are terminal leaf nodes (the truck will run out of gas whether it moves left or right). At this point, the graph looks like:
           A
         / | \
        /  |  \
       /   |   \
      /    |    \
     /     |     \
    B      C      D
  /|\ \    |\
 / | \ \   | \
E  F  G H  I  J

At this point, it should be clear that everything leads to a terminal node except for (E), whose children will be expanded until either the goal is reached or all nodes in the graph are explored (i.e. there is no solution). 
If a goal is encountered, it's guaranteed to be the shortest path because the expansion depth increases by 1 on each step and all transition possibilities are considered in succession for each depth level. 
I hope this exercise makes the algorithm more clear; in fact, it looks like (E) is only two steps from the goal--see if you can find the rest of the path by hand.
In implementation, keep in mind that using a stack (or recursive calls) does a DFS, while a queue does a BFS. Also, each node should have its own copy of the "desert" array or will need a way to undo its move if invalid. Lastly, on each node, loop through every possible child by decrementing some amount of gas (or adding 3 if at base camp) and trying both left and right moves for each one.
Last step: optimization. By keeping track of already-explored nodes and avoiding recomputing them (this can also be helpful for avoiding infinite cycles in the graph which doesn't seem to be a problem in this case (why?)), you can sacrifice storage space and gain speed. You can also use heuristic searches to further improve speed by prioritizing more promising routes through the graph.

