Puzzles and Search

Question 1

What is necessary when defining a search problem?

Answer 1

• state description: an abstract representation of the current state of the puzzle
• goal function: checks whether a state description satisfies the goal

Question 2

What is a state space, in the context of a search problem?

Answer 2

a collection of all state descriptions of a puzzle

Question 3

What is a Simple Exhaustive Search? How does it work?

Answer 3

it means you try out every single possible state of a puzzle and check them all with the goal function. you don’t use heuristics, nor constraints to reduce the number of states.
you do this until you’ve found the solution or until all states have been checked (if all have been checked and non satisfy the goal function, then there is no solution to the puzzle).

Question 4

What is a Local Search? How does it work?

Answer 4

you choose one state and try to improve it by maximizing a heuristic evaluation. similar to solving a puzzle by hand.
if you keep track of the solutions you’ve tried, you will either find a solution or the certainty that there is not solution. without keeping track, if there is no solution, the program might run forever.

Question 5

What are the advantages of the Local Search?

Answer 5

• uses very little memory
• quick

Question 6

What are the disadvantages of the Local Search?

Answer 6

• no guarantee for completeness (unless you keep track of the tried solutions)
• no guarantee for optimality (that best/shortest solution is found)

Question 7

What is the 8 Queen Problem?

Answer 7

it’s a puzzle where you need to put 8 queens on a chess board.
considering that a queen can move any number of tiles in horizontal, vertical and diagonal direction, all queens must be placed without them being in the hit-path of any of the other 7 queens.

Question 8

What is an heuristic?

Answer 8

comes from the greek. is like a “rule of thumb”, some knowledge that may be helpful in solving a puzzle. they can also go wrong though.

in search algorithms, it’s often a function that estimates how close to the goal a certain state is.

Question 9

On the example of the 8-Queens-Problem, how does the basic idea of an heuristic work?

Answer 9

heuristic = the number of queens, that are in each others hit paths is calculated for each state.
the algorithm follows the state where the heuristic is getting smaller until it reaches the goal (zero).

Question 10

What is a different name for Hill-climbing Search?

Answer 10

Greedy Local Search

Question 11

How does the Hill-Climbing Search work?

Answer 11

starting with the current state, the algorithm calculates all possible states that can exist, if one move is made. from these possible states it chooses the one with the higher evaluation (the best one). it does this until all possible future states would be worse than the current one.

Question 12

What is the main problem of the Hill-Climbing Search?

Answer 12

Local Optima: the algorithm stops as soon as it has reached the top of a hill, even if it isn’t the highest hill there is.

Question 13

What is Random Restart Hill-Climbing?

Answer 13

its a randomized variant of the Hill-Climbing Search. once the algorithm has reached a top, it starts again with a different starting position. after x iterations of this, a solution should be found.

Question 14

What is Stochastic Hill-Climbing?

Answer 14

it is a randomized variant of the Hill-Climbing Search. Instead of always moving the the state with the best evaluation, you select a random state to move to.

Question 15

What is a Beam Search? How does it work?

Answer 15

it is similar to the Hill-Climbing Search, but instead of moving to the one best possible future state, the algorithm moves to the k best possible future states.
k = number of states it should move to = beam size
the information from different beams is combined.

Question 16

What is a problem of the Beam Search?

Answer 16

it suffers from lack of diversity of the k-number of states.
means: if one state has better successors, it’s chosen more often than other states.
therefore, it is often no more effective than Hill-Climbing

Question 17

What is Stochastic Beam Search?

Answer 17

randomized variant of the Beam Search. it chooses k-number of successors at random.

Question 18

What does the term “Annealing” mean? Where does it come from?

Answer 18

it’s comes from metallurgy and material science. it’s a heat treatment of materials to change its properties like strength and hardness, and then cooling it very slowly.

Question 19

What is Simulated Annealing Search? How does it work?

Answer 19

the idea is to escape local maxima by throwing in random moves. the frequency of the random moves gradually decreases.
used in VLSI layouts, airline scheduling,…

Question 20

What is a Genetic Algorithm? How does it work?

Answer 20

similar to Stochastic Beam Search, except that new nodes always have two predecessors.

• the algorithm starts with k-amount of randomly generated states (population).
• each state is represented as a string and evaluated by a fitness function (how fit is this state? how close to the goal?)
• the next generation of states is produced by selection, cross-over, and mutation.

Question 21

In regards to Genetic Algorithms, what is Selection?

Answer 21

basically: best one wins.
two possible future states are compared, the better one is moved to.

Question 22

In regards of Genetic Algorithms, what is Mutation?

Answer 22

the next state is generated by taking one parent state and modifing a random value.

comparable to a stochastic hill-climbing step.

Question 23

In regards to Genetic Algorithms, what is Cross-Over?

Answer 23

the next state is generated by taking both parent strings, cutting them at a cross-over point and recombining the pieces.

Question 24

What are the advantages of Genetic Algorithms?

Answer 24

they are popular, easy to implement, easy to explain, perform well (other randomized algorithms perform equally well or better)

Question 25

Who popularized Genetic Programming?

Answer 25

John R Koza

