程序代写代做代考 algorithm Algorithms Week 4

Algorithms Week 4
Ljubomir Perkovi ́c, DePaul University

Backtracking
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
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.

Text Segmentation
Input: A sequence of characters stored in A[1..n].
Output: True if A can be segmented into a sequence of words,
False otherwise.

Text Segmentation
Input: Output:
Given:
A sequence of characters stored in A[1..n].
True if A can be segmented into a sequence of words, False otherwise.
Function IsWord(w) that returns True if sequence of characters w is a word, False otherwise.

Text Segmentation
Input: Output:
Given: Example:
A sequence of characters stored in A[1..n].
True if A can be segmented into a sequence of words, False otherwise.
Function IsWord(w) that returns True if sequence of characters w is a word, False otherwise.
If sequence A consists of characters
BOTHEARTHANDSATURNSPIN
and IsWord(w) is True if w is a word in English, then:
• Output True because BOTH·EARTH·AND·SATURN·SPIN is a valid segmentation of A

Backtracking algorithm idea
We consider a process that consumes the input characters in order from left to right

Backtracking algorithm idea
We consider a process that consumes the input characters in order from left to right and produces the output words in order from left to right.

Backtracking algorithm idea
We consider a process that consumes the input characters in order from left to right and produces the output words in order from left to right.
So, at any point in time of the process we might have the following situation:
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN

Backtracking algorithm idea
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
We need to decide on the next word.

Backtracking algorithm idea
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
We need to decide on the next word. Options:
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN

Backtracking algorithm idea
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
We need to decide on the next word. Options:
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEAR
THANDSATURNSPIN

We need to decide on the next word. Options:
Backtracking algorithm idea
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEAR
THANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEART
HANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEARTH
ANDSATURNSPIN
Which option do we choose? We try all of them, using backtracking and letting the recursion fairy do the work.

Backtracking algorithm strategy
We start with:
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN

Backtracking algorithm strategy
We start with:
We tentively accept HE as the next word and let the recursion fairy make the rest of the decisions:
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN

We start with:
Backtracking algorithm strategy
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN
We then tentively accept HEAR as the next word and let the recursion fairy make the rest of the decisions:
BLUE
STEM
UNIT
ROBOT
HEAR
THANDSATURNSPIN

We start with:
Backtracking algorithm strategy
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEAR
THANDSATURNSPIN
We then tentively accept HEART as the next word and let the recursion fairy make the rest of the decisions:
BLUE
STEM
UNIT
ROBOT
HEART
HANDSATURNSPIN

We start with:
Backtracking algorithm strategy
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEAR
THANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEART
HANDSATURNSPIN
We then tentively accept HEARTH as the next word and let the recursion fairy make the rest of the decisions:
BLUE
STEM
UNIT
ROBOT
HEARTH
ANDSATURNSPIN

We start with:
Backtracking algorithm strategy
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEAR
THANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEART
HANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEARTH
ANDSATURNSPIN
If the recursion fairy reports success on any of these, we report success.

We start with:
Backtracking algorithm strategy
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HE
ARTHANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEAR
THANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEART
HANDSATURNSPIN
BLUE
STEM
UNIT
ROBOT
HEARTH
ANDSATURNSPIN
If, on the other hand, the recursion fairy does not report success then we report failure.

Backtracking algorithm strategy, simplified
Past decisions do not affect the choices we have available now:
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUEST
EMU
NITRO
BOT
HEARTHANDSATURNSPIN

Backtracking algorithm strategy, simplified
Past decisions do not affect the choices we have available now:
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUEST
EMU
NITRO
BOT
HEARTHANDSATURNSPIN
So the recursive process can be simplified by ignoring the past:
HEARTHANDSATURNSPIN

Base case?
A recursive algorithm needs a base case.

Base case?
A recursive algorithm needs a base case.
We stop when the input sequence is of length 0.

Base case?
A recursive algorithm needs a base case.
We stop when the input sequence is of length 0. What is returned then? Success or Failure?

Segmentation backtracking algorithm
Splittable(A[1 .. n]): if n = 0
return True for i ← 1 to n
if IsWord(A[1 .. i]) and Splittable(A[i + 1 .. n])
return True
return False

Index formulation
Passing arrays as input parameters to recursive functions is inefficient.

Index formulation
Passing arrays as input parameters to recursive functions is inefficient.
It is better to treat the original input array as a global variable and reformulate the problem and the algorithm in terms of array indices.
For the string segmentation problem, the argument of any recursive call is always a suffix A[i..n] of the original input array A[1..n].
So if we treat the input array A[1..n] as a global variable, we can reformulate our recursive problem as follows:

Segmentation backtracking algorithm, v2.0
// Is the suffix A[i..n] Splittable?
Splittable(i):
if i > n
return True
for j ← i to n
if IsWord(i, j) and Splittable(j + 1)
return True
return False

Longest Increasing Subsequence
For any sequence S,
26142429535783

Longest Increasing Subsequence
For any sequence S, a subsequence of S is another sequence obtained from S by deleting zero or more elements, without changing the order of the remaining elements.
Problem: Given a sequence of integers S find the Longest Increasing Subsequence (LIS) of S.
Input: Output:
Example:
Integer array A[1..n].
Longest possible sequence of indices 1≤i1 n
return 0
else if A[i] ≥ A[j]
return LISbigger(i, j + 1)
else
skip ← LISbigger(i, j + 1) take ← LISbigger(j, j + 1) + 1 return max{skip, take}

