Search Resources
Codecademy https://www.codecademy.com/about has a list of AI search algorithms.
University of California Berkeley, CS 188 Intro to AI course had useful slides on search, https://inst.eecs.berkeley.edu/~cs188/sp20/
Uninformed Search
- Depth-first search (DFS)
- Breadth-first search (BFS)
- Iterative deepening search
References
Vincent Conitzer and Aditi Raghunathan. 2023. 15-281 Artificial Intelligence: Representation and Problem Solving Course. Carnegie Mellon University, School of Computer Science.
- Lecture slides https://www.cs.cmu.edu/~15281/lectures/15281_Fa23_Lecture_2_Agents_and_Uninformed_Search.pdf
Andrew Joseph Davies. 2022. Breadth-First Search, Depth-First Search, Dijakras and A* Pathfinding Algorithms in Python. Codex. Medium. https://medium.com/codex/python-project-idea-graph-traversal-and-pathfinding-algorithm-visualisations-99595c414293
Bryan Gibson, Ph.D., principal data scientist https://www.linkedin.com/in/bryanrgibson/, former instructor at University of Wisconsin-Madison https://pages.cs.wisc.edu/~bgibson/
- Lecture slides from CS 540 course at University of Wisonson-Madison https://pages.cs.wisc.edu/~bgibson/cs540/handouts/uninformed_search.pdf
Mussmann, Steve, and Abi See. n.d. Graph Search Algorithms. https://cs.stanford.edu/people/abisee/gs.pdf.
Informed Search
frontier data structure is a priority queue
- Uniform cost search
- Select node n with the lowest cost
g(n), summ of the costs of the edges in the path from source to n
- Select node n with the lowest cost
- Best-first search
- Greedy search (or best-first search)
- Select node n with the lowest estimated cost from n to the goal,
h(n)
- Select node n with the lowest estimated cost from n to the goal,
- A* search
- Select node the lowest-cost node n that has the lowest estimated cost from n to the goal,
f(n) = g(n) + h(n)
- Select node the lowest-cost node n that has the lowest estimated cost from n to the goal,
- Greedy search (or best-first search)
References
Vincent Conitzer and Aditi Raghunathan. 2023. 15-281 Artificial Intelligence: Representation and Problem Solving Course. Carnegie Mellon University, School of Computer Science.
Anthony Rhodes, senior research scientist (https://www.linkedin.com/in/anthonydrhodes/)
- Lecture slides: https://web.pdx.edu/~arhodes/ai8.pdf
Mussmann, Steve, and Abi See. n.d. Graph Search Algorithms. https://cs.stanford.edu/people/abisee/gs.pdf.
Great Learning Team. 2022. Best First Search Algorithm in AI | Concept, Implementation, Advantages, Disadvantages. Great Learning Blog. Great Learning Educational Services Private. Limited. https://www.mygreatlearning.com/blog/best-first-search-bfs/
Search Example
See search example and use it to trace uninformed and informed search algorithms.
Local Search
- Hill climbing
- Random walk
- Simulated annealing
References
Harvard University. 2023. CS50 Intro to AI - Lecture 3 Local Search. https://cs50.harvard.edu/ai/2023/notes/3/
Vincent Conitzer and Aditi Raghunathan. 2023. 15-281 Artificial Intelligence: Representation and Problem Solving Course. Carnegie Mellon University, School of Computer Science.
Course https://www.cs.cmu.edu/~15281/coursenotes/localsearch/
Lecture slides: https://www.cs.cmu.edu/~15281/lectures/15281_Fa23_Lecture_6_Local_Search.pdf
Anthony Rhodes, senior research scientist (https://www.linkedin.com/in/anthonydrhodes/)
- Lecture slides: https://web.pdx.edu/~arhodes/ai9.pdf
Adversial Search
- Mini-max
- Alpha-pruning
- Monte Carlo tree search
References
Mayefsky, Eric, Francine Anene, and Marina Sirota. 2003. Strategies and Tactics for Intelligent Search: MiniMax and Alpha-Beta Pruning.
Philip Muens. 2021. Minimax and Monte Carlo Tree Search. https://philippmuens.com/minimax-and-mcts
Ben Mitchell. 2020. TCS drawbacks. CS63 Artificial Intelligence, Swarthmore CollegeM https://www.cs.swarthmore.edu/~mitchell/classes/cs63/f20/reading/mcts.html
- GitHub web page https://ai-boson.github.io/mcts/
Keyon, Morgan. 2020. SharperDeve Blog. Coding a perfect Tic-Tac-Toe Bot. https://thesharperdev.com/coding-the-perfect-tic-tac-toe-bot/
GitHub repo https://github.com/morgankenyon/RandomML/tree/master/src/tictactoe
Morgan Keyon’s LinkedIn https://www.linkedin.com/in/morgan-kenyon/
Cruz, Clederson. 2019. Tic-Tac-Tow mini–max. GitHub. https://github.com/Cledersonbc/tic-tac-toe-minimax/tree/master
- Clederson Cruz’s LinkedIn https://www.linkedin.com/in/clederson-cruz/?locale=en_US
Machine Learning Search
Stochastic Gradient Descent
Mirko Stojiljković. 2021. Stochastic Gradient Descent Algorithm With Python and NumPy. Real Python. https://realpython.com/gradient-descent-algorithm-python/
Other Optimization Algorithms: Dynamic Programming
MIT Courseware. 2011. Lecture 19: Dynamic Programming: Fibonacci and Shortest Path. Instructor: Erik Demaine. https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-19-dynamic-programming-i-fibonacci-shortest-paths/.