Uninformed Search Problems

Question 1

What are the two types of search algorithms?

Answer 1

> Uninformed search: Each State has no additional information
Informed search: Each state has some information about how far the goal state could be

Question 2

What is a search tree? Why is it called a tree? How is it given?

Answer 2

> It is a route for all the posible solutions
It starts at the root node and terminates at the leaf nodes
It is not explicitly given but is worked out as the search develops

Question 3

What is a state?

Answer 3

> This is a representation of a physical configuration

> e.g. A city on a train map

Question 4

What is a node? What does it represent and what information does it include?

Answer 4

> This is a data structure constituting part of a search tree
It includes the parent node, the children nodes, the depth
It represents a state. A state ≠ node

Question 5

Why does a state ≠ node?

Answer 5

Because multiple nodes might represent the same state.

Each node representing the same state will have a different path / depth etc

Question 6

What is the initial state?

Answer 6

this is the state that the problem starts at

Question 7

What is the goal state?

Answer 7

This is the state that the problem is aiming to get towards

Question 8

How can we analyse a problem into a search probelm?

Answer 8

> Conceptualise possible solutions and intermediate stages towards a solution
Identify the inital state
Identify the goal states
Possible actions: Identify transitions that allow a state to be transformed into other successor states
Devise an alorithm that will systematically search through possible paths from the inital state in order to find a path that ends in a goal

Question 9

What is a path cost?

Answer 9

This is the sum of all costs asiated with transitioning between states (between nodes).

Question 10

What is the fringe array?

Answer 10

This is a queue of all nodes that have been found but not processed

Question 11

What is the explored array?

Answer 11

This is a collection of all the processed nodes

Question 12

What are 2 main types of uninformed search?

Answer 12

> Breadth-frist search

> Depth-first search

Question 13

What is breadth-first search?

Answer 13

This is where you always search the node with the smallest depth
[Picture1]

Question 14

How is breadth-first search done?

Answer 14

> This is achieved with a First-in-first-out (FIFO) queue.

> The earliest node to be found and added to the fringe is the next one to be explored

Question 15

How is a node removed from the fringe?

Answer 15

After it has been explored, it will be removed from the queue and added to the explored array.

Question 16

How does a FIFO queue cause the search to be breadth first?

Answer 16

Because the nodes with the smallest depth are explored first before the deeper nodes as they are descovered first

Question 17

What is depth-first search?

Answer 17

This is where you always search the node with the greatest depth
[Picture2]

Question 18

How is depth-frist search done?

Answer 18

> This is achieved with a Last-in-first-out (LIFO) queue.

> The most recent node to be found and added to the fringe is the next one to be explored

Question 19

How is a node removed from the fringe?

Answer 19

After it has been explored, it will be removed from the queue and added to the explored array.

Question 20

How does a LIFO queue cause the search to be breadth first?

Answer 20

The nodes with the greatest depth are explored first before the deeper nodes as they are discovered most recently

Question 21

What is the general procedure for an uninformed tree search?

Answer 21

[FUNCTION TREE_SEARCH]
fringe += initial_state
[LOOP]
> IF fringe IS empty RETURN failure
> node_test = fringe[LIFO/FIFO]
> fringe.remove(node_test)
> IF node_test == goal_state RETURN node_test
> fringe += node_test.children

Question 22

What is loop testing?

Answer 22

> This essentially adds a new array of all states that have been checked already.
Before a node is added to the fringe, it is checked to see if that state it already represents has been checked or not. This prevents loop issues

Question 23

What is the general procedure for an uninformed tree search with loop checking?

Answer 23

[FUNCTION TREE_SEARCH]
fringe[] += initial_state
[LOOP]
> IF fringe[] IS empty RETURN failure
> node_test = fringe[LIFO/FIFO]
> fringe.remove(node_test)
> IF node_test == goal_state RETURN node_test
> explored[] += node_test
> add_fringe = Unexplored(node_test.children)
> fringe[] += add_fringe

Question 24

What are methods of evaluating a search strategy?

Answer 24

> Completeness: Does it always find a solution (if one exists)
Time complexity: The number of nodes traversed until a goal
Space complexity: Largest number of nodes the fringe can store
Optimally: Does it always find the least-cost solution

Question 25

How can time and space complexity be measured?

Answer 25

b = Maximum branching factor of the search tree
d = depth of the least cost solution
m = maximum depth of the state space (may be ∞)

Question 26

Evaluate breadth-first search

Answer 26

> Completenes: Yes (if b (branching factor) is finite)
Time = 1 + b + b^2 + … + b^d = O(b^d)
Space = O(b^(d+1))
Optimal: Yes (if cost = q per step), but not optimal in general

Question 27

Evaluate depth-first search

Answer 27

> Completness: No, fails in infinite-depth spaces
Time = O(b^m)
Space = O(bm) linear space
Optimal: No