算法詳解之回溯法具體實(shí)現(xiàn)

2020-01-26 15:36:50

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

理論輔助：

回溯算法也叫試探法，它是一種系統(tǒng)地搜索問(wèn)題的解的方法。回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試。用回溯算法解決問(wèn)題的一般步驟為：

1、定義一個(gè)解空間，它包含問(wèn)題的解。

2、利用適于搜索的方法組織解空間。

3、利用深度優(yōu)先法搜索解空間。

4、利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。

問(wèn)題的解空間通常是在搜索問(wèn)題的解的過(guò)程中動(dòng)態(tài)產(chǎn)生的，這是回溯算法的一個(gè)重要特性。

還是那個(gè)基調(diào)，不喜歡純理論的東西，喜歡使用例子來(lái)講訴理論，在算法系列總結(jié)：動(dòng)態(tài)規(guī)劃(解公司外包成本問(wèn)題）的那一節(jié)里面我們舉得是經(jīng)典的0-1背包問(wèn)題，在回溯算法里面也有一些很經(jīng)典的問(wèn)題，當(dāng)然，動(dòng)態(tài)規(guī)劃的0-1背包問(wèn)題其實(shí)也可以使用回溯算法來(lái)解。在諸如此類(lèi)似的求最優(yōu)解的問(wèn)題中，大部分其實(shí)都可以用回溯法來(lái)解決，可以認(rèn)為回溯算法一個(gè)”通用解題法“，這是由他試探性的行為決定的，就好比求一個(gè)最優(yōu)解，我可能沒(méi)有很好的概念知道怎么做會(huì)更快的求出這個(gè)最優(yōu)解，但是我可以嘗試所有的方法，先試探性的嘗試每一個(gè)組合，看看到底通不通，如果不通，則折回去，由最近的一個(gè)節(jié)點(diǎn)繼續(xù)向前嘗試其他的組合，如此反復(fù)。這樣所有解都出來(lái)了，在做一下比較，能求不出最優(yōu)解嗎？

例子先行，現(xiàn)在我們來(lái)看看經(jīng)典的N后問(wèn)題

問(wèn)題描述：在n*n格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。按照國(guó)際象棋的規(guī)矩，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問(wèn)題等價(jià)于在n*n格的棋盤(pán)上方置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。我們需要求的是可放置的總數(shù)。

基本思路：用n元組x[1；n]表示n后問(wèn)題的解。其中，x[i]表示皇后i放置在棋盤(pán)的第i行的第x[i]列。由于不容許將2個(gè)皇后放在同一列上，所以解向量中的x[i]互不相同。2個(gè)皇后不能放在同一斜線上是問(wèn)題的隱約束。對(duì)于一般的n后問(wèn)題，這一隱約束條件可以化成顯約束的形式。如果將n*n 格的棋盤(pán)看做二維方陣，其行號(hào)從上到下，列號(hào)從左到右依次編號(hào)為1,2，...n。從棋盤(pán)左上角到右下角的主對(duì)角線及其平行線（即斜率為-1的各斜線）上，2個(gè)下標(biāo)值的差（行號(hào)-列號(hào)）值相等。同理，斜率為+1的每條斜線上，2個(gè)下標(biāo)值的和（行號(hào)+列號(hào)）值相等。因此，若2個(gè)皇后放置的位置分別是（i,j）和（k,l）,且 i-j = k -l 或 i+j = k+l，則說(shuō)明這2個(gè)皇后處于同一斜線上。以上2個(gè)方程分別等價(jià)于i-k = j-l 和 i-k =l-j。由此可知，只要|i-k|=|l-j|成立，就表明2個(gè)皇后位于同一條斜線上。

1、從空棋盤(pán)起，逐行放置棋子。
2、每在一個(gè)布局中放下一個(gè)棋子，即推演到一個(gè)新的布局。
3、如果當(dāng)前行上沒(méi)有可合法放置棋子的位置，則回溯到上一行，重新布放上一行的棋子。
代碼：

復(fù)制代碼代碼如下:

#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("%d/n",sum);
}
}

這段代碼有必要解釋一下，Place（int）即嘗試看是否可以，如果不可以則回退到t+1層，再?lài)L試其他的組合。

這里也道出了回溯算法的核心思想：但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇

算法實(shí)踐：

問(wèn)題描述：在一個(gè)n*n的網(wǎng)格里，每個(gè)網(wǎng)格可能為“墻壁”（用‘X'表示）和“街道”（用‘.'表示）。現(xiàn)在在街道放置碉堡，每個(gè)碉堡可以向上下左右四個(gè)方向開(kāi)火，子彈射程無(wú)限遠(yuǎn)。墻壁可以阻擋子彈。問(wèn)最多能放置多少個(gè)碉堡，使它們彼此不會(huì)互相摧毀。

如下面四張圖，墻壁用黑正方形表示，街道用空白正方形表示，圓球就代表碉堡。1,2,3是正確的，4,5是錯(cuò)誤的。以為4,5里面在某一行或者某一列有兩個(gè)碉堡，這樣他們就會(huì)互相攻擊了。意思明白了嗎？可能我的表達(dá)很不清晰，呵呵….

輸入輸出示例

Sample input:
――――――輸入的n值
.X..
....

XX..
....

XX
.X
.X.
X.X
.X.
....
....
....
....

Sample output:

初拿到這個(gè)問(wèn)題，你會(huì)不會(huì)想到回溯算法呢？有人說(shuō)遍歷墻的位置，然后再墻的上下左右四個(gè)格子放置碉堡會(huì)得到最優(yōu)解，這個(gè)我沒(méi)有驗(yàn)證過(guò)，細(xì)細(xì)的用筆畫(huà)了畫(huà)，好像是這么回事，但是很多時(shí)候要知道最優(yōu)解用什么方法是很難發(fā)現(xiàn)的，利用通用解題方法回溯法，我們可以在一片茫然的時(shí)候開(kāi)始我們的編程

首先我們來(lái)分析一下這個(gè)問(wèn)題：使用回溯法，我們嘗試每一種可能放置的情況，然后進(jìn)行判斷是否滿(mǎn)足要求，若不滿(mǎn)足，嘗試放到下一個(gè)單元格，如此反復(fù)，最終，我們將所有可能放置的情況全部遍歷出來(lái)了，連所有情況都出來(lái)了，難不成還找不到最優(yōu)解嗎？哈哈。。說(shuō)做就做…

復(fù)制代碼代碼如下:

#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("%d/n",best);
          n=0;                             
          scanf("%d",&n);
        }
        return 0;
 }