實(shí)驗(yàn)原理：

1. 要求用回溯法求解8-皇后問(wèn)題，使放置在8*8棋盤(pán)上的8個(gè)皇后彼此不受攻擊，即：任何兩個(gè)皇后都不在同一行、同一列或同一斜線上。請(qǐng)輸出8皇后問(wèn)題的所有可行解。
2. 用回溯法編寫(xiě)一個(gè)遞歸程序解決如下裝載問(wèn)題：有n個(gè)集裝箱要裝上2艘載重分別為c1和c2的輪船，其中集裝箱i的重量為wi（1≤?i?≤?n），且Σ????≤??1_+_??2_????=_1_。問(wèn)是否有一個(gè)合理的裝載方案可以將這n個(gè)集裝箱裝上這2艘輪船？如果有，請(qǐng)給出裝載方案。
3. 提示：參考子集和數(shù)問(wèn)題的求解方法。
4. 舉例：當(dāng)n=3，c1=c2=50，且w=[10,40,40]時(shí)，可以將集裝箱1和2裝到第一艘輪船上，集裝箱3裝到第二艘輪船上；如果w=[20,40,40]時(shí)，無(wú)法將這3個(gè)集裝箱都裝上輪船。

   實(shí)驗(yàn)內(nèi)容：

   ?1、8皇后問(wèn)題

   通過(guò)求解n-皇后問(wèn)題，體會(huì)回溯法深度優(yōu)先遍歷狀態(tài)空間樹(shù)，并利用約束函數(shù)進(jìn)行剪枝的算法思想。?代碼實(shí)現(xiàn)：

5. #include <iostream>
   #include <cmath>
   using namespace std;
   
   bool Place(int k,int i,int *x){ //判定兩個(gè)皇后是否在同一列或在同一斜線上
       for(int j=0;j<k;j++)
           if ((x[j]==i)||(abs(x[j]-i)==abs(j-k))) return false;
       return true;
   }
   void NQueens(int k,int n,int *x){ //遞歸函數(shù)（求解n皇后問(wèn)題）
       for (int i=0;i<n;i++){
           if(Place(k,i,x)){
               x[k]=i;
               if (k==n-1){
                   for (i=0;i<n;i++) cout<<x[i]<<" ";
                   cout<<endl;
               }
               else{
                   NQueens(k+1,n,x);
               }
           }
       }
   }
   
   void NQueens(int n,int *x){
       NQueens(0,n,x);
   }
   
   int main()
   {
       int x[8];
       for (int i=0;i<8;i++) x[i]=-1;
       NQueens(8,x);
       return 0;
   }
   

   實(shí)驗(yàn)結(jié)果：

6. 

   ?思考題1：請(qǐng)編程實(shí)現(xiàn)從n-皇后問(wèn)題的所有92種可行解中篩選出12種獨(dú)立解，而其余的解都可以由這些獨(dú)立解利用對(duì)稱性或旋轉(zhuǎn)而得到。

   ?

   #include <iostream>
   #include <cmath>
   #include <cstring> // 新增頭文件用于調(diào)用 memcpy 函數(shù)
   using namespace std;
   
   bool Place(int k,int i,int *x){ //判定兩個(gè)皇后是否在同一列或在同一斜線上
       for(int j=0;j<k;j++)
           if ((x[j]==i)||(abs(x[j]-i)==abs(j-k)))
               return false;
       return true;
   }
   
   bool IsEquivalent(int n, int *x, int *y) { // 判斷兩個(gè)解是否等價(jià)
       for (int i =0; i < n; i++) {
           if (x[i] ==  n - y[i] - 1)
               return false; // 檢查是否為旋轉(zhuǎn)等價(jià) false代表不相等
       }
   
       for (int i = 0; i < n; i++) { // 檢查是否為對(duì)稱等價(jià)
           if (x[i] == y[n - 1 - i]) return false;
       }
       return true;
   }
   
   void NQueens(int k,int n, int *x, int solutions[100][8], int &num){ //遞歸函數(shù)（求解n皇后問(wèn)題）
       int i,j,h;
       for (i=0;i<n;i++){
           if(Place(k,i,x)){
               x[k]=i;
               if (k==n-1){
                   bool is_independent=true;
                   for(j=0; j<num; j++){// 判斷是否與已有解等價(jià)
                       if(IsEquivalent(n, x, solutions[j])){
                           is_independent = false;
                           break;
                       }
                   }
   
                   if(is_independent) {
                       for (h = 0; h < n; h++){
                           solutions[num][h] = x[h];
                       }
                       num++;
                   }
               }
               else{
                   NQueens(k+1,n,x,solutions,num);
               }
           }
       }
   }
   
   void NQueens(int n,int *x,int solutions[100][8], int &num){
       NQueens(0,n,x,solutions,num);
   }
   
   int main()
   {
   
       int x[8];
       for (int i=0;i<8;i++)
           x[i]=-1;
       int solutions[100][8];
       int num_solutions = 0;
       NQueens(0,8,x,solutions,num_solutions);
       //NQueens(8,x, solutions,num_solutions);
   
       cout << "共找到 " << num_solutions << " 種獨(dú)立解：" << endl;
       for (int i = 0; i < num_solutions; i++) {
           cout << "解 " << i + 1 << ": ";
           for (int j = 0; j < 8; j++) {
               cout << solutions[i][j] << " ";
           }
           cout << endl;
       }
       return 0;
   }
   

   實(shí)驗(yàn)結(jié)果：

