Informed Search Problems

Question 1

What is Uniform cost graph search?

Answer 1

If the action costs between varios states vary we can use this alorithm to find the minimum cost path to the goal

Question 2

How is uniform cost implamented?

Answer 2

> By arranging the fringe in order of cost from cheapest to the most expensive.
Then the cheapest node is tested first

Question 3

In uniform cost search what happens if there are 2 of the same states in the fringe?

Answer 3

> If we find there are 2 nodes that represent the same state, the one with the lower cost replaces the more expensive one

Question 4

In uniform cost search what happens if all the costs are the same?

Answer 4

> If the cost of all actions are the same then it is simply breadth first search

Question 5

What is the general procedure for uniform cost search with loop checking?

Answer 5

[FUNCTION UC_GRAPH SEARCH]
fringe[] += initial_state
explored[] = 0
[LOOP]
> IF fringe IS empy RETURN failure
> node_test = fringe[LOWEST COST]
> IF node_test == goal_state RETURN node_test
> explored[] += node_test
> add_fringe = Unexplored(node_test.children)
> fringe[] += add_fringe
> fringe[] = orderbycheapest(fringe)

Question 6

What is heuristic search?

Answer 6

> These are search algorithms that use information that is beyond the definition of the problem
Generally a heuristic search can tell how close it is to the goal state

Question 7

What is the cost function?

Answer 7

> g(n)

> This is the cost of node n from the start

Question 8

How is the cost function used in uniform search?

Answer 8

> In uniform cost, the node with the lowest g(n) is removed and tested first from the fringe

Question 9

What is the heuristic cost function?

Answer 9

> h(n)

> This is an estimate of the cost to go from the node n to the goal

Question 10

What is the greedy best-first algorithm?

Answer 10

The fringe queue is ordered based on the node with the lowest h(n)

Question 11

What is the A* alorithm?

Answer 11

The fringe queue is ordered based on the node with the lowest h(n) + g(n)

Question 12

What is the issue with using greedy best-first alorithm with this map when the goal is D?
[Picture 3]

Answer 12

Greedy best would say that the most optimal route would be A⇒B⇒D when in fact we see that the cost of B⇒D is large so the better route would be A⇒C⇒D.
A* would fix this issue

Question 13

What are the assumed conditions for A*?

Answer 13

> Each state in the search space has finitely many successors
All actions have a cost > 0
Admissibility: The heuristic function never overestimates the cost to a goal node
- Underestimating is fine
- If h(n) = 0 then it simply becomes uniform cost
A* will terminate with a minimal cost path to a goal (as long as everything above is correct)

Question 14

«»

Answer 14

sdfsdf