Tag: search
24. Reviews and Exercises
In this post are gathered the tutorials and exercises, called “mega-recitations”, to apply the concepts presented in the Artificial Intelligence course of Prof. Patrick Winston.
8. Constraints: Search, Domain Reduction
https://www.youtube.com/watch?v=d1KyYyLmGpA Domain Reduction Algorithm Vocabulary Variable v: something that can have an assignment Value x: something that can be assigned Domain d: set of all different values Constraint c: limit on variable values With a depth-first search, the domain reduction algorithm goes back up one node when it is unable to comply with a constraint. It…
6. Search: Games, Minimax, and Alpha-Beta
How a computer can play games (like Chess) How human play chess: mixing analysis, strategy, tactics to choose a move If-Then rules Look ahead and evaluate British museum algorithm To evaluate the potential of the next situation of the board, (methods 2 and 3) we can use a linear scoring polynomial to give number to…
5. Search: Optimal, Branch and Bound, A*
Optimal search trees Finding the best possible sequence of choices. Getting closer to the goal is generally considered good, but it may lead to dead ends or non-optimal choices. Oracle Knowing the minimum path length to the goal, the search algorithm records the length of path already extended and always extends the shortest path first until…
4. Search: Depth-First, Hill Climbing, Beam
Search trees Search trees represent all the possibilities to search for the quickest path without coming back to previous paths. They are particularly used for quickest paths on maps with nodes (intersections), but not exclusively. They are primarily about choices, and finding the best sequence of choices. British Museum Algorithm = complete expansion of all paths Depth…