Solving problems by search

Question 1

What is meant by a problem solving agent?

Answer 1

An agent that considers a sequence of actions to reach a goal.

Question 2

What is the purpose of a goal formulation?

Answer 2

Determining whether a problem solving agent has solved the problem.

Question 3

What is a problem formulation?

Answer 3

A description of the states and actions necessary to reach the goal.

Question 4

What is meant by search in the context of search problems?

Answer 4

The act of simulating sequences of actions to reach a goal.

Question 5

What are the six parts of a search problem?

Answer 5

1. State space (Set of possible states the environment can be in)
2. Initial state
3. Goal state(s)
4. Actions from a given state.
5. Transition model (RESULT): Describes what each action does.
6. Action cost function. Used for comparing solutions.

Question 6

What does the nodes of a search tree represent?

Answer 6

States.

Question 7

What does the edges of a search tree represent?

Answer 7

Actions

Question 8

What is the difference between a state space and a search tree.

Answer 8

In a search tree, each node has a unique path back to the root node.

The state space describes the set of states, and the actions that allow transitions between different states.

Question 9

What is a frontier in the context of search problems?

Answer 9

The set of all unexpanded nodes.

Question 10

List the different types of queues used in frontiers.

Answer 10

Priority queue: first pops node with minimum cost. Used in best-first search

FIFO: Pops the node that was added to the queue first (normal queue). Used in BFS.

LIFO (stack): pops first the most recently added node. Used in DFS.

Question 11

List different ways to deal with redundant paths in search trees.

Answer 11

Remember previously reached states, allowing detected reudundant paths to be eliminated.

Don’t worry about them. Can in some cases save memory.

Check for cycles, but not redundant paths. This is done by following the chain of parent nodes, to check whether a node appears multiple times.

Question 12

What is the difference between graph search and tree-like search

Answer 12

Graph search: Checks redundant paths.

Tree-Like search: Doesn’t check redundant paths.

Question 13

List ways to measure problem-solving performance of search-algorithms

Answer 13

Completeness: Garanteed to find a solution.

Cost optimality: Finds a solution with lowest possible path cost.

Time complexity: Time it takes to find solution.

Space complexity: Memory used.