分支限界演算法解決數獨問題

A. 數獨高級解法有哪些

具體如下：

1、聯除法：在兩行三個隔膜中查找相同的數字，然後用它們查找另一行中的位數。該方法適用於中、高級數獨。

2、巡格法：找出每個橫膈膜數字的頻率，找出它的位置。

3、排它法：這種方法是解決問題的關鍵，容易被普通老百姓所忽視。觀察隊列或橫膈膜，如果有一個位置不能被其他數字填補，填補剩下的數字。

4、待定法：這種方法不常使用，但很有效。在區域中臨時定位一個數字，並將其用於排除。

5、行列法：該方法用於提高破階求解問題的效率。

6、假設法：作為專家，我並不主張這種做法。

7 、頻率法：這種方法比以前的方法更有效。列出行中或框中的所有情況，然後選擇一個高頻率的數字。

8、用候選方法解決數獨問題的候選演算法首先，必須建立一個候選列表。在不同的條件下，每個宮格不可能的候選人可以逐步和安全地被清除。

候選數方法可以用來解決復雜的數獨問題，但是候選數方法的使用不像直覺方法那樣直接，需要建立候選人名單的准備過程，所以實際使用可以先用可視化方法解決問題，而不能用候選人的方法來解決問題。

候選人數方法的解決方法是逐步排除不合適候選數的過程，所以在刪除候選數時一定要小心，要確定刪除的候選人是否安全，否則，多次都要重做的問題。在電腦軟體的幫助下，使得候選數表的維護變得輕鬆起來。

常規解題手法：

依解題填制的過程可區分為直觀法與候選數法。

直觀法就是不做任何記號，直接從數獨的盤勢觀察線索，推論答案的方法。

候選數法就是刪減等位群格位已出現的數字，將剩餘可填數字填入空格做為解題線索的參考，可填數字稱為候選數(Candidates，或稱備選數)。

直觀法和候選數法只是填制時候是否有注記的區別，依照個人習慣而定，並非鑒定題目難度或技巧難度的標准，無論是難題或是簡單題都可上述方法填制，一般程序解題以候選數法較多。

B. dijakstra演算法和分支限演算法在解決單源最短路徑問題的異同

記dijakstra演算法為D演算法
D演算法為貪心演算法,每一步的選擇為當前步的最優,復雜度為O(n*n) (又叫爬山法)
分支限界演算法,每一步的擴散為當前耗散度的最優,復雜度為(沒算)

都是A演算法的極端情況
(說錯了哈,下面我的文字中的的分支限界演算法實際上是在說動態規劃法,我查了一下書,動態規劃法是對分支限界法的改進,分支限界法不屬於A演算法(啟發式搜索演算法),但是這時用動態規劃法和D演算法比較也是有可比性的,而直接用分支限界演算法和D演算法比較也是可以的)
關鍵詞:耗散度 評估函數
即:對當前優先搜索方向的判斷標准為,有可能的最優解
而最優解可以用一個評估函數來做,即已經有的耗散度加上以後有可能的耗度
A演算法就是把兩個耗散度加在一起,作為當前狀態的搜索搜索方向;
但是對以後的耗散度的評估是麻煩的,D演算法就是把當前有的路的最短的作為,以後耗散度的評估.
分支限界演算法就是只以以前的耗散度為評估函數

你給的兩個演算法當然是A演算法的特例
你還可以參考一下 A*演算法 修正的A*演算法,相信對你的編程水平有幫助

參考:
隊列式分支限界法的搜索解空間樹的方式類似於解空間樹的寬度優先搜索，不同的是隊列式分支限界法不搜索以不可行結點（已經被判定不能導致可行解或不能導致最優解的結點）為根的子樹。按照規則，這樣的結點不被列入活結點表。

優先隊列式分支限界法的搜索方式是根據活結點的優先順序確定下一個擴展結點。結點的優先順序常用一個與該結點有關的數值p來表示。最大優先隊列規定p值較大的結點點的優先順序較高。在演算法實現時通常用一個最大堆來實現最大優先隊列，體現最大效益優先的原則。類似地，最小優先隊列規定p值較小的結點的優先順序較高。在演算法實現時，常用一個最小堆來實現，體現最小優先的原則。採用優先隊列式分支定界演算法解決具體問題時，應根據問題的特點選用最大優先或最小優先隊列，確定各個結點點的p值。

C. 用分支限界法求解0/1背包問題

1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。

2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。

#include

struct good
{
int weight;
int benefit;
int flag;//是否可以裝入標記
};

int number=0;//物品數量
int upbound=0;
int curp=0, curw=0;//當前效益值與重量
int maxweight=0;
good *bag=NULL;

void Init_good()
{
bag=new good [number];

for(int i=0; i {
cout<<"請輸入第件"<cin>>bag[i].weight;
cout<<"請輸入第件"<cin>>bag[i].benefit;
bag[i].flag=0;//初始標志為不裝入背包
cout< }

}

int getbound(int num, int *bound_u)//返回本結點的c限界和u限界
{
for(int w=curw, p=curp; num {
w=w+bag[num].weight;
p=w+bag[num].benefit;
}

*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}

void LCbag()
{
int bound_u=0, bound_c=0;//當前結點的c限界和u限界

for(int i=0; i {
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍歷左子樹
upbound=bound_u;//更改已有u限界,不更改標志

if( getbound(i, &bound_u)>bound_c )//遍歷右子樹
//若裝入，判斷右子樹的c限界是否大於左子樹根的c限界，是則裝入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//從已有重量和效益加上新物品
bag[i].flag=1;//標記為裝入
}
}

}

void Display()
{

cout<<"可以放入背包的物品的編號為：";
for(int i=0; iif(bag[i].flag>0)

cout<
｝

參考：
http://cache..com/c?word=%B7%D6%D6%A7%3B%CF%DE%BD%E7%3B%B7%A8%3B%C7%F3%BD%E2%3B0%2C1%3B%B1%B3%B0%FC%3B%CE%CA%CC%E2&url=http%3A//www%2Edaxiongonline%2Ecom/dvbbs/dispbbs%2Easp%3FboardID%3D31%26ID%3D1016&b=10&a=0&user=