[Original] Kuibing 2003-11-14 This paper is mainly discussed for the retrospective algorithm to discuss the retrospective algorithm. After each discussion, there is also a relevant recommended question. 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 << end1; return;} for (i = 0; i
If (! used [i]) {/ * If the i-I element is not used * / / * uses the iFro using the i-I element, the purpose is made, the purpose is to make the element not available * / usd [i] ; / * Save the current searched first element * / p [pOS] = i; / * recursive search * / permute (POS 1); / * Restore the values before recursive, the purpose is to make the later modified elements available * / used [i] -;}}
Related Issues UVA 524 Prime Ring Problem Arable: A rejected element arrangement is taken from any n element. For example, for collection or = {1, 1, 2, 2}, n = | OR | = 4, R = 2, then arrangements as follows: {1, 1}; {1, 2}; {1, 2}; {1,1}; {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}. Algorithm is as follows:
#define free -1 int N, r; / * makes an order * / int E [MAXN] = {0, 0, 1, 1, 1}; int P [MAXN]; char usd [MAXN]; Void Permute (INT POS) {INT i; / * If the R element has been selected, print them * / if (pOS == r) {for (i = 0; i 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 Problems: Ural 1034 Queens in Peaceful Position Rehabilitates: Similar to a heavy alone. [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 Void DFS (INT POS) {IF (POS == R) {for (i = 0; I Related questions: URAL 1005 Stone Pile 1060 Flip Game 1152 The False Mirrors [Example] Looking for the biggest group problem. 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 For (j = 0; J CIN >> PATH [I] [J]; MAX = 1; /*initialization*/ Inclique [0] = 0; INGRAPH [0] = N; For (i = 0; i DFS (INGRAPH); Cout < < CIN >> N; } Return 0;} Reference papers Thanks to Bamboo, Leemars help related questions: acm.zju.edu.cn: 1492 maximum clique related website http://acm.uva.es/p http://acm.timus.ru/
