【問(wèn)題】       n皇后問(wèn)題

    問(wèn)題描述：求出在一個(gè)n×n的棋盤上，放置n個(gè)不能互相捕捉的國(guó)際象棋“皇后”的所有布局。

       這是來(lái)源于國(guó)際象棋的一個(gè)問(wèn)題�；屎罂梢匝刂�縱橫和兩條斜線4個(gè)方向相互捕捉。如圖所示，一個(gè)皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個(gè)皇后相互捕捉。

      

    從圖中可以得到以下啟示：一個(gè)合適的解應(yīng)是在每列、每行上只有一個(gè)皇后，且一條斜線上也只有一個(gè)皇后。

       求解過(guò)程從空配置開(kāi)始。在第1列至第m列為合理配置的基礎(chǔ)上，再配置第m+1列，直至第n列配置也是合理時(shí)，就找到了一個(gè)解。接著改變第n列配置，希望獲得下一個(gè)解。另外，在任一列上，可能有n種配置。開(kāi)始時(shí)配置在第1行，以后改變時(shí)，順次選擇第2行、第3行、…、直到第n行。當(dāng)?shù)?/SPAN>n行配置也找不到一個(gè)合理的配置時(shí)，就要回溯，去改變前一列的配置。得到求解皇后問(wèn)題的算法如下：

       {     輸入棋盤大小值n；

              m=0;

              good=1;

              do {

                     if (good)

                            if (m==n)

                            {     輸出解；

                                   改變之，形成下一個(gè)候選解;

                            }

                            else  擴(kuò)展當(dāng)前候選接至下一列；

                     else  改變之，形成下一個(gè)候選解；

                     good=檢查當(dāng)前候選解的合理性；

              } while (m!=0);

       }

       在編寫程序之前，先確定邊式棋盤的數(shù)據(jù)結(jié)構(gòu)。比較直觀的方法是采用一個(gè)二維數(shù)組，但仔細(xì)觀察就會(huì)發(fā)現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性帶來(lái)困難。更好的方法乃是盡可能直接表示那些常用的信息。對(duì)于本題來(lái)說(shuō)，“常用信息”并不是皇后的具體位置，而是“一個(gè)皇后是否已經(jīng)在某行和某條斜線合理地安置好了”。因在某一列上恰好放一個(gè)皇后，引入一個(gè)一維數(shù)組（col[ ]），值col[i]表示在棋盤第i列、col[i]行有一個(gè)皇后。例如：col[3]=4，就表示在棋盤的第3列、第4行上有一個(gè)皇后。另外，為了使程序在找完了全部解后回溯到最初位置，設(shè)定col[0]的初值為0當(dāng)回溯到第0列時(shí)，說(shuō)明程序已求得全部解，結(jié)束程序運(yùn)行。

       為使程序在檢查皇后配置的合理性方面簡(jiǎn)易方便，引入以下三個(gè)工作數(shù)組：

（1）       數(shù)組a[ ]，a[k]表示第k行上還沒(méi)有皇后；

（2）       數(shù)組b[ ]，b[k]表示第k列右高左低斜線上沒(méi)有皇后；

（3）       數(shù)組 c[ ]，c[k]表示第k列左高右低斜線上沒(méi)有皇后；

    棋盤中同一右高左低斜線上的方格，他們的行號(hào)與列號(hào)之和相同；同一左高右低斜線上的方格，他們的行號(hào)與列號(hào)之差均相同。

       初始時(shí)，所有行和斜線上均沒(méi)有皇后，從第1列的第1行配置第一個(gè)皇后開(kāi)始，在第m列col[m]行放置了一個(gè)合理的皇后后，準(zhǔn)備考察第m+1列時(shí)，在數(shù)組a[ ]、b[ ]和c[ ]中為第m列，col[m]行的位置設(shè)定有皇后標(biāo)志；當(dāng)從第m列回溯到第m-1列，并準(zhǔn)備調(diào)整第m-1列的皇后配置時(shí)，清除在數(shù)組a[ ]、b[ ]和c[ ]中設(shè)置的關(guān)于第m-1列，col[m-1]行有皇后的標(biāo)志。一個(gè)皇后在m列，col[m]行方格內(nèi)配置是合理的，由數(shù)組a[ ]、b[ ]和c[ ]對(duì)應(yīng)位置的值都為1來(lái)確定。細(xì)節(jié)見(jiàn)以下程序：

【程序】

