Lecture notes, lecture Week 11 - Professor abdou youssef PDF

Preview

Summary

Professor Abdou Youssef...

Description

Backtracking I. Introduction II. Formulation of the Problem of Generating Combinatorial Objects III. The General Backtracking Algorithm IV. Implementations for the Eight Applications I. Introduction Backtracking is a systematic method for generating all (or subsets of) combinortial objects. Examples of combinatorial objects include 1. Binary strings of n bits 2. Subsets of a given set E of n elements 3. Directed graphs of n nodes 4. Undirected graphs of n nodes 5. Permutations of a given size n 6. Hamiltonian cycles of a given graph 7. K-cliques of a given graph 8. K-colorings of a given graph Back to Top

II. Formulation of the Problem of Generating Combinatorial Objects In most of the generation problems, we have 1. Each object is represented by an array X[1:N] 2. The elements of the array are taken from a domain S={a1,a2,...,am}. Often, S is a finite set of successive integers.

3. The values of array X must satisfy some constraints C so that X represents a legitimate object of the type in question. We will show the specifics in each of the following instances of combinatorial object generation Problem 1: Generation of all n-bit binary strings Every n-bit binary string is represented by an array X[1:n] X[i] takes its values from {0,1} The constrainst C are empty because the values of the individual bits are indepedent Problem 2: Generation of all subsets of the set {1,2,...,n} Every subset is represented by the bitmap (i.e., Boolean array) X[1:n]; X[i] takes its values from {0,1}. X[i]=1 if i is in the subset being represented; X[i]=0 if i is not in the subset being represented. The constrainst C are empty because whether i is an element of the subset has no bearing on whether or not j is an element of the subset. Problem 3: Generation of all directed graphs of n nodes Every digraph of n nodes is representable by a 2D array A[1:n,1:n], which is the well-known adjacency matrix. The values of the entries in the array are binary and also are independent of one another. The 2D array can be represented by a a 1D binary array X[1:N] where N=n2 The value of each X[i] is in {0,1} The constraints C are empty because the values of entries of X (which are the entries of A) are independent Mapping from A to X: Stack the rows of A one after another. Thus, X[(i-1)n + j] = A[i,j] Problem 4: Generation of all undirected graphs of n nodes Every graph of n nodes is also representable by the 2D adjacency matrix A[1:n,1:n]. The values of the entries in the array are binary but are not independent of one another: A[i,j] = A[j,i] for all i and j Which is the symmetry contraint (or property) The 2D array can be represented by a a 1D binary array X[1:N] where N=n2, like in the case of directed graphs, but this time with the symmetry constraint. A preferable alternative is to only represent the upper triangle only, and thus eliminate the constraints as follows.

Map the upper triangle of A into a 1D binary array X[1:N], N=n(n-1)/2: A[1,2:n] goes first into X A[2,3:n] goes next into X A[3,4:n] goes next into X . . . A[n-1,n] goes last into X The value of each X[i] is in {0,1} The constraints C are back to being empty. Problem 5: Generation of all permutations of {1,2,...,n} A permutation is a one-to-one and onto mapping (function) f from {1,2,...,n} to {1,2,...,n}. The mapping of element i is denoted f(i). Another definition: A permutation is a re-ordering (re-arrangement) of the elements 1,2,...,n A third defintion: A permutation is a one-to-one matching. i is said to be matched with f(i). A permutation f can be represented by an array X[1:n] where X[i]=f(i). X[i] takes its elements from {1,2,...,n} Constraints: X[i] != X[j] for all i != j Problem 6: Generation of all Hamiltonian cycles in a given graph G=(V,E) of n nodes A Hamiltonian cycle is a cycle that goes through every node of the graph exactly once. Note that not all graphs have Hamiltonian cycles. A Hamiltonian cycle can be represented by an array X[1:n] where X[i] is the label of the i-th node in the cycle. Each X[i] takes its elements from {1,2,...,n}, which are the labels of the nodes. Constraints: 1. X[i] != X[j] for all i != j 2. (X[i],X[i+1]) is an edge for every i=1,2,...n-1, and (X[n],X[1]) is also an edge. Problem 7: Generation of all k-cliques in a given graph G=(V,E) of n nodes, where k is an integer, 1...