Search Algorithms:
Informed vs. Uninformed Search:
Informed search uses additional information about the problem to more effectively search for a solution. This additional information can be used to estimate how good certain paths are compared to others, which generally results in more effective search.
Uninformed search uses no additional information other than the problem specification. This is generally slower and less effective than informed search.
What is a heuristic?
...
Depth First Search (DFS):
Depth first search is a very simple uninformed graph-traversal algorithm. With DFS we start at the root or “start” position and traverse one path completely before backtracking and exploring other paths.
A common example of DFS is the Sudoku brute-force algorithm. It will pick one number for a square, and explore deep, until it is no longer possible to choose a valid value, then we backtrack.
DFS does not work well for finding the shortest path.
Breadth First Search (BFS):
Breath first search is somewhat similar to DFS, the difference is that BFS searches the level completely before moving on, while DFS searches a path completely before moving on. BFS is also uninformed.
BFS may be used to find the shortest path in a graph or tree structure.
Greedy Search:
...
A-star (A*)
A* is by far the most effective search algorithm we have explored in this course. One of the reasons for this, is that A* is an informed search algorithm. This means that the algorithm uses heuristics to create a priority-queue for nodes it should explore.
A heuristic is an estimated value that helps the algorithm effectively choose what nodes to explore next. A heuristic is admissible as long as it does NOT overestimate, that will break the algorithm.
Constraint Satisfaction Problems:
Work in progress.
Will exten on this later.