In programming, there is a special program - recursive program, and the recursive program is directly called yourself or through a series of procedures indirect calls their own programs. The recursive program often appears in programming, so you should learn to solve the problem using recursive procedures, but the efficiency of recursive program is generally relatively low, so it should be optimized.
The following is a combination of traveler's problems to talk about recursive optimization.
One. Recursive process
The travelist problem is as follows: Travelers want to travel N cities and ask all cities to experience and only experience one time, and require the shortest distance. This issue is also known as the goods, the postman problem, the salesperson problem, is one of the famous N-P puzzles. When N is large, the recursion traversal method used herein is not used, but other methods, such as neural networks, genetic algorithms, etc., resulting in problem solutions.
To get the shortest path experienced by N cities, each should be compared to the approach to N cities, and select the minimum value as the return result.
When using recursive procedures to solve the travelist problem, the idea is the same as the loop method: find out various possible sequences, compare the approach taken under various sequences, and find out the shortest approach to experience. How to get the experience of all possible paths in this problem should be used as a focus, and the calculation, comparison, update and loop method are similar to the process. In the recursive call of this problem, the Nth to judge the city that has been passed from the N-1 layer, to determine if it has traversed, if n cities have traversed, calculate, compare, update the distance, then one The layer returns; if it is not traversed, select a city that has not experienced the city that has experienced experienced and passed together to the N 1 layer. Here, the N-layer invoking parameters can be regarded as the city and the shortest route that has been undergoing, and the result of the returned result can be regarded as the shortest distance and experience order.
Define a class in Java
Class Cities
{
Private int [] [] CITIES; // Each city is expressed as (x, y) x, y is between 0 and 99
Private int [] shortestpath; // Save the shortest distance corresponding to the experience
Private int Num; // Save N (Urban number)
Private long shortestLength = 100000000; // N cities can have a maximum distance over time
Private long getLength (int [] tpath) {. . . } // Calculate the approach to tPath
Public cities (int N) // Constructs the coordinates of n cities, assumes random numbers between 0 and 99
{
. . .
}
Public int [] getshortestpath () // Get the shortest path
{
int [] Temppath = new int [Num];
ShortestPath = new int [Num];
int [] citive = new int [Num]; // Whether to save the iChate I have experienced
INT CITIESNUM = 0; // has experienced the number of cities
For (int i = 0; i CITIESTOURED [I] = 0; Gothrough (Temppath, CitiesNum, Citiestoured); // Traverse For (int i = 0; i Temppath [i] = shortestpath [i]; // get traversal order Return Temppath; // Returns the result } Private vid gothrough (int [] tpath, int cnum, int [] ctoured) // traversal N cities { IF (cnum == 0) // When there is no experience in the city, choose 1st City { CNUM ; Tpath [0] = 0; CTOURED [0] = 1; Gothrough (TPath, CNUM, CTOURED); } Else if (cnum == Num) // Each city has experienced, end { Long templength = getLength (TPATH); // Calculate the approach to this experience IF (Templength { ShortestLength = Templength; // Update the shortest distance and its experience For (int i = 0; i ShortestPath [i] = tpath [i]; } } Else { For (int i = 0; i IF (ctoured [i]! = 1) // Choose an unnecessary city { CTOURED [I] = 1; // Join the city Tpath [cnum] = i; CNUM ; // Expected city number 1 Gothrough (tpath, cnum, ctoured); // Call the next layer CTOURED [I] = 0; // Restore the status of this layer: CNUM -; // Visual city and number } // End if in for (i) } // END ELSE } Private long getLength (int [] tpath) // calculate traversal access in the specified order { Long length = 0; // journey INT nowPoint = 0; // Current city, take 0 For (int i = 1; i { INT j = tpath [i]; Length = (long) Math.SQRT ((CITIES [J] [0]) * (CITIES [J] [0] -cities [nowpoint] [0]) (cities [j] [1] -cities [nowPoint] [1]) * (CITIES [J] [1]); // Plus the current, the distancePoint = j between the next city is; // Update the current city } Length = (long) Math.SQRT ((CITIES [0] [0]) * (CITIES [0] [0] -cities [nowpoint] [0]) (CITIES [0] [1] -cities [nowPoint] [1]) * (CITIES [0] [1] -cities [nowpoint] [1])); / / Plus the distance between the first tail Return Length; } } // CITIES class definition end Recursive here, the solution to the N variable time is achieved. three. Optimization of recursive procedures Optimization of recursive procedures is a kind of program optimization, with a generality of program optimization, while more consideration of it. The recursive program optimization should focus on the recursion as soon as possible, avoid unnecessary calls, because the more the price paid by the program is less than the reception of the program. In the travelist question, the traversal gothrough function of the city is a recursive program, which is discussed below to optimize it. I. The first optimization of this problem: The distance between the various cities has been determined when the CITIES class is constructed, and after each city is traversed, the GetLength function must calculate the distance between adjacent two cities and the first tail, obviously The calculation of the distance can be made once. It can therefore define a function initdistance, call in the constructor cities (), and redefine the getLength function, take directly to the distance and the distance of the adjacent and first tail. as follows: 1. Increase the property private long [] distance; // in the initdistance method 2. Define private methods private void initDistance () // calculate the distance between the various cities (because only once, no optimization) Private voidinitance () { Distance = new long [Num] [NUM]; For (int i = 0; i For (int J = 0; J { IF (i == j) Distance [i] [j] = 0L; Else Distance [i] [j] = (long) math.sqrt (CITIES [I] [0]) * (CITIES [I] [0] -CIITIES [J]) (CITIES [I] [1] -CIITIES [J] [ 1]) * (CITIES [I] [1] -cities [j]); } } 3. Redefine GetLength Private long getLength (int [] tpath) { Long length = 0L; For (int i = 1; i Length = distance [tpath [0]] [tpath [NUM-1]]; Return Length; } 4. Redefine constructor CITIES (INT R) Public CITIES (INT R) {. . . INITDISTANCE (); // Calculate the distance between each city } II. The second optimization of the problem: Considering the following situation, experience the order of 1-2-3-4-5-6-6-6-2-3-4-6-5-, the first four cities in the first four cities Similarly, a variable can be defined to save the experienced route, and only the experience has been updated only when the order is changed. Perform the following optimization: 1. Increase the private long touredLength attribute and initialize 0 to record the approach experienced by "current". 2. Redefine Gothrough Private void gothrough (int [] tpath, int cnum, int [] ctoured) { . . . // ELSE IF (cnum == Num) { Long TL = TouredLength Distance [TPath [NUM-1]] [TPath [0]]; ▲ // TL record has experienced access (Use ▲ mark improvements, the same below) IF (TL { ShortestLength = TL; For (int i = 0; i ShortestPath [i] = tpath [i]; } } ELSE // 0 { For (int i = 0; i IF (CTOURED [I]! = 1) // not Toured { Tpath [cnum] = i; CTOURED [I] = 1; TouredLength = distance [tpath [cnum-1]] [i]; ▲ CNUM ; Gothrough (TPath, CNUM, CTOURED); CNUM-- TouredLength - = distance [tpath [cnum-1]] [i]; ▲ CTOURED [I] = 0; } } } 3. Remove GetLength. III. The second optimization of this problem: further considering the calculation of the distance, envision the situation below: n = 5, has experienced two cities, and the travel route is 200, the shortest approach is now 260, while the other three The distance between any two cities of the city is greater than 30. In this case, continue to traverse is just futile, and you can end the call back. In response to this situation, the following optimization: 1. Add Property Private Long ShortestDistance [] to save the shortest distance between the city, the shortest distance, the shortest distance for the secondary. . . And to get the value of each distance in the initdistance. Private voidinitance () { . . . ShortestDistance = new long [Num 1]; ShortestDistance [0] = 0; For (int i = 0; i { Long DIS = 10000L; For (int J = i 1; j IF (Distance [i] [j] DIS = Distance [i] [j]; ShortestDistance [i 1] = ShortestDistance [i] DIS; } } 2. Update gothrough Private void gothrough (int [] tpath, int cnum, int [] ctoured) { . . . ELSE IF (cnum == Num) { Long TL = TOURENGTH DISTANCE [TPath [NUM-1]] [TPath [0]]; IF (TL { ShortestLength = TL; For (int i = 0; i ShortestPath [i] = tpath [i]; } } ELSE // 0 { IF (TouredLength ShortestDistance [NUM - CNUM] // If you have experienced a distance possible shortest distance> The shortest distance is known, no longer continue { For (int i = 0; i IF (CTOURED [I]! = 1) // not Toured { Tpath [cnum] = i; CTOURED [I] = 1; TouredLength = distance [tpath [cnum-1]] [i]; CNUM ; Gothrough (TPath, CNUM, CTOURED); CNUM-- TouredLength - = distance [tpath [cnum-1]] [i]; CTOURED [I] = 0;} } } } Compare the solution time of various optimization methods, data for the following table (Windows 98, PIII550, 128M): Program The problem is only introduced into the Distance to introduce the Distance "to introduce TouredLength to introduce TouredLength. Remove GetLength to introduce ShortestDistance n = 10 1850 milliseconds 390 milliseconds 100 milliseconds less than 1 millisecond n = 12 220000 milliseconds 48200 milliseconds 1000 milliseconds 100 milliseconds From the above data, it can be concluded that recursive procedures generally have large optimization space, and after the recursive procedure is optimized, it can greatly improve the efficiency of the program. Optimized procedures retain both the characteristics of the recursive procedure, and to a certain extent, it makes up for the shortcomings of the program time efficiency. At the same time, it is also possible to see the innate defects of recursive procedures. The recursive procedure in reality is unable to resolve (within acceptable time), and generally adopted genetic algorithm to solve it, should we decide whether to decide in advance Use recursive procedures to solve their own problems. Even so, this article also has a certain reference significance for the recursive program that can be applied.
