Consider the problem of moving a knight on a 3 time 4 board, with start and goal

Question

Consider the problem of moving a knight on a 3 time 4 board, with start and goal states labeled as S and G in picture below. The search space can be translated into the following graph. The letter in each node is its name and the subscript digit is the path cost. Note: The knight can move to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The complete move therefore looks like the letter L. Make the following assumptions: All the algorithms do not generate paths with loops. In a tie, nodes are selected In alphabetical order. Nodes at the front of the search queue are visited first. Write the sequence of nodes in the order visited by the specified methods along with the total path cost. Note: You may find it useful to draw the search tree corresponding to the graph above. (a) Depth-first search. (b) Breadth-first search.

Explanation / Answer

1. Depth-first search

S A C H E B D F J K G

Here we will push the nodes into the stack travesing the adjacent nodes, in case of tie we will consider the nodes which alphabetically lies on top and then pop it of till the stack is empty. Assumption - No path with loops will be traversed.

start from node S, and write it on output. {s}

So the first node in the stack is S, now we need to find the adjacent node to s,

node adjacent to S we find A and B. Going alphabetical order A will be put into stack, add A to output {S A}

From A we traverse to C and add C to output {S A C}

Then from C we traverse to H, adding H to stack we get {S A C H} i output.

Similarly traversing the whole path we get the output as

S A C H E B D F J K G

2. Breadth-first search

S A B C D E H F I G

Here we will use queue data structure. We use currently working node.

We start from S and add to the output because it is currently working node. {S}

Now we will see the adjacent nodes and consider it alphabetically. So we get A and then B. Alphabetically we consider A, output { S A } and then B as it will be currently working node, which will be then dequeued

output - {S A B}

Similarly when we traverse the complete tree we get,

S A B C D E H F I G

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.