# include <stdio.h>

# include <stdlib.h>

# define   MAXN    20

int n,m,good;

int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

 

void main()

{     int j;

       char awn;

       printf(“Enter n:    “);   scanf(“%d”,&n);

       for (j=0;j<=n;j++)   a[j]=1;

       for (j=0;j<=2*n;j++)      cb[j]=c[j]=1;

       m=1;       col[1]=1;        good=1;  col[0]=0;

       do {

              if (good)

                     if (m==n)

                     {     printf(“列\t行”);

                            for (j=1;j<=n;j++)

                                   printf(“%3d\t%d\n”,j,col[j]);

                            printf(“Enter  a  character (Q/q  for  exit)!\n”);

                            scanf(“%c”,&awn);

                            if (awn==’Q’||awn==’q’)      exit(0);

                            while (col[m]==n)

                            {     m--;

                                   a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

                            }

                            col[m]++;

                     }

                     else

                     {     a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;

                            col[++m]=1;

                     }

              else

              {     while (col[m]==n)

                     {     m--;

                            a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

                     }

                     col[m]++;

              }

              good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];

       } while (m!=0);

}

       試探法找解算法也常常被編寫成遞歸函數(shù)，下面兩程序中的函數(shù)queen_all()和函數(shù)queen_one()能分別用來(lái)解皇后問(wèn)題的全部解和一個(gè)解。

【程序】

# include <stdio.h>

# include <stdlib.h>

# define   MAXN    20

int n;

int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

void main()

{     int j;

       printf(“Enter n:    “);   scanf(“%d”,&n);

       for (j=0;j<=n;j++)   a[j]=1;

       for (j=0;j<=2*n;j++)      cb[j]=c[j]=1;

       queen_all(1,n);

}

 

void queen_all(int k,int n)

{     int i,j;

       char awn;

       for (i=1;i<=n;i++)

              if (a[i]&&b[k+i]&&c[n+k-i])

              {     col[k]=i;

                     a[i]=b[k+i]=c[n+k-i]=0;

                     if (k==n)

                     {     printf(“列\t行”);

                            for (j=1;j<=n;j++)

                                   printf(“%3d\t%d\n”,j,col[j]);

                            printf(“Enter  a  character (Q/q  for  exit)!\n”);

                            scanf(“%c”,&awn);

                            if (awn==’Q’||awn==’q’)      exit(0);

                     }

                     queen_all(k+1,n);

                     a[i]=b[k+i]=c[n+k-i];

              }

}

       采用遞歸方法找一個(gè)解與找全部解稍有不同，在找一個(gè)解的算法中，遞歸算法要對(duì)當(dāng)前候選解最終是否能成為解要有回答。當(dāng)它成為最終解時(shí)，遞歸函數(shù)就不再遞歸試探，立即返回；若不能成為解，就得繼續(xù)試探。設(shè)函數(shù)queen_one()返回1表示找到解，返回0表示當(dāng)前候選解不能成為解。細(xì)節(jié)見(jiàn)以下函數(shù)。

【程序】

# define   MAXN    20

       int n;

       int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

       int queen_one(int k,int n)

       {     int i,found;

              i=found=0;

              While (!found&&i<n)

              {     i++;

                     if (a[i]&&b[k+i]&&c[n+k-i])

                     {     col[k]=i;

                            a[i]=b[k+i]=c[n+k-i]=0;

                            if (k==n) return 1;

                            else

                                   found=queen_one(k+1,n);

                            a[i]=b[k+i]=c[n+k-i]=1;

                     }

              }

              return found;

       }

六、貪婪法

       貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗�省去了為找最�?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

       例如平時(shí)購(gòu)物找錢時(shí)，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開(kāi)始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優(yōu)，是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪算法，應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣，共找回5個(gè)硬幣。但最優(yōu)的解應(yīng)是3個(gè)5單位面值的硬幣。

