Optimization Flashcards
choosing the best option from a set of possible options.
Optimization
search algorithm that maintains a single node and searches by moving to a neighboring node
Local Search
a function that we use to maximize the value of the solution.
Objective Function
a function that we use to minimize the cost of the solution
Cost Function
the state that is currently being considered by the function.
Current State
a state that the current state can transition to.
Neighbor State
In this algorithm, the neighbor states are compared to the current state, and if any of them is better, we change the current node from the current state to that neighbor state.
Hill Climbing
a state that has a higher value than its neighboring states
A local maximum
a state that has the highest value of all states in the state-space.
global maximum
state that has a lower value than its neighboring states
local minimum
state that has the lowest value of all states in the state-space
global minimum
multiple states of equal value are adjacent, forming a plateau whose neighbors have a worse value
flat local maximum/minimum
multiple states of equal value are adjacent and the neighbors of the plateau can be both better and worse
shoulder
Variants of Hill Climbing
Steepest-ascent
Stochastic
First-choice
Random-restart
Local Beam Search
Variant that chooses the highest-valued neighbor.
Steepest-ascent
Variant that chooses randomly from higher-valued neighbors.
Stochastic
Variant that chooses the first higher-valued neighbor
First-choice
Variant that conduct hill climbing multiple times
Random-restart
Variant that chooses the k highest-valued neighbors.
Local Beam Search
allows the algorithm to “dislodge” itself if it gets stuck in a local maximum.
Simulated Annealing
the task is to connect all points while choosing the shortest possible distance.
Traveling Salesman Problem
a family of problems that optimize a linear equation
Linear Programming
Components of Linear Programming
Cost Function we want to minimze
Constraint represented as a sum of variables that is either less than or equal to a value
or precisely equal to this value
Individual bounds on variables
a class of problems where variables need to be assigned values while satisfying some conditions.
Constraint Satisfaction
Constraint Satisfaction properties
Set of Variables
Set of domains for each variable
Set of constraints C
a constraint that must be satisfied in a correct solution.
Hard Constraint
a constraint that expresses which solution is preferred over others.
Soft Constraint
a constraint that involves only one variable.
Unary Constraint
a constraint that involves two variables.
Binary Constraint
when all the values in a variable’s domain satisfy the variable’s unary constraints.
Node consistency
when all the values in a variable’s domain satisfy the variable’s binary constraints
Arc consistency
a type of a search algorithm that takes into account the structure of a constraint satisfaction search problem.
Backtracking search
This algorithm will enforce arc-consistency after every new assignment of the backtracking search.
Maintaining Arc-Consistency algorithm
ways to make the AC-3 algorithm more efficient
- MRV (Minimum Remaining Values) heuristic
- Degree heuristic
