[1 pt] When carrying out search process by using a search tree, whether a finite

Question

[1 pt] When carrying out search process by using a search tree, whether a finite state space always leads to a finite search tree? If not, please show an example where a finite state space may lead to an infinite search tree. Please also suggest solutions to avoid an infinite tree (1 pt) 1. 2. [2 pt] What are the four measures used to evaluate a search algorithm, please explain the definition of each measure (1.0 pt)? Please fill in the following table for the listed search algorithms (1 pt) Please use following symbols and use O0 notation for time and space complexities: b: branching factor & minimum step cost C* optimal path cost. s: depth of the shallowest solution. /: maximum depth of the search tree t: the depth limit Depth Limited Search nce Breath FirstDepth First Uniform Iterative Performa Measure Search Search Cost Search Deeping Search Complete? Optimal? Time Complexit Space Complexit

Explanation / Answer

1.

NO, finite state space doesnot always leads to finite search tree. A finite search space tree can lead to an infinite search tree if states are repeated i.e cyclic traversal, then it will lead to infinite search.

Example:

In the 8 puzzle, you can always return to the state of a node's parent by moving the empty tile back. By doing this, you can generate an infinite long chain of search nodes.

Solution:

Repeated states has to be avoided which can be achieved by using DAG i.e Direct Acyclic Graph.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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