Backtracking

The General Backtracking Method

\begin{algorithm}
\caption{BACKTRACKREC}
\begin{algorithmic}
\Input  Explicit or implicit description of the sets $X_1,X_2,\dots,X_n$.
\Output A solution vector $v = (x_1,x_2,\dots,x_i),0 \leq i \leq n$.
\State $v \gets ()$
\State $flag \gets$ \False
\State \Call{advance}{1}
\If{$flag$}
\State output $v$
\Else
\State output "no solution"
\EndIf
\Procedure{advance}{$k$}
\For{each $x \in X_k$}
\State $x_k \gets x$; append $x_k$ to $v$
\If{$v$ is a final solution}
\State set $flag \gets$ \True and exit
\Elif{$v$ is partial}
\State \Call{advance}{$k+1$}
\EndIf
\EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{BACKTRACKINER}
\begin{algorithmic}
\Input  Explicit or implicit description of the sets $X_1,X_2,\dots,X_n$.
\Output A solution vector $v = (x_1,x_2,\dots,x_i),0 \leq i \leq n$.
\State $v \gets ()$
\State $flag \gets$ \False
\State $k \gets 1$
\While{$k \geq 1$}
\While{$X_k$ is not exhausted}
\State $x_k \gets$ next element in $X_K$; append $x_k$ to $v$
\If{$v$ is a final solution}
\State set $flag \gets$ \True and exit from the two while loops.
\Elif{$v$ is partial}
\State $k \gets k + 1$ \Comment{advance}
\EndIf
\EndWhile
\State Reset $X_k$ so that the next element is the first.
\State $k \gets k-1$ \Comment{backtrack}
\EndWhile
\If{$flag$}
\State output $v$
\Else
\State output "no solution"
\EndIf
\end{algorithmic}
\end{algorithm}

The 3-Coloring Problem

Consider the problem 3-coloring: Given an undirected graph G=(V,E)G = (V, E), it is required to color each vertex in VV with one of three colors, say 11, 22, and 33, such that no two adjacent vertices have the same color. We call such a coloring legal; otherwise, if two adjacent vertices have the same color, it is illegal. A coloring can be represented by an nn-tuple (c1,c2,…,cn)(c_1, c_2, \ldots, c_n) such that ci∈{1,2,3}c_i \in \{1, 2, 3\}, 1≤i≤n1 \leq i \leq n.

An example of using backtracking to solve the problem 3-coloring. 
\begin{algorithm}
\caption{3-COLORREC}
\begin{algorithmic}
\Input An undirected graph $G = (V,E)$.
\Output A $3$-coloring $c[1..n]$ of the vertices of $G$, where each $c[j]$ is $1$, $2$, and $3$.
\For{$k \gets 1$ \To $n$}
\State $c[k] \gets 0$
\EndFor
\State $flag \gets$ \False
\State \Call{graphcolor}{1}
\If{$flag$}
\State output $c$
\Else
\State output "no solution"
\EndIf
\Procedure{graphcolor}{$k$}
\For{$color = 1$ \To $3$}
\State $c[k] \gets color$
\If{$c$ is a legal coloring}
\State set $flag \gets$ \True and exit
\Elif{$c$ is partial}
\State \Call{graphcolor}{$k+1$}
\EndIf
\EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{3-COLORITER}
\begin{algorithmic}
\Input An undirected graph $G = (V,E)$.
\Output A $3$-coloring $c[1..n]$ of the vertices of $G$, where each $c[j]$ is $1$, $2$, or $3$.
\For{$k \gets 1$ \To $n$}
\State $c[k] \gets 0$
\EndFor
\State $flag \gets$ \False
\State $k \gets 1$
\While{$k \ge 1$}
    \While{$c[k] \le 2$}
        \State $c[k] \gets c[k] + 1$
        \If{$c$ is a legal coloring} 
            \State set $flag \gets$ \True and exit from the two while loops.
        \ElsIf{$c$ is partial} 
            \State $k \gets k + 1$ \Comment{advance}
        \EndIf
    \EndWhile
    \State $c[k] \gets 0$
    \State $k \gets k - 1$ \Comment{backtrack}
