程序代写代做代考 game algorithm Algorithms Week 3

Algorithms Week 3
Ljubomir Perkovi ́c, DePaul University

Backtracking
Consider the problem of navigating a maze. In general, one does not know the structure of the maze when starting. In fact, a maze may be constructed not to have any particular structure. So there is typically no way to break down the problem into smaller subproblems.
One way to solve a maze is to try every potential solution in the search space, i.e. every possible sequence of steps from the maze entrance until the maze exit is found.

Backtracking, more formally
The basic strategy of backtracking is to systematically explore the space of all potential solutions. It does so by:
• extending a partial solution in some feasible way,

Backtracking, more formally
The basic strategy of backtracking is to systematically explore the space of all potential solutions. It does so by:
• extending a partial solution in some feasible way,
• trying another extension if the extension fails,
• backing up to a smaller partial solution when the options for extending a partial solution are exhausted.

n-Queens problem
Classic problem to illustrate backtracking. Input: An integer n ≥ 4.
Output: A placement of n queens on an n × n chessboard so that no two can attack each other.

n-Queens problem
Classic problem to illustrate backtracking. Input: An integer n ≥ 4.
Output: A placement of n queens on an n × n chessboard so that no two can attack each other.
Recall that a queen may move any length along a diagonal or any length along a row or column.

Potential solutions
In order to use backtracking for this problem, we need to describe what a potential solution looks like.
As seen in the previous example, a potential solution is n points in an n × n array:
(x1, y1), (x2, y2), …, (xn, yn).
Note that an exhaustive search will check (n2)n possible solutions,
one for each set of n coordinates.
Let us use backtracking to narrow down the search space. To do this, we first need to design a more efficient representation of potential solutions and to develop tests that check whether a partial solution can be extended to a complete solution.

Analyzing the partial solutions and pruning
We can make several observations that eliminate some of the possible partial solutions:
1 There must be exactly one queen per row; this means that the solutions must have the form:
(1, y1), (2, y2), …, (n, yn).
2 There must be exactly one queen per column; this means that (y1, y2, …, yn) must be a permutation of (1, 2, …, n). Note that this decreases the search space to ”only” n! permutations.
3 There is at most one queen on each diagonal; this means that if two queens are at positions (a, b) and (c, d) then
|a−c|≠ |b−d|.

The strategy
We will generate all n! permutation until we find a solution. We do this by building up the solutions one position at a time.

The strategy
We will generate all n! permutation until we find a solution. We do this by building up the solutions one position at a time.
Step 1: Choose a column for the queen in row 1.

The strategy
We will generate all n! permutation until we find a solution. We do this by building up the solutions one position at a time.
Step 1: Choose a column for the queen in row 1.
Step i: Given the positions of the first i − 1 queens
(1, y1), (2, y2), …, (i − 1, yi−1), choose the position for (i,yi).

The strategy
We will generate all n! permutation until we find a solution. We do this by building up the solutions one position at a time.
Step 1: Step i:
Choose a column for the queen in row 1.
Given the positions of the first i − 1 queens
(1, y1), (2, y2), …, (i − 1, yi−1), choose the position for (i,yi).
If you cannot complete Step i for some choice of previous positions (1,y1),(2,y2),…,(i −1,yi−1), then backtrack and re-choose the position for (i − 1, yi−1).

n-Queens backtracking algorithm
Let Q[1 . . . n] store the positions of the n queens, i.e. Q[i] will be the column of the queen in row i.
PlaceQueens(Q[1 .. n], r):
// extends a partial solution of size r-1
// to one of size r,
// unless the partial solution
// is a complete solution, in
// which case it is output;
// the initial call is PlaceQueens(Q, 1)
// with Q storing a partial solution of size 0
.

n-Queens backtracking algorithm
Let Q[1 . . . n] store the positions of the n queens, i.e. Q[i] will be the column of the queen in row i.
PlaceQueens(Q[1 .. n], r): if r = n + 1
print Q[1 .. n]
else
for j ← 1 to n Q[r] ← j
if Feasible(Q, r)
PlaceQueens(Q, r + 1)
Feasible(Q[1 .. n], r)
// Return true if
// the placement of the queen
// in row r is feasible,
// false otherwise

