Network flow algorithm is an efficient and practical algorithm. Compared with other graph theory algorithms, its model is more complex and its programming complexity is higher. However, it integrates some other algorithms in graph theory (such as the shortest path and width search algorithm), so it has a wider scope of application and can often solve some non-np problems that cannot be solved by search and dynamic programming.
The most challenging thing in the application of network flow in specific problems is the construction of models, which can be applied without ready-made models. It requires us to know the nature of various network flows like the palm of our hand (for example, a point has capacity, the capacity has upper and lower limits, multiple edges, etc.). ) and give play to our creativity according to specific problems. Many models can often be established for a problem, and different models have different effects on the efficiency of solving the problem. This paper discusses how to determine the appropriate model and improve the efficiency of network flow algorithm through examples.
Second, the time efficiency of network traffic algorithm
When we determine that the problem can be solved by the maximum flow algorithm, we will solve it according to the commonly used ford-fulkerson notation. The minimum (large) cost maximum flow problem can also be solved by a dual algorithm similar to the labeling method. The running time of ford-fulkerson labeling method is o(ve2), and the running time of dual method to find the minimum cost flow is about o(v3e2).
Obviously, the main factors that affect the time efficiency of network flow algorithm are the number of vertices and edges in the network. These two factors are not independent of each other, but interrelated and contradictory. In the construction of network model, sometimes, one factor is optimized and the other factor is also optimized; Sometimes, the optimization of one factor is at the expense of adding another. Therefore, when solving specific problems, we should adhere to the "overall view" and achieve a balance between the two.
Thirdly, the optimization and selection of the model
(1) Reduce the number of vertices and edges of the model and optimize the model.
If the number of vertices and edges in the network model can be reduced according to some special properties of the problem, the efficiency of the algorithm can be greatly improved.
Example 1: Minimum Queen Control
In chess, the queen can attack in eight directions (as shown in figure 1(a), in which the black grid is the position of the queen and the grid marked with K is the grid that the queen can attack). Now, given a chessboard with m * n (neither n nor m is greater than 50), some squares on the chessboard have obstacles. Each queen ant is placed in a barrier-free grid, which controls the grid. In addition, it can choose at most one grid from the eight grids it can attack, as shown in figure 1(b), and the grid numbered 1 is controlled by a queen.
Please make a program to calculate how many queens are required to completely control the whole chessboard.
Figure 1(a) Figure 1(b)
Input format:
The first line of the input file has two integers m and n, which represent the number of rows and columns of the chessboard respectively. Next, M rows and N columns are a character matrix with the symbol "". ' represents a blank grid, and' x' represents a grid with obstacles.
Output format:
The first line of the output file has only one number S, which indicates how many queens are needed.
Sample value input
3 4
x ...
x.x。
. x ..
Sample output
five
Problem analysis]
If simple search is used to solve this problem, the search algorithm is difficult to solve in a short time, because the chessboard given by the title is very large. Since a queen can only control two squares at most, the lower bound of the minimum number of queens required is [n*m/2]. In order to minimize the number of queens, the control of two squares must be as many queens as possible. If we add a directed arc between every two cells that can attack each other, the problem is very similar to the maximum matching problem of bipartite graphs.
[model 1]
1. Number each barrier-free grid according to the row priority (0~m*n- 1).
2. Fold each grid I into two grids I'' and I''' as vertices in the network model.
3. If lattice I can attack lattices J and I,
4. Add a source point S and an arc from point S to all vertices I'; Add a junction T and an arc from all vertices J'''' to T, with the capacity of 1.
The chessboard shown in figure 1(b) corresponds to the following model:
Figure 2
Obviously, any solution corresponds to a maximum match of the above model. And in the maximum match, the number of matches must be even. So at least the required number of horses is m * n- obstacle number-maximum matching number /2.
[Model 2]
If we draw the chessboard into black and white squares, then the two squares controlled by a queen must be Haig and the other is white squares (as shown in Figure 3). Let's put the queens in these two squares on the white one. Therefore, we divide the n*m grid into two parts: the white grid and Haig. Therefore, we can optimize the model 1 to:
Figure 3
1. Divide all the squares in the chess board into two parts, number all the squares, and add an arc from the white square to Haig between each white square and the Haig it can attack (except obstacles) to form a bipartite graph.
2. Add a source point S, and add an arc from point S to all white squares without obstacles; Add a junction T and add an arc from all accessible Haig to T.
3. Set the flow of all arcs to 1.
The chessboard shown in figure 1(b) corresponds to the following model:
Figure 4
[Comparison of two models]
Obviously, the number of vertices and edges in model 2 is about half that of model 1. The following is the time efficiency comparison of the two models in the bp environment (p 166/32m):
Model 1 model 2
Scalability It is not easy to print a solution, but it is easy to print a solution.
The second model divides the grid points into white and black according to the particularity of the problem (that is, the horse's walking), and stipulates that the horse can only jump from white to Haig, thus avoiding splitting each grid point in two, reducing the number of vertices and sides of the model. Good optimization results have been achieved.
(2) Integrating the advantages of various models and intelligently selecting models.
Sometimes, various models of the same problem have their own characteristics and advantages and disadvantages. In this case, the advantages and disadvantages of various models should be considered comprehensively, and the model of the problem should be selected intelligently according to the test data.
Example 2 Mars probe (ioi97)
There is a landing module (pod) with many obstacle detection vehicles (mev) that will land on the surface of Mars. After landing, the rover left the lander and moved to the launcher not far away in advance. Mev collects rocks when moving. Stones are collected by the mev who visited it first, and each stone can only be collected once. But after that, other mevs can pass through here. The rover mev cannot pass through the ground with obstacles.
This topic limits that the rover mev can only move south or east along the grid from the landing point to the transmitter, allowing multiple rover mev to occupy the same position at the same time.
Task: Calculate the moving path of all probe cars to maximize the number of rock samples sent to the conveyor, and all probe cars must reach the conveyor.
Input:
The position between the lander pod and the launcher on the surface of Mars is represented by networks P and Q. The position of the lander pod is (1, 1) and the position of the launcher is (p, q).
Different surfaces on Mars are represented by three different numerical symbols:
0 stands for flatness and accessibility.
1 stands for obstacle.
2 stands for stone.
The input file consists of the following:
Number of vehicles
p
q
(x 1y 1)(x2y 1)(x3，y 1)……(XP- 1y 1)(xpy 1)
(x 1y2)(x2y2)(x3，y2)……(XP- 1y 1)(XP y2)
(x 1y3)(x2y3)(x3，y3)……(XP- 1y 3)(xpy 3)
…
(x 1yq- 1)(x2yq- 1)(x3，yq- 1)……(XP- 1yq- 1)(xpyq- 1)
(x 1yq)(x2yq)(x3，yq)……(XP- 1yq)(xpyq)
P and q are the size of the network; The number of vehicles is an integer less than 1000, which indicates the number of exploration vehicles driven by the lander. * * * There are q rows of data, each row represents a set of data on the surface of Mars, and both p and q do not exceed 128.
[model 1]
Naturally, we take the position of the lander as the source point and the position of the transmitter as the sink point. At the same time, a stone is collected by the first mev to visit it, and each stone can only be collected once. But then other mevs can pass, allowing multiple exploration vehicles to occupy the same position at the same time. So we divide each point in the map into two points, namely (x, y)à(x, y, 0) and (x, y, 1). Specifically, the network model describing the map of Mars is constructed as follows:
1. Divide each non-obstacle point in the grid into (x, y) two points (x, y, 0) and (x, y, 1), where the source point s = v( 1, 1, 0) and the sink point t =.
2. Add the following three types of edges E 1, E2 and E3 to the above vertices, and record the corresponding capacities and costs as c 1, c2 and c3, and w 1, w2 and w3, respectively:
u e 1 = v(x，y，0)-& gt； v(x，y， 1)，c 1 = maxint，w 1 = 0 .
u e2 = v(x，y，0)-& gt； V(x, y, 1), c2 = 1, w2 =-1 (here, (x, y) must be ore).
u e3 = v(x，y， 1)-& gt； v(x ' '，y ' '，0)，c3 = maxint，w3 = 0。
Where x''=x+ 1 y''=y or x'' = x y'' = y+ 1, 1
As can be seen from the above model, in the process of construction, a point on the map is "disassembled" into two nodes of the network. Adding e 1 edge makes each point can be visited many times, while adding e2 edge makes the ore of a certain point. For this network, a path from S to T can be regarded as the action route of a probe car. The path cost is the amount of ore collected by the probe car. For network G, the solution of the problem can be obtained by finding the fixed minimum cost flow with the number of vehicles.
[Model 2]
In fact, if we only consider which minerals are loaded on each car in turn. Then the ore passing by each car is a flow, so we take the ore in the grid as the vertex of the network and establish the following network flow model.
1. Divide each starting point (upper left corner of the grid) and the mine (x, y) point that can reach its end point (lower right corner) into two points: the left point (x, y, 0) and the right point (x, y, 1), plus the source point S and the sink point T. ..
2. Add the following five types of edges E 1, E2 and E3 to the above vertices, and record the corresponding capacities and costs as c 1, c2 and c3, and w 1, w2 and w3, respectively:
u e 1 = v(x，y，0)-& gt； v(x，y， 1)，c 1 = 1，w 1 = - 1 .
U e2 = v(x, y, 1) ->V(x'', y'', 0), c2 = 1, w2 = 0 (occurrence (x, y) can reach occurrence (x'', y'')).
u E3 = s-& gt； v(x，y，0)，c3 = 1，w3 = 0 .
u e4 = v(x，y， 1)->t，c4 = 1，w4 = 0 .
u E5 = s-& gt； t，c5=maxint，w5=0 .
Because each stone is folded into two points, the capacity is 1, and each stone is guaranteed to be taken only once, and the cost of taking a stone at the same time is-1. Therefore, for the above model, we can find the minimum cost flow with $ number vehicles.
[Comparison of two models]
1. model 1 takes the grid as the vertex and model 2 takes the ore as the vertex, so model 2 is obviously superior to model 1 in the number of vertices. For some data with sparse ore and large grid, model 2 is more efficient than model 1. Moreover, as long as the number of ores does not exceed a certain number, model 2 can handle data with large P and Q, but model 1 can't.
2. The maximum number of edges of model 1 is 3*p*q, while the number of edges of model 2 is about p * q * (p+1) * (q+1)/4-p * q in the worst case. Therefore, in this problem, for some data with dense ore and large grid, the number of edges of model 2 will greatly exceed that of model 1, thus making the time efficiency much lower than that of model 1.
The following is a comparison of the case where all lattices are minerals (piii700/ 128m, bp7.0 protection mode):
Number of vehicles = 10 model 1 2 model
As can be seen from the above data, the model 1 can be solved within 10 second when p and q are less than 60. Model 2 is very slow in the worst case of P and q = 30. When P and Q exceed 30, there will be memory overflow, which cannot be solved.
Therefore, for this problem, the above two models have their own advantages and disadvantages, and we can decide what model to build according to the ore sparsity in the test data. If the ore is sparse, we can consider establishing network models such as Model 2. If the ore is dense, the network model shown in model 1 is established. Then, the minimum cost maximum flow algorithm is applied to solve the problem. For the case that P, Q > 60 and there are many ores, the network flow algorithms of the two models can not be solved. In practical applications, problems often only need approximate solutions, and at this time, some other algorithms can be integrated to solve them.
Four. Concluding remarks
To sum up, the optimization of model in network flow algorithm is fundamental to improve the efficiency of network flow algorithm. According to practical problems, how to optimize the model from the point of view of reducing vertices and edges is considered, and the appropriate model is selected to improve the efficiency of the algorithm. For some problems, when various models for solving problems have their own advantages and disadvantages, the program can automatically analyze the test data, decide which model to use under what circumstances, give full play to the advantages of various models, and achieve the purpose of optimizing program efficiency.