\EndWhile
\If{$flag$} 
\State output $c$
\Else 
\State output "no solution"
\EndIf
\end{algorithmic}
\end{algorithm}

Below is the implementation of these pseudocodes in Python(Adjacency list):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
G = {
    'a': ['b','c'],
    'b': ['a','d','e'],
    'c': ['a','d','e'],
    'd': ['b','c'],
    'e': ['c','d']
}

V = list(G.keys())


def three_color_rec(G):
    c = {v: 0 for v in V}
    flag = False
    n = len(V)

    def is_legal(v, color):
        for neighbor in G[v]:
            if c[neighbor] == color:
                return False
        return True

    def graphcolor(k):
        nonlocal flag
        if k > n:
            flag = True
            return
        
        for color in range(1,4):
            if is_legal(V[k-1], color):
                c[V[k-1]] = color
                graphcolor(k + 1)
                if flag:
                    return
                c[V[k-1]] = 0

    graphcolor(1)
    if flag:
        print(c)
    else:
        print("no solution")

def three_color_iter(G):
    n = len(V)
    c = {v: 0 for v in V}
    flag = False
    k = 1

    def is_legal():
        for v in V:
            if c[v] == 0:
                return False
        for v in V:
            for neighbor in G[v]:
                if c[v] == c[neighbor]:
                    return False
        return True

    def is_partial():
        for i in range(1, k+1):
            v = V[i-1]
            for neighbor in G[v]:
                if neighbor in V[:k] and c[neighbor] == c[v]:
                    return False
        return True

    while k >= 1:
        if k > n:
            if is_legal():
                flag = True
                break
            k -= 1
            continue
            
        found_next_step = False
        while c[V[k-1]] <= 2 and not found_next_step:
            c[V[k-1]] += 1
            
            if is_legal():
                flag = True
                break
            elif is_partial():
                k += 1
                found_next_step = True
        
        if flag:
            break
            
        if not found_next_step:
            c[V[k-1]] = 0
            k -= 1

    if flag:
        print(c)
    else:
        print("no solution")

The 8-Queens Problem

The classical 8-queens can be stated as follows. How can we arrange eight queens on an 8×88 \times 8 chessboard so that no two queens can attack each other? Two queens can attack each other if they are in the same row, column, or diagonal.
Consider a chessboard of size 4×44 \times 4. Since no two queens can be put in the same row, each queen is in a different row. Since there are four positions in each row, there are 444^4 possible configurations. Each possible configuration can be described by a vector with four components x=(x1,x2,x3,x4)x = (x_1, x_2, x_3, x_4).

\begin{algorithm}
\caption{4-QUEENSITER}
\begin{algorithmic}
\Input None.
\Output Vector $x[1..4]$ corresponding to the solution of the $4$-queens problem.
\For{$k \gets 1$ \To $4$}
\State $x[k] \gets 0$ \Comment{no queens are placed on the chessboard}
\EndFor
\State $flag \gets$ \False
\State $k \gets 1$
\While{$k \ge 1$}
    \While{$x[k] \le 3$}
        \State $x[k] \gets x[k] + 1$
        \If{$x$ is a legal placement}
            \State set $flag \gets$ \True and exit from the two while loops.
        \ElsIf{$x$ is partial}
            \State $k \gets k + 1$ \Comment{advance}
        \EndIf
    \EndWhile
    \State $x[k] \gets 0$
    \State $k \gets k - 1$ \Comment{backtrack}
\EndWhile
\If{$flag$}
\State output $x$
\Else
\State output "no solution"
\EndIf
\end{algorithmic}
\end{algorithm}

Below is the implementation of the above pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def n_queens(n):
    x = [0] * n
    flag = False

    def is_legal(x,k):
        for i in range(k):
            if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k):
                return False
        return True


    k = 0
    while k >= 0:
        while x[k] < n:
            if is_legal(x,k):
                if k == n - 1:
                    flag = True
                    break
                else:
                    k += 1
                    x[k] = 0
            else:
                x[k] += 1
        if flag:
            break

        x[k] = 0
        k -= 1
        if k >= 0:
            x[k] += 1
    if flag:
        print(x)

    else:
        print("No solution")

