Void main () {Int a [MAXN], N, K; Printf ("Enter the Number N:"); Scanf ("% D", & N); A [0] = 1; A [1] = 1; Write (a, 1); for (k = 2; k <= n; k ) {PNEXT (A, K); Write (A, K); getchar ();}} four, recursive recursive is design and description algorithm A powerful tool, because it is often used in the description of the complex algorithm, to discuss it before further introducing other algorithm design methods. The algorithm that can be recursively described usually has such a feature: to solve the problem of size N, try to decompose it into a smaller problem, then the solution from these small problems can easily construct a large problem solution, and these scale Smaller problems can also use the same decomposition and integrated methods to decompose smaller problems, and deconstructing the solution to the larger problem from these smaller problems. In particular, when the scale n = 1, it can be directly affected. [Question] Write the Nth function FIB (N) of the Fibonacci number column. The number of Civic of Fibo is listed as: 0, 1, 1, 2, 3, ..., ie: FIB (0) = 0; FIB (1) = 1; FIB (N) = FIB (N-1) FIB ( N-2) (when n> 1). Write a recursive function: int FIB (INT N) {if (n == 0) Return 0; if (n == 1) Return 1; if (n> 1) Return FIB (N-1) FIB (N- 2);} The execution process of the recursive algorithm is pushed and regained two stages. In the period of the push, the solicity of more complex problems (N) is pushed into a simple problem (scale smaller than N) than the original problem. For example, in the above example, the FIB (N) is solved, and it is pushed to solve FIB (N-1) and FIB (N-2). That is to say, in order to calculate the FIB (N), FIB (N-1) and FIB (N-2) must be calculated, and FIB (N-1) and FIB (N-2) must be calculated, and the FIB must be calculated first. N-3) and FIB (N-4). Up to the subkey until FIB (1) and FIB (0) can be calculated, the results 1 and 0 can be obtained immediately. In the period of progress, there must be a case where it is returned. For example, in the function FIB, when n is 1 and 0. In the regression phase, when the simplest case is obtained, the step by step is returned, and the solution to a slightly complex problem is obtained. For example, after obtaining FIB (1) and FIB (0), the result of the Fib (2) is returned, ..., After obtaining the results of FIB (N-1) and FIB (N-2), the result of obtaining FIB (N) is returned. When writing a recursive function, local variables and parameter knowledge in the function are limited to the current call layer, and when the recursive enters the "simple problem" layer, the parameters and local variables at the original hierarchy are concealed. In a series of "simple questions" layers, they have their own parameters and local variables. Since recursive causes a series of function calls, and there may be a series of repetitive calculations, the recursive algorithm is relatively low. When a hand-altered algorithm can be easily converted into a handling algorithm, the program is usually written according to the recursive algorithm. For example, in the case, the function FIB (N) of the Nth item of the Fiboacci number should be used, that is, the first two items from the Fibo-Cilia number will be calculated from the first two items. Until Calculate the Nth item required. [Problem] Combination Problem Description: Find all the combinations of R number from Nature 1, 2, ..., N.
For example, all combinations of n = 5, r = 3 are: (1) 5, 4, 3 (2) 5, 4, 2 (3) 5, 4, 1 (4) 5, 3, 2 (5) 5, 3, 1 (6) 5, 2, 1 (7) 4, 3, 2 (8) 4, 3, 1 (9) 4, 2, 1 (10) 3, 2, 1 analysis list 10 combinations You can use such recursive ideas to consider the algorithm for combined functions. The set function is Void COMB (INT M, INT K) to find all the combinations of K numbers from natural numbers 1, 2, ..., m. When the combined first digital is selected, the subsequent numbers are a combination of K-1 number from the remaining M-1 number. This will change the combination of K-1 number in the M-1 number of combinations of k-1. The function introduced into the combination of work arrays a [], and the first number of the determined K digital combination is placed in a [K], and will be A [] after a combination is obtained. One combination output in the middle. The first number can be M, M-1, ..., K, and function will determine the first number of combinations, there are two possible options, due to the remaining elements that have not been set, continue to recurrent Determine; or because all elements of the combination have been determined, this combination is output. Details see the function COMB in the following procedure. [Program] # include # Define MaxN 100 INT A [MAXN]; Void Comb (INT M, INT K) {INT I, J; for (i = m; I> = K; I -) {a [k] = i; if (k> 1) COMB (i-1, k-1); else {for (j = a [0]; j> 0; j -) Printf ("% 4D" , A [J]); Printf ("/ n");}}}
Void main () {a [0] = 3; COMB (5, 3);} [Problem] Backpack Problem Description: There are different values, different weight items n pieces, and see some items from this N items. Select the scheme to make the total weight of the selected items do not exceed the specified limit weight, but the value of the item is selected. The weight of the N pieces is W0, W1, ..., Wn-1, respectively, and the value of the items are V0, V1, ..., VN-1, respectively. Use recursive search options. Set up a variety of options in front, and retains the total value of the total value to array Option [], the total value of the scheme is stored in the variable Maxv. The new program is currently being investigated, and its item selection is preserved in the array of COP []. It is assumed that the current program has considered the first I-1 item, and now you have to consider the first item; the weight of the item already included is TW; here, if the remaining items are selected, this program can be achieved. The expected value of the total value is TV. The algorithm introduces TV is when the expected value of the total value of the current program is less than the total value Maxv of the previous scheme, continue to investigate the current plan to become meaningless work, and should terminate the current program and immediately check the next scheme. Because when the total value of the program is not larger than the maxv, the program will not be re-examined, while ensuring that the scheme found after the function will be better than the previous program. There are two possibilities for the choice of the first item: (1) Consider the item i is selected, this possibility is only possible when it contains it not exceeding the total weight limit of the scheme. After selecting, continue to recursively consider the choice of the remaining items. (2) Considering the item I is not selected, this possibility is only the case where the value of the value is not included. The recursive algorithm is written as follows: try (item i, the currently selected weight and the total value of the total value of this program may be achieved) {/ * Consider the possibility of item i in the current program * / if (included Item I is acceptable) {contains item I in the current scheme; if (i
Writing functions and procedures as follows: [Program] # 程序 DE # define n 100 double limited, totv, maxv; int option [n], cop [n]; struct {double weight; Double value;} a [n]; int N; Void Find (INT I, Double TW, Double TV) {INT K; / * Considering the possibility of item i included in the current program * / if (TW A [i] .weight < = LIMITW) {COP [I] = 1; if (i maxv) IF (i
[Program] # include # define n 100 double limited; int Cop [N]; Struct ELE {Double Weight; double value;} a [n]; int K, n; struct {int FLG; Double TW Double TV;} TWV [N]; Void next (int i, double tw, double TV) {TWV [i] .flg = 1; TWV [i] .tw = TW; TWV [i] .tv = TV; } Double Find (struct ele * a, int N) {INT I, K, F; Double Maxv, TW, TV, Totv; Maxv = 0; for (TOTV = 0.0, K = 0; K = 0) {f = TWV [i] .flg; TW = TWV [i] .tw; TV = TWV [i] .tv; switch (f) {case 1: TWV [i] .flg ; if (Tw a [i] .weight <= limited) IF (i maxv) IF (i
V. Tracking backtracking method is also known as tentative method, which first gives up the limitations of the size of the problem, and gives the problematic candidate according to a certain order and inspect. When the current candidate is not possible, the next candidate is selected; if the current candidate does not satisfy the problem requirement, all other requirements are met, the scale of the current candidate is continuing to expand. If the current candidate is satisfied, the candidate is a solution of the problem when all requirements including the problem scale. In the backtracking method, give up the current candidate, find the next candidate process called back. Expand the scale of the current candidate solution, to continue the test, referred to a forward test. 1. Generally description of the backtracking method P, which is usually expressed as: a state space E = = = = {(x1, x2) for a known state space for known niece groups (x1, x2, ..., xn) , ..., XN) | ∈ ∈ ∈, i = 1, 2, ..., n}, give a constraint set D of one component in the n tone group, require E, all N yuan to satisfy all constraints of D in D. group. Where Si is the definition domain of the component XI, and | Si | Limited, i = 1, 2, ..., n. We call e-group groups of all constraints that satisfy D D. The simple method of solving the problem P is the enumeration method, that is, the all NM groups in E have detected whether it satisfies all of D. If satisfied, it is a solution to the problem P. But obvious, its calculation is quite large. We found that for many problems, the given constraints D is complete, namely I tone group (x1, x2, ..., xi) satisfying only X1, X2, ..., Xi all constraints means J (J j. Therefore, for the constraint set D has a complete problem P, once the determination of a J-group (X1, X2, ..., XJ) violates only X1, X2, ..., XJ, can be affirmed, Any N toll group (x1, x2, xj) (x1, x2, ..., xj, xj 1, x2, xn) prefixed in (x1, x2, ..., x1) is not a problem P, so you don't have to search them. Test them.
Backtracking Method is a higher algorithm that is more efficient than the enumeration method using the above nature of these problems. The backtracking method first expresses the state space E of the N-tuple of the problem P to a highly N-position-right ordered tree T, and all the solutions to the problem P in E are all pending solutions to the problem P in T. Tree T is similar to the search tree, which can be constructed: the elements in Si can be arranged to XI (1), xi (2), ..., xi (mi-1), | Si | = Mi, I = 1, 2 , ..., n. From the root start, every node of the i-layer of T has Mi son. This MI son to their parents, according to the order from left to right, respectively, respectively, Xi 1 (1), XI 1 (2), ..., xi 1 (mi), i = 0, 1 , 2, ..., n-1. According to this configuration, an N-group group (x1, x2, ..., xn) corresponds to a leaf node in T, the root of the root of the T in the path of the leaf node. X1, X2, ..., XN, and vice versa. Further, a prefix I tone group (x1, x2, x2, x1) (x1, x2, ..., xi) corresponds to one non-leaf in T in any 0 ≤ i ≤ N-1, E. Node, the root of T to this path of this non-leaven node, the weights of the I strips are X1, X2, ..., Xi, and vice versa. In particular, any of the n metaps in E is an air prefixed (), corresponding to the root of T. Thus, a solution to the problem P in e Searching a leaf node in T, requiring the n-strip from the n-strip from the root of the root of the Leaves to the n-string N rights x1, X2 , ..., XN satisfies all constraints of constraint set D. Searching in t in t, a natural way is from the root starting, with a depth priority strategy, in turn, sequentially sequentially sequentially meets the prefix (X1i) of constraint conditions (X1i), and the prefix 2 yuan group ( X1, x2), ..., prefix I tuple (x1, x2, ..., xi), ... until i = n so. In the backtracking method, the introduced tree referred to as a state space tree of problem P; an arbitrary node on the tree t is called the state node of the problem P; any of the leaf nodes on the tree T are called a problem P One solution state node; any of the remaining constraints that satisfy the constraint set D is referred to as a question P, which corresponds to a solution P. [Problem] Combination Problem Description: Find all the combinations of R number from Nature 1, 2, ..., N.
For example n = 5, R = 3 is all combinations: (1) 1, 2, 3 (2) 1, 2, 4 (3) 1, 2, 5 (4) 1, 3, 4 (5) 1, 3,5 (6) 1, 4, 5 (7) 2, 3, 4 (8) 2, 3, 5 (9) 2, 4, 5 (10) 3, 4, 5, the state space of this problem is : E = {(x1, x2, x3) | xi∈S, i = 1, 2, 3} where: s = {1, 2, 3, 4, 5} constraints are: x1
In the process of discharging the reciprocating method, that is, in the process of traverse the status space tree, if the non-recursive method is used, we generally use the stack data structure. At this time, not only can the nodes of the tree that are traversed by the stack, but also conveniently represent the establishment of a child node and backtracking process. For example, in a combination problem, we use a one-dimensional array stack [] indicating the stack. When the stack is started, the root node of the tree. If the element 1 is in the stack, then it is established and traversed (1) node; then if the element 2 is in the stack, it means establishing and traversing (1, 2) nodes; the element 3 is further in the stack, then it is established and traversed ( 1, 2, 3) Node. At this time, it can be judged that it satisfies all constraints, which is a solution, output (or saved). At this time, the top element (3) is out of the stack, that is, the backpoint (1, 2, 3) is back to the node (1, 2). [Problem] Combination Problem Description: Find all combinations from Nature 1, 2, ..., N. The solution to the problem is used to find a problem, and the combination of the found will be stored in A [0], A [1], ..., A [R-1] from a small to large sequence, the combined element satisfies the following properties: (1) a [i 1]> a [i], the latter number is larger than the previous; (2) a [i] -i <= N-R 1. According to the retrospective thinking, find the process can be described below: First give up the number of combinations of several numbers, the candidate combination begins with only one number 1. Because the candidate is satisfied with all the conditions other than the problem scale, the scale is expanded, and it satisfies the above conditions (1), and the candidate combination is changed to 1, 2. Continue this process to obtain a candidate combination 1, 2, 3. The candidate is satisfied with all the conditions including the problem scale, and is therefore a solution. On the basis of this solution, select a candidate, due to the 3 adjustment of 4 on A [2], and adjust all the requirements for problems in the future, get solutions 1, 2, 4 and 1, 2, 5 . Since the 5 cannot be adjusted again, it is to be traced from a [2] to a [1]. At this time, A [1] = 2 can be adjusted to 3, and the forward is protected forward, and the solution 1, 3, 4 is obtained. Repeat the above forward test and backward tracery until you want to retrore from A [0], explain all the solutions that have been finished. The procedures are written as follows: [Program] # Define MaxN 100 INT A [MAXN]; Void Comb (int M, INT R) {INT I, J; i = 0; A [I] = 1; do {IF A [i] -i <= m-r 1 {if (i == r-1) {for (j = 0; j
Main () {Comb (5, 3);} [Problem] Description of the Crossword: In the 3 × 3 squares of square marsh, you must fill in the number 1 to n (n≥10) in a number of numbers. Each square fills an integer, all of all adjacent two squares of the two integers. Various digital fillings that meet this requirement. The solution can be found by trying to find a problem, that is, starting from the first square, find a reasonable integer fill in the current checkered, and find a reasonable integer that can be fill in the next party. If you can't find a reasonable fill certificate for the current square, you will return to the previous equation and adjust the number of fills in the previous checkered. When the ninth checkered is also filled in a reasonable integer, it will find a solution, the solution is output, and adjust the ninth filling integer, find the next solution. In order to find a 9 digits that meet the requirements, it has not been filled in a number of beginnings, in a certain order (such as a small to large order), fill in an integer each time, then check the currently filled Can you meet the requirements. In the case of satisfying the requirements, the same method is continued to fill the integer as the next one. If the most recently filled integer does not meet the requirements, change the integer of the filled. If an integer for the current square test is unable to meet the requirements, you have to go back to the previous square, and adjust the integer filled in the previous side. Repeated extension, check or adjust, check until you find a solution to meet the problem requirements, will be designed. Retrospection method finds a solution algorithm: {INT M = 0, OK = 1; int N = 8; do {if (ok) extension; ELSE adjustment; OK = rationality of the previous M intense fill;} while (! OK || M! = N) && (M! = 0)) IF (M! = 0) Outputs; ELSE Output No report;} If the program is looking for all solutions, then after the decision will be found It should continue to adjust the integer fill in the last position and try to find the next solution. The corresponding algorithm is as follows: The algorithm for the retrospect list: {INT M = 0, OK = 1; int N = 8; do {if (ok) {if (m == n) {output solution; adjustment;} else Expansion;} else adjustment; OK = check the rationality of the previous M intense fill;} while (m! = 0);} To ensure that the program can terminate, adjustment must ensure that the exquisite fill sequence will not be again Experiments, that is, the required filling sequence is required to generate a model. The candidate given is set to form a candidate one by one in this order and test. From small to large or from large to small, it is possible to use. For example, when expanding, first fill in an integer 1, adjust, to find an integer that has not been used in the current candidate solution. The above expansion, adjustment, and inspection are written as procedures, see the procedures for all solutions to find all the solutions. [Program] # clude # Define N 12 Void Write (INT A []) {INT I, J; for (i = 0; i <3; i ) {for (j = 0; J <3 ; J ) Printf ("% 3D", A [3 * i j]); Printf ("/ n");} scanf ("% * c");}
INT B [N 1]; Int a [10]; int isprime (int m) {Int i; int primes [] = {2, 3, 5, 7, 11, 17, 19, 23, 29, -1 }; if (m == 1 || M% 2 = 0) RETURN 0; for (i = 0; primes [i]> 0; i ) IF (m == primes [i]) return 1; for (i = 3; i * i <= m;) {IF (m% i == 0) Return 0; i = 2;} return 1;} int Checkmatrix [] [3] = {{-1}, {0, -1}, {1, -1}, {0, -1}, {1, 3, -1}, {2, 4, -1}, {3, -1}, {4, 6, -1 }, {5, 7, -1}}; int selectnum (int start) {INT J; for (j = start; j <= n; j ) ing (b [j]) return j return 0;}
INT CHECK (INT POS) {INT I, J; IF (POS <0) Return 0; for (i = 0; (J = Checkmatrix [POS] [i])> = 0; i ) IF (! isprime) [POS] a [J]) Return 0; Return 1;}
INT Extend (INT POS) {a [ POS] = SELECTNUM (1); B [A] [POS]] = 0; RETURN POS;
INT Change (INT POS) {Int J; While (POS> = 0 && (J = SELECTNUM (A [POS] 1)) == 0) B [A [POS -]] = 1; IF (POS <0 ) RETURN-1 B [A [POS]] = 1; A [POS] = J; B [J] = 0; Return POS;
Void Find () {INT OK = 0, POS = 0; A [POS] = 1; B [A [POS]] = 0; DO {IF (OK) IF (POS == 8) {Write (a); POS = Change (POS); Else Pos = Extend (POS); Else Pos = Change (POS); OK = Check (POS);} While (POS> = 0)}
Void main () {INT i; for (i = 1; i <= n; i ) B [i] = 1; Find ();} [problem] N Queen problem problem Description: Ask it in a N × N On the chessboard, place all the layout of the Queen "of the Queen" that cannot be captured. This is a question from chess. Queen can capture each other in four directions along the vertical and two slashes. As shown in the figure, an queen placed in the 3rd column of the 4th line of the board, and the Queen on the "×" position can capture each other with this queen.
1 2 3 4 5 6 7 8 × × × × × × × × × × × × × × × × × × × × × × × can get the following inspiration from the map: a suitable solution is Column, only one queen on each line, and there is only one queen on a slash. The solve process starts from the air configuration. On the basis of the rational configuration, the first list is column M 1 column, until the N-column configuration is also reasonable, it will find a solution. Then change the N-column configuration and want to obtain the next solution. In addition, in any column, there may be n types. When it is configured in Chapter 1, when changing, select Chain 2, line 3, ... until the Nth line. When the N-line configuration is not found, it is necessary to turn back to change the configuration of the previous column. The algorithm for solving the Queen is as follows: {Enter the checkerboard size N; m = 0; good = 1; do {if (good) IF (m == n) {output solution; change, form the next candidate;} ELSE expands the current candidate to the next column; ELSE changes, form the next candidate, check the rationality of the current candidate;} While (M! = 0);} Before writing the program, first determine the edge chessboard data structure. A more intuitive method is to adopt a two-dimensional array, but it will find that this representation will bring difficult to adjust candidate and inspect their rationality. A better way is to directly represent those common information as much as possible. For this question, "common information" is not a specific location of the queen, but "whether an Queen has been reasonably placed in a certain row and a slash." Because of the queen in a certain column, introduce a one-dimensional array (col []), value col [i] means a queen in the Queen of COL [i] in the chess board For example: col [3] = 4, it means that there is a queen on the 4th line in the third column of the board. In addition, in order to make the program after receiving all the detrogenic to the initial position, the initial value of the set of col [0] is 0 when retracting to 0, and the program has been completed, and the program is running. In order to make the procedure simple and convenient in checking the rationality of the Queen's configuration, the following three work arrays: (1) array a [], a [k] means that there is no queen on the row; (2) array B [], B [K] indicates that there is no queen on the left and left low oblique lines of the row; (3) array C [], C [K] indicates that the row is left on the left and right low oblique lines; the chessboard is in the same right high left The checkered in low oblique lines, the sum of their line numbers and columns; the same left high and low-lateral checkered lines, their line numbers are the same as the difference. At the beginning, there is no queen on all rows and slashes, from the first line of the first line, the first queen begins, and placed a reasonable queen after the row col [M] line, ready to investigate the M When 1 column, in the array a [], b [] and c [], the position of the column is set to the position of the col [m] row; when it is traced back to the M-1 column from the M-M column, and Preparing to adjust the Queen Configuration of the M-1 column, clear the Queen's logo on the M-1 column, col [m-1] in the array, column, col [m-1]. An Queen is in M columns, col [m] rowner configuration is reasonable, determined by the array a [], b [] and c [] corresponding to the corresponding position.
See the following procedures: [Program] # include # include # Define MaxN 20 INT N, M, GOOD; INT Col [MAXN 1], A [MAXN 1], B [ 2 * MAXN 1], C [2 * MAXN 1]; void main () {Int J; char Awn; Printf ("Enter N:"); Scanf ("% D", & n); for (j = 0; j <= n; j ) a [j] = 1; for (j = 0; j <= 2 * n; j ) CB [J] = C [j] = 1; m = 1; col [1 ] = 1; good = 1; col [0] = 0; do {if (good) IF (m == n) {Printf ("column / T row"); for (j = 1; j <= n; J ) Printf ("% 3D / T% D / N", J, COL [J]); Printf ("Enter a character (q / q forward)! / n"); scanf ("% C", & AWN ); if (AWN == 'q' || AWN == 'q') EXIT (0); while (col [m] == n) {m -; a [col [m] = b [m COL [M]] = C [N m]] = 1;} col [m] ;} else {a [col [m] = b [m col [m]] = C [N M-COL [M]] = 0; COL [ M] = 1;} else {while (col [m] == n) {m -; a [col [m]] = B [M COL [M]] = C [N M-COL [M]] = 1;} col [m] ;} Good = a [col [M]] && B [M COL [M]]] && C [N M-COL [M]];} while (m! = 0);} Test method finding solution algorithm is often written into a recursive function, and the function queen_all () and functions in the two programs below are Queen_one () All solutions used to solve the Queen after the Queen. [Program] # include # include # Define MaxN 20 INT N; INT COL [MAXN 1], A [MAXN 1], B [2 * MaxN 1], C [ 2 * MAXN 1]; void main () {Int J; Printf ("Enter N:"); scanf ("% D", & n); for (j = 0; j <= n; j ) a [J ] = 1; for (j = 0; j <= 2 * n; j ) CB [J] = C [J] = 1; Queen_all (1, n);}
Void queen_all (int K, int N) {INT I, J; Char Awn; for (i = 1; i <= n; i ) IF (a [i] && b [k i] && c [n ki]) {col [k] = i; a [i] = b [k i] = C [N ki] = 0; if (k == n) {Printf ("column / T row"); for (J = 1; J <= n; J ) Printf ("% 3D / T% D / N", J, Col [J]); Printf ("Enter a character (q / q for exit)! / N"); Scanf ("% C", & AWN); IF (AWN == 'q' || awn == 'q') exit (0);} Queen_all (k 1, n); A [i] = b [k i] = c [n ki];}} Find a solution with the recursive method to find all the solutions, in the algorithm for finding a solution, the recursive algorithm should be a solution to the current candidate . When it becomes the final solution, the recursive function will no longer recurs the test, return immediately; if it is not a solution, it will continue to be tested. Setting function queen_one () Returns 1 means finding the solution, returning 0 means the current candidate cannot be a solution. See the following functions. [Program] # Define MaxN 20 INT N; INT COL [MAXN 1], A [MAXN 1], B [2 * MaxN 1], C [2 * MAXN 1]; Int Queen_one (int K, int K, int n) {INT I, FOUND; I = FOUND = 0; While (! Found && i
6. The greedy greedy method is a method that does not pursue the optimal solution and only wants to get a more satisfactory solution. Greedy method can generally be satisfied with satisfactory solution, because it saves a lot of time that must be expensive for finding the best solving and exhausting. Greed is often based on the current situation, regardless of the various possible overall conditions, so greed is not back. For example, when shopping is purchasing money, in order to make the number of coins retrieved, all the various issues of changing the change, but start from the biggest currency, consider the currency in the order of decreasing, first try to use A large-faced currency is to consider the next smaller face value when it is not enough money to currency. This is in using greedy law. This method is always optimal here because banks have a clearance type and coin value of the coin of the bank. If only face values are coins of 1, 5 and 11 units, and it is desirable to retrieve a total of 15 units. According to greedy algorithm, you should find 1 11 unit-wide coin and 4 1 unit-wide coins, and find 5 coins. But the optimal solution is a 3-unit face value of coins. [Problem] Packing Problem Description: The packing problem can be briefly summarized as follows: N items numbered 0, 1, ..., N-1, V0, V1, ..., VN-1, respectively. The N items are loaded into a plurality of boxes of V. It is contemplated that the volume of the N items does not exceed V, that is, for 0 ≤ n, there are 0
[Program] # include # include typedef struct ele {int vno; struct ele * link;} ele; typef struct hnode {int Remainder; ele * head; struct hnode * next;} hnode void main () {INT N, I, Box_Count, Box_Volume, * a; hnode * box_h, * box_t, * j; ele * p, * q; printf ("Input Box Locompital / N"); scanf ("% D ", & Box_volume); Printf (" input product species / N "); scanf ("% D ", & n); a = (int *) malloc (sizeof (int) * n); printf (" Please follow the volume Enter the volume of each item from the large to small order: "); for (i = 0; i vno = i; for (j = box_h; j! = null; j = j-> next) IF (j-> remainder> = a [i]) Break; if (j == null) {j = (hnde *) malloc (SizeOf (hnode)); J-> Remainder = Box_volume-a [i]; j -> Head = null; if (Box_H == NULL) Box_H = Box_t = J; ELSE BOX_T = BOIX_T-> Next = J; J-> Next = Null; Box_Count ;} else j-> remainder- = a [i] For (q = j-> next; q! = null && q-> link! = null; q = q-> link); if (q == null) {P-> link = j-> head; j-> HEAD = P;} else {p-> link = null; q-> link = p;}} printf ("A total of% D box", Box_count); Printf ("All box equipment is as follows:") ; for (j = bo X_H, I = 1; J! = NULL; J = J-> Next, i ) {Printf ("The% 2D Box, the remaining volume% 4D, the item is there; / n", I, J-> Remainder; for (p = j-> head; p! = null; p = p-> link) Printf ("% 4d", p-> vno 1); printf ("/ n");}} Question] The traversal problem of horses: On the 8 × 8 checkerboard, from any designated checker, find a path to each of the chessboard and only once. The horse is in a checkered, and there are up to 8 different locations reaching in one step, as shown. If the two-dimensional array BOARD [] [] means the checkerboard, its element records the step number when the horse is passed through this position.
Another eight possibility of the horse (called method) set a order, such as the current location in the board (i, j) checkered, the next possible location is (i 2, j 1) (I 1, j 2), (i-1, j 2), (i-2, j 1), (i-2, j-1), (i-1, j-2) (I 1, j-2), (i 2, j-1), the actual location is within the position that has not yet passed and the position of the boundary. In order to facilitate the procedure of the program, two arrays can be introduced to store various vertical and horizontal increments of the current position, respectively. 4 3 5 2 Ma 6 1 7 0 For this question, the backtracking method can generally be used. Here is a WARNSDOFF policy. This is also a greedy method. It chooses the greedy standard for the next export to the location where you are allowed, choose Exit The least that position. If the current location (i, j) is only three exits, they are positions (i 2, j 1), (i-2, j 1) and (i-1, j-2), such as respectively Go to these locations, these three locations will have different exits, assume that the number of exports of these three locations is 4, 2, 3, respectively, the program will choose to let the horse go (I-2, J 1) position. Since the program uses a greedy method, the entire finding process is always forward, there is no backtrack, so I can find the solution very quickly. However, for some beginning, it is actually solved, and the algorithm cannot find solutions. For the case where the solution is not found, the program can only change the selection order of 8 possible exports, you can find the solution. Changing the exit selection order is to change the selection standard when there is the same exit. The following procedures are taken into account that the variable START is introduced to control 8 possible selection sequences. At the beginning of 0, when you can't find a solution, let Start add 1, re-find. Details The following procedures. [Program] # include int delta_i [] = {2, 1, -1, -2, -2, -1, 1, 2}; int delta_j [] = {1, 2, 2, 1 , -1, -2, -2, -1}; int BOARD [8] [8]; int exitn (int I, int J, int S, int a []) {Int i1, j1, k, count; For (count = k = 0; k <8; k ) {i1 = i delta_i [(S K)% 8]; j1 = i delta_j [(S K)% 8]; if (i1> = 0 && I1 <8 && J1> = 0 && J1 <8 && Board [i1] [j1] == 0) a [count ] = (s K)% 8;} return count;}
INT NEXT (INT I, INT J, INT S) {INT M, K, MM, Min, A [8], B [8], Temp; M = EXITN (I, J, S, A); IF (M == 0) RETURN-1; for (min = 9, k = 0; k 64) BREAK; START ; } while (step <= 64) for (i = 0; i <8; i ) {for (j = 0; j <8; j ) Printf ("% 4d", Board [i] [j]); printf ("/ N / n");} scanf ("% * c");}}
Seven, granted method 1, the basic idea of granted the method of grants, any calculation time required to solve the problem with computers is related to its scale N. The smaller the problem, the easier directly solve, the less calculation time required for the problem. For example, for the sorting problem of n elements, when n = 1, no calculation is required; n = 2, as long as the comparison can be arranged in order; n = 3, as long as it is compared to 3 times, .... When N is large, the problem is not so easy to handle. To solve a larger problem directly, it is sometimes difficult. The design idea of grasping method is to divide a large problem that is difficult to solve, divided into some smaller the same problem, so that all breaks, divide them. If the original problem can be divided into k sub-problems (1
Its general algorithm design pattern is as follows: Divide_and_conquer (P) IF | P | ≤n0 Then Return (Adhoc (P)) Drake P Decomposed into less child problems P1, P2, ..., PK for i ← 1 to k DO yi ← Divide-And-Conquer (PI) △ Recursive Solution PI T ← MERGE (Y1, Y2, ..., YK) △ Mr. Return (T) Where | P | Represents the size of the problem P; N0 is a threshold, indicated When the size of the problem P does not exceed N0, the problem is easy to solve directly, and it is not necessary to continue to decompose. ADHOC (P) is the basic sub-algorithm in the grahe method for direct solution to a small scale P. Therefore, when the size of P does not exceed N0, the algorithm Adhoc (P) is solved directly. Algorithm MERGE (Y1, Y2, ..., YK) is the combined sub-algorithm in the grahe method, used to combine the corresponding solutions of P1, P2, ..., and PK of the Pk. Solution. According to the segmentation principle of the grahe method, how many sub-problems should be divided? How should the scale of each sub-problem be appropriate? These problems have been hard to answer. However, in a large number of practices, it is best to make the scale of the sub-problem substantially the same time when designing the algorithm with the granted method. In other words, the processing method of dividing a problem with k sub-problem equally equally equal is effective. Many problems can take K = 2. This approach to which this makes the sub-problem is approximately a balanced sub-problem, it is almost always good than the scientific scale. The merge step of the grahe method is the key to the algorithm. Some problems have a more obvious merger, and some problem mergers are more complicated, or there are a variety of mergers; or the merge scheme is not obvious. How to merge, there is no unified mode, and the specific problem is required. [Problem] Grand Integer Multiplication Description: Typically, when analyzing a calculation complexity of an algorithm, the addition and multiplication operations are treated by basic operations, and the calculation time required to perform a addition or multiplication is as one Depending on the constant of the computer hardware processing speed. This assumption is reasonable only if the computer hardware can directly represent and process the integer of the operation. However, in some cases, we have to handle a large integer, which cannot be processed within the range that the computer hardware can directly represent. If it is represented by floating point, it can only be approximately indicative of its size, and the valid numbers in the calculation result are also limited. To accurately represent a large integer and require a number on all digits on the calculation result, you must use the software method to implement a big integer arithmetic operation. Please design an effective algorithm to make two N-bit multiplier multiplication. Setting x and y are n-bit binary integers, and now calculate their product xy. We can design a method of calculating the product XY, but there is too much efficiency in this way. If each 2 1-digit multiplication or addition is a step operation, then this method is to be o (n2) step to obtain the product XY. Here we use the granted method to design a more efficient large integer product algorithm.
Figure 6-3 Big integer x and y We divide the n-bit binary integers x and y each section into 2 segments, the length of each section is N / 2 (for simplicity, assuming N is 2 power), As shown in Figure 6-3. Thus, x = A2N / 2 B, Y = C2N / 2 D. Thus, the product of X and Y is: XY = (A2N / 2 B) (C2N / 2 D) = AC2N (AD CB) 2N / 2 BD (1) If XY is calculated in formula (1), then We must perform multiplication (AC, AD, BC, and BD) of N / 2-bit integers, and 3 times not more than N-bit integer addition (corresponding to the plus sign in equation (1), etc. 2 times shift (respectively, 2n and 2n / 2) of the formula (1)). All of these additions and shifts share O (n) step operations. Set t (n) is the total number of computing required by two N-bit integers, and we have: (2) thus available to T (n) = O (N2). Therefore, the product of X and Y is not more effective than the product of X and Y is more effective than the method of primary school. To improve the calculation complexity of the algorithm, you must reduce the number of multiplication. To this end, we write XY to another: XY = AC2N [(AB) (DC) AC BD] 2N / 2 BD (3) Although, equation (3) seems to be complicated (1), But it only needs to do 3 N / 2-bit integers (AC, BD, and (AB) (DC)), 6 addition, subtraction and 2 shifts. This allows: (4) The set of formulas with decryption equation can be solved to T (N) = O (NLOG3) = O (N1.59). Using the formula (3), and considering the effects of X and Y symbols on the results, we give the full algorithm of the multiplication of large-scale multiplication MULT as follows: function MULT (X, Y, N); {x and y is 2 less than The integer of 2N, the return result is the product xy} begin s = Sign (x) * siGN (Y); {s (x); y = ABS (Y); y = abs (y) {X and Y take absolute value} if n = 1 THEN IF (x = 1) and (y = 1) THEN RETURN (S) else return (0) else begin a = x left side N / 2 bits; B. = X of the right side N / 2; C = Y, the left N / 2 bits; D = Y, the right side N / 2; ml = MULT (A, C, N / 2); M2 = MULT (AB, DC, N / 2); M3 = MULT (B, D, N / 2); s = s * (M1 * 2N (M1 M2 M3) * 2N / 2 m3); Return (S); end; end; The above binary integer multiplication can also be applied to the multiplication of the decimal integer to improve the number of multiplication of multiplication. [Problem] The closest point is a description of the problem: In the application, simple geometric objects such as points, circles are commonly used representatives in the real world.
In the issue involving these geometric objects, information is often required to understand other geometric objects in its neighborhood. For example, in the air traffic control problem, if the aircraft is taken as a point in the space, the two aircraft with the largest collision risk is the closest point in this space. Such problems are one of the basic problems of research in geometry. Below we focus on the closest point on the plane. The closest point to the problem is: the N points on a given plane, find a pair of points, so that in all directions of N points, the point pair is minimized. Strictly speaking, the closest point may be more than 1 pair. For the sake of simplicity, it is limited to one pair of findings. This problem is easy to understand, and it seems that it is not difficult to resolve. As long as we calculate each point from the distance from other N-1 points, we can find two points to achieve the minimum distance. However, this is too low, and the calculation time is required for o (N2). Whether we can find an O (NLOGN) algorithm. This problem clearly meets the first and second applicable conditions of the granted method. We consider dividing the set S of N points on the plane into two subsets S1 and S2, and about N / 2 points in each subset. Then, then recursively seek the closest point pair in each subset. Here, a key problem is how the merger step in the granted method, that is, how the closest point pair in the original set S is obtained by the closest point pair of S1 and S2, because the closest point of S1 and S2 The closest point pair that is not necessarily S is not. If the two points of the closest point pair of compositions S are in S1 or in S2, the problem is easy to solve. However, if these two points are in S1 and S2, the maximum number of N / 2 points in S1 is mostly N / 2 points in S1, respectively, and the N2 / 4 calculation is still required. And compare can determine the closest point pair of S. Therefore, according to this idea, the merge step consumption is O (N2). The calculation time t (n) required for the entire algorithm should be satisfied: t (n) = 2t (n / 2) O (N2) It is determined to t (n) = O (N2), that is, the time consumption with the merge step. In the same order, it does not have a better way to use exhaustion. From the set of formula law from the decipherent equation, we see that there is too much time when the problem is consumed. This inspires that we put the attention on the merge step. In order to make the problem easy to understand and analyze, we will first consider one-dimensional situation. At this time, N points are degraded into N solids x1, x2, ..., xn on the X-axis. The closest point is two real numbers that are different from the N implementings. We will apparent that X1, X2, ..., XN will be sequenced first, then, you can find the closest point pair with a linear scan. This method mainly calculates that time spent in sort, thus demonstrated in the sorting algorithm, time consumption is O (NLOGN). However, this method cannot be directly extended to two-dimensional situations. Therefore, in the simple case of this one-dimensional, we still try to solve the granted method and hope to promote the two-dimensional situation. Suppose we divide S with a point m on the X-axis to two subsets S1 and S2 such that S1 = {x ∈S | x ≤ M}; S2 = {x∈S | x> m}. In this way, there is P
Figure 1 Minimal level of one-dimensional situation We note that if the closest point of S is {P3, Q3}, ie | P3-Q3 | <Δ, the distance between P3 and Q3 and M does not exceed δ, That is, | P3-M | <Δ, | Q3-M | <δ, that is, P3 ∈ (m, m), Q3 ∈ (m, m δ). Since the semi-closed interval of each length is δ contains to a point (otherwise there must be a two-point distance of less than δ), and M is the split point of S1 and S2, so (m-Δ, m) is included in the present A point in s. In the same way, (m, m δ) is also included in a point in S. As can be seen from Fig. 1, if there is a point in (m-δ, m), this point is the greatest point in S1. Similarly, if there is a point in S in (m, m δ), this point is the minimum point in S2. Therefore, we can find a bit of the interval (M-δ, M) and (M, M δ) in linear time, namely P3 and Q3. Therefore, we can use the solution and S2 of S1 with the linear time and become the solution of S. That is, according to this granting strategy, the synthesis step can be completed in O (n) time. Do you have a valid algorithm? There is also a problem that needs to be seriously considered, that is, the selection of the split point M, and the division of S1 and S2. One basic requirement for selecting the split point M is thus derived a linear division of the set S, ie s = S1∪s2, S1∩S2 = φ, and S1 {x | x ≤ M}; s2 {x | x> m} . It is easy to see that if M = [MAX (S) Min (s)] / 2 is selected, the linear segmentation can be met. After selecting the split point, then the S is divided into S1 = {x∈S | x ≤ M} and S2 = {x ∈S | x> M}. However, such a segmentation point M is selected, it is possible to cause the imbalance of divided subsets S1 and S2. For example, in worst cases, | S1 | = 1, | S2 | = N-1, the resulting grade method to calculate the calculation time t (n) required in the worst case, should meet the recursive equation: t (n ) = T (N-1) O (n) Its solution is T (n) = O (N2). This phenomenon of this efficiency can be resolved by the method of "balance sub-problem" in division. That is, we can appropriately select the split point M, so that there are substantially equal number of points in S1 and S2. Naturally, we will think of the median number of coordinates of the N points of s. The linear time algorithm for selecting the number of bits described in the selection algorithm allows us to determine a balanced split point M within the o (n) time. At this point, we can design a algorithm of the closer point to the closest point of the point set S.
Float Pair (s); {if | s | = 2 Δ = | x [2] -X [1] | /*X[1..n] is stored in the N point coordinate * / else {if (| S | = 1) δ = ∞ ∞ ∞ {= s The median value of the coordinate value of each point; constructs S1 and S2, so that S1 = {x∈S | x ≤ M}, S2 = {x∈S | x> m}; Δ1 = pair (S1); Δ2 = pair (S2); p = max (S1); q = min (S2); Δ = min (Δ1, Δ2, QP);} return (Δ) The above analysis can be seen that the division step of the algorithm and the total share of the merged step O (N). Therefore, the calculation time t (n) consumed by the algorithm is satisfied: Solution This recursive equation can be t (n) = O (nlogn).
[Question] Cycling schedule problem description: The N = 2K athletes must be played in the tennis cycle. Now design a game schedule to meet the following requirements: (1) Each player must be once again with other N-1 players; (2) Every player can only participate once a day; (3) cycle in N-1 The end of the day. Please press this request to design a table with N rows and N-1 columns. In the first line in the table, the third player is filled with the players encountered in JINs. Where 1 ≤ i ≤ N, 1 ≤ j ≤ N-1. According to the grahe policy, we can divide all the players into two halves, and the N-player game schedule can be determined by the N / 2 players. Recursively use this one-to-two strategy to divide the players until only two players are left, the development of the game schedule is very simple. At this time, just make these two players to play.
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 6 7 8 5 3 4 1 2 7 8 5 6 1 2 3 4 3 2 1 8 5 6 7 1 2 3 4 5 6 7 8 1 4 3 2 1 2 1 4 3 6 5 8 7 2 1 4 3 1 2 3 4 1 2 7 8 5 6 3 2 1 4 2 1 4 3 2 1 8 7 6 5 4 3 2 1 (1) (2) (3) Figure 1 2, 4 and 8 player game schedule Table 1 The square table (3) listed in Figure 1 is 8 players. The upper left corner and the two small pieces of the lower left corner are the players 1 to players 4 and players 5 to players 8 for 3 days. According to this, all the numbers in the upper left corner small block are copied in the lower right corner accordingly, and all the numbers in the lower left corner block are copied in the upper right corner according to their relative position, so that we will arrange 1 to 1 Players 4 and players 5 to players 8 in the next 4 days. This idea is easy to extend this game schedule to the situation with any number of players.
8. Dynamic planning methods often encounter complex problems that cannot be simply decomposed into several sub-problems, and will decompose a series of sub-problems. Simply use a method of decomposing a problem with a sub-problem, and the solution to the solution to the solution, the problem will increase when the problem is increased. In order to save the same amount of the same sub-problem, an array is introduced, regardless of whether they are for final solution, solving all sub-problems in this array, this is the basic method used by the dynamic planning method. The following uses an example to illustrate the use of dynamic planning methods. [Problem] For the longest common character subsequence of two character sequences: The subsequence of the character sequence refers to the number of characters (may not be removed) from a given character sequence (may not be removed) The character sequence formed. Let the given character sequence x = "x0, x1, ..., xm-1", sequence y = "Y0, Y1, ..., YK-1" is the subsequence of X, and there is a strict incremental subscript sequence of X < I0, I1, ..., IK-1> make all J = 0, 1, ..., k-1, with xij = Yj. For example, x = "abcbdab", y = "bcdb" is a subsequence of X. Given two sequences A and B, the sequence z is a common subsequence of A and B, refers to the subsequences of A and B. The problem requires the longest common subsequence of two sequences A and B. If all subsequences listed in A, the subsequences of the b is employed, and the subsequences of the subsequent sequences are detected, and the resulting subsequences are recorded, the longest common subsequence is finally obtained. This method is too much time consumption. Consider how to decompose a sub-problem for the longest public subsequence, set a = "A0, A1, ..., AM-1", B = "B0, B1, ..., BM-1", and z = "Z0, Z1, ... ZK-1 "for their longest common subsequences. It is not difficult to prove that there is a nature: (1) If AM-1 = BN-1, zK-1 = AM-1 = BN-1, and "Z0, Z1, ..., ZK-2" is "A0, A1, ..., AM-2 "and" B0, B1, ..., BN-2 ", one of the longest public subsequences; (2) if AM-1! = BN-1, if zK-1! = AM-1, The "Z0, Z1, ..., ZK-1" is a maximum common subsequence of "A0, A1, ..., AM-2" and "B0, B1, ..., BN-1"; (3) if AM- 1! = BN-1, if ZK-1! = BN-1, Implication "Z0, Z1, ..., ZK-1" is "A0, A1, ..., AM-1" and "B0, B1, ..., One longest common subsequence of BN-2.
In this way, when finding a and b, if there is AM-1 = BN-1, further solve a child problem, find "A0, A1, ..., AM-2" and "B0, B1, ..., One of the longest public subsequences of BM-2; if AM-1! = BN-1, we must solve two child problems, find "A0, A1, ..., AM-2" and "B0, B1, ..., One of the longest common subsequences of BN-1 and finds a maximum public subsequence of "A0, A1, ..., AM-1" and "B0, B1, ..., BN-2", and then takes two The longer member is the longest common subsequence of A and B. Definition C [I] [J] is the length of the longest common subsequence of sequence "A0, A1, ..., AI-2" and "B0, B1, ..., BJ-1", calculate C [I] [J] Recounted is as follows: (1) C [I] [j] = 0 If i = 0 or J = 0; (2) C [i] [j] = C [i-1] [j-1] 1 If i, j> 0, and A [i-1] = b [j-1]; (3) C [i] [j] = max (c [i] [j-1], C [i- 1] [j]) If i, j> 0, and A [i-1]! = B [j-1]. According to this calculation, the length function of the longest common subsequence of two sequences can be written. Since C [I] [J] is only dependent on C [I-1] [J-1], C [I-1] [J] and C [I] [J-1], so it can be from C [ m] [n] Start, track the generation process of C [I] [J], and the longest common subsequence is reversed. See the details. # include # include # Define n 100 Char a [n], b [n], str [n]; int LCS_LEN (Char * a, char * b, int C [] [ N]) {INT M = Strlen (A), N = Strlen (b), i, j; for (i = 0; i <= m; i ) C [i] [0] = 0; for (i = 0; i <= n; i ) C [0] [i] = 0; for (i = 1; i <= m; i ) for (j = 1; j <= m; j ) IF (a [i -1] == b [j-1]) C [i] [j] = c [i-1] [j-1] 1; ELSE IF (C [i-1] [j]> = C [ I] [J-1]) C [I] [J] = C [i-1] [J]; ELSE C [I] [J] = C [i] [J-1]; Return C [M] [n];
Char * Buile_lcs (Char s [], Char * A, Char * B) {INT K, I = Strlen (A), J = Strlen (B); K = LCS_LEN (A, B, C); S [K] = '/ 0'; while (k> 0) IF (C [i] [j] == C [i-1] [j]) i -; else f (c [i] [j] == c [i] [j-1]) j -; else {s [- k] = a [i-1]; I -; J-;} returnz
Void main () {Printf ("Enter Two String (<% D)! / N"; Scanf ("% S% S", A, B); Printf ("LCS =% S / N", Build_lcs (STR, A, B));} 1. The applicable conditions for dynamic planning have certain limitations, beyond specific conditions, it lost its role. Similarly, dynamic planning is not universal. The problem of applicable dynamic plan must meet the optimization principles and no-time. (1) Optimization principle (most merely sub-structural properties) The optimization principle can be elaborated: A optimization strategy has such a nature, regardless of the pre-decision-making, regardless of the state of the previous decision, the rest Decision must constitute the optimal strategy. In short, the sub-strategy of one optimized strategy is always optimal. One problem satisfies the principle of optimization, but it has the most description of the nature.
Figure 2, for example, if the routes i and j are the optimal path of A to C, depending on the optimization principle, the route J is the optimal route from b to c. This can be proven to be proven to be proven: assuming that another path J 'is the optimal path of B to C, then the route of A to C takes I and J' than I and J, contradictory. Thus, J 'must be the optimal path of B to C. The optimization principle is the basis of dynamic planning, any problem, if the support of the optimization principle is not possible, it is impossible to calculate the dynamic planning method. Dynamic planning basic equations based on optimization principles are basic methods to solve all dynamic planning issues. (2) Non-rearwardness will be arranged in each stage, and for a given stage state, the status of each stage cannot directly affect its future decisions, but can only pass the current state. In other words, each state is a complete summary of past history. This is no rear direction, also known as there is no effect. (3) The key to the superimposed dynamic planning algorithm of child problems is to solve redundancy, this is the fundamental purpose of dynamic planning algorithm. Dynamic planning is essentially a technique in spatial transfer time, which has to store various states in the process in the process of implementation, so its spatial complexity is greater than other algorithms. Selecting the dynamic planning algorithm is because the dynamic planning algorithm can bear in space, and the search algorithm cannot be spaced at time, so we take time. Therefore, there is also a significant feature of the problem that can be solved with dynamic planning: the overlap of the child. This nature is not a necessary condition for dynamic planning, but if the nature cannot meet, the dynamic planning algorithm does not have advantages compared to other algorithms. 2. The basic idea of dynamic planning mainly introduces some of the theoretical basis for dynamic planning, and we will show the dynamic plan of the above-mentioned obvious stage division and state transfer equation called standard dynamic planning, this standard dynamic plan is studying The multi-stage decision issues are derived, with strict mathematical forms, suitable for theoretical analysis. In practical applications, the phase division of many problems is not obvious, and if it is deliberately divided by the phase method. In general, as long as the problem can be divided into a smaller child problem, and the best solution of the original problem contains the best solution of the child problem (ie, the most desirable principle), can consider the use of dynamic planning . The essence of dynamic planning is to grants thoughts and solve redundancy. Thus, dynamic planning is a sub-problem that decomposes problem instances into smaller, similar sub-problems, and solves the repetitive child problem. Algorithm strategy for optimization problems. It can be seen that the dynamic planning method is similar to the granted method and greedy method, and they are induced by the problem instance into smaller, similar sub-problems, and produce a global optimal solution by solving the problem. Among them, the current choice of greed can rely on all the options that have been made, but do not rely on the choices and sub-problems they have to do. Therefore, the greedy method is topped downwards, and a greedy choice will be made step by step; while the various sub-issues in the grahe method are independent (ie, the public sub-problem is not included), so once the subsequent problem is obtained. It is possible to solve the solution of the subprocess from the solution. However, it is not enough, if the current choice may have a problem that may rely on sub-problem, it is difficult to achieve the global optimal solution through local greed; if each sub-problem is not independent, the rule of control must do many unnecessary work, Repeat the public subprocess. Solving the above problems is to use dynamic planning. This method is primarily applied to optimization problems, which will have a variety of possible solutions, each solution has a value, and dynamic plan finds the solution of the optimal (maximum or minimum) value. If there are several solutions to take the best value, it only takes one of them.
During the solution, the method is also the solution to the global optimal solution by solving the partial problem, but is different from the granted method and greedy. Dynamic planning allows these sub-problems to be not independent, (ie, each child problem can be included) Public sub-issues also allow it to be selected by the solution of their own sub-problems, which is only solved by each child, and saves the results to avoid calculation every time you encounter. Therefore, the problem for the dynamic planning method has a significant feature, that is, the child problems in the sub-problem tree have exhibited a large amount of repetition. The key to the dynamic planning method is that for repeated child problems, only the first encounter is solved, and saves the answer, let the answer directly to the direct reference, do not have to resolve. 3. The basic steps of the dynamic planning algorithm are designed to design a standard dynamic planning algorithm, which can usually be carried out in the following steps: (1) Division phase: divide the problem into several phases. Note that such a certain stage must be ordered or can be sorted (ie, no post-pendant), otherwise the problem cannot be solved by dynamic planning. (2) Select Status: A variety of objective conditions in which problems develop to each stage are expressed in different states. Of course, the choice of state should be met without post. (3) Determine the decision and write the status transfer equation: The reason why the two steps are placed, because decision-making and state shift has natural links, state shift is based on the state and decision in the previous stage to derive the state of this phase. . So, if we identify the decision, the status transfer equation is written. But in fact, we often do it, determine the decision based on the relationship between the two adjacent numbers of states. (4) Write a planning equation (including boundary conditions): The basic equation of dynamic planning is a general formal expression of the planning equation. Generally speaking, this step is still relatively simple as long as the phase, state, decision making and state shift is determined. The main difficulty of dynamic plan is theoretically design, once design is completed, and the implementation is very simple. According to the basic equation of the dynamic plan, the optimal value can be recursively recursively calculated, but it is generally changed to a recurrent calculation, and the general framework implemented is as follows: the basic framework of standard dynamic planning 1. Initializing FN 1 (XN 1) ; {Border Condition} for K: = N DOWNTO 1 Do I for each xk∈xk do for each UK∈UK (XK) DO Begin 5. FK (XK): = One Extreme Value; {∞ or -∞} 6 . xk 1: = TK (XK, UK); {State Transfer Equation} 7. T: = φ (FK 1 (XK 1), VK (XK, UK)); {Basic Equation (9)} IF T ratio FK (XK) better THEN FK (XK): = T; {calculation fk (xk) optimal value} end; 9. T: = one extreme value; {or -∞} for each x1 ∈X1 DO 11. IF F1 (x1) ratio T better THEN T: = F1 (x1); {According to 10 octopus, the optimal indicator} 12. Output T; however, often does not explicitly according to the above Steps design dynamic planning, but in the following steps: (1) Analyze the nature of the optimal solution and scrapen its structural characteristics. (2) Decarily define the optimal value. (3) The optimal value is calculated from the bottom-up mode or the auto-down memory method (memo method). (4) Constructs an optimal solution based on the information obtained when calculating the optimal value.
Steps (1) ~ (3) are the basic steps of the dynamic planning algorithm. In the case where the optimal value is required, step (4) can be omitted, and if a problem is required, step (4) must be performed. At this time, when the optimum value is calculated in step (3), more information is usually required to quickly construct a optimal solution according to the recorded information in step (4). [Problem] Optimal Triangulation Problem Problem Problem Problem of Convex Polygon: The polygon is a segmental linear closure of the plane. That is, the polygon is composed of a series of first-tail line segments. The linear segments of the polygon are called the edges of the polygon. The connection point of the multilateral phase is referred to as a vertex of the polygon. If there is no other common point in addition to the vertices between the edges, the polygon is called a simple polygon. A simple polygon is divided into three parts: all points surrounded in the polygon constitute the internal interior of the polygon; the polygon itself constitutes the boundary of the polygon; the rest of the plane constitutes the exterior of the polygon. When a simple polygon is constituted, the simple polygon is called convex polygons. That is to say, all points on the linear segments of any two points in the convex polygon boundary or the internal direction are all in the internal or boundary of the convex polygon. Typically, a convex polygon is represented by the counterclockwise sequence of polygonal vertices, i.e., P = represents a convex polygon having n strips V0v1, V1v2, ..., VN-1VN, wherein Convention V0 = Vn. If VI and VJ are two vertices that are not adjacent to the polygon, the line segment Vivj is called a string of the polygon. The strings are divided into convex two sub-polygon and . The polygonal triangulation is a collection T of a triangular string that divides the polygon into a triangular string that does not overlap each other. Figure 1 is a two different triangulation of a convex polygon.
(a) (b) Figure 1 2 different triangularities of convex polygon in a triangular tip of convex polygon P, each string is not interacting and the number of chords has reached the maximum, that is, any of P is not in T The strings must intersect a certain string in t. In a triangular triangular scraping with N-top points, there is just N-3 strings and N-2 triangles. The problem of convex polygon optimal triangulation is: given a convex polygon P = , and defined the right Ω on a triangular shape consisting of a parallel string of the polygon. A triangulation of the convex polygon is required such that the amount of power on the triangle is minimized in the triangular cross section. Various powerful function ω can be defined on the triangle. For example: Defining ω (△ Vivjvk) = | Vivj | | Vivk | | VKVJ |, where | vivj | is a European Distance of Point VI to VJ. The optimal triangulation of this power function is the slice of length. (1) The optimal triangulation problem of the most excited polygonal polygonal polygon is the most excited sub-structural property. In fact, if a convex (N 1) edge P = is a triangular V0VKVN, 1 ≤ K ≤ N-1, then T is 3 Some weights, ie the weight of the triangle V0VKVN, the weight of the sub-polygon and the right of . It is also possible to assert that the triangulation of the two sub-polygons determined by T is also optimal because if there is or more powerful triangular triangle The split will result in the contradiction between T is not the optimal triangle. (2) The recursive structure of the right triangular cross section corresponds, first, definition T [I, J] (1 ≤ i The weight corresponding to the triangulation, the optimal value. For the convenience, the retracted polygon has the weight zero. According to this definition, the highest value of the power to be calculated as the row of the multilateral P P corresponds to T [1, n]. The value of t [i, j] can be calculated using the mostteficized child structure properties. Since the weight of the degraded 2 vertex polygon is 0, T [I, I] = 0, i = 1, 2, ..., n. When J 1 I≥1, the child polygon has at least 3 top points. From the most preferred of the structural properties, the value of T [I, J] should be T [K 1, J] value, plus the weight of ΔVi-1Vkvj, and Take the smallest in the range of i ≤ K ≤ J-1. Thus, T [I, J] can be recursively defined as:
(3) Calculate the dynamic planning algorithm of the calculated convex (N 1) edge P = described below, and the input is the convex polygon P = power function ω, output is the optimum value T [I, J] and make T [I, K] T [K 1, J] Ω (△ Vi-1Vkvj) To achieve the optimal position (k =) s [i, j], 1 ≤ i ≤ j ≤ n. Procedure minimum_weight (p, w); begin n = length [p] -1; for i = 1 to n DO T [i, i]: = 0; for ll = 2 to n DO for i = 1 to N-LL 1 Do Begin J = I LL-1; T [I, J] = ∞; for K = I to J-1 Do Begin Q = T [I, K] T [K 1, J] Ω (△ vi-1vkvj); if q When the weight T [I, J] corresponding to the separation, the third of this optimal triangle cross section is also recorded in S [I, J]. The position of the vertex. Therefore, using the mosttefic structure properties and by means of S [I, J], 1 ≤ I ≤ J ≤ N, the optimal triangulation of the optimal triangulation of the boss (N L) edge It is easily constructed in ο (n) time.
Exercise: 1, car refueling question: There is a road with a distance of L kilometer, which is distributed with M gas stations, and their positions are p [i] (i = 1, 2, ..., m), while the car After the fuel tank is filled with oil (the fuel tank can be cheaper with the fuel km), you can travel N kilometers. Design a solution to make the car pass through this highway as small as possible (the car is filled with oil). 2, the shortest path: There is a network, requiring the shortest path from a certain vertex to other vertices 3, hip horses: on 8 * 8 checkered board, starting from any designated square, looking for a walk The checkerboard is passed and only one path is passed. 4, the traversal of the binary tree 5, backpack problem 6, achieve two large integers by dividing 7, X1, X2, ..., XN is the N points on the straight line, to cover the closed interval of the unit length This n point, how many such unit closed intervals do you need? 8. When the relationship "<" and "=" will be arranged in sequence, there are 13 different order relationships: A = B = C, A = B 0), and the k sheet flake is moved to I 1 (i
