Lecture SIX.

What is the basic idea of a search algorithm?

• It takes a problem as an input and returns a solution in the form of an action sequence.

• It always finds a solution with a minimal number of actions.

• It uses knowledge for the searching process.

• It expands the deepest node first.

Each NODE in in the search tree is an entire PATH in the problem graph.

• True

• False

What is the state space?

• describes the sequence of actions, and the root of the tree corresponds to the initial state of the problem.

• describes the set of states in the world, and the actions that allow transitions from one state to another.

• describes each node in the tree has a unique path back to the root.

• describes paths between these states, reaching towards the goal.

What is the search tree?

• describes the sequence of actions, and the root of the tree corresponds to the initial state of the problem.

• describes the set of states in the world, and the actions that allow transitions from one state to another.

• describes each node in the tree has many paths back to the root.

• describes paths between these states, reaching towards the goal.

Each node in the tree has a many paths back to the root.

• True

• False

Answer explanation

Each node in the tree has a unique path back to the root.

What are the properties of search strategies/algorithms ?

• 1. 1. completeness.

  2. 2. optimality.
     3. time complexity.

  3. 4. space complexity.

• 1. 1. completeness.

  2. 2. optimality.
     3. cost complexity.

  3. 4. space complexity.

• 1. 1. BFS.

  2. 2. DFS.
     3. AI complexity.

  3. 4. cost complexity.

• 1. 1. color.

  2. size.
  3. shape

Define "Optimality" in Search Strategies' properties.

• Is the algorithm guaranteed to find a solution when there is one?

• Does the strategy find the optimal solution?

• How long does it take to find a solution?

• How much memory is needed to perform the search?

Define "Time complexity" in Search Strategies' properties.

• Is the algorithm guaranteed to find a solution when there is one?

• Does the strategy find the optimal solution?

• How long does it take to find a solution?

• How much memory is needed to perform the search?

Define "Space complexity" in Search Strategies' properties.

• Is the algorithm guaranteed to find a solution when there is one?

• Does the strategy find the optimal solution?

• How long does it take to find a solution?

• How much memory is needed to perform the search?

Define "Completeness" in Search Strategies' properties.

• Is the algorithm guaranteed to find a solution when there is one?

• Does the strategy find the optimal solution?

• How long does it take to find a solution?

• How much memory is needed to perform the search?