Algoritmes Lecture 0

Question 1

Search

Answer 1

Any problem a computer can face to search for something

Question 2

Solving Search Problems

Answer 2

Initial state, action, goal test, path cost function

Question 3

Node

Answer 3

Data Points that connect

Question 4

Stack

Answer 4

Last in first out

Question 5

Frontier first

Answer 5

Explorer set next

Question 6

Depth First Search

Answer 6

An algorithm that always explores the deepest node

Question 7

Breadth-First Search

Answer 7

Like DFS but, uses a queue

Question 8

Queue

Answer 8

First in First out

Question 9

Greedy Best-First Search

Answer 9

Goes to the node closes to the goal h(n)

Question 10

Heuristic

Answer 10

Estimating

Question 11

Manhattan Distance

Answer 11

Counts how many blocks from point A to point B

Question 12

A* Search formula

h(n) + g(n)

Answer 12

h(n)= steps to reach the node g(n) = estimated cost to reach the goal

Question 13

A* Search formula

Answer 13

Search for the nodes with the lowest value

Question 14

Adversarial Search

Answer 14

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.

Question 15

Minimax

Answer 15

Translating the games into numbers and trying to get the best outcome

Question 16

Alpha-Beta Pruning

Answer 16

Uses the minimax algorithm to evaluate the best outcome in a search tree of two layers,

Question 17

Depth-Limited Minimax

Answer 17

Works like dept first search using Minimax but limits itself after a certain amount of steps.

Question 18

Evaluation Function

Answer 18

Checks over the game from a given state and try’s to give an estimate the expected utility.

Question 19

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.

Answer 19

Search algorithms