本章的例題主要還是以回溯法章節(jié)的例題為主
創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),西藏企業(yè)網(wǎng)站建設(shè),西藏品牌網(wǎng)站建設(shè),網(wǎng)站定制,西藏網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,西藏網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。創(chuàng)新互聯(lián)公司專注于慶城網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供慶城營銷型網(wǎng)站建設(shè)，慶城網(wǎng)站制作、慶城網(wǎng)頁設(shè)計(jì)、慶城網(wǎng)站官網(wǎng)定制、小程序設(shè)計(jì)服務(wù)，打造慶城網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供慶城網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。據(jù)題目要求，一個(gè)圖的團(tuán)需要滿足它是一個(gè)完全子圖，并且不被更大的完全子圖包含。然后需要我們求出這個(gè)圖G的大團(tuán)，如果像如圖給出的例子有三種大團(tuán)，也就是說大團(tuán)也不唯一。大團(tuán)也同時(shí)滿足大獨(dú)立集（任意兩點(diǎn)無連線）。
首先我們確定團(tuán)包含的點(diǎn)集合肯定與排序無關(guān)，因此我們要構(gòu)建的是一個(gè)子集樹。
其次我們要根據(jù)題目的要求列出剪枝條件：
1.選取的頂點(diǎn)任意兩點(diǎn)都存在邊，也就是若已有n個(gè)頂點(diǎn)，每加入一個(gè)頂點(diǎn)要多n-1條邊；
2.如果有更大團(tuán)，就應(yīng)當(dāng)將大團(tuán)更新
3.大團(tuán)還是大獨(dú)立集（可以用于確定上界）
我們?cè)诨厮莘〞r(shí)的總結(jié)依然適用，不過我們現(xiàn)在要用分支限界法來寫。
由于分支限界法使用的是大堆的結(jié)構(gòu)，不過在這個(gè)題目里12345沒有大大小之分（雖然我們也可以以度的大小作為大大小，但是為什么不這么做呢？原因是因?yàn)椴环奖阄覀冞M(jìn)行界限的判斷，往下看）。然后我們將在每層來判斷圖中對(duì)應(yīng)節(jié)點(diǎn)是否選取，比如第一層（根節(jié)點(diǎn)不算）判斷1是選取還是不選，選就走左子樹，不選就是右子樹，以此類推。
另外知道了分支，我們還要確定界限，很顯然題目要求我們的大團(tuán)中每2個(gè)頂點(diǎn)之間都要有邊，那么就用鄰接表表示原圖并看看選取的兩個(gè)節(jié)點(diǎn)ij是否有邊。這時(shí)也體現(xiàn)出按層來判斷對(duì)應(yīng)序號(hào)節(jié)點(diǎn)的好處了，這樣我們就可以直接通過循環(huán)遍歷，遍歷n以內(nèi)的數(shù)字節(jié)點(diǎn)和其他節(jié)點(diǎn)是否有邊。
問題如下：某售貨員要到若干個(gè)城市推銷商品，已知各城市之間的路程（或旅費(fèi)），他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一遍最后回到駐地的路線，使總的路線（或總的旅費(fèi)）最小。也就是說給定一個(gè)無向圖，求遍歷每一個(gè)頂點(diǎn)一次且僅一次的一條回路，最后回到起點(diǎn)的最小花費(fèi)，這是一個(gè)無向圖的最小回路問題。
用分支限界法來解決，我們依舊是使用堆的結(jié)構(gòu)，不過要求最小值的話我們就用最小堆
分支原理還是一樣的，每層代表一個(gè)節(jié)點(diǎn)，然后左子樹代表選擇，右子樹代表沒選。
界限上我們需要滿足題目，首先我們要選取最優(yōu)值，那么得記錄當(dāng)前最優(yōu)解bestx吧，如果發(fā)現(xiàn)一條路徑的路長(zhǎng)>=bestx，那就不可能更小，就可以直接剪枝。
其次這個(gè)問題需要我們形成回路，那么我們?cè)谧詈笠粚右簿褪莕-1層（從0開始，葉子節(jié)點(diǎn)為結(jié)束點(diǎn)）一定就要和我們的第0層（出發(fā)點(diǎn)）的選擇是一樣的了，也就是說我們無需直接遍歷到葉子節(jié)點(diǎn)，只需判斷n-2層的節(jié)點(diǎn)是否能到達(dá)葉子節(jié)點(diǎn)，如果能就代表是有回路的，否則就直接剪枝。
從這兩題我們可以總結(jié)出代碼的編寫規(guī)范了
在確定了分支條件和界限之后，我們要選擇用堆的形式來判斷分支選擇，一般以每層來代表一個(gè)節(jié)點(diǎn)，然后對(duì)其進(jìn)行上界和下界的剪枝，其中界限也是會(huì)動(dòng)態(tài)變化的，因此也要用算法來確定動(dòng)態(tài)變化的界限，最后當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)則得到我們的答案。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
重慶分公司
重慶分公司
