For example, below is one of the solution for famous 8 Queen problem.
Let’s begin by describing backtracking solution. “The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.”
We need to figure out an efficient way of keeping track of which cells are under attack. In previous solution we kept an 8-by-8 Boolean matrix and update it each time we placed a queen, but that required linear time to update as we need to check for safe cells.
Number 1 is automatic because of the way we store the solution. For number 2, 3 and 4, we can perform updates in O(1) time. The idea is to keep three Boolean arrays that tell us which rows and which diagonals are occupied.
Lets do some pre-processing first. Let’s create two N x N matrix one for / diagonal and other one for \ diagonal. Let’s call them slashCode and backslashCode respectively. The trick is to fill them in such a way that two queens sharing a same /diagonal will have the same value in matrix slashCode, and if they share same \diagonal, they will have the same value in backslashCode matrix.
For an N x N matrix, fill slashCode and backslashCode matrix using below formula –
The ‘N – 1’ in the backslash code is there to ensure that the codes are never negative because we will be using the codes as indices in an array.
Now before we place queen i on row j, we first check whether row j is used (use an array to store row info). Then we check whether slash code ( j + i ) or backslash code ( j – i + 7 ) are used (keep two arrays that will tell us which diagonals are occupied). If yes, then we have to try a different location for queen i. If not, then we mark the row and the two diagonals as used and recurse on queen i + 1. After the recursive call returns and before we try another position for queen i, we need to reset the row, slash code and backslash code as unused again, like in the code from the previous notes.
In
computer science, the
subset sum problem is an important problem in
complexity theory and
cryptography. The problem is this: given a set (or
multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is
yes because the subset {−3, −2, 5} sums to zero. The problem is
NP-complete.
An equivalent problem is this: given a set of integers and an integer
s, does any non-empty subset sum to
s? Subset sum can also be thought of as a special case of the
knapsack problem. One interesting special case of subset sum is the
partition problem, in which
s is half of the sum of all elements in the set.
Complexity
The
complexity of the subset sum problem can be viewed as depending on two parameters,
N, the number of decision variables, and
P, the precision of the problem (stated as the number of binary place values that it takes to state the problem). (Note: here the letters
N and
P mean something different from what they mean in the
NP class of problems.)
The complexity of the best known algorithms is
exponential in the smaller of the two parameters
N and
P. Thus, the problem is most difficult if
N and
P are of the same order. It only becomes easy if either
N or
P becomes very small.
If
N (the number of variables) is small, then an
exhaustive search for the solution is practical. If
P (the number of place values) is a small fixed number, then there are
dynamic programming algorithms that can solve it exactly.
Efficient algorithms for both small N and small P cases are given below.
Exponential time algorithm[edit]
There are several ways to solve subset sum in time exponential in
N. The most
naïve algorithm would be to cycle through all subsets of N numbers and, for every one of them, check if the subset sums to the right number. The running time is of order
O(2
NN), since there are 2
N subsets and, to check each subset, we need to sum at most
N elements.
A better exponential time algorithm is known which runs in time
O(2
N/2). The algorithm splits arbitrarily the
N elements into two sets of
N/2 each. For each of these two sets, it stores a list of the sums of all 2
N/2possible subsets of its elements. Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time
O(2
N/2N). However, given a sorted list of sums for
k elements, the list can be expanded to two sorted lists with the introduction of a (
k + 1)st element, and these two sorted lists can be merged in time
O(2
k). Thus, each list can be generated in sorted form in time
O(2
N/2). Given the two sorted lists, the algorithm can check if an element of the first array and an element of the second array sum up to
s in time
O(2
N/2). To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than
s, the algorithm moves to the next element in the first array. If it is less than
s, the algorithm moves to the next element in the second array. If two elements with sum
s are found, it stops. Horowitz and
Sahni first published this algorithm in a technical report in 1972.
Pseudo-polynomial time dynamic programming solution
- x1, ..., xN
and we wish to determine if there is a nonempty subset which sums to zero. Define the boolean-valued function Q(i, s) to be the value (true or false) of
- "there is a nonempty subset of x1, ..., xi which sums to s".
Thus, the solution to the problem "Given a set of integers, is there a non-empty subset whose sum is zero?" is the value of Q(N, 0).
Let A be the sum of the negative values and B the sum of the positive values. Clearly, Q(i, s) = false, if s < A or s > B. So these values do not need to be stored or computed.
Create an array to hold the values Q(i, s) for 1 ≤ i ≤ N and A ≤ s ≤ B.
The array can now be filled in using a simple recursion. Initially, for A ≤ s ≤ B, set
- Q(1, s) := (x1 == s)
where == is a boolean function that returns true if x1 is equal to s, false otherwise.
Then, for i = 2, …, N, set
- Q(i, s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi), for A ≤ s ≤ B.
For each assignment, the values of Q on the right side are already known, either because they were stored in the table for the previous value of i or because Q(i − 1,s − xi) = false if s − xi < A or s − xi > B. Therefore, the total number of arithmetic operations is O(N(B − A)). For example, if all the values are O(Nk) for some k, then the time required is O(Nk+2).
This algorithm is easily modified to return the subset with sum 0 if there is one.
The dynamic programming solution has runtime of
where
is the sum we want to find in set of
numbers. This solution does not count as polynomial time in complexity theory because
B − A is not polynomial in the
size of the problem, which is the number of bits used to represent it. This algorithm is polynomial in the values of
A and
B, which are exponential in their numbers of bits.
For the case that each xi is positive and bounded by a fixed constant C, found a linear time algorithm having time complexity O(NC) (note that this is for the version of the problem where the target sum is not necessarily zero, otherwise the problem would be trivial). In 2015, Koiliaris and Xu found the 
algorithm for the subset sum problem where is the sum we need to find.
Polynomial time approximate algorithm
An
approximate version of the subset sum would be: given a set of
N numbers
x1,
x2, ...,
xN and a number
s, output
- yes, if there is a subset that sums up to s;
- no, if there is no subset summing up to a number between (1 − c)s and s for some small c > 0;
- any answer, if there is a subset summing up to a number between (1 − c)s and s but no subset summing up to s.
If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in N and 1/c.
The solution for subset sum also provides the solution for the original subset sum problem in the case where the numbers are small (again, for nonnegative numbers). If any sum of the numbers can be specified with at most P bits, then solving the problem approximately with c = 2−P is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in N and 2P (i.e., exponential in P).
The algorithm for the approximate subset sum problem is as follows:
initialize a list S to contain one element 0.
for each i from 1 to N do
let T be a list consisting of xi + y, for all y in S
let U be the union of T and S
sort U
make S empty
let y be the smallest element of U
add y to S
for each element z of U in increasing order do
//trim the list by eliminating numbers close to one another
//and throw out elements greater than s
if y + cs/N < z ≤ s, set y = z and add z to S
if S contains a number between (1 − c)s and s, output yes, otherwise no
The algorithm is polynomial time because the lists S, T and U always remain of size polynomial in N and 1/c and, as long as they are of polynomial size, all operations on them can be done in polynomial time. The size of lists is kept polynomial by the trimming step, in which we only include a number z into S if it is greater than the previous one by cs/N and not greater than s.
This step ensures that each element in S is smaller than the next one by at least cs/N and do not contain elements greater than s. Any list with that property consists of no more than N/c elements.
The algorithm is correct because each step introduces an additive error of at most cs/N and N steps together introduce the error of at most cs.
Graph coloring
L(S),
sum of the two edges of least cost adjacent to v