Branch and Bound

7.3 旅行商问题 - 分支界限法_哔哩哔哩_bilibili 可以听听印度老哥的超绝口音

Randomized Algorithms

Randomized algorithms can be classified into two categories. The first category is referred to as Las Vegas algorithms. It constitutes those ran- domized algorithms that always give a correct answer or do not give an answer at all. This is to be contrasted with the other category of random- ized algorithms, which are referred to as Monte Carlo algorithms. A Monte Carlo algorithm always gives an answer, but may occasionally produce an answer that is incorrect. However, the probability of producing an incorrect answer can be made arbitrarily small by running the algorithm repeatedly with independent random choices in each run.

Randomized Quicksort

\begin{algorithm}
\caption{Randomized Quicksort}
\begin{algorithmic}
\Input  An array $A[1..n]$ of $n$ elements.
\Output The elements in $A$ sorted in nondecreasing order.
\State \Call{rquicksort}{$1, n$}
\Procedure{rquicksort}{$low,high$}
\If{$low < high$}
\State $v \gets$ \Call{random}{$low,high$}
\State interchange $A[low]$ and $A[v]$
\State \Call{split}{$A[low..high]$,$w$}
\State \Call{rquicksort}{$low, w-1$}
\State \Call{rquicksort}{$w+1, high$}
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{SPLIT}
\begin{algorithmic}
\Input An array of elements $A[low..high]$.
\Output (1) $A$ with its elements rearranged as described; (2) $w$, the new position of the splitting element $A[low]$.
    \State $i \gets low$
    \State $x \gets A[low]$
    \For{$j \gets low+1$ \textbf{to} $high$}
        \If{$A[j] \leq x$}
            \State $i \gets i + 1$
            \If{$i \neq j$}
                \State interchange $A[i]$ and $A[j]$
            \EndIf
        \EndIf
    \EndFor
    \State interchange $A[low]$ and $A[i]$
    \State $w \gets i$
    \Return $A$ and $w$
\end{algorithmic}
\end{algorithm}

Below is the implementation of the above pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random

def split(A, low, high):
    i = low
    x = A[low]

    for j in range(low + 1, high + 1):
        if A[j] <= x:
            i += 1
            if i != j:
                A[i], A[j] = A[j], A[i]

    A[low], A[i] = A[i], A[low]
    w = i
    return (A,w)

def rquicksort(A, low, high):
    if low < high:
        v = random.randint(low, high-1)
        A[low], A[v] = A[v], A[low]
        A, w = split(A, low, high)
        rquicksort(A, low, w - 1)
        rquicksort(A, w + 1, high)

The algorithm is Las Vegas algorithm since it always produces a correctly sorted array. The expected running time of randomized quicksort is Θ(nlog⁡n)\Theta(n \log n), and the worst-case running time is Θ(n2)\Theta(n^2).

Randomized Selection

\begin{algorithm}
\caption{Randomized Selection}
\begin{algorithmic}
\Input An array $A[1..n]$ of $n$ elements and an integer $k$, $1 \leq k \leq n$.
\Output The $k$th smallest element in $A$.
\State \Return \Call{rselect}{$A, 1, n, k$}
\Procedure{rselect}{$A, low, high, k$}
\State $v \gets$ \Call{random}{$low, high$}
\State $x \gets A[v]$
\State Partition $A$ into three arrays $A_1 = \{a \mid a < x\}$, $A_2 = \{a \mid a = x\}$, $A_3 = \{a \mid a > x\}$
\If{$|A_1| \ge k$}
    \Return \Call{rselect}{$A_1, 1, |A_1|, k$}
\ElsIf{$|A_1| + |A_2| \ge k$}
    \Return $x$
\Else
    \Return \Call{rselect}{$A_3, 1, |A_3|, k - |A_1| - |A_2|$}
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of the above pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import random

def rselect(A,low,high,k):
    v = random.randint(low,high)
    x = A[v]

    A_1 = []
    A_2 = []
    A_3 = []

    for a in A:
        if a < x:
            A_1.append(a)
        elif a == x:
            A_2.append(a)
        else:
            A_3.append(a)

    if k <= len(A_1):
        return rselect(A_1,0,len(A_1)-1,k)
    elif k <= len(A_1) + len(A_2):
        return x
    else:
        return rselect(A_3,0,len(A_3)-1,k - len(A_1) - len(A_2))

