資源簡介
★問題描述：給定一個賦權無向圖G=(V,E),每個頂點v∈V都有一個權值w(v)。如果U∈V,且對任意(u,v)∈E有u∈U或v∈U,就稱U為圖G的一個頂點條覆蓋.G的最小權頂點覆蓋是指G中所含頂點權之和最小的頂點覆蓋。
★算法設計：對于結定的無向圖G,設計一個優先隊列式分支限界法,計算G的最小權頂點覆蓋。
★數據輸入：由文件input.txt給出輸入數據。第1行有2個正整數n和m,表示給定的圖G有n個頂點和m條邊,頂點編號為1,2,.....,n.第2行有n個正整數表示n個頂點的權.接下來的m行中,每行有2 個正整數u,v,表示圖G的一條邊(u,v)。
★結果輸出：將計算出的最小權頂點覆蓋的頂點權之和以及最優輸出到文件output.txt.文件第1行是最小權頂點覆蓋頂點權之和;第2行是最優解xi,1≤i≤n,xi=0表示頂點i不在最小權頂點覆蓋中。
代碼片段和文件信息
#include?
#include“MinHeap.h“;
using?namespace?std;
?
//最小堆結點元素類型是HeapNode
class?HeapNode
{
????friend?class?VertexCover;
public:
????operator?int（）?const?{?return?cn;?}
private:
????int?i????//活結點所處的層序號
cn???//當前權植和
????????*x???//當前解
*c;???//指向活結點在子集樹中的結點的指針
};
//解最小權項點覆蓋問題的優先隊列式分支界限法
class?VertexCover
{
????friend?int?MinCover（int**?int[]?int）;
private:
????void?search（）;
????bool?cover（HeapNode?E）;
????void?AddLiveNode（MinHeap?&H?HeapNode?E?int?cn?int?i?bool?ch）;
????int?**a??????????//圖的鄰接矩陣
n????????????//圖的頂點數
*w???????????//圖中每個頂點的權值
*bestx??????//最優解
bestn;???????//當前最小權值和
};
void?VertexCover::search（）
{
????int?j;
????MinHeap?H（1000）;?????//定義最小堆的容量為1000
????HeapNode?E;
????E.x?=?new?int[n+1];
????E.c?=?new?int[n+1];
????for（j?=?1;?j?<=?n;?j++）?
{
????????E.x[j]?=?E.c[j]?=?0;
????}
????int?i?=?1?cn?=?0;??????//初始時擴展結點在第一層，權值和為0
????while（1）?
{
????????if（i?>?n）?
{//到達葉結點
????????????if（cover（E））?
{??//如果所有結點都覆蓋，得到一組頂點覆蓋，更新當前最優值和相應的當前最優解
????????????????for（j?=?1;?j?<=?n;?j++）
????????????????????bestx[j]?=?E.x[j];
????????????????bestn?=?cn;
????????????????break;
????????????}
????????}?
else?
{//非葉結點
????????????if（!cover（E））?//結點沒有全部覆蓋，則添加活結點
????????????????AddLiveNode（H?E?cn?i?1）;????//檢查左兒子結點
????????????AddLiveNode（H?E?cn?i?0）;????????//右兒子結點
????????}
????????if（H.Size（）?==?0）???//如果堆容量為0，則跳出循環
????????????break;
???????//?將舍棄結點的存儲空間收回
???????delete?[]E.x;
???????delete?[]E.c;
????????//取下一擴展結點
????????H.DeleteMin（E）;??????//堆非空?
????????cn?=?E.cn;
????????i?=?E.i+1;
????}
}
//判定圖是否已完全覆蓋
bool?VertexCover::cover（HeapNode?E）
{
????for（int?j?=?1;?j?<=?n;?j++）
????????if（?E.x[j]?==?0?&&?E.c[j]?==?0?）
????????????return?false;
????return?true;
}
//將活結點加入堆中
void?VertexCover::AddLiveNode（MinHeap?&H?HeapNode?E?int?cn?int?i?bool?ch）
{
????int?j;
????HeapNode?N;???
????N.x?=?new?int[n+1];
????N.c?=?new?int[n+1];
????for（j?=?1;?j?<=?n;?j++）?
{
????????N.x[j]?=?E.x[j];
????????N.c[j]?=?E.c[j];
????}
????//檢查左兒子結點
????N.x[i]=ch?1:0;
????if（ch）?
{//可行結點
????????N.cn?=?cn?+?w[i];
????????for（j?=?1;?j?<=?n;?j++）
????????????if（a[i][j]）
????????????????N.c[j]++;
????}?
else
{
????????N.cn?=?cn;
}
????N.i?=?i;
????H.Insert（N）;??//插入到活結點隊列
}
//完成最小覆蓋計算
int?MinCover（int**?a?int?v[]?int?n）
{
????VertexCover?Y;
????Y.w?=?new?int[n+1];??????//記錄每個結點的權值
????for（int?j?=?1;?j?<=?n;?j++）
????????Y.w[j]?=?v[j];
????Y.a?=?a;
????Y.n?=?n;
????Y.bestx?=?v;
????Y.search（）;
????return?Y.bestn;
}
void?main（）
{
????int?n?e?u?v?i?j;
????int*?p;
????int**?a;
????
cout<<“input.txt:“<
????a?=?new?int*[n+1];
????for（i?=?0;?i?<=?n;?i++）
????????a[i]?=?new?int[n+1];
????for（i?=?0;?i?<=?n;?i++）
????????for（j?=?0;?j?<=?n;?j++）
????????????a[i][j]?=?0;
????p?=?new?int[ ?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????3722??2009-12-20?20:45??五、分支限界法\6-2.cpp
?????文件???????3367??2009-12-23?11:03??五、分支限界法\6-2.dsp
?????文件????????514??2009-12-23?11:04??五、分支限界法\6-2.dsw
?????文件??????41984??2009-12-23?11:04??五、分支限界法\6-2.ncb
?????文件??????48640??2009-12-23?11:04??五、分支限界法\6-2.opt
?????文件????????733??2009-12-23?11:03??五、分支限界法\6-2.plg
?????文件?????548928??2009-12-23?11:03??五、分支限界法\Debug\6-2.exe
?????文件?????257300??2009-12-23?11:03??五、分支限界法\Debug\6-2.obj
?????文件????1098752??2009-12-23?11:03??五、分支限界法\Debug\6-2.pdb
?????文件?????118784??2009-12-23?11:03??五、分支限界法\Debug\vc60.pdb
?????文件???????1619??2009-12-20?20:02??五、分支限界法\MinHeap.h
?????目錄??????????0??2010-07-14?14:07??五、分支限界法\Debug
?????目錄??????????0??2009-12-23?11:04??五、分支限界法
-----------?---------??----------?-----??----
??????????????2124343????????????????????13
評論
共有 條評論
川公網安備 51152502000135號