[Original]
ZENGYI820
2003-06-14 Introduction to Combination Algorithm (A Brief Introduction To Combinator Algorithm)
The combination algorithm is a very important branch in algorithm analysis. I will not say about it in computer science, I will finish the entire material, the algorithm is what I collected, just a simple introduction, then I put me The material has made a finishing, everyone collects, it feels very useful, I have a long time and energy, I am ready to postively study, not too much time to send a lot of classic articles, this piece is big.
About the algorithm of combined problem, the calculation object is a discrete, limited mathematical structure. From the perspective of methodology, the combined algorithm includes two aspects of the algorithm design and algorithm analysis. Regarding the design of algorithms, a number of methods and techniques with universal significance have been summed up, including dynamic planning, backtracking, branch limit, grahe methods, greedy methods. Below we focus on several representative combination algorithms:
Single form:
This is a linear planning algorithm, which is proposed by G.B. Dantzig in 1947, and later he and other scholars have proposed a simple formation and improvement. These have proven to be effective, linear planning research linear target functions in a set of linear equations and linear inequality constraints. This is a continuous problem, and Dantzig discovers the feasible solution of linear planning issues (that is, all of the constraints) is a super polyhedron. If its best solution exists, this optimal solution must be taken at a vertex of the super multifisa. Since the vertex of the super polyhedron is only limited, linear planning is a group and optimization problem. The simple form is to transfer from a vertex from a veins to another according to a certain rule, making the value of the target function constantly improve, and finally reaches optimal. Although the simple method has been used very well, it requires an index run time in worst case, so that the linear planning issue belongs to the Plass, the problem of being concerned. The subsequent ellipsoid algorithm and the projection algorithm have solved this problem.
Sort and search:
These two parts should be more familiar, so-called sorting, the given element sequence is rearranged in an ordered sequence in accordance with some sequential relationship. For example, sequences of n numbers are rearranged in order from small to large sequential; sequence consisting of n English words is rearranged in the order of dictionary. The so-called retrieval is to find a particular element or an element group in a given collection. Sorting and retrieving has become the most basic and frequently used algorithm in computer science technology. Below we specialize in the sorting algorithm.
When this algorithm is discussed, the data is usually referred to by a file consisting of several records, each record contains one or more data items, wherein the data item that can be marked is referred to as a key code. The n record {R1, R2, ..., RN} of a given file and the set {K1, K2, ..., KN} thereof. The so-called sorting algorithm is the algorithm that requires a certain order of records in the file in the file in the data processing. If the file to be sorted can be loaded into the main memory of the computer, the entire sorting process is not required to access the exemption, and it is called the internal sorting; if the number of recorded records is large, the sequence of the entire sequence The process is impossible to complete in memory, some must be placed on the outside, saying that such sorting problems are externally sorted. When the recorded file is included in the file, if the relative order of the records of the same key code remains unchanged after being sorted, the corresponding sorting algorithm is stable, otherwise it is unstable. If the sorting algorithm is designed to be completed, this sorting algorithm is called a serial (or order) sorting algorithm; if the sorting algorithm is designed to be implemented, it is called a parallel sorting algorithm.
First talk
Internal Sort: Internal Sorting Process is a process of gradually expanding recorded ordered sequence length. During the sorting process, there are two regions in the sorted recording sequence: an ordered zone and a disorder zone. Adding one or several operations in the number of ordered zones is called a sort.
Methods to gradually expand the length of the sequence of sequences, there are several categories:
One. Insert order
It is assumed that during the sorting process, the state of the recording sequence R [1..n] is:
Then, the basic idea of direct insertion sorting is: will record R
Inserted into a sequence sequence r [1..i-1], enabling the recorded ordered sequence from R [1..i-1] to R [1..i].
Obviously, complete this "insert" needs to be divided into three steps:
1. Find R's insertion position J 1;
2. Make a position behind the record in R [J 1..i-1];
3. Copy R to the position of R [J 1].
[I] Direct insertion sort
Insert sorting of "Inserting Location in R [1..i-1] is used in sequence lookup.
Pay attention to the three main points of direct insertion algorithm:
1. During the order of order from R [i-1], the monitoring whistle is set in R [0];
R [0] = r; // Set "Sentry"
For (j = i-1; r [0] .Key Return J 1; // Returns R's Insert Location to j 1 2. For records found in the lookup process, it is possible to move backward while finding. For (j = i-1; r [0] .Key R [J 1] = R [J] 3. I = 2, 3, ..., n, realize the sort of the entire sequence. Template Void Insertionsort (Elem R [], INT N) { // Direct insertion sorting of the recording sequence r [1..n]. For (i = 2; i <= n; i) { R [0] = r; // Copy to monitor whistle For (j = i-1; r [0] .Key R [j 1] = r [j]; // Record after shift R [J 1] = R [0]; // Insert to the correct position } } // insertsort Time analysis: There are two basic operations that achieve sorting: (1) The size of two keywords in the "comparison" sequence; (2) "Mobile" record. Sort by direct insertion: [II] Folding semiconeration Because R [1..i-1] is an ordered ordered sequence in keyword, you can use a folder search to implement "insertion of R to find R in R [1..i-1], which is implemented Insert sorting is a folded sequencing. Its algorithm is as follows: Template Void Biinsertionsrth (Elem R [], INT N) { // Sedimentation of the recording sequence R [1..n] is folded sequentially. For (i = 2; i <= L.LENGTH; i) { R [0] = r; // Temporal q to R [0] Low = 1; high = i-1; While (low <= high) {// Find inserted in the R [low..high] m = (low high) / 2; // folded IF (r [0] .Key High = m-1; // Insert point in low zone Else Low = m 1; // Insertion point in a high half zone } For (j = i-1; j> = high 1; --j) R [j 1] = r [j]; // Record after shift R [high 1] = r [0]; // insert } } // binsertsort Folding sequencing is significantly reduced by direct insertion sorting significantly reduced the "comparison" number of keywords, but the number of times that records "moving" is unchanged. [III] Table Insert Sort In order to reduce the operation of "moving" records during the sorting process, the storage structure used during the sorting process must be changed. Use a static linked list to sort and adjust the positions between each record mutually adjusted once, and each record is adjusted to each of them should be in place. The algorithm is described as follows: Template Void Linsertionsrth (Elem SL [], INT N) { // Insert the recording sequence SL [1..n] as a table. SL [0] .Key = maxint; SL [0] .Next = 1; SL [1] .next = 0; For (i = 2; i <= n; i) For (j = 0, k = SL [0] .next; SL [k] .key <= sl.key; j = k, k = sl [k] .next) {SL [J] .next = i; sl.next = k;} / / Node i is inserted between node J and node K } // linsertions Regarding the adjustment record sequence after sorting: Three poins in the algorithm: Where: p indicates the current position of the i-th record; i indicates the position where the i-th record should be; q Indicates the current location of the i 1 record Template Void Arrange (SlinkListType SL [], int N) { / / According to the correction value of each node in the static linked list // Record position, so that SL is recorded by keyword non-decrement // Order order P = SL [0] .next; // p Indicates the current location of the first record For (i = 1; i // SL [1..i-1] records have been arranged in ordered in keywords, // The current position of the i-i record in SL should not be less than i While (P / / Find the i-th record and use P to / / It is currently in SL Q = SL [P] .next; // q Indicates the end of the end IF (p! = i) { SL [P] ← → SL; / / exchange record, make the i // Record in place Sl.next = p; // Point to the removed record, / / Make it from the While cycle } P = q; // p indicates that the end of the end of the end, / / Preparation for finding the i 1 record } } // arrange two. The exchange sort is obtained by the record in the "exchange" disorder sequence to obtain the smallest or maximum record, and add it to the order in which the recording is increased in this manner; [I] Bubbling Sort It is assumed that during the sorting process, the status of the recording sequence R [1..n] is: N-I 1 Then, the basic idea of the first bubble insertion sorting is: "exchange" to the keyword record "exchange" to R [N-I 1] in the keyword "exchange" operation in the record of the record in the disorder sequence Position. Algorithm Description: Template Void Bubblesort (Elem R [], INT N) { // i indicates the location of the last record in the disorder sequence i = n; While (i> 1) { LastexchangeIndex = 1;
