Arrangement combination and backtracking algorithm
Kuibing
Thank Bamboo, Leemars help
[Keyword] Recursive DFS
[Foreword] This paper mainly discusses the retrospective algorithm for the alignment combination. After each discussion, there are relevant recommendations. Before you start, we should first look at the concept of backtracking algorithms, so-called back: the process of searching a state tree, this process is similar to the depth of the map (DFS), each step in search (every step here The first layer of the search tree produces a correct solution, and then checks the previous step record in each step in the future, and it will select each search state after the condition (ie, i 1 layer of state node).
The basic algorithm that needs to be grasped:
Arrange: is the arrangement of R element simultaneously from n elements, remember to be p (n, r). (When r = N, we call P (n, n) = n! For all-alumnism) For example, we have set or = {1, 2, 3, 4}, then n = | OR | = 4, cut regulations R = 3, then P (4, 3) is:
{1,2,3}; {1, 3, 2}; {1, 3, 4}; {1,4,2}; {1, 4, 3}; {2 1, 3}; {2, 3, 1}; {2, 3, 4}; {2, 4, 1}; {2, 4, 3}; {3, 1 2}; {3, 1, 4}; {3, 2, 1}; {3, 4, 1}; {3, 4, 2}; {4, 1, 2 }; {4, 1, 3}; {4, 2, 1}; {4, 2, 3}; {4, 3, 1}; {4, 3, 2}
The algorithm is as follows:
INT N, R;
CHAR USED [MAXN];
INT P [MAXN];
Void Permute (INT POS)
{INT I;
/ * If it is already the first element, you can print RE elements.
IF (POS == R) {
For (i = 0; i COUT << (p [i] 1); Cout << Endl; Return; } For (i = 0; i IF (! used [i]) {/ * If the i-I element is not used * / / * Use the i-th element to make the used mark, the purpose is to make the element not available * / Used [i] ; / * Save the current searched i kind of element * / P [POS] = i; / * Recursive search * / Permute (POS 1); / * Restore the value before recursive, the purpose is to make the elements available in the future * / Used [i] -; } } Related questions UVA 524 Prime Ring Problem Alternative: is from any n element, take R-repeatable elements. For example, for collection or = {1, 1, 2, 2}, n = | OR | = 4, R = 2, then arrangements as follows: {1,1}; {1, 2}; {1,1}; {1, 2}; {1, 2}; {2, 1}; {2, 1}; {2 , 2}; {2,1}; {2,1}; {2,2} The rearrangement is: {1,1}; {1,2}; {2,1}; {2,2}. The algorithm is as follows: #define free -1int n, r; / * Make the elements Ordered * / int E [MAXN] = {0, 0, 1, 1, 1}; int P [MAXN]; char usd [MAXN]; Void Permute INT POS) {INT i; / * If R element has been selected, print them * / if (pOS == r) {for (i = 0; i UVA 10098 Generating Fast, Sorted Permutations Combination: A non-repetitive element in n different elements constitutes a subset without considering the order of its elements, called the non-heavy combination of R, for example or = {1, 2, 3, 4}, n = 4, r = 3 has no recombination: {1,2,3}; {1,2,4}; {1, 3, 4}; {2, 3, 4}. The algorithm is as follows: INT N, R; INT C [5]; char usd [5]; Void Combine (int POS, INT H) {INT i; / * If you have selected R element, print them * / if (POS = = r) {for (i = 0; i related question: Ural 1034 Queens in Peaceful Position Remainable combination: similar to a heavy arrangement. [Example] Give a given N (n <10) point, draw a simple path, including all points, so that the path is shorter. Solution: This is a travel salesman problem TSP. This is an NP problem, in fact, is a ranked selection problem. The algorithm is as follows: INT N, R; CHAR USED [MAXN]; INT P [MAXN]; Double Min; Void Permute (INT POS, DOUBLE DIST) {INT I; IF (POS == N) {IF (Dist Solution This question is very simple, in fact, from the binary representation of 0 to 2 ^ R. The algorithm is as follows: Void DFS (INT POS) {IF (POS == R) {for (i = 0; I Related questions: Ural 1005 stone pile 1060 Flip Game 1152 The False Mirror [Example] Looking for the biggest group. The group of a figure is a sub-map of all points of the figure, and is connected. That is, a sub-figure contains N top points and N * (n-1) / 2, looking for the biggest group problem is an NP issue. The algorithm is as follows: #define maxn 50 int N, max; int path [maxn] [MAXN]; int inclique [max "; void DFS (int ingraph []) {INT i, J; int graph [MAXN]; if (Inclique [0] INGRAPH [0] <= max) Return; IF (Inclique [0]> max) max = inclique [0]; / * For all points in the figure * / for (i = 1; i <= ingraph [0] ; i ) {/ * placed the node * / Inclique [0]; Inclique [Inclique [0]] = ingraph [i]; / * Generate a new sub-map * / graph [0] = 0 For (J = I 1; J <= INGRAPH [0]; J ) IF (Path [ingraph [i]] [ingraph [j]]) GRAPH [ graph [0]] = ingraph [j]; DFS (graph); / * Remove node from the group * / --inclique [0];}}}}}} int main () {int}} int main () {INT I, J; CIN >> N; While (n> 0) {For (i = 0; i Related questions: ACM.ZJU.EDU.CN: 1492 Maximum Clique Related Websites http://acm.uva.es/p http://acm.timus.ru/ Contact me: MSN: bing0672@hotmail.com