LISbigger v2.0
LISbigger(i, j):
if j > n
return 0
else if A[i] ≥ A[j]
return LISbigger(i, j + 1)
else
skip ← LISbigger(i, j + 1) take ← LISbigger(j, j + 1) + 1 return max{skip, take}
What is the initial call on A[1..n]? There is not index i initially…

LIS backtracking algorithm wrapper function
LIS(A[1 .. n]):
A[0] ← −∞
return LISbigger(0, 1)

Optimal Binary Search Trees
The running time for a successful search in a binary search tree is proportional to the depth of the target node.
7
3 13
9 18 12

Optimal Binary Search Trees
The running time for a successful search in a binary search tree is proportional to the depth of the target node.
7
3 13
9 18 12
• The worst-case search time is proportional to the depth of the tree.

Optimal Binary Search Trees
The running time for a successful search in a binary search tree is proportional to the depth of the target node.
79
3 13 3 13
9 18 7 12 18 12
• The worst-case search time is proportional to the depth of the tree.
• To minimize the worst-case search time, the tree should be balanced.

Optimal Binary Search Trees
It is often more important to minimize the total cost of several searches
• Rather than the worst-case cost of a single search.

Optimal Binary Search Trees
It is often more important to minimize the total cost of several searches
• Rather than the worst-case cost of a single search.
79
3 13 3 13
9 18 7 12 18 12

Optimal Binary Search Trees
It is often more important to minimize the total cost of several searches
• Rather than the worst-case cost of a single search.
79
3 13 3 13
9 18 7 12 18 12
If x is a more frequent search target than y, we can save time by building a tree where the depth of x is smaller than the depth of y
• Even if that means increasing the overall depth of the tree.

Optimal Binary Search Trees
This state of affairs suggests the following problem:
Given a sorted array of keys A[1..n] and an array of corresponding access frequencies f [1..n], build the binary search tree to store the keys and that minimizes the total search time, assuming that there will be exactly f [i] searches for each key A[i].
It is helpful to write a good recursive definition of the function we are trying to optimize.

Optimization function
The total cost of performing all the binary searches is given by the following expression:
n Cost(T,f[1..n]) = 􏰀f[i]×dT(vi)
i=1
where dT (vi ) is the depth of vi in T (where depth of root is 1).
Letvr,where1≤r≤nbetherootofT andletl(T)andr(T) be the left and right subtrees of vr .
l(T)
r(T)
vr

Optimization function
Then:
n Cost(T,f[1..n]) = 􏰀f[i]×dT(vi)
i=1
nr−1 n
=􏰀f[i]+􏰀f[i]×dl(T)(vi)+ 􏰀 f[i]×dr(T)(vi) i=1 i=1 i=r+1
n
= 􏰀f[i]+Cost(l(T),f[1..r −1])+Cost(r(T),f[r +1..n]) i=1
l(T)
r(T)
vr

Optimization function
Goal is to compute optimal tree Topt that minimizes:
Cost(T , f [1..n]) = n
􏰀f[i]+Cost(l(T),f[1..r −1])+Cost(r(T),f[r +1n ̇]) i=1

Optimization function
Goal is to compute optimal tree Topt that minimizes:
Cost(T , f [1..n]) = n
􏰀f[i]+Cost(l(T),f[1..r −1])+Cost(r(T),f[r +1n ̇]) i=1
Let vr be the root of Topt; the above definition implies that:
• the left subtree l(Topt) must be the optimal search tree for
the keys A[1..r − 1] and access frequencies f [1..r − 1]
• the right subtree r(Topt) must be the optimal search tree for the keys A[r + 1..n] and access frequencies f [r + 1..n].

Optimization function
Goal is to compute optimal tree Topt that minimizes:
Cost(T , f [1..n]) = n
􏰀f[i]+Cost(l(T),f[1..r −1])+Cost(r(T),f[r +1n ̇]) i=1
Let vr be the root of Topt; the above definition implies that:
• the left subtree l(Topt) must be the optimal search tree for
the keys A[1..r − 1] and access frequencies f [1..r − 1]
• the right subtree r(Topt) must be the optimal search tree for
the keys A[r + 1..n] and access frequencies f [r + 1..n].
So, if we choose the correct key to store at the root, the recursion fairy will construct the rest of the optimal tree.

Optimization function
Goal is to compute optimal tree Topt that minimizes:
Cost(T , f [1..n]) = n
􏰀f[i]+Cost(l(T),f[1..r −1])+Cost(r(T),f[r +1n ̇]) i=1
Let vr be the root of Topt; the above definition implies that:
• the left subtree l(Topt) must be the optimal search tree for
the keys A[1..r − 1] and access frequencies f [1..r − 1]
• the right subtree r(Topt) must be the optimal search tree for
the keys A[r + 1..n] and access frequencies f [r + 1..n].
So, if we choose the correct key to store at the root, the recursion
fairy will construct the rest of the optimal tree. So how do we choose the correct key?

Optimization function
Goal is to compute optimal tree Topt that minimizes:
Cost(T , f [1..n]) = n
􏰀f[i]+Cost(l(T),f[1..r −1])+Cost(r(T),f[r +1n ̇]) i=1
Let vr be the root of Topt; the above definition implies that:
• the left subtree l(Topt) must be the optimal search tree for
the keys A[1..r − 1] and access frequencies f [1..r − 1]
• the right subtree r(Topt) must be the optimal search tree for
the keys A[r + 1..n] and access frequencies f [r + 1..n].
So, if we choose the correct key to store at the root, the recursion
fairy will construct the rest of the optimal tree.
So how do we choose the correct key? Try each one!

Related Posts