The backtracking method of algorithm elaboration is implemented in detail
- 2020-04-02 02:14:01
- OfStack
Theoretical AIDS:
Backtracking algorithm, also called heuristic, is a method of systematically searching for solutions to problems. The basic idea of backtracking algorithm is: go forward from a road, can enter into, can not enter back, another way to try again. The general steps to solve the problem with the backtracking algorithm are as follows:
1. Define a solution space that contains the solution to the problem.
2. Use the method suitable for searching to organize the solution space.
3. Search solution space by depth-first method.
4. Use the limit function to avoid moving to the subspace where the solution cannot be generated.
The solution space of the problem is usually generated dynamically in the process of searching the solution of the problem, which is an important characteristic of the backtracking algorithm.
Or the tone, not like pure things, like to use examples to tell theory, the algorithm series conclusion: dynamic programming (solution company outsourcing cost) of the section which we raised the 0-1 knapsack problem is a classic, inside the backtracking algorithm has some very classic problem, of course, the dynamic programming 0-1 knapsack problem is also can use the backtracking algorithm to the solution. In such as the optimal solution of the problem, the most can use backtracking method to solve, actually can think backtracking algorithm is a general problem solving method ", which is decided by his tentative behavior, is just like an optimal solution, I may not have a good concept will know how to do it faster and the optimal solution, but I can try all methods, first tentative try every combination, see how impassability, if not, is going back, by the recent a node to move on to try other combinations, and repeat. So now that we've got all the solutions, and we're doing some comparisons, can't we find the optimal solution?
Example first, now let's look at the classic post-n problem
Problem description: place n queens on an n by n checkerboard. In chess, a queen can attack a piece on the same row or column or slash. The problem after n is equivalent to placing n queens above an n-by-n checkerboard, with any two queens not placed on the same row or the same column or the same slash. What we want is the total number of places we can put.
< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201402/2014217145358979.png" >
Basic ideas: The solution of the problem after n is represented by the n-tuple x[1; n]. Where, x[I] represents the x[I] column of queen I placed in row I of the checkerboard. Since it is impossible to put two queens in the same column, the x[I] in the solution vector are different. Two queens cannot be placed on the same slash is an implicit constraint of the problem. For the general problem after n, this implicit constraint condition can be converted into the form of explicit constraint. If the checkerboard with n by n grids is regarded as a two-dimensional square matrix, its row Numbers are numbered from top to bottom, and column Numbers are numbered 1,2 from left to right... N. From the upper left corner of the board to the lower right corner of the board, the difference between the two lower values (line number - column number) is the same on the main diagonal and its parallel lines (that is, each oblique line with slope of -1). Similarly, for every diagonal line with a slope of +1, the sum of the two lower values (row number + column number) is the same. Therefore, if the positions of the two queens are respectively (I,j) and (k,l), and I -j = k -l or I +j = k+l, then the two queens are on the same oblique line. The above two equations are respectively equivalent to I -k = j-l and I -k =l-j. Therefore, as long as | I -k|=|l-j| is true, it means that the two queens are on the same diagonal line.
1. Place the pieces line by line from the empty board.
2, each in a layout to put down a piece, that is to deduce a new layout.
3. If there is no position on the current line where the piece can be legally placed, then go back to the previous line and re-arrange the piece on the previous line.
Code:
#include <stdio.h>
#include <math.h>
#include<stdlib.h>
static int n,x[1000];
static long sum;
int Place(int k)
{
for(int j=1;j <k; j++)
if((abs(k-j) == abs(x[j]-x[k]))||(x[j]==x[k])) return 0;
return 1;
}
void Backtrak(int t)
{
if(t>n) sum++;
else
for(int i=1; i <= n; i++)
{
x[t] =i;
if(Place(t))Backtrak(t+1);
}
}
int main()
{
int nn;
while(scanf("%d",&nn)!=EOF)
{
n=nn;
sum=0;
for(int i=0;i<=n;i++)
x[i]=0;
Backtrak(1);
printf("%dn",sum);
}
}
It's worth explaining that Place (int) is to try to see if it works, and if it doesn't, go back to t+1 and try some other combination.
Here, too, is the core idea of the backtracking algorithm: but when you reach a certain step, you find that the original choice is not good or can not reach the goal, you step back and choose again
Algorithm practice:
Problem description: in an n by n grid, each grid may be "wall" (represented by "X") and "street" (represented by ". "). Now there are bunkers in the streets, each of which can fire in four directions, up, down, left, right, and with a bullet that can go an infinite distance. Walls can block bullets. Ask how many more bunkers can be placed so that they do not destroy each other.
As shown in the following four pictures, the walls are represented by black squares, the streets by blank squares, and the ball represents the bunker. One, two, three is right, four, five is wrong. Think 4,5 has two bunkers in one row or one column, so they'll attack each other. Does that make sense? Maybe my expression is not clear, hehe... .
< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201402/2014217150830066.jpg" >
I/o example
The Sample input:
-- the input value of n
X..
.
XX..
.
XX
X
X.
7.0.x.x
X.
.
.
.
.
The Sample output:
When you first got this question, did you think of backtracking algorithms? Some people say that traverse the location of the wall, then up and down or so four of the wall grid placed bunkers will get the optimal solution, this I don't have validated, draw the picture carefully, as if so return a responsibility, but a lot of time to know it is hard to find the optimal solution with what method, using the general problem solving method retrospective method, we can start our in a daze programming
First of all, let's analyze the problem: the use of backtracking, we tried every possible place, and then judge whether meet the requirements, if not satisfied, try to put down a cell, so repeatedly, eventually, we place all possible traverse out entirely, even out of all cases, maybe still can't find the optimal solution? Ha ha.. Say what you do...
#include <stdio.h>
char map[4][4];
int best,n;
int canput(int row, int col)
{
int i;
for (i = row - 1; i >= 0; i--)
{
if (map[i][col] == 'o') return 0;
if (map[i][col] == 'x') break;
}
for (i = col - 1; i >= 0; i--)
{
if (map[row][i] == 'o') return 0;
if (map[row][i] == 'x') break;
}
return 1;
}
void solve(int k,int tot)
{
int x,y;
if(k==n*n)
{
if(tot>best)
{
best=tot; return;
}
}
else
{
x=k/n;
y=k%n;
if((map[x][y]=='.') && (canput(x,y) ) )
{
map[x][y]='o';
solve(k+1,tot+1);
map[x][y]='.';
}
solve(k+1,tot);
}
}
int main()
{
int i,j;
scanf("%d",&n);
while(n>0)
{
for(i=0;i< n;i++)
for(j=0;j< n;j++)
scanf("%1s",&map[i][j]);
best=0;
solve(0,0);
printf("%dn",best);
n=0;
scanf("%d",&n);
}
return 0;
}
To explain the code above, canput is to do the test, check whether it is feasible to put it in a certain place, solve is the function that really does recursive backtracking.