Question 26

Who is John R Koza?

Answer 26

he popularized Genetic Programming

Question 27

What is Genetic Programming?

Answer 27

applies Genetic Algorithms to program trees, and added special operations like inventing/deleting a subroutine, deleting/adding an argument,…

Question 28

What are the Towers of Hanoi?

Answer 28

it’s a mathematical puzzle by Eduoard Lucas, where a number of disks need to be placed from one peg to another. only one disk at a time may be moved. every disk may only be place on top of a bigger disk or the table.

Question 29

What is Divide-and-Conquer in regards to problem solving?

Answer 29

strategy with many applications.

basic idea:
* divide the problem into simpler partial problems
* solve the simpler problems (possibly again by division (=recursive programming))
* combine the partial solutions

Question 30

What are Constraint Satisfaction Problems?

Answer 30

they’re a special type of search problem, where
* the state is defined by variables X with d values from Domain D
* the goal test is a set of constraints specifying allowable combinations of values for subsets of variables

Question 31

What are some examples of Constraint Satisfaction Problems in the real world?

Answer 31

• assignment problems (who teaches what class?)
• timetable problems (which class is offered when and where?)
• hardware configuration
• spreadsheets
• job scheduling (constraints are start and end times for each job)
• transportation scheduling
• floor planning
  *…

Question 32

What is a Constraint Graph?

Answer 32

visual representation of a state in a Constraint Satisfaction Problem.
* nodes are variables
* edges are constraints between nodes

Question 33

What types of constraints are there for the Constraint Satisfaction Problem?

Answer 33

• unary: involves one variable
• binary: involves a pair of variables
• higher-order: involves 3 or more variables

Question 34

What are hard and soft constraints (in Constraint Satisfaction Problems)?

Answer 34

• soft constraint (preferences): not binding but and many as possible need to be respected –> constrained optimization problems
• hard constraints: have to be satisfied

Question 35

When solving Constraint Satisfaction Problems, how does the principle of Search work?

Answer 35

• assign value to one variable
• check if the constraints are satisfied
• if yes: assign value to next variable and check again
• if not: try a different value and check again. if all values were tried and failed, go back one variable and try a different value there. check again (backtrack)

Question 36

When solving Constraint Satisfaction Problems, how does the principle of Constraint Propagation work?

Answer 36

• maintain a set of possible values D for each variable X
• try to reduce the size of D by identifying values that violate constraints

Question 37

How do you calculate the number of possibilities in Naive Search?

Answer 37

Assumptions:
* we have n variables
* all solutions are at depth n in the search tree
* all variables have v possible values

Then:
* there are n! * (v^n) possibilities to go through before finding the solution

Question 38

How can the complexity of Naive Search be reduced?

Answer 38

with Commutative Variable Assignments.
if we already checked if a = blue and b = red violates any constraints, then we don’t have to check if a = red and b = blue violates any.
total complexity of search tree reduces to v^n.

Question 39

What is Backtracking Search?

Answer 39

it’s the basic search algorithm for Constraint Satisfaction Problems.
* assign value to one variable
* check if the constraints are satisfied
* if yes: assign value to next variable and check again
* if not: try a different value and check again. if all values were tried and failed, go back one variable and try a different value there. check again (backtrack)

domain-independent heuristics for selecting variables and for ordering values can improve practical performance.

Question 40

What types of heuristics are there for Constraint Satisfaction Problems?

Answer 40

• domain-specific heuristics: depend on the particular characteristics of the puzzle
• general-purpose heuristics: should work for all kinds of CSPs

Question 41

What types of General-purpose heuristics are there?

Answer 41

• minimum remaining values heuristic: choose the variable with the fewest consistent values
• degree heuristic: choose the variable with the most constraints on the other variables
• least constraining value heuristic: for a variable, choose the value that rules out the fewest values in the other variables

Question 42

What is Constraint Propagation?

Answer 42

the passing on of constraint information (if I put value 3 to variable x, how does that effect other variables and their possible values?)

example Sudoku: if I put a 3 in this box, i can’t put a 3 in any box in the same row, column or square.

Question 43

What is Node Consistency?

Answer 43

• all possible values of a variable must conform to all unary constraints

Example Sudoku: some boxes are already filled out, they are constrained to a single value

Question 44

What is Local Consistency?

Answer 44

making each node in the constraint graph consistent with its neighbors by iteratively enforcing the constraints corresponding to the edges

Question 45

What is Forward Checking?

Answer 45

while choosing values for variables, keep track of the remaining valid values for other variables.
terminate search when any variable has no more valid values.

Question 46

What is Arc Consistency?

Answer 46

every domain must be consistent with the neighbors:

a variable x(i) is arc-constistent with a variable x(j) if
* for every value in its domain D(i)
* there is some value in D(j)
* that satisfies the constraint on the arc ( X(i), X(j) )

after each new assignment of a value to a variable, possible values of the neighbors have to be updated and again, their neighbors need to be checked too because they might have lost a possible value as well.

Question 47

What is Min-Conflicts Heuristic?

Answer 47

• randomly select a conflicted variable
• choose the value that violates the fewest constraints