Puzzles and Search

Select a square (or a set of squares) –> heuristics

check all possibilities for the selected square(s) –> constraint satisfaction

propagate the information to other squares –> constraint propagation

repeat these steps until the solution is complete –> search

State description

• An abstract representation of the current state of a puzzle

• set of all such representations is called state space

Goal function –> checks i a certain state description satisfies the goal

Type of search algorithm, which generates all possible states

It does not use heuristics for selecting a search or constraints for reducing the number of possibilities

The goal function is then evaluated over each state

complete and optimal solution can be found when comparing the different solutions

uses a lot of memory and takes a lot of time to process

Type of search that keeps a single current state and tries to improve it by maximizing a heuristic evaluation

uses very little memory and quickly finds a solution

there is no guarantee for completeness (solution is always found) or optimality (shortest solution is found)

Sometimes a certain goal of a puzzle cannot be achieved –> a good state representation should reckon this (e.g. Dominoes on a modified chess board)

Find a way to represent the states and to perform the actions (ideally come up with a smart algorithm)

Greek "heurisko" (εὑρίσκω) → "I find"

informally denotes knowledge that can be useful when solving a problem

In search algorithms, a heuristic often denotes a function that estimates the quality of a given state

Type of search that expands the current state and moves to the state with the highest evaluation of the heuristic function until the evaluation goes down

The algorithm assumes that the states have some sort of order and continuity regarding small state changes

The main problem of the algorithm are local optima, since it can reach a locally the optimal state but this is not always the general optimal state

Random restart hill climbing –> different initial positions result in defferent local optima

Stochastic hill climbing –> select the succesor randomly, better states have a higher probability of ebing selceted

Type of search algorithm which keeps track of k different states

k different initital states are generated, at each iteration all succesors of all k states are also generated and the best succesors are selected

Beam search differs from different hill climbing algorithm since the information of the different states are combined

The algorithm often suffers due to the lack of diversity of the k different states, often only one state has the best succesor –> often not better than the hill climbing algorithm

There is also stochastic beam search –> works similiar to stochastic hill climbing

A search algorithm which is a combination of beam search and random walk

The idea is that local optima can be circumvented by allowing "bad" trains, but the frequency (temperature) should gradually decrease

It is proven that if the temperature is lowered slowly enough the probability of reaching a global omptimum approaches 1

Search algorithm which uses the same idea of beam search, but uses “sexual” reproduction instead

Start:

k randomly generated states, represented by a string over a finite alphabet (population)

Evaluation:

fitness function

Improving state:

by selection, cross-over and mutation

It is rather easy implemented but very powerful and often used

Selection: only strings with a high fitness function are evaluated

Mutation: a random value of a parent string is modified

Cross-over: a new string is created by combining parts of two parent strings

Automated method for creating a program

Starts from the high-level statement “what needs to be done” and automatically creates a fitting computer program

Genetic algorithms are applied to program trees

Search algorithm

Decompose the problem into simpler partial problems

Solve each of these simpler problems

CSP are special types of search problems containing

• a state is defined by variables X with d values from domain D

• a goal test is a set of constraints specifying allowable combinations of values for subsets of variables

As an example Soduko:

• each square x is defined with a number 1-9 from D

• different constraints like, not the same number in the same row or column

A constraint graph visualizes a CSP, where

• nodes are variables

• edges indicate constraints between them

As an example Map coloring:

• different countries are nodes

• Two neighboring nodes must not have the same color

unary –> constraints involve a single variable

binary –> constraints involve pairs of variables

higher order –> constraints involve 3 or more variables

Preferences or soft constraints –> are not binding, but task is to respect as many as possible; constrained optimization problems

There are two principal approaches when solving a CSP

• Search

  • successively assign values to variable

  • check all constraints

  • if a constraint is violated → backtrack

  • until all variables have assigned values

• Constraint Propagation

  • maintain a set of possible values Di for each variable Xi

  • try to reduce the size of Di by identifying values that violate

    some constraints

branching factor at depth l: (n−l+1)*v

The search tree has n!*v*n leaves

Depth-first search with single variable assignments per level is also called backtracking search

Backtracking is the basic search algorithm for CSPs (Constraint Satisfaction Problems)

• add one constraint at a time without conflict

• succeed if a legal assignment is found

Complexity

• Worst case is still exponentional

• Domain-independent heuristics for selecting variables and for ordering values can improve practical performance

  
  

Which variable should be assigned next

In what order should its values be tried

Can we detect inevitable failure early

)Can we take advantage of problem structure

Domain-Specific Heuristics –> a heuristic for the n-queens problem is not helpful for the map coloring problem

General-purpose heuristics

• Mininum Remaining Values Heuristic, e.g. choose the variable with the fewest consistent values

• Degree Heuristic, e.g. choose the variable with the most constraints on remaining variables

• Least Constraining Value Heuristic, e.g. given a variable, choose the value that rules out the fewest values in the remaining variables

used in this order, this can speed up the search process

node/local consistency

forward checking

arc consistency

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

can be trivially enforced

As an example Sudoku: Some nodes are already filled out, i.e. constrained to a single value

make each node in the constraint graph consistent with its neighbors (local consistency)

by (iteratively) enforcing the constraints corresponding to the edges

keep track of remaining legal values for unassigned variables

terminate search when any variable has no more legal values

A variable x is arc consistent, if for every value d1 in the domain there is some value d2 in the domain that satisfies the constraints x1, x2

Search is the process of trying out various possibilities in a systematic way so that in the end we can find a valid solution. Search problems are defined with :

• a state decription

• a Goal function

The algorithm will stop as soon as it reaches a point from which it only can go downwards, but that point does not necessarely have to be the global maximum –> local minimum

Local optima can be prevented with two techniques:

• Random Restart Hill-Climbing –> several iterations with different starting positions

• Stochastic Hill-Climbing –> select the successor node randomly, better nodes have a higher probability of being selected

Minimum Remaining Value Heuristic –> choose variable with fewest consistent values

Degree Heuristic –> choose variable with most constraints on remaining variables

Least Constraining Value Heuristic –> choose value that rules out fewest values in remaining variables

maintain a set of possible values D for each variable X

try to reduce the size of D by identifying values that violate some constraints

Decompose the problem into simpler/smaller subproblems

Solve each of the subproblems

Combine the subproblems to a complete solution