What do humans usally do when solving a Sudoku?

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

What is needed for defining a search problem?

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

What is simple exhaustive search?

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

What is local search?

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)

What is important when choosing a state representation?

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)

What does the term heuristics mean?

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

What is Hill Climbing search/greedy local search?

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

What are possible methods to improve the hill climbing search?

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

What is beam search?

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

What is simulated annealing?

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

What are genetic algorithms?

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

What are the different possibilities when trying to improve a state with a genetic search algorithm?

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

What is genetic programming?

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

What is divide and conquer

Search algorithm

Decompose the problem into simpler partial problems

Solve each of these simpler problems

What is the case for an exhaustive search

Is the Mutilated chess problem solvable? The Mutilated chess problem requeres one to place domino pieces (each covering two adjacent squares) on a chessboard where two opposite corners are missing.

A heuristic is ...?

What are operations done between generations in genetic algorithms?

Which of the following statements about stochastic search are true?

For defining a search problem, we need

A state description is an abstract representation of the current state of a puzzle. The set of all such descriptions is called the state space.

A goal function checks whether a state description satisfies the goal.

Which statements about ”Local Search” are true?

Choosing a good state representation may already be crucial for finding a good solution.

Which statements about ”Heuristic” are true?

The Algorithm from the Beam Search is:

Start with k randomly generated states.

At each iteration, all the successors of all k states are generated

Select the k best successors from the complete list and repeat.

If the algorithm will stop as soon as is at the top of a hill, this will be named ”Local Optima” and is a main problem. Of which Search variant?

Information from different beams is combined so the Beam search is different from k parallel hill-climbing searches, but the effectiveness suffers from lack of diversity of the k states.

Simulated Annealing Search is ...

In the Genetic Algorithms there will be the next generation produced by selection, cross-over and mutation.

The Genetic Programming is popularized by David Fogel.

What can happen, if the analysis of the solutions of a recursive solution rise to a simple non- recursive solution?

Which steps belong to which algorithms?

try to find solutions by looking at near elements

Local Search

applying random changes

Greedy Hill-Climbing Search

trying to improve the current state step by step using an heuristic

Divide and Conquer

combine multiple partial solutions into one

Genetic algorithms

Map phases of genetic algorithms to their description.

Fitness

Evaluate usefulness of generation states.

Cross-over

Perform small and random changes of the newly generated states.

Mutation

Create new states by combining selected pairs

Selection

Select states to reproduce with probability corresponding to their fitness.

There are many specialized tricks to solve a Sudoku, but the most follow a general pattern. Match the sentences correctly.

Constraint Propagation

check all possibilities for the selected square(s)

Constraint Satisfaction

propagate the information to other squares

Search

select a square (or a set of squares)

Heuristics

repeat these steps until the solution is complete

Match the statements to the correct area of Hill-climbing-search

States may be refined in multiple ways; → similarity along various dimensions

State Space Landscape

select the successor node ramdomly; better nodes have a higher probability of being selected

Stochastic Hill-Climbing

Different initial positions result in different local optima; → make several iterations with different starting positions

Random Restart Hill-Climbing

location: states

elevation: heuristic value (objective function) Assumption: states have some sort of (linear) order; continuity regarding small state changes

Multi-Dimensional State-Landscape

”Divide-and-Conquer” is a general problem solving strategy with many applications. Match the sentences correctly!

recursive programming

Solve each of these simpler problems by possibly solving them again by division

DIVIDE

CONQUER

Combine the partial solutions to a…

complete solution

What are constaraint saftisfaction problems (CSP)?

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

What is a constraint graph?

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

What are different types of constraints?

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

How are constraint satisfactions problems solved?

There are two principal approaches when solving a CSP

successively assign values to variable

check all constraints

if a constraint is violated → backtrack

until all variables have assigned values

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

What is the formula for the complexity of naive search in a search tree?

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

The search tree has n!*v*n leaves

What is backtracking?

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

What methods with backtracking can give huge gains in speed?

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

What are general heuristics for constraint satisfation constraints?

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

What is are different types of constraint propagation?

node/local consistency

forward checking

arc consistency

What is node 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

What is forward checking?

keep track of remaining legal values for unassigned variables

terminate search when any variable has no more legal values

What is arc consistency?

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

Variable assignemnts commutative in the map coloring problem

Constraint propagation and backtracking search be combined to speed up the search process

With the right combination of sontraint propagation and backtracking search there is no critical ratio in which a generated CSP can be solved in short runnung time

Choose what those terms refer to

Method to check whether a state description satisfies the goal

backtracking

The abstract representation of the current state of a puzzle

state space

Trying a potential solution and revising it later

state description

The set of all possible descriptions

goal function

How can a search problem be defined?

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

What are local optima and what can you do to prevent them?

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

What general-purpose heuristics are there for selecting constrained variables and their values?

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

How does constraint propagation work?

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

What is the key idea of divide-and-conquer?

Decompose the problem into simpler/smaller subproblems

Solve each of the subproblems

Combine the subproblems to a complete solution

Last changed5 months ago