最大團(tuán)問(wèn)題
1、相關(guān)定義
給定一個(gè)無(wú)向圖 G = ( V , E ) G=(V, E) G=(V,E) , 其中 V V V是圖的頂點(diǎn)集， E E E是圖的邊集：
- 完全子圖：如果 U ? V U?V U?V，對(duì)任意的 u , v ∈ U u, v∈U u,v∈U, 有 ( u , v ) ∈ E (u, v)∈E (u,v)∈E, 則稱 U U U是 V V V的完全子圖
- 團(tuán)：
G
G
G的完全子圖
U
U
U就是
G
G
G的團(tuán)。
- 一個(gè)無(wú)向圖中，滿足兩兩之間都有邊連接的頂點(diǎn)的集合，被稱為該無(wú)向圖的團(tuán)
- 極大團(tuán)：增加任一頂點(diǎn)都不再符合團(tuán)定義的團(tuán)。
- 也就是說(shuō)，極大團(tuán)不能被任何一個(gè)更大的團(tuán)所包含。
- 最大團(tuán)：是一個(gè)圖中頂點(diǎn)數(shù)最多的團(tuán)。
- 即 G G G的最大團(tuán)是指 G G G的最大完全子圖。
- 同時(shí)也是一個(gè)圖的極大團(tuán)中頂點(diǎn)數(shù)最多的團(tuán)。
舉例：
左圖為圖
G
=
(
V
,
E
)
G=(V, E)
G=(V,E), 右邊是它的一些子圖。
2、最大團(tuán)問(wèn)題
- 簡(jiǎn)而言之，最大團(tuán)問(wèn)題就是在一個(gè)無(wú)向圖中找出一點(diǎn)數(shù)最多的完全圖。
- 最大團(tuán)問(wèn)題可以看作是圖 G G G的頂點(diǎn)集 V V V的子集選取問(wèn)題。因此我們可以用子集樹來(lái)表示該問(wèn)題的解空間。
3、回溯法解最大團(tuán)
3.1 回溯法基本思想：
回溯法有“通用解題法之稱”。用它可以系統(tǒng)地搜索問(wèn)題的所有解?；厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在問(wèn)題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄇ髥?wèn)題的所有解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可結(jié)束。這種以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱為回溯法。她適用于求解組合數(shù)較大的問(wèn)題。
3.2 MCP問(wèn)題之回溯算法基本思想
設(shè)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z位于解空間樹的第 i i i 層。在進(jìn)入左子樹前，必須確認(rèn)從頂點(diǎn) i i i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連（確保是團(tuán)）。在進(jìn)入右子樹前，必須確認(rèn)還有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。
//初始化： ??????????=0，cn=??
//cn：表示當(dāng)前頂點(diǎn)數(shù)
//bestn：表示當(dāng)前最優(yōu)定點(diǎn)數(shù)
回溯算法()
如果到達(dá)葉子結(jié)點(diǎn)：
輸出最優(yōu)解
如果沒(méi)有到達(dá)葉子結(jié)點(diǎn)：
如果當(dāng)前頂點(diǎn)與當(dāng)前團(tuán)每點(diǎn)有邊連接：//對(duì)左子樹的判斷
進(jìn)入左子樹，x[i]=1
進(jìn)行處理
進(jìn)行下一層的遞歸求解(i+1)//進(jìn)入回溯算法(i+1)
將處理回退到處理之前
如果右子樹中可能含有最優(yōu)解cn+n-i>bestn：//對(duì)右子樹的判斷
進(jìn)入右子樹；進(jìn)行下一層(i+1)//進(jìn)入回溯算法(i+1)
3.2.1 Java代碼
public class MaxClique
static int[] x; // 當(dāng)前解
static int n; //圖 G的頂點(diǎn)數(shù)
static int cn; // 當(dāng)前頂點(diǎn)數(shù)
static int bestn; // 當(dāng)前最大頂點(diǎn)數(shù)
static int [] bestx; //當(dāng)前最優(yōu)解
static boolean[][] a; //圖G的鄰接矩陣
public static int maxClique(int [] v)
{
// 初始化
x=new int[n+]]:cn=0;
bestn=0;
bestx= v;
//回溯搜索
backtrack(1);
return bestn;
}
private static void backtrack(int i)
{
f(i>n)
{//到達(dá)葉結(jié)點(diǎn)
for(intj=l;j<=n;j++)
bestx[j]=x[j];
bestn= cn;
return;
}
//檢查頂點(diǎn)i與當(dāng)前團(tuán)的連接
boolean ok= true;
for (int j=l;j<i; j++)
if (x[j]==1&&!a[]Cj])
{
//i與j不相連
ok=false;
break;
}
if(ok)
{
//進(jìn)入左子樹
x[i]=1
cn++;
backtrack(i+1);
cn--;
}
if (cn+n-i>bestn)
{
//進(jìn)人右子樹
x[i]=0;
backtrack(i+1);
}
}
}
3.2.2 舉例
圖引自：https://www.cnblogs.com/wkfvawl/p/11923848.html ----有一個(gè)更詳細(xì)的講解
4、分支限界法解最大團(tuán)
4.1 分支限界法基本思想
分支限界法類似于回溯法，是在問(wèn)題的解空間樹上搜索問(wèn)題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。
由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法對(duì)解空間樹的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。
分支限界法的搜索策略是，在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加速搜索進(jìn)程，在每一處活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹上最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。這種方法成為分支限界法。
4.2 MPC問(wèn)題之分支限界算法基本思想
同樣，與回溯法類似的，設(shè)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z位于解空間樹的第 i i i 層。在進(jìn)入左子樹前，必須確認(rèn)從頂點(diǎn) i i i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連（確保是團(tuán)）。在進(jìn)入右子樹前，必須確認(rèn)還有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。
//初始化： 建立優(yōu)先隊(duì)列，存儲(chǔ)活結(jié)點(diǎn)。初始化根結(jié)點(diǎn)為第一個(gè)擴(kuò)展結(jié)點(diǎn)。i=0
//cn：表示當(dāng)前頂點(diǎn)數(shù)
//n: 總頂點(diǎn)數(shù)
//bestn：表示當(dāng)前最優(yōu)定點(diǎn)數(shù)
//i：在一定程度上衡量結(jié)點(diǎn)所在層數(shù)
分支限界算法()：
While(i!=n+1)：//非葉結(jié)點(diǎn)
如果頂點(diǎn)i與當(dāng)前團(tuán)中其他頂點(diǎn)是否都有邊相連：
進(jìn)入左子樹；
如果cn+1>bestn：左子結(jié)點(diǎn)加入優(yōu)先隊(duì)列；否則舍去該結(jié)點(diǎn)
如果右子樹可能有最優(yōu)解（cn+n-i>bestn）：
將右子樹結(jié)點(diǎn)加入到優(yōu)先隊(duì)列
選優(yōu)先級(jí)高的作為擴(kuò)展結(jié)點(diǎn) （當(dāng)前頂點(diǎn)數(shù)最大結(jié)點(diǎn)）
4.2.1 Java代碼
static class BBnode
{
BBnode parent; // 父結(jié)點(diǎn)
boolean leftChild; // 左兒子結(jié)點(diǎn)標(biāo)志
//構(gòu)造方法
BBnode( BBnode par，boolean ch)
{
parent一 par;
leftChild= ch;
}
}
static class HeapNade implements Comparable
{
BBnode liveNode;
int upperSize; //當(dāng)前團(tuán)最大頂點(diǎn)數(shù)的上界
int cliqueSize; //當(dāng)前團(tuán)的頂點(diǎn)數(shù)
int level; //結(jié)點(diǎn)在子集空間樹中所處的層次
//構(gòu)造方法
HeapNode(BBnode node. int up.int size. int lev)
{
liveNode=node.
upperSize-up;
cliqueSize= size;
level= lev;
}
public int compareTo(Object x)
{
int xup=((HeapNode) x).upperSize;
if (upperSize<xup) return一1;
if (upperSize-=xup) return 0i
return 1;
}
}
public class BBClique
{
static boolean [][] a; //圖 G的鄰接短陣
static MaxHeap heap; // 活結(jié)點(diǎn)優(yōu)先隊(duì)列
}
private static void addLiveNode(int up int size, int lev, BBnode par, boolean ch)
{//將活結(jié)點(diǎn)加人到子集空間樹中并插人最大堆中
BBnode b= new BBnode( par.ch);
HeapNode node= new HeapNode(b，up，size，lev);
heap.put(node);
}
public static int bbMaxClique(int [] bestx)
{// 解最大團(tuán)間題的優(yōu)先隊(duì)列式分支限界法
int n= bestx. length-l；
heap-new MaxHeap();
// 初始化
BBnode enode=null;
int i=l;
int cn=0;
int bestn=0
// 搜索子集空間樹
while(i!=n+1)
{//非葉結(jié)點(diǎn)
// 檢查頂點(diǎn)i與當(dāng)前團(tuán)中其他頂點(diǎn)之間是否有邊相連
boolean ok=true;
BBnode bnode = enode;
for (intj=i-1;j>0;bnode= bnode. parent,j-一)
if (bnode. leftChild &.&.!a[i][i])
{
ok=false;
break ;
}
if (ok)
{//左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn)
if(cn+1>bestn) bestn=cn+1;
addLiveNode(cn+n-i+1，cn+1，i+1，enode，true);
}
if(cn+n-i>=bestn)
//右子樹可能含最優(yōu)解
addLiveNode(cn+n-i，cn，i+1，enode，false);
// 取下一擴(kuò)展結(jié)點(diǎn)
HeapNode node=(HeapNode) heap.removeMax();
enode=node.liveNode;
cn=node.cliqueSize;
i= node.level;
//構(gòu)造當(dāng)前最優(yōu)解
for (intj=n;j>0;j--)
{
bestx[j]=(enode. leftChild) ?1 :0;
enode=enode.parent;
}
return bestn;
}
4.2.2 舉例
4.2.2.1 四個(gè)頂點(diǎn)的圖
4.2.2.2 五個(gè)頂點(diǎn)的圖
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-468044.html
文獻(xiàn)：
文中代碼來(lái)自于書籍：《算法設(shè)計(jì)與分析（第3版）》——王曉東 編著文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-468044.html
到了這里，關(guān)于最大團(tuán)問(wèn)題(MPP)之回溯法、分支限界法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
