Chapter 3, Problem 26E

Program Plan Intro

State space problem:

• One general formulation of intelligent action is in terms of state space.
• A state includes all the necessary information to predict the result of an action and to determine whether it is a target state.
• The state-space search assumes that,
  • The agent knows the state space well and can observe the state in which it is.
  • The agent has a set of actions proven to have deterministic effects.
  • Several states are target/goal state, the agent wants to enter one of these target state and the agent may identify a target state.
  • A solution is a series of acts that will turn the agent in to a target state from its current state.

Branching factor:

• The branching factor is the outdegree, the number of children at each node.
• If the branching factor is not uniform, it is possible to calculate an average branching factor.
• The average branching factor can be determined easily as the number of non-root nodes divided by the number of non-leaf nodes. Where the number of root node is determined by as the size of the tree, minus one.

Program Plan Intro

States:

• The set of states forms a graph that connects two states when there is an operation that can be performed to turn the first state into the second.
• A state includes all the necessary information to predict the result of an action and to determine whether it is a target state.

Program Plan Intro

c.

Breadth first search(BFS):

• The breadth first search algorithm is the most commonly used algorithm to traverse on a graph.
• In BFS, the traversing starts from a user selected node then traverse the graph layer wise for exploring the neighbour nodes. The neighbour nodes are the nodes that are directly connected to the source node. After this, move towards the next-level neighbour nodes.
• The breadth first search algorithm has a strategy that it expands the root node first, then it expands the successor nodes of root, and then expands their successors and so on.
• In BFS, the traversing done as follows,
  • First, go horizontally to visit all the nodes of current layer.
  • Move to the next layer.

Program Plan Intro

d.

Breadth first search(BFS):

• The breadth first search algorithm is the most commonly used algorithm to traverse on a tree or a graph.
• In BFS, the traversing starts from a user selected node then traverse the graph layer wise for exploring the neighbour nodes. The neighbour nodes are the nodes that are directly connected to the source node. After this, move towards the next-level neighbour nodes.
• The breadth first search algorithm has a strategy that it expands the root node first, then it expands the successor nodes of root, and then expands their successors and so on.
• In BFS, the traversing done as follows,
  • First, go horizontally to visit all the nodes of current layer.
  • Move to the next layer.

Explanation of Solution

e.

“Yes”, because “h = |u − x| + |v − y|” is Manhattan Distance Metric. The Manhattan Distance

 is admissible heuristic for the state (u,v).

Manhattan Distance Metric:

• The Manhattan Distance is a metric in which the distance between two points is the sum of their Cartesian coordinates’ absolute differences...

Program Plan Intro

A* search algorithm:

• The A* search algorithm is a search algorithm used to search a particular node of a graph.
• A* algorithm is a variant of the best-first algorithm based on the use of heuristic methods to achieve optimality and completeness.
• The algorithm A* is an example of a best-first search algorithm.
• If a search algorithm has the property of optimality, it means that the best possible solution is guaranteed to be found. Here, the user wants the shortest path to the final state.

Program Plan Intro

Admissible heuristic:

• In path related algorithms, it is said that a heuristic function is admissible if it never overestimates the cost of achieving the goal.
• That is the cost of achieving the goal is not higher than the lowest possible cost from the current point of the route.
• The estimated cost must always be lower than or equal to the actual cost of reaching the goal state in order for a heuristic to be admissible to the search problem.
• The search algorithm uses the admissible heuristic to find the optimal path from the current node to the target node.

Program Plan Intro

Admissible heuristic:

• In path related algorithms, it is said that a heuristic function is admissible if it never overestimates the cost of achieving the goal.
• That is the cost of achieving the goal is not higher than the lowest possible cost from the current point of the route.
• The estimated cost must always be lower than or equal to the actual cost of reaching the goal state in order for a heuristic to be admissible to the search problem.
• The search algorithm uses the admissible heuristic to find the optimal path from the current node to the target node.