运动员最佳配对问题C.C++程序实现及其效率分析.doc

运动员最佳配对问题1) 回溯法求解问题的一般思路，回溯法求解本问题的思路及其C/C+程序实现及效率分析。回溯法求解本问题的思路： 假设男运动员已经按照1到n排好序不动，用一个数组w存放配对的女运动员的编号，即第i号男运动员配第wi号女运动员，初始时设wi=i,然后不断的重新排列w数组，每得到一次排列，就要计算在此排列下的配对总和，若发现比之前的总和大，则更新最优解。套用排列树框架，做好初始化后开始回溯，关键在于到达叶子节点时，需要计算sum += piwi * qwii，若发现sum比之前的最优值大，则更新最优值和配对顺序，回溯完成后则可得到最大总和及其相应的运动员配对方法。1) 分支限界法求解问题的一般思路，分支限界法求解本问题的思路及其C/C+程序实现及效率分析。代码：#include#include /文件输入输出流#include /I/O流控制头文件#include /vector是一个能够存放任意类型的动态数组，/能够增加和压缩数据using namespace std;vector Re; /全局变量,Re用来记录配对情况vectorvector P;vectorvector Q;class PairUp friend int nPairUp(int);private:bool Place(int k);void Backtrack(int k);int n; /运动员个数int bestsum;vector x; /当前解public:PairUp(int m,int c,int b) x.resize(m+1); Re.resize(m+1);n = c; bestsum = b; PairUp() ;bool PairUp:Place(int k) for(int j=1;jn)int currentsum=0; /第次还原为进行下次的累加for(int i=1;i=n;i+) currentsum += (Pixi) * (Qxii); /累加，计算当前配对总和 if(bestsum=currentsum) /记录最大可行解bestsum=currentsum;copy(x.begin(),x.end(),Re.begin(); elsefor(int i=t;i=n;i+) swap(xt,xi);if(Place(t)Backtrack(t+1);swap(xt,xi); int nPairUp(int n) PairUp X(n,n,0); /初始化Xvector p;for(int i=0;i=n;i+)p.push_back(i); /当前的P数组尾部插入i的值copy(p.begin(),p.end(),X.x.begin();X.Backtrack(1);return X.bestsum;int main() ifstream fin(input.txt);ofstream fout(output.txt);int n,i,j,currentsum;vector r; vector t;finn;r.push_back(0); P.push_back(r);t.push_back(0); Q.push_back(t);cout回溯法求解运动员最佳配对endlendl;cout从文件input.txt中获得数据.endl;for(i=1;i=n;i+)for(j=1;jcurrentsum;r.push_back(currentsum); P.push_back(r);for(vector:iterator vr = r.begin()+1;vr != r.end();) vr = r.erase(vr); for(i=1;i=n;i+) for(j=1;jcurrentsum;t.push_back(currentsum); Q.push_back(t);for(vector:iterator vt = t.begin()+1;vt != t.end();)vt = t.erase(vt); cout结果为：nPairUp(n)，并已保存至output.txt.endlendl;cout男运动员 & 女运动员endl;for(i=1;i=n;i+) coutsetw(4)isetw(12)Reiendl; /保证输出宽度为n foutnPairUp(n)endl;return 0 ;效率分析：回溯法用到的是递归的进行深度优先搜索整个排列树，算法中没有剪枝函数和限界函数，算法的时间复杂度为O(n!),复杂度很高2）分支限界法求解本问题思路：算法开始时创建一个最大堆，用于表示活结点优先队列堆中每个节点的val值是优先队列的优先级。接着算法计算出图中每个顶点的最大val如果搜索到所搜索的排队树的叶子节点，算法即告结束。代码：#include #include #include #include #include using namespace std; int n; int *P; /女运动员和男运动员配对的竞赛优势 int *Q; /男运动员和女运动员配对的竞赛优势 int best; /最优解 int *w;/当前男运动员排列 class ArgNode public: int x;/arg1:x已排列 int csum;/此种排列的竞赛优势值 public: int *w;/当前男运动员排列 ArgNode(const ArgNode &one) w = new int n + 1; for (int i = 0; i w= new int n + 1; for (int i = 0; i wi = wi; this-x = x; this-csum = csum; ; /大顶堆 bool operator csum other.csum) return false; else return true; void compute();/计算当前节点值 ; void ArgNode:compute() csum = 0; for (int i = 1; i x; +i) csum += Piwi * Qwii; int Athletes() /初始化 priority_queue Heap; int *iniArr = new intn + 1; int i= 0; for (i = 0; i = n; +i) iniArri = i; ArgNode *initial = new ArgNode(iniArr,0,0); delete iniArr; Heap.push(*initial); while(!Heap.empty() ArgNode fatherNode = Heap.top(); Heap.pop(); if (fatherNode.x = n)/是一个全排列，则比较节点内值是否比当前最优值更佳 if (best fatherNode.csum) best = fatherNode.csum; else for (i = fatherNode.x + 1; i = n; +i)/广度优先所搜子树 ArgNode newNode(fatherNode);/把子节点内容先复制为父节点内容 +newNode.x;/深度+ newNode.wnewNode.x = fatherNode.wi;/选择第i个女选手 newNode.wi = fatherNode.wnewNode.x; newNpute();/子节点计算val Heap.push(newNode); return best; int main() ifstream infile(input3.txt); ofstream outfile(output3.txt); cout分支限界法求解运动员最佳配对 endl; coutinput.txt n; int i,j; P = new int *n + 1; Q = new int *n + 1; for (i = 0; i = n; +i) Pi = new intn + 1; Qi = new intn + 1; for (i = 1; i= n; +i) for (j = 1; j Pij; fo