The expected running time of randomized selection is Θ(n)\Theta(n), and in the worst case, it is Θ(n2)\Theta(n^2).

Testing String Equality

Another alternative would be for AA to derive from xx a much shorter string that could serve as a “fingerprint” of xx and send it to BB. BB then would use the same derivation to obtain a fingerprint for yy, and then compare the two fingerprints. If they are equal, then BB would assume that x=yx=y; otherwise, he would conclude that x≠yx\neq y. BB then notifies AA of the outcome of the test. This method requires the transmission of a much shorter string across the channel. For a string ww, let I(w)I(w) be the integer represented by the bit string ww. One method of fingerprinting is to choose a prime number pp and then use the fingerprint function

Ip(x)=I(x) (mod p).I_{p}(x)=I(x)\ (\text{mod}\ p).

If pp is not too large, then the fingerprint Ip(x)I_{p}(x) can be sent as a short string. The number of bits to be transmitted is thus O(log⁡p)O(\log p). If Ip(x)≠Ip(y)I_{p}(x)\neq I_{p}(y), then obviously x≠yx\neq y. However, the converse is not true. That is, if Ip(x)=Ip(y)I_{p}(x)=I_{p}(y), then it is not necessarily the case that x=yx=y. We refer to this phenomenon as a false match. In general, a false match occurs if x≠yx\neq y, but Ip(x)=Ip(y)I_{p}(x)=I_{p}(y), i.e., pp divides I(x)−I(y)I(x)-I(y). We will later bound the probability of a false match.
The weakness of this method is that, for fixed pp, there are certain pairs of strings xx and yy on which the method will always fail. We get around the problem of the existence of these pairs xx and yy by choosing pp at random every time the equality of two strings is to be checked, rather than agreeing on pp in advance. Moreover, choosing pp at random allows for resending another fingerprint and thus increasing the confidence in the case x=yx=y. This method is described in Algorithm Stringequalitytest shown below (the value of MM will be determined later).

\begin{algorithm}
\caption{String Equality Test}
\begin{algorithmic}
\State $A$ chooses $p$ at random from the set of primes less than $M$.
\State $A$ sends $p$ and $I_p(x)$ to $B$.
\State $B$ checks whether $I_p(x) = I_p(y)$ and confirms the equality or inequality of the two strings $x$ and $y$.
\end{algorithmic}
\end{algorithm}

Below is the implementation of the above pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
import random
from sympy import primerange
def string_equality_test(x, y, M):
    primes = list(primerange(1, M))
    p = random.choice(primes)

    I_p_x = int(x, 2) % p
    I_p_y = int(y, 2) % p

    return I_p_x == I_p_y

Pattern Matching

Given a string of text X=x1x2…xnX = x_1 x_2 \ldots x_n of length nn and a pattern P=p1p2…pmP = p_1 p_2 \ldots p_m of length mm, where m≤nm \leq n, determine whether or not the pattern appears in the text.

Ip(Xj)=(xj⋅2m−1+⋯+xj+m−1) mod pIp(Y)=(y1⋅2m−1+⋯+ym) mod p\begin{aligned} I_p(X_j) = (x_j \cdot 2^{m-1} + \dots + x_{j+m-1}) \bmod p\\ I_p(Y) = (y_1 \cdot 2^{m-1} + \dots + y_m) \bmod p \end{aligned} 

\begin{algorithm}
\caption{Pattern Matching}
\begin{algorithmic}
\Input A string of text $X$ and a pattern $Y$ of lengths $n$ and $m$, respectively, where $m \leq n$.
\Output The first position of $Y$ in $X$ if $Y$ occurs in $X$; otherwise $0$.
\State Choose $p$ at random from the set of primes less than $M$
\State $j \gets 1$
\State Compute $W_p \gets 2^m \ (\text{mod}\ p)$, $I_p(Y)$, and $I_p(X_j)$
\While{$j \leq n - m + 1$}
    \If{$I_p(X_j) = I_p(Y)$}
        \Return $j$ \Comment{A match is found (probably)}
    \EndIf
    \State $j \gets j + 1$
    \State Compute $I_p(X_j)$ using $I_p(X(j+1)) = (2I_p(X(j)) - 2^m x_j + x_{j+m})(\bmod \ p)$
