ChenGen

          一切歸零,重新開始
          隨筆 - 13, 文章 - 10, 評論 - 21, 引用 - 0
          數據加載中……

          復習回溯算法——N皇后問題

          ???今天復習了回溯算法。N皇后問題是一個典型的需要用回溯算法來解決的問題。回溯算法可以用遞歸方法來實現,也可以用非遞歸方法來實現。用遞歸的方法來解決回溯的問題思路很清晰,但是耗費的內存資源較多,速度也較慢;非遞歸方法具有速度快和耗費較少內存資源的優點,但是程序的邏輯結構卻很復雜——不過搞懂之后覺得也很簡單。

          ???在寫非遞歸算法之前,參考了網上的一些文章,但是覺得那些程序都很晦澀難懂,而且存在一些問題,我索性自己寫了一個,花了我不少時間。

          ???遞歸實現:
          #include?"stdio.h"
          #include?
          "stdlib.h"
          #include?
          "time.h"

          /*?記錄當前的放置方案?*/
          int?*x;?
          /*?皇后的個數N?和?方案數目?*/
          int?n,sum=0;
          /*?檢查參數所指示的這一行皇后放置方案是否滿足要求?*/
          int??Place(int);
          /*?遞歸方法求取皇后放置方案*/
          void?Queen1(void);
          /*?用戶遞歸求取皇后放置方案的遞歸方法?*/
          void?TraceBack(int);
          /*?打印當前成功的放置方案?*/
          void?PrintMethod(void);

          void?main(void)
          {
          ????
          long?start,stop;
          ????printf(
          "input?n:?");
          ????scanf(
          "%d",&n);
          ????x
          =(int?*)malloc(sizeof(int)*n);
          ????time(
          &start);/*記錄開始時間*/
          ????Queen1();
          ????time(
          &stop);/*記錄結束時間*/
          ????printf(
          "\nmethod?total?%d?\n",sum);
          ????printf(
          "\nuse?%d?seconds?\n",(int)(stop-start));
          }


          int?Place(int?r)
          {
          ????
          int?i;
          ????
          for(i=0;i<r;i++){
          ????????
          if(x[r]==x[i]?||?abs(r-i)==abs(x[r]-x[i]))
          ????????????
          return?0;
          ????}

          ????
          return?1;
          }


          void?TraceBack(int?r)
          {
          ????
          int?i;
          ????
          if(r>=n){
          ????????sum
          ++;
          ????????
          /*?PrintMethod();?*/
          ????}
          else{
          ????????
          for(i=0;i<n;i++){
          ????????????x[r]
          =i;
          ????????????
          if(Place(r))?TraceBack(r+1);
          ????????}

          ????}

          }


          void?PrintMethod(void)
          {
          ????
          int?i,j;
          ????printf(
          "\nmethod?%d\n",sum);
          ????
          for(i=0;i<n;i++){
          ????????
          for(j=0;j<n;j++){
          ????????????
          if(j==x[i])?printf("*");
          ????????????
          else?printf("#");
          ????????}

          ????????printf(
          "\n");
          ????}

          }


          void?Queen1(void)
          {
          ????TraceBack(
          0);
          }

          ???非遞歸實現:

          #include?"stdio.h"
          #include?
          "stdlib.h"
          #include?
          "time.h"

          /*?記錄當前的放置方案?*/
          int?*x;?
          /*?皇后的個數N?和?方案數目?*/
          int?n,sum=0;
          /*?檢查參數所指示的這一行皇后放置方案是否滿足要求?*/
          int??Place(int);
          /*?非遞歸的方法求取皇后放置方案?*/
          void?Queen2(void);
          /*?打印當前成功的放置方案?*/
          void?PrintMethod(void);

          void?main(void)
          {
          ????
          long?start,stop;
          ????printf(
          "input?n:?");
          ????scanf(
          "%d",&n);
          ????x
          =(int?*)malloc(sizeof(int)*n);
          ????time(
          &start);/*記錄開始時間*/
          ????Queen2();
          ????time(
          &stop);/*記錄結束時間*/
          ????printf(
          "\nmethod?total?%d?\n",sum);
          ????printf(
          "\nuse?%d?seconds?\n",(int)(stop-start));
          }


          int?Place(int?r)
          {
          ????
          int?i;
          ????
          for(i=0;i<r;i++){
          ????????
          if(x[r]==x[i]?||?abs(r-i)==abs(x[r]-x[i]))
          ????????????
          return?0;
          ????}

          ????
          return?1;
          }


          void?Queen2(void)
          {
          ????
          int?i,k;
          ????
          for(i=0;i<n;i++)
          ????????x[i]
          =0;
          ????k
          =0;
          ????
          while(1){
          ????????
          if(x[k]>=n){
          ????????????
          /*?如果當前第K行的放置位置超出了范圍,那么檢查該行是否為第0行
          ???????????????如果是第0行,說明所有的方案都已經遍歷完畢,函數返回;否則回退到前一行
          ????????????
          */

          ????????????
          if(k==0)?break;
          ????????????x[k]
          =0;?/*?下次遍歷的初始位置?*/
          ????????????k
          --;?/*?返回上一行?*/
          ????????????x[k]
          ++;?/*下一種放置方案*/
          ????????}

          ????????
          else?if(!Place(k)){
          ????????????
          /*?如果當前第K行的放置方案不滿足要求,采取下一種放置方案*/
          ????????????x[k]
          ++;
          ????????}

          ????????
          else{
          ????????????
          if(k==(n-1)){
          ????????????????
          /*?如果已經是最后一行,那么表示已經成功得到一種放置方案*/
          ????????????????sum
          ++;
          ????????????????
          /*?PrintMethod();?*/
          ????????????????x[k]
          =0;?/*下次遍歷的初始位置*/
          ????????????????k
          --;?/*返回上一行*/
          ????????????????x[k]
          ++;?/*下一種放置方案*/
          ????????????}
          else
          ????????????????k
          ++;?/*?否則開始配置下一行的皇后?*/
          ????????}

          ????}

          }


          void?PrintMethod(void)
          {
          ????
          int?i,j;
          ????printf(
          "\nmethod?%d\n",sum);
          ????
          for(i=0;i<n;i++){
          ????????
          for(j=0;j<n;j++){
          ????????????
          if(j==x[i])?printf("*");
          ????????????
          else?printf("#");
          ????????}

          ????????printf(
          "\n");
          ????}

          }


          ???兩種方法的性能比較:

          N

          遞歸算法所用時間(秒)

          非遞歸算法所用時間(秒)

          13

          6

          6

          14

          37

          35

          15

          267

          254

          ???從上面的數據可以看出,兩種方法所用的時間相差并不大,但是遞歸算法所耗用的內存空間要比非遞歸算法大得多。因為我還不知道如何檢測應用程序所用的內存空間的大小,所以無法給出準確的證明。

          ?

          ?

          ?

          posted on 2006-09-27 22:11 ChenGen 閱讀(6811) 評論(6)  編輯  收藏 所屬分類: 數據結構復習

          評論

          # re: 復習回溯算法——N皇后問題  回復  更多評論   

          在嗎?加個友情鏈接啊,以后復習算法就來找你!
          2006-09-27 22:31 | 壞男孩

          # re: 復習回溯算法——N皇后問題  回復  更多評論   

          @壞男孩
          有什么算法方面的問題的話,可以發郵件給我,很樂意為大家解決算法的問題~
          2006-09-27 22:43 | ChenGen

          # re: 復習回溯算法——N皇后問題  回復  更多評論   

          。。。你的遞歸算法不用回溯?
          2008-09-24 11:01 | sw

          # re: 復習回溯算法——N皇后問題[未登錄]  回復  更多評論   

          @sw
          這是非遞歸算法
          2008-10-05 17:35 | chengen

          # re: 復習回溯算法——N皇后問題  回復  更多評論   

          你的遞歸實現有問題吧?
          2009-09-01 11:17 | 啊啊啊

          # re: 復習回溯算法——N皇后問題[未登錄]  回復  更多評論   

          用數據結構實現五皇后問題,你有代碼嗎
          2012-06-20 23:54 | su
          主站蜘蛛池模板: 富锦市| 潞西市| 威信县| 唐河县| 肃北| 新巴尔虎右旗| 新民市| 鸡西市| 平和县| 乌拉特前旗| 东平县| 北辰区| 广宗县| 图木舒克市| 鞍山市| 八宿县| 镇江市| 玉溪市| 台南县| 遂平县| 页游| 庄河市| 凤凰县| 体育| 晋江市| 秦安县| 宣汉县| 星座| 无锡市| 仁布县| 工布江达县| 内乡县| 恩平市| 通海县| 江孜县| 新安县| 金华市| 涟水县| 成安县| 陆良县| 泗洪县|