2016-04-13

posted Apr 13, 2016, 8:53 AM by Samuel Konstantinovich   [ updated Apr 14, 2016, 8:39 AM ]

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.

e.g.

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.


Tree


terminoloTREE

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                                                 


complete binary tree  a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.?


taxonaTREE * = will be implemented by you

  • binary tree*

  • ternary tree

  • quad tree

  • binary search tree*

  • splay tree

  • red black tree

  • heap*

Comments