Graph Search Methods

Question 1

How are costs reduced during graph searches?

Answer 1

-Nodes are not revisited
-search trees find optimal paths for the environment

Question 2

Functionality of the breadth-first search

Answer 2

Begins at the start node and explores local nodes
-from neighbouring nodes, explore unexplored nodes
-repeats until goal nodes are found

Question 3

Functionality of depth-first search

Question 4

Comparison of the Breadth-first and depth-first

Answer 4

-both used often for path searches
-both are simple to implement but might be inefficient
DFS:
-has lower memory footprint than BFS
-mainly used to completely explore a graph
BFS:
-faster computation

Question 5

Why would the star algorithms be used instead of BFS/DFS

Answer 5

BFS and DFS do not consider when the edges have weights
-Star algorithm can calculate the shortest path with the lowest cost

Question 5

Give the pros/cons of Dijkstra’s

Answer 5

PROs:
-considers weights of each node
-calculates shortest path and cost
-easy to implement

CONs:
-attention required on priortity queue
-not possible to determine if solution exists untul it reaches it

Question 5

Define A* algorithim

Answer 5

Dijkstra’s algorithm + heurisitc
-a heuristic function provides an optimistic estimate of how close the goal is
-improves efficiency of the Dijkstra algorithm

Question 6

Compare Dijkstra and A*

Answer 6

-A* is an extension of Dijkstras algorithm

Question 7

Define D* algorithm

Answer 7

-A variation of A* which resuses previous search effort for iterations
-it only tackles state effected by change

Question 8

Define RRTs

Answer 8

-Rapidly exploring random trees
-grow a graph online only requiring an obstacle map
-begins with an inital tree and succesively adds nodes closest to random points on graph

Question 9

Give the cons of RRTs

Answer 9

Lack optimality but the solution is eventually found as number of ndoes grows towards infinity