Algoritmes Lecture 0 Flashcards
Search
Any problem a computer can face to search for something
Solving Search Problems
Initial state, action, goal test, path cost function
Node
Data Points that connect
Stack
Last in first out
Frontier first
Explorer set next
Depth First Search
An algorithm that always explores the deepest node
Breadth-First Search
Like DFS but, uses a queue
Queue
First in First out
Greedy Best-First Search
Goes to the node closes to the goal h(n)
Heuristic
Estimating
Manhattan Distance
Counts how many blocks from point A to point B
A* Search formula
h(n) + g(n)
h(n)= steps to reach the node g(n) = estimated cost to reach the goal
A* Search formula
Search for the nodes with the lowest value
Adversarial Search
Is used in games with an enemy like Tic Tac Toe
changing the state of the problem every step in a direction you do not want. Where you don’t control the next state. The opponent will change the next state in a way: unpredictable.
Minimax
Translating the games into numbers and trying to get the best outcome
Alpha-Beta Pruning
Uses the minimax algorithm to evaluate the best outcome in a search tree of two layers,
Depth-Limited Minimax
Works like dept first search using Minimax but limits itself after a certain amount of steps.
Evaluation Function
Checks over the game from a given state and try’s to give an estimate the expected utility.
Depth Limited Minimax Arrives At A Decision Faster Because Fewer Steps
Depth Limited Minimax Is The Same As Without, Sometimes Uses Less Memory
Depth Limited Minimax Makes More Optimal Decision By Not Exploring Suboptimal
Depth Limited Minimax Is Never Preferable To Minimax.
Search algorithms
