CAP4630 Introduction to Artificial Intelligence Homework 2 (7 pts, Due Sep 22 20

Question

CAP4630 Introduction to Artificial Intelligence Homework 2 (7 pts, Due Sep 22 2018) [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 I. avoid an infinite tree (1 pt) 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 O) notation for time and space complexities: b: branching factor. c minimum step cost. C* optimal path cost s: depth of the shallowest solution I: maximum depth of the search tree t: the depth limit PerformanceBreath FirstDepth First Uniform Measure Iterative Depth- Limited Search Search Search Cost Search Deeping Search Complete? Optimal? ime Complexi Space Complexi

Explanation / Answer

Will a finite state space always leads to a finite search tree?

NO. If there are repeated states 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 C
• Subjects

---

---

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