Goal: IntroducTREE lesson.
A* Search and Best First Search add heuristics to optimize solving problems similar to mazes. They both utilize Priority Queue, in which every thing in the queue is assigned a priority somehow.In Best First search, you would always choose the spot in the frontier with the minimal distance to the end of the maze.
In A* Search, you would always choose the spot with the minimal total distance(steps already taken + distance to end of maze) to the end of the maze
using the priority from A*: (distance to goal + moves so far) will guarantee optimal solution.
This is because:
(distance so far + theoretical number of moves to goal) is best case solution that includes the current node.
I took 10 steps, the goal is 10 more steps away(at least). That means this position has at least 20 steps to reach the goal.
When I prioritize the spaces that have the lowest theoretical number of steps,
I will never pass up a better possible solution elsewhere.
root - node at top from which all other nodes can be reached
parent/child - the parent points to the child(ren); nodes can have at most one parent but a parent can have many children
full binary tree a tree where every node except the leaves have 2 children
taxonaTREE * = will be implemented by you