n-Queens backtracking algorithm
Let Q[1 . . . n] store the positions of the n queens, i.e. Q[i] will be the column of the queen in row i.
PlaceQueens(Q[1 .. n], r): if r = n + 1
print Q[1 .. n]
else
for j ← 1 to n Q[r] ← j
if Feasible(Q, r)
PlaceQueens(Q, r + 1)
Feasible(Q[1 .. n], r) for i ← 1 to r-1
if Q[i] = Q[r] or |Q[i] – Q[r]| = |i-r| then return false
return true

Game trees
Backtracking is a very general-purpose algorithm design technique. Most game-playing programs use a version of bactracking to decide
on the next move
For example, one can develop a relatively simple backtracking algorithm that can play a two-player game perfectly (assuming a game that has no randomness or hidden information and that ends after a finite number of moves).
Given the current state of the game, this backtracking algorithm can tell you whether it is possible to win against another perfect player and also tell you how to win.

Game trees

Game trees
This algorithm takes as input the state of the game X and one of the two players and returns Good or Bad depending on whether player can win or not.
PlayAnyGame(X, player):
if player has already won in state X
return Good
if player has already lost in state X
return Bad
for all legal moves X 􏰂 Y
if PlayAnyGame(Y, ¬ player) = Bad return Good
return Bad

Subset sum
Subset sum is a classic problem:
Input: A set S of positive integers and an integer T.
Output: A subset X of S such that 􏰃x∈X x = T.

Subset sum
Subset sum is a classic problem:
Input: Output: Example:
A set S of positive integers and an integer T. A subset X of S such that 􏰃x∈X x = T.
Let S = {4,7,6,3,1} and T = 10.

Subset sum
Subset sum is a classic problem:
Input: Output: Example:
A set S of positive integers and an integer T. A subset X of S such that 􏰃x∈X x = T.
Let S = {4,7,6,3,1} and T = 10.
• 4+6=10,soX ={4,6}isavalidsolution.

Recursive solution
Suppose that X is a solution. In other words, 􏰃x∈X x = T.

Recursive solution
Suppose that X is a solution. In other words, 􏰃x∈X x = T. Now consider a particular number e of S. Note that either
e ∈ X or e ̸∈ X.

Recursive solution
Suppose that X is a solution. In other words, 􏰃x∈X x = T. Now consider a particular number e of S. Note that either
e ∈ X or e ̸∈ X.
• Ife∈X thenitfollowsthatthereisasubset(X\{e})of
S \ {e} that adds up to T − e.
• Ife̸∈X thenthereisasubset(X)ofS\{e}thataddsupto
T.
In both cases we reduce the problem with inputs S and T to two smaller problem instances: one with inputs S \ {e} and T − e and one with inputs S \ {e} and T.

Recursive solution
What about the base case of the recursion?

Recursive solution
What about the base case of the recursion? • IfT =0,thesolutionisX =∅

Recursive solution
What about the base case of the recursion? • IfT =0,thesolutionisX =∅
• If T < 0, there is no solution. Recursive solution What about the base case of the recursion? • IfT =0,thesolutionisX =∅ • If T < 0, there is no solution. • IfT>0andS=∅,thereisnosolution.

Recursive solution
What about the base case of the recursion? • IfT =0,thesolutionisX =∅
• If T < 0, there is no solution. • IfT>0andS=∅,thereisnosolution.
So, recursion can be used to implement an algorithm.
Backtracking makes use of the recursion to more systematically search the space of potential solutions and prune the search when we find partial solutions that cannot be extended to a complete valid solution.

Backtracking approach
To solve the problem via backtracking we need a way to represent potential partial solutions. We start by assuming that the numbers in set S are stored in an array S[1..n].

Backtracking approach
To solve the problem via backtracking we need a way to represent potential partial solutions. We start by assuming that the numbers in set S are stored in an array S[1..n].
We then use array X[1..r] containing zeros and ones to represent a partial potential solution that incorporates our decisions whether to include numbers S[1], S[2], . . . , S[r], where
• X[i] = 1 if number S[i] is included in the partial solution.
• X[i] = 0 if number S[i] is not included in the partial solution.

Backtracking approach
For example. Let S = [4,7,6,3,1] and T = 10.

