OPTIMIZATION

Question 1

choosing the best option from a set of possible options

Answer 1

Optimization

Question 2

a search algorithm that maintains a single node and searches by moving to a neighboring node.

Answer 2

local search

Question 3

a function that we use to maximize the value of the solution.

Answer 3

objective function

Question 4

a function that we use to minimize the cost of the solution

Answer 4

cost function

Question 5

the state that is currently being considered by the function

Answer 5

current state

Question 6

a state that the current state can transition to

Answer 6

neighbor state

Question 7

one type of a local search algorithm

Answer 7

hill climbing

Question 8

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.

Answer 8

hill climbing

Question 9

hill climbing pseudocode

Answer 9

function Hill-Climb(problem):

current = initial state of problem
repeat:
neighbor = best valued neighbor of current
if neighbor not better than current:
return current
current = neighbor

Question 10

a state that has a higher value than its neighboring states

Answer 10

local maximum (plural: maxima)

Question 11

a state that has the highest value of all states in the state-space.

Answer 11

global maximum

Question 12

a state that has a lower value than its neighboring states.

Answer 12

local minimum (plural: minima)

Question 13

a state that has the lowest value of all states in the state-space.

Answer 13

global minimum

Question 14

problem with hill climbing

Answer 14

they may end up in local minima and maxima

Question 15

multiple states of equal value are adjacent, forming a plateau whose neighbors have a worse value

Answer 15

flat local maximum/minimum

Question 16

where multiple states of equal value are adjacent and the neighbors of the plateau can be both better and worse

Answer 16

shoulder

Question 17

hill climbing variants

Answer 17

Steepest-ascent
Stochastic
First-choice
Random-restart
Local Beam Search

Question 18

choose the highest-valued neighbor

Answer 18

Steepest-ascent

Question 19

choose randomly from higher-valued neighbors

Answer 19

stochastic

Question 20

choose the first higher-valued neighbor

Answer 20

First-choice

Question 21

conduct hill climbing multiple times

Answer 21

random-restart

Question 22

chooses the k highest-valued neighbors

Answer 22

local beam search

Question 23

allows the algorithm to “dislodge” itself if it gets stuck in a local maximum.

Answer 23

Simulated annealing

Question 24

simulated annealing algorithm

Answer 24

starts with a high temperature, being more likely to make random decisions, and, as the temperature decreases, it becomes less likely to make random decisions, becoming more “firm.” This mechanism allows the algorithm to change its state to a neighbor that’s worse than the current state, which is how it can escape from local maxima.

Question 25

simulated-annealing pseudocode

Answer 25

function Simulated-Annealing(problem, max): current = initial state of problem for t = 1 to max: T = Temperature(t) neighbor = random neighbor of current ΔE = how much better neighbor is than current if ΔE > 0: current = neighbor with probability e^(ΔE/T) set current = neighbor return current

Question 26

a family of problems that optimize a linear equation

Answer 26

linear programming

Question 27

Linear programming will have the following components:

Answer 27

- A cost function that we want to minimize - A constraint that’s represented as a sum of variables that is either less than or equal to a value - Individual bounds on variables of the form lᵢ ≤ xᵢ ≤ uᵢ.

Question 28

a class of problems where variables need to be assigned values while satisfying some conditions.

Answer 28

constraint satisfaction problems

Question 29

Constraints satisfaction problems have the following properties:

Answer 29

- Set of variables (x₁, x₂, …, xₙ) - Set of domains for each variable {D₁, D₂, …, Dₙ} - Set of constraints C

Question 30

a constraint that must be satisfied in a correct solution.

Answer 30

hard constraint

Question 31

a constraint that expresses which solution is preferred over others.

Answer 31

soft constraint

Question 32

a constraint that involves only one variable

Answer 32

unary constraint

Question 33

a constraint that involves two variables

Answer 33

binary constraint

Question 34

when all the values in a variable’s domain satisfy the variable’s unary constraints.

Answer 34

node consistency

Question 35