【問(wèn)題】       裝箱問(wèn)題

    問(wèn)題描述：裝箱問(wèn)題可簡(jiǎn)述如下：設(shè)有編號(hào)為0、1、…、n-1的n種物品，體積分別為v₀、v₁、…、v_n-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過(guò)V，即對(duì)于0≤i＜n，有0＜v_i≤V。不同的裝箱方案所需要的箱子數(shù)目可能不同。裝箱問(wèn)題要求使裝盡這n種物品的箱子數(shù)要少。

       若考察將n種物品的集合分劃成n個(gè)或小于n個(gè)物品的所有子集，最優(yōu)解就可以找到。但所有可能劃分的總數(shù)太大。對(duì)適當(dāng)大的n，找出所有可能的劃分要花費(fèi)的時(shí)間是無(wú)法承受的。為此，對(duì)裝箱問(wèn)題采用非常簡(jiǎn)單的近似算法，即貪婪法。該算法依次將物品放到它第一個(gè)能放進(jìn)去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。不失一般性，設(shè)n件物品的體積是按從大到小排好序的，即有v₀≥v₁≥…≥v_n-1。如不滿足上述要求，只要先對(duì)這n件物品按它們的體積從大到小排序，然后按排序結(jié)果對(duì)物品重新編號(hào)即可。裝箱算法簡(jiǎn)單描述如下：

{     輸入箱子的容積；

       輸入物品種數(shù)n；

       按體積從大到小順序，輸入各物品的體積；

       預(yù)置已用箱子鏈為空；

       預(yù)置已用箱子計(jì)數(shù)器box_count為0；

       for (i=0;i<n;i++)

       {     從已用的第一只箱子開(kāi)始順序?qū)ふ夷芊湃胛锲?/SPAN>i 的箱子j；

              if （已用箱子都不能再放物品i）

              {     另用一個(gè)箱子，并將物品i放入該箱子；

                     box_count++；

              }

              else

                     將物品i放入箱子j；

       }

}

       上述算法能求出需要的箱子數(shù)box_count，并能求出各箱子所裝物品。下面的例子說(shuō)明該算法不一定能找到最優(yōu)解，設(shè)有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個(gè)單位體積。按上述算法計(jì)算，需三只箱子，各箱子所裝物品分別為：第一只箱子裝物品1、3；第二只箱子裝物品2、4、5；第三只箱子裝物品6。而最優(yōu)解為兩只箱子，分別裝物品1、4、5和2、3、6。

       若每只箱子所裝物品用鏈表來(lái)表示，鏈表首結(jié)點(diǎn)指針存于一個(gè)結(jié)構(gòu)中，結(jié)構(gòu)記錄尚剩余的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構(gòu)成鏈表。以下是按以上算法編寫的程序。

【程序】

# include <stdio.h>

# include <stdlib.h>

typedef  struct  ele

{     int  vno;

       struct  ele  *link;

}     ELE;

typedef  struct  hnode

{     int  remainder;

       ELE  *head;

       Struct  hnode  *next;

}     HNODE;

 

void  main()

{     int  n, i, box_count, box_volume, *a;

       HNODE  *box_h,  *box_t,  *j;

       ELE   *p,  *q;

       Printf(“輸入箱子容積\n”);

       Scanf(“%d”,&box_volume);

       Printf(“輸入物品種數(shù)\n”);

       Scanf(“%d”,&n);

       A=(int *)malloc(sizeof(int)*n);

       Printf(“請(qǐng)按體積從大到小順序輸入各物品的體積：”);

       For (i=0;i<n;i++)    scanf(“%d”,a+i);

       Box_h=box_t=NULL;

       Box_count=0;

       For (i=0;i<n;i++)

       {     p=(ELE *)malloc(sizeof(ELE));

              p->vno=i;

              for (j=box_h;j!=NULL;j=j->next)

                     if (j->remainder>=a[i])   break;

              if (j==NULL)

              {     j=(HNODE *)malloc(sizeof(HNODE));

                     j->remainder=box_volume-a[i];

                     j->head=NULL;

                     if (box_h==NULL)        box_h=box_t=j;

                     else  box_t=boix_t->next=j;

                     j->next=NULL;

                     box_count++;

              }

              else  j->remainder-=a[i];

              for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);

              if (q==NULL)

              {     p->link=j->head;

                     j->head=p;

              }

              else

              {     p->link=NULL;

                     q->link=p;

              }

       }

       printf(“共使用了%d只箱子”，box_count);

       printf(“各箱子裝物品情況如下：”);

       for (j=box_h,i=1;j!=NULL;j=j->next,i++)

       {     printf(“第%2d只箱子，還剩余容積%4d，所裝物品有；\n”,I,j->remainder);

              for (p=j->head;p!=NULL;p=p->link)

                     printf(“%4d”,p->vno+1);

              printf(“\n”);

       }

}

 

上一頁(yè)  [1] [2] [3] [4] [5] [6] 下一頁(yè)