\EndWhile
\Return $0$ \Comment{$Y$ does not occur in $X$ (definitely)}
\end{algorithmic}
\end{algorithm}

The expected running time of the above algorithm is O(n+m)O(n + m).

Approximation Algorithms

Basic Definitions

A combinatorial optimization problem Π\Pi is either a minimization problem or a maximization problem. It consists of three components:

  • A set DΠD_{\Pi} of instances.
  • For each instance I∈DΠI\in D_{\Pi}, there is a finite set SΠ(I)S_{\Pi}(I) of candidate solutions for II.
  • Associated with each solution σ∈SΠ(I)\sigma\in S_{\Pi}(I) to an instance II in DΠD_{\Pi}, there is a value fΠ(σ)f_{\Pi}(\sigma) called the solution value for σ\sigma.
    If Π\Pi is a minimization problem, then an optimal solution σ∗\sigma^{*} for an instance I∈DΠI\in D_{\Pi} has the property that for all σ∈SΠ(I)\sigma\in S_{\Pi}(I), fΠ(σ∗)≤fΠ(σ)f_{\Pi}(\sigma^{*})\leq f_{\Pi}(\sigma). An optimal solution for a maximization problem is defined similarly. Throughout this chapter, we will denote by OPT(I)OPT(I) the value fΠ(σ∗)f_{\Pi}(\sigma^{*}).
    An approximation algorithm AA for an optimization problem Π\Pi is a (polynomial time) algorithm such that given an instance I∈DΠI\in D_{\Pi}, it outputs some solution σ∈SΠ(I)\sigma\in S_{\Pi}(I). We will denote by A(I)A(I) the value fΠ(σ)f_{\Pi}(\sigma).

Difference Bounds

For all instances II of the problem, the most desirable solution that can be obtained by an approximation algorithm AA is such that ∣A(I)−OPT(I)∣≤K|A(I) − OPT (I)| \leq K, for some constant KK.
Let G=(V,E)G = (V, E) be a planar graph. In solving the nn-coloring problem for GG, it holds that ∣A(I)−OPT(I)∣≤1|A(I) − OPT (I)| \leq 1.
There is no approximation algorithm with difference bound that solves the knapsack problem. Since the knapsack problem is known to be NPNP-complete, it is highly unlikely that the approximation algorithm A exists unless NP=PNP = P.

Relative Performance Bounds

Let II be a minimization problem and II an instance of II. Let AA be an approximation algorithm to solve II. We define the approximation ratio RA(I)R_A(I) to be

RA(I)=A(I)OPT(I).R_A(I) = \frac{A(I)}{OPT(I)}.

If II is a maximization problem, then we define RA(I)R_A(I) to be

RA(I)=OPT(I)A(I).R_A(I) = \frac{OPT(I)}{A(I)}.

Thus, the approximation ratio is always greater than or equal to 1. This has been done so that we will have a uniform measure for the quality of the solution produced by AA.

The bin packing problem

The optimization version of the BIN PACKING problem can be stated as follows. Given a collection of items u1,u2,…,unu_1, u_2, \ldots, u_n of sizes s1,s2,…,sns_1, s_2, \ldots, s_n, where each sjs_j is between 0 and 1, we are required to pack these items into the minimum number of bins of unit capacity. We list here one heuristic for the BIN PACKING problem.
First Fit (FF). In this method, the bins are indexed as 1, 2, \ldots All bins are initially empty. The items are considered for packing in the order u1,u2,…,unu_1, u_2, \ldots, u_n. To pack item uiu_i, find the least index jj such that bin jj contains at most 1−si1 - s_i, and add item uiu_i to the items packed in bin jj.

RFF(I)=FF(I)OPT(I)<2R_{FF}(I) = \frac{FF(I)}{OPT(I)} < 2