when all the values in a variable’s domain satisfy the variable’s binary constraints

Answer 35

arc consistency

Question 36

revise pseudocode

Answer 36

function Revise(csp, X, Y): revised = false for x in X.domain: if no y in Y.domain satisfies constraint for (X,Y): delete x from X.domain revised = true return revised

Question 37

ac-3 which uses revise pseudocode

Answer 37

function AC-3(csp): queue = all arcs in csp while queue non-empty: (X, Y) = Dequeue(queue) if Revise(csp, X, Y): if size of X.domain == 0: return false for each Z in X.neighbors - {Y}: Enqueue(queue, (Z,X)) return true

Question 38

a type of a search algorithm that takes into account the structure of a constraint satisfaction search problem

Answer 38

backtracking search

Question 39

it is a recursive function that attempts to continue assigning values as long as they satisfy the constraints. If constraints are violated, it tries a different assignment

Answer 39

backtracking search

Question 40

backtrack pseudocode

Answer 40

function Backtrack(assignment, csp): if assignment complete: return assignment var = Select-Unassigned-Var(assignment, csp) for value in Domain-Values(var, assignment, csp): if value consistent with assignment: add {var = value} to assignment result = Backtrack(assignment, csp) if result ≠ failure: return result remove {var = value} from assignment return failure

Question 41

interleaving backtracking search with inference (enforcing arc consistency), so we can get at a more efficient algorithm.

Answer 41

Maintaining Arc-Consistency algorithm

Question 42

This algorithm will enforce arc-consistency after every new assignment of the backtracking search.

Answer 42

Maintaining Arc-Consistency algorithm

Question 43

Backtrack algorithm that maintains arc-consistency pseudocode:

Answer 43

function Backtrack(assignment, csp): if assignment complete: return assignment var = Select-Unassigned-Var(assignment, csp) for value in Domain-Values(var, assignment, csp): if value consistent with assignment: add {var = value} to assignment inferences = Inference(assignment, csp) if inferences ≠ failure: add inferences to assignment result = Backtrack(assignment, csp) if result ≠ failure: return result remove {var = value} and inferences from assignment return failure

Question 44

types of heuristic

Answer 44

minimum remaining values heuristic degree heuristic least constraining values heuristic

Question 45

For which of the following will you always find the same solution, even if you re-run the algorithm multiple times? Assume a problem where the goal is to minimize a cost function, and every state in the state space has a different cost.

Answer 45

Steepest-ascent hill-climbing, each time starting from the same starting state

Question 46

Consider this optimization problem: A farmer is trying to plant two crops, Crop 1 and Crop 2, and wants to maximize his profits. The farmer will make $500 in profit from each acre of Crop 1 planted, and will make $400 in profit from each acre of Crop 2 planted. However, the farmer needs to do all of his planting today, during the 12 hours between 7am and 7pm. Planting an acre of Crop 1 takes 3 hours, and planting an acre of Crop 2 takes 2 hours. The farmer is also limited in terms of supplies: he has enough supplies to plant 10 acres of Crop 1 and enough supplies to plant 4 acres of Crop 2. Assume the variable C1 represents the number of acres of Crop 1 to plant, and the variable C2 represents the number of acres of Crop 2 to plant.

Answer 46

500 * C1 + 400 * C2

Question 47

Consider the same optimization problem as in Question 2. What are the constraints for this problem?

Answer 47

3 * C1 + 2 * C2 <= 12; C1 <= 10; C2 <= 4

Question 48

Consider the below exam scheduling constraint satisfaction graph, where each node represents a course. Each course is associated with an initial domain of possible exam days (most courses could be on Monday, Tuesday, or Wednesday; a few are already restricted to just a single day). An edge between two nodes means that those two classes must have exams on different days. After enforcing arc consistency on this entire problem, what are the resulting domains for the variables C, D, and E?

Answer 48

C’s domain is {Mon}, D’s domain is {Mon, Wed}, E’s domain is {Tue, Wed}