7. 

   思考題2:?若n-皇后問(wèn)題要求在求得第一個(gè)可行解之后算法即終止，請(qǐng)編程實(shí)現(xiàn)。?

代碼：

#include <iostream>
#include <cmath>
using namespace std;

bool Place(int k,int i,int *x){ //判定兩個(gè)皇后是否在同一列或在同一斜線上
    for(int j=0;j<k;j++)
        if ((x[j]==i)||(abs(x[j]-i)==abs(j-k)))
            return false;
    return true;
}
bool NQueens(int k,int n,int *x){ //遞歸函數(shù)（求解n皇后問(wèn)題）
    for (int i=0;i<n;i++){
        if(Place(k,i,x)){
            x[k]=i;
            if (k==n-1){
                for (i=0;i<n;i++) cout<<x[i]<<" ";
                cout<<endl;
                return true;
            }
            if(NQueens(k+1,n,x))
                return true;
            }
        }
    return false;
    }

void NQueens(int n,int *x){
    NQueens(0,n,x);
}

int main()
{
    int x[8];
    for (int i=0;i<8;i++)
        x[i]=-1;
    NQueens(8,x);
    return 0;
}

運(yùn)行結(jié)果：?

?

2、裝載問(wèn)題

算法實(shí)現(xiàn)主體部分已給出，請(qǐng)補(bǔ)充完整，并使用下面三個(gè)測(cè)試案例調(diào)試通過(guò)。

第一艘船載重60，第二艘船載重40，5個(gè)集裝箱重量分別為：

（1）22 35 24 19 4?

（2）22 35 24 15 4

（3）22 35 24 15 3

代碼實(shí)現(xiàn)：運(yùn)行結(jié)果：

#include <iostream>
#include <cmath>
#include <cstring> // 新增頭文件用于調(diào)用 memcpy 函數(shù)
using namespace std;

class Loading {
private:
    int n, //集裝箱數(shù)
    *x, //當(dāng)前解
    *bestx; //當(dāng)前第一艘船的最優(yōu)解
    int c1, //第一艘輪船的核定載重量
    c2, //第二艘輪船的核定載重量
    *w, //集裝箱重量數(shù)組
    total, //所有集裝箱重量之和
    cw, //當(dāng)前第一艘船的載重量
    bestw, //當(dāng)前第一艘船的最優(yōu)載重量
    r; //剩余集裝箱總重量
public:
    Loading() //構(gòu)造函數(shù)
    {
        n = 5;
        x = new int[n+1];
        bestx = new int[n+1];
        w = new int[n+1];
        c1 = 60;
        c2 = 40;
        w[1] = 22;
        w[2] = 35;
        w[3] = 24;
        w[4] = 19;
        w[5] = 4;
        total = w[1]+w[2]+w[3]+w[4]+w[5];
        r = total;
        bestw = 0;
    }
        ~Loading() //析構(gòu)函數(shù)
        {
            delete[] x;
            delete[] bestx;
            delete[] w;
        }
            void Backtrack(int i); //找到最接近第一艘輪船載重c1的最佳裝載方案，
//最優(yōu)載重值bestw，最優(yōu)解數(shù)組bestx。
            void Show();//輸出整個(gè)裝載方案
};


void Loading::Backtrack(int i)
{ //搜索第i層結(jié)點(diǎn)
    if (i>n)
    {//到達(dá)葉節(jié)點(diǎn)
        if (cw>bestw)
        {
            for (int j=1;j<=n;j++) bestx[j]=x[j];
            bestw=cw;
        }
        return;
    }
//搜索子樹(shù)
    r-=w[i];
    if (cw+w[i]<=c1) //x[i]=1時(shí)的可行解約束條件
    {//搜索左子樹(shù)
        x[i]=1;
        cw+=w[i];
        Backtrack(i+1);
        cw-=w[i];
    }
    if (cw+r>bestw) //x[i]=0時(shí)增加的約束函數(shù)，剪去不含最優(yōu)解的分枝
    {//搜索右子樹(shù)
        x[i]=0;
        Backtrack(i+1);
    }
    r+=w[i];
}

void Loading::Show()
{
    cout << "裝載方案：" << endl;
    cout << "第一艘船：";
    for (int i = 1; i <= n; i++)
    {
        if (bestx[i] == 1)
        {
            cout << w[i] << " ";
        }
    }
    cout << endl;
    cout << "第二艘船：";
    for (int i = 1; i <= n; i++)
    {
        if (bestx[i] == 0)
        {
            cout << w[i] << " ";
        }
    }
    cout << endl;
    cout << "第一艘船最優(yōu)載重量：" << bestw << endl;
}

