【問(wèn)題】 馬的遍歷
問(wèn)題描述：在8×8方格的棋盤(pán)上，從任意指定的方格出發(fā)，為馬尋找一條走遍棋盤(pán)每一格并且只經(jīng)過(guò)一次的一條路徑。
馬在某個(gè)方格，可以在一步內(nèi)到達(dá)的不同位置最多有8個(gè)，如圖所示。如用二維數(shù)組board[ ][ ]表示棋盤(pán)，其元素記錄馬經(jīng)過(guò)該位置時(shí)的步驟號(hào)。另對(duì)馬的8種可能走法（稱(chēng)為著法）設(shè)定一個(gè)順序，如當(dāng)前位置在棋盤(pán)的（i，j）方格，下一個(gè)可能的位置依次為（i+2，j+1）、（i+1，j+2）、（i-1，j+2）、（i-2，j+1）、（i-2，j-1）、（i-1，j-2）、（i+1，j-2）、（i+2，j-1），實(shí)際可以走的位置盡限于還未走過(guò)的和不越出邊界的那些位置。為便于程序的同意處理，可以引入兩個(gè)數(shù)組，分別存儲(chǔ)各種可能走法對(duì)當(dāng)前位置的縱橫增量。
|
|
4 |
|
3 |
|
|
5 |
|
|
|
2 |
|
|
|
馬 |
|
|
|
6 |
|
|
|
1 |
|
|
7 |
|
0 |
|
對(duì)于本題，一般可以采用回溯法，這里采用Warnsdoff策略求解，這也是一種貪婪法，其選擇下一出口的貪婪標(biāo)準(zhǔn)是在那些允許走的位置中，選擇出口最少的那個(gè)位置。如馬的當(dāng)前位置（i，j）只有三個(gè)出口，他們是位置（i+2，j+1）、（i-2，j+1）和（i-1，j-2），如分別走到這些位置，這三個(gè)位置又分別會(huì)有不同的出口，假定這三個(gè)位置的出口個(gè)數(shù)分別為4、2、3，則程序就選擇讓馬走向（i-2，j+1）位置。
由于程序采用的是一種貪婪法，整個(gè)找解過(guò)程是一直向前，沒(méi)有回溯，所以能非�？斓卣业浇�。但是，對(duì)于某些開(kāi)始位置，實(shí)際上有解，而該算法不能找到解。對(duì)于找不到解的情況，程序只要改變8種可能出口的選擇順序，就能找到解。改變出口選擇順序，就是改變有相同出口時(shí)的選擇標(biāo)準(zhǔn)。以下程序考慮到這種情況，引入變量start，用于控制8種可能著法的選擇順序。開(kāi)始時(shí)為0，當(dāng)不能找到解時(shí)，就讓start增1，重新找解。細(xì)節(jié)以下程序。
【程序】
# include <stdio.h>
int delta_i[ ]={2,1,-1,-2,-2,-1,1,2};
int delta_j[ ]={1,2,2,1,-1,-2,-2,-1};
int board[8][8];
int exitn(int i,int j,int s,int a[ ])
{ int i1,j1,k,count;
for (count=k=0;k<8;k++)
{ i1=i+delta_i[(s+k)%8];
j1=i+delta_j[(s+k)%8];
if (i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)
a[count++]=(s+k)%8;
}
return count;
}
int next(int i,int j,int s)
{ int m,k,mm,min,a[8],b[8],temp;
m=exitn(i,j,s,a);
if (m==0) return –1;
for (min=9,k=0;k<m;k++)
{ temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);
if (temp<min)
{ min=temp;
kk=a[k];
}
}
return kk;
}
void main()
{ int sx,sy,i,j,step,no,start;
for (sx=0;sx<8;sx++)
for (sy=0;sy<8;sy++)
{ start=0;
do {
for (i=0;i<8;i++)
for (j=0;j<8;j++)
board[i][j]=0;
board[sx][sy]=1;
I=sx; j=sy;
For (step=2;step<64;step++)
{ if ((no=next(i,j,start))==-1) break;
I+=delta_i[no];
j+=delta_j[no];
board[i][j]=step;
}
if (step>64) break;
start++;
} while(step<=64)
for (i=0;i<8;i++)
{ for (j=0;j<8;j++)
printf(“%4d”,board[i][j]);
printf(“\n\n”);
}
scanf(“%*c”);
}
}
七、分治法
1、分治法的基本思想
任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模N有關(guān)。問(wèn)題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問(wèn)題，當(dāng)n=1時(shí)，不需任何計(jì)算；n=2時(shí)，只要作一次比較即可排好序；n=3時(shí)只要作3次比較即可，…。而當(dāng)n較大時(shí)，問(wèn)題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問(wèn)題，有時(shí)是相當(dāng)困難的。
分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。
如果原問(wèn)題可分割成k個(gè)子問(wèn)題（1<k≤n），且這些子問(wèn)題都可解，并可利用這些子問(wèn)題的解求出原問(wèn)題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。
2、分治法的適用條件
分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：
（1）該問(wèn)題的規(guī)�？s小到一定的程度就可以容易地解決；
（2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；
（3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；
（4）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。
上述的第一條特征是絕大多數(shù)問(wèn)題都可以滿足的，因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心法或動(dòng)態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。
3、分治法的基本步驟
分治法在每一層遞歸上都有三個(gè)步驟：
（1）分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；
（2）解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；
（3）合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。
它的一般的算法設(shè)計(jì)模式如下：
Divide_and_Conquer（P）
if |P|≤n0
then return（ADHOC（P））
將P分解為較小的子問(wèn)題P1、P2、…、Pk
for i←1 to k
do
yi ← Divide-and-Conquer（Pi） △ 遞歸解決Pi
T ← MERGE（y1，y2，…，yk） △ 合并子問(wèn)題
Return（T）
其中 |P| 表示問(wèn)題P的規(guī)模；n0為一閾值，表示當(dāng)問(wèn)題P的規(guī)模不超過(guò)n0時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題P。因此，當(dāng)P的規(guī)模不超過(guò)n0時(shí)，直接用算法ADHOC（P）求解。
算法MERGE（y1，y2，…，yk）是該分治法中的合并子算法，用于將P的子問(wèn)題P1、P2、…、Pk的相應(yīng)的解y1、y2、…、yk合并為P的解。
根據(jù)分治法的分割原則，原問(wèn)題應(yīng)該分為多少個(gè)子問(wèn)題才較適宜？各個(gè)子問(wèn)題的規(guī)模應(yīng)該怎樣才為適當(dāng)？這些問(wèn)題很難予以肯定的回答。但人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。換句話說(shuō)，將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。許多問(wèn)題可以取k=2。這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。
分治法的合并步驟是算法的關(guān)鍵所在。有些問(wèn)題的合并方法比較明顯，有些問(wèn)題合并方法比較復(fù)雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應(yīng)該怎樣合并，沒(méi)有統(tǒng)一的模式，需要具體問(wèn)題具體分析。
【問(wèn)題】 大整數(shù)乘法
問(wèn)題描述：
通常，在分析一個(gè)算法的計(jì)算復(fù)雜性時(shí)，都將加法和乘法運(yùn)算當(dāng)作是基本運(yùn)算來(lái)處理，即將執(zhí)行一次加法或乘法運(yùn)算所需的計(jì)算時(shí)間當(dāng)作一個(gè)僅取決于計(jì)算機(jī)硬件處理速度的常數(shù)。
這個(gè)假定僅在計(jì)算機(jī)硬件能對(duì)參加運(yùn)算的整數(shù)直接表示和處理時(shí)才是合理的。然而，在某些情況下，我們要處理很大的整數(shù)，它無(wú)法在計(jì)算機(jī)硬件能直接表示的范圍內(nèi)進(jìn)行處理。若用浮點(diǎn)數(shù)來(lái)表示它，則只能近似地表示它的大小，計(jì)算結(jié)果中的有效數(shù)字也受到限制。若要精確地表示大整數(shù)并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字，就必須用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。
請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算。
設(shè)X和Y都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積XY。我們可以用小學(xué)所學(xué)的方法來(lái)設(shè)計(jì)一個(gè)計(jì)算乘積XY的算法，但是這樣做計(jì)算步驟太多，顯得效率較低。如果將每2個(gè)1位數(shù)的乘法或加法看作一步運(yùn)算，那么這種方法要作O(n2)步運(yùn)算才能求出乘積XY。下面我們用分治法來(lái)設(shè)計(jì)一個(gè)更有效的大整數(shù)乘積算法。
圖6-3 大整數(shù)X和Y的分段
我們將n位的二進(jìn)制整數(shù)X和Y各分為2段，每段的長(zhǎng)為n/2位（為簡(jiǎn)單起見(jiàn)，假設(shè)n是2的冪），如圖6-3所示。
由此，X=A2n/2+B，Y=C2n/2+D。這樣，X和Y的乘積為：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD （1）
如果按式（1）計(jì)算XY，則我們必須進(jìn)行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)，以及3次不超過(guò)n位的整數(shù)加法（分別對(duì)應(yīng)于式（1）中的加號(hào)），此外還要做2次移位（分別對(duì)應(yīng)于式（1）中乘2n和乘2n/2）。所有這些加法和移位共用O（n）步運(yùn)算。設(shè)T（n）是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，則由式（1），我們有：
由此可得T（n）=O（n2）。因此，用（1）式來(lái)計(jì)算X和Y的乘積并不比小學(xué)生的方法更有效。要想改進(jìn)算法的計(jì)算復(fù)雜性，必須減少乘法次數(shù)。為此我們把XY寫(xiě)成另一種形式：
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD （3）
雖然，式（3）看起來(lái)比式（1）復(fù)雜些，但它僅需做3次n/2位整數(shù)的乘法（AC，BD和（A-B）（D-C）），6次加、減法和2次移位。由此可得：
用解遞歸方程的套用公式法馬上可得其解為T(n)=O(nlog3)=O(n1.59)。利用式（3），并考慮到X和Y的符號(hào)對(duì)結(jié)果的影響，我們給出大整數(shù)相乘的完整算法MULT如下：
function MULT(X，Y，n); {X和Y為2個(gè)小于2n的整數(shù)，返回結(jié)果為X和Y的乘積XY}
begin
S=SIGN(X)*SIGN(Y); {S為X和Y的符號(hào)乘積}
X=ABS(X);
Y=ABS(Y); {X和Y分別取絕對(duì)值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A=X的左邊n/2位;
B=X的右邊n/2位;
C=Y的左邊n/2位;
D=Y的右邊n/2位;
ml=MULT(A,C,n/2);
m2=MULT(A-B,D-C,n/2);
m3=MULT(B,D,n/2);
S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二進(jìn)制大整數(shù)乘法同樣可應(yīng)用于十進(jìn)制大整數(shù)的乘法以提高乘法的效率減少乘法次數(shù)。
【問(wèn)題】 最接近點(diǎn)對(duì)問(wèn)題
問(wèn)題描述：
在應(yīng)用中，常用諸如點(diǎn)、圓等簡(jiǎn)單的幾何對(duì)象代表現(xiàn)實(shí)世界中的實(shí)體。在涉及這些幾何對(duì)象的問(wèn)題中，常需要了解其鄰域中其他幾何對(duì)象的信息。例如，在空中交通控制問(wèn)題中，若將飛機(jī)作為空間中移動(dòng)的一個(gè)點(diǎn)來(lái)看待，則具有最大碰撞危險(xiǎn)的2架飛機(jī)，就是這個(gè)空間中最接近的一對(duì)點(diǎn)。這類(lèi)問(wèn)題是計(jì)算幾何學(xué)中研究的基本問(wèn)題之一。下面我們著重考慮平面上的最接近點(diǎn)對(duì)問(wèn)題。
最接近點(diǎn)對(duì)問(wèn)題的提法是：給定平面上n個(gè)點(diǎn)，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)的距離最小。
嚴(yán)格地說(shuō)，最接近點(diǎn)對(duì)可能多于1對(duì)。為了簡(jiǎn)單起見(jiàn)，這里只限于找其中的一對(duì)。
這個(gè)問(wèn)題很容易理解，似乎也不難解決。我們只要將每一點(diǎn)與其他n-1個(gè)點(diǎn)的距離算出，找出達(dá)到最小距離的兩個(gè)點(diǎn)即可。然而，這樣做效率太低，需要O(n2)的計(jì)算時(shí)間。我們能否找到問(wèn)題的一個(gè)O (nlogn)算法。
這個(gè)問(wèn)題顯然滿足分治法的第一個(gè)和第二個(gè)適用條件，我們考慮將所給的平面上n個(gè)點(diǎn)的集合S分成2個(gè)子集S1和S2，每個(gè)子集中約有n/2個(gè)點(diǎn)，然后在每個(gè)子集中遞歸地求其最接近的點(diǎn)對(duì)。在這里，一個(gè)關(guān)鍵的問(wèn)題是如何實(shí)現(xiàn)分治法中的合并步驟，即由S1和S2的最接近點(diǎn)對(duì)，如何求得原集合S中的最接近點(diǎn)對(duì)，因?yàn)?/SPAN>S1和S2的最接近點(diǎn)對(duì)未必就是S的最接近點(diǎn)對(duì)。如果組成S的最接近點(diǎn)對(duì)的2個(gè)點(diǎn)都在S1中或都在S2中，則問(wèn)題很容易解決。但是，如果這2個(gè)點(diǎn)分別在S1和S2中，則對(duì)于S1中任一點(diǎn)p，S2中最多只有n/2個(gè)點(diǎn)與它構(gòu)成最接近點(diǎn)對(duì)的候選者，仍需做n2/4次計(jì)算和比較才能確定S的最接近點(diǎn)對(duì)。因此，依此思路，合并步驟耗時(shí)為O(n2)。整個(gè)算法所需計(jì)算時(shí)間T(n)應(yīng)滿足：
T(n)=2T(n/2)+O(n2)
它的解為T(n)=O(n2)，即與合并步驟的耗時(shí)同階，顯示不出比用窮舉的方法好。從解遞歸方程的套用公式法，我們看到問(wèn)題出在合并步驟耗時(shí)太多。這啟發(fā)我們把注意力放在合并步驟上。
為了使問(wèn)題易于理解和分析，我們先來(lái)考慮一維的情形。此時(shí)S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù)x1、x2、…、xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。我們顯然可以先將x1、x2、…、xn排好序，然后，用一次線性掃描就可以找出最接近點(diǎn)對(duì)。這種方法主要計(jì)算時(shí)間花在排序上，因此如在排序算法中所證明的，耗時(shí)為O(nlogn)。然而這種方法無(wú)法直接推廣到二維的情形。因此，對(duì)這種一維的簡(jiǎn)單情形，我們還是嘗試用分治法來(lái)求解，并希望能推廣到二維的情形。
假設(shè)我們用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2，使得S1={x∈S | x≤m}；S2={x∈S | x>m}。這樣一來(lái)，對(duì)于所有p∈S1和q∈S2有p<q。
遞歸地在S1和S2上找出其最接近點(diǎn)對(duì){p1，p2}和{q1，q2}，并設(shè)δ=min{|p1-p2|，|q1-q2|}，S中的最接近點(diǎn)對(duì)或者是{p1，p2}，或者是{q1，q2}，或者是某個(gè){p3，q3}，其中p3∈S1且q3∈S2。如圖1所示。
圖1 一維情形的分治法
我們注意到，如果S的最接近點(diǎn)對(duì)是{p3，q3}，即 | p3-q3 | < δ，則p3和q3兩者與m的距離不超過(guò)δ，即 | p3-m | < δ，| q3-m | < δ，也就是說(shuō)，p3∈(m-δ，m)，q3∈(m，m+δ)。由于在S1中，每個(gè)長(zhǎng)度為δ的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于δ），并且m是S1和S2的分割點(diǎn)，因此(m-δ，m)中至多包含S中的一個(gè)點(diǎn)。同理，(m，m+δ)中也至多包含S中的一個(gè)點(diǎn)。由圖1可以看出，如果(m-δ，m)中有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。同理，如果(m，m+δ)中有S中的點(diǎn)，則此點(diǎn)就是S2中最小點(diǎn)。因此，我們用線性時(shí)間就能找到區(qū)間(m-δ，m)和(m，m+δ)中所有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。也就是說(shuō)，按這種分治策略，合并步可在O(n)時(shí)間內(nèi)完成。這樣是否就可以得到一個(gè)有效的算法了呢？
還有一個(gè)問(wèn)題需要認(rèn)真考慮，即分割點(diǎn)m的選取，及S1和S2的劃分。選取分割點(diǎn)m的一個(gè)基本要求是由此導(dǎo)出集合S的一個(gè)線性分割，即S=S1∪S2 ，S1∩S2=Φ，且S1
T（n）=T（n-1）+O（n）
它的解是T（n）=O（n2）。這種效率降低的現(xiàn)象可以通過(guò)分治法中“平衡子問(wèn)題”的方法加以解決。也就是說(shuō)，我們可以通過(guò)適當(dāng)選擇分割點(diǎn)m，使S1和S2中有大致相等個(gè)數(shù)的點(diǎn)。自然地，我們會(huì)想到用S的n個(gè)點(diǎn)的坐標(biāo)的中位數(shù)來(lái)作分割點(diǎn)。在選擇算法中介紹的選取中位數(shù)的線性時(shí)間算法使我們可以在O（n）時(shí)間內(nèi)確定一個(gè)平衡的分割點(diǎn)m。
至此，我們可以設(shè)計(jì)出一個(gè)求一維點(diǎn)集S中最接近點(diǎn)對(duì)的距離的算法pair如下。
Float pair（S）;
{ if | S | =2 δ= | x[2]－x[1] | /*x[1..n]存放的是S中n個(gè)點(diǎn)的坐標(biāo)*/
else
{ if ( | S | =1) δ=∞
else
{ m=S中各點(diǎn)的坐標(biāo)值的中位數(shù);
構(gòu)造S1和S2，使S1={x∈S | x≤m}，S2={x∈S | x＞m};
δ1=pair(S1);
δ2=pair(S2);
p=max(S1);
q=min(S2);
δ=min(δ1，δ2，q-p);
}
return(δ);
}
，我們將會(huì)及時(shí)處理。如轉(zhuǎn)載本網(wǎng)內(nèi)容，請(qǐng)注明出處。