Backtracking approach
For example. Let S = [4,7,6,3,1] and T = 10.
• X = [] is the starting partial solution that does not incorporate any decisions about including numbers in S[1..n]; it represents an empty set.
• X = [0] represents the partial solution that incorporates our decisions on number S[1]; the number is not included and X represents an empty set as well.
• X = [1, 0] represents the partial solution that incorporates our decision on numbers S[1] and S[2]; S[1] is in and S[2] is out.
• X = [1, 0, 1, 0, 0] represents a partial solution that incorporates our decisions on all numbers in S[1..5]; it happens to be a complete and valid solution.

Backtracking approach
We will use the following backtracking strategy:

Backtracking approach
We will use the following backtracking strategy: 1 Start with X = [].

Backtracking approach
We will use the following backtracking strategy:
1 Start with X = [].
2 Given a partial solution X [1..i − 1] (of length i − 1) that includes our choices which numbers in S[1..i − 1] to include, try including number S[i] and extending the resulting partial potential solution X[1..i]
3 Given a partial solution X [1..i − 1] (of length i − 1) that includes our choices which numbers in S[1..i − 1] to include, try excluding number S[i] and extending the resulting partial potential solution X[1..i]

Backtracking approach
Let us implement this strategy on input S = [4, 7, 6, 3, 1] and T = 10.

Subset Sum algorithm
SubsetSum(S[1..n], T, X[1..n], r)
// extends a partial solution X[1..r-1]
// of size r-1 to one of size r,
// unless the partial solution
// is a complete solution, in
// which case it is output;
// the initial call is SubsetSum(S, T, X, 1)
// with X storing a partial solution of size 0
.

Subset Sum algorithm
SubsetSum(S[1..n], T, X[1..n], r) if r = n+1 then
output X
return
X[r] ← 0
if Feasible(S, T, X, r) then
SubsetSum(S, T, X, r+1) X[r] ← 1
if Feasible(S, T, X, r) then
SubsetSum(S, T, X, r+1)

Subset Sum algorithm
When is partial solution X[1..r] infeasible?

Subset Sum algorithm
When is partial solution X[1..r] infeasible? We can clearly prune X if
r
􏰀X[i]S ̇[i] > T i=1

Subset Sum algorithm
When is partial solution X[1..r] infeasible? We can clearly prune X if
r
􏰀X[i]S ̇[i] > T i=1
Feasible(S[1..n], T, X[1..n], r) S1 ← 􏰃ri=1 X[i]S[i]
if S1 > T then
return false
return true

Subset Sum algorithm
Furthermore, X can also be pruned if
kn
􏰀X[i]S[i]+ 􏰀 S[i] T then
return false
S2 ←􏰃ni=r+1 S[i] if S1 + S2 < T then return false return true General recursive backtracking Solve(partial solution) if partial solution is a solution then // if goal is to find a solution output solution and quit for all possible extensions of partial solution if extension is feasible then Solve(extension) General recursive backtracking Solve(partial solution) if partial solution is a solution then // if goal is to find all solutions output solution and return for all possible extensions of partial solution if extension is feasible then Solve(extension) General recursive backtracking Solve(partial solution) if partial solution is a solution then // if goal is to find optimal solution keep solution if best so far and return for all possible extensions of partial solution if extension is feasible then Solve(extension) Algorithm engineering Backtracking is a very general-purpose algorithm design technique. Algorithm engineering Backtracking is a very general-purpose algorithm design technique. The actual implementation of a backtracking algorithm involves engineering decisions that are not typically made explicit in a more theoretical description of an algorithm. Algorithm engineering Backtracking is a very general-purpose algorithm design technique. The actual implementation of a backtracking algorithm involves engineering decisions that are not typically made explicit in a more theoretical description of an algorithm. Algorithm engineering is an area of computer science that goes beyond the design and analysis of algorithms and includes their implementation, optimization, profiling and experimental evaluation. Algorithm engineering Backtracking is a very general-purpose algorithm design technique. The actual implementation of a backtracking algorithm involves engineering decisions that are not typically made explicit in a more theoretical description of an algorithm. Algorithm engineering is an area of computer science that goes beyond the design and analysis of algorithms and includes their implementation, optimization, profiling and experimental evaluation. To illustrate this, I develop next a backtracking solution for the Kattis problem Class Picture.

Related Posts