int main()
{
    Loading ld;
    ld.Backtrack(1);
    ld.Show();
    system("pause");
    return 0;
}

?運(yùn)行結(jié)果：

?

?

思考題3：求上面回溯法求解裝載問(wèn)題的計(jì)算時(shí)間復(fù)雜度？有什么方法可以繼續(xù)改進(jìn)算法的時(shí)間復(fù)雜度？

由于bestx可能被更新O(2^n)次，因此該算法的時(shí)間復(fù)雜度是O(n2^n)。

改進(jìn)策略可以有下面兩種，均可將算法的時(shí)間復(fù)雜度降為O(2^n)：

（1）?首先運(yùn)行只計(jì)算最優(yōu)值的算法，計(jì)算出最優(yōu)裝載量W，所耗時(shí)間O(2^n)。然后再將算法Trace中的bestw置為W后運(yùn)行，這樣在首次到達(dá)的葉節(jié)點(diǎn)處（即首次i>n時(shí)）終止算法，返回的bestx即為最優(yōu)解。

（2）?另一種策略是在算法中動(dòng)態(tài)的更新bestx。在第i層的當(dāng)前結(jié)點(diǎn)處，當(dāng)前最優(yōu)解由x[j]，1≤j<i和best[j]，i≤j≤n所組成。每當(dāng)算法回溯一層時(shí)，將x[i]存入bestx[i]。

思考題4：請(qǐng)用非遞歸的迭代回溯方式，重新實(shí)現(xiàn)裝載問(wèn)題的求解。

代碼：

?

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

class Loading {
private:
    int n; // 集裝箱數(shù)
    int *x; // 當(dāng)前解
    int *bestx; // 當(dāng)前第一艘船的最優(yōu)解
    int c1; // 第一艘輪船的核定載重量
    int c2; // 第二艘輪船的核定載重量
    int *w; // 集裝箱重量數(shù)組
    int total; // 所有集裝箱重量之和
    int cw; // 當(dāng)前第一艘船的載重量
    int bestw; // 當(dāng)前第一艘船的最優(yōu)載重量
    int r; // 剩余集裝箱總重量

public:
    Loading() // 構(gòu)造函數(shù)
    {
        n = 5;
        x = new int[n + 1];
        bestx = new int[n + 1];
        w = new int[n + 1];
        c1 = 60;
        c2 = 40;
        w[1] = 22;
        w[2] = 35;
        w[3] = 24;
        w[4] = 19;
        w[5] = 4;
        total = w[1] + w[2] + w[3] + w[4] + w[5];
        r = total;
        bestw = 0;
    }

    ~Loading() // 析構(gòu)函數(shù)
    {
        delete[] x;
        delete[] bestx;
        delete[] w;
    }

    void Backtrack(); // 找到最接近第一艘輪船載重c1的最佳裝載方案，最優(yōu)載重值bestw，最優(yōu)解數(shù)組bestx。
    void Show(); // 輸出整個(gè)裝載方案
};

void Loading::Backtrack()
{
    int i = 1;
    while (i > 0)
    {
        if (i > n)
        {
            // 找到更優(yōu)的裝載方案
            if (cw > bestw)
            {
                memcpy(bestx, x, (n + 1) * sizeof(int));
                bestw = cw;
            }
            
            // 回溯到上一個(gè)箱子位置
            i--;
            while (i > 0 && x[i] == 0)
            {
                cw -= w[i];
                r += w[i];
                i--;
            }
            
            // 如果仍有箱子可選，則放置到第二艘船上
            if (i > 0)
            {
                x[i] = 0;
                cw -= w[i];
                r += w[i];
            }
        }
        else
        {
            // 嘗試將箱子放置到第一艘船上
            if (cw + w[i] <= c1)
            {
                x[i] = 1;
                cw += w[i];
                r -= w[i];
                i++;
            }
            else
            {
                // 將箱子放置到第二艘船上
                x[i] = 0;
                r -= w[i];
                i++;
            }
        }
    }
}

void Loading::Show()
{
    cout << "裝載方案：" << endl;
    cout << "第一艘船：";
    for (int i = 1; i <= n; i++)
    {
        if (bestx[i] == 1)
        {
            cout << w[i] << " ";
        }
    }
    cout << endl;
    cout << "第二艘船：";
    for (int i = 1; i <= n; i++)
    {
        if (bestx[i] == 0)
        {
            cout << w[i] << " ";
        }
    }
    cout << endl;
    cout << "第一艘船最優(yōu)載重量：" << bestw << endl;
}

int main()
{
    Loading ld;
    ld.Backtrack();
    ld.Show();
    return 0;
}

運(yùn)行結(jié)果

?碼字不易，都看到這了，歡迎打賞?。?span toymoban-style="hidden">文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-453354.html

到了這里，關(guān)于南京郵電大學(xué)算法與設(shè)計(jì)實(shí)驗(yàn)四：回溯法（最全最新，與題目要求一致）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！