算法设计与分析 实验二 分治法求最近点对

//算法设计与分析 --- 回溯法 /* 回溯法---优化过的蛮力法,具有限界函数的深度优先生成法 使用剪枝函数,删除不可能出现的情况 根据相应约束条件找到问题的可行解||最优解 */ /* 回溯法模板 注意分成横纵两个方面思考回溯 void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { //注意i=0,i=start的区别 处理节点; backtracking(路径，选择列表); // 递归 注意(i)和(i++)的区别 回溯，撤销处理结果 } } */ #include<iostream> #include<algorithm> #include <vector> /* WA NT WA SA NT Q NT SA Q SA Q NSW NSW SA NSW V V SA */ using namespace std; class graph{ private: int **arr; //邻接矩阵存储图表信息 int l; //大小 int kind; //涂料的种类/数量 string *s; //存储各个区域的名称 int n; //存储边的的数量 int sum; //记录走过区域的总次数 vector<vector<int>> solutions; //存储具体的方案 public: graph(){ kind=5; //决定颜色种类的数量为5 l=7; s=new string[l]{"WA","NT","Q","SA","NSW","V","T"}; sum=0; arr=new int*[l]; for(int i=0;i<l;i++) arr[i]=new int[l]; for(int i=0;i<l;i++) for(int j=0;j<l;j++) arr[i][j]=0; n=9; while(n--){ string s1,s2; cin>>s1>>s2; arr[find(s1)][find(s2)]=arr[find(s2)][find(s1)]=1; } } int find(const string& str){ for(int i=0;i<l;i++) if(str==s[i]) return i; return -1; } //普通回溯法解决涂色方案 void start(){ solveGraphColoring(); if (solutions.empty()) cout << "No solutions" << endl; else cout << "Total has " << solutions.size() << " methods" << endl; cout << sum << endl; } bool isValid(vector<int> &colors, int node, int color) { for (int i = 0; i < l; i++) { if (arr[node][i] == 1 && colors[i] == color) { return false; } } return true; } void backtrack( vector<int> &colors, int node, vector<vector<int>> &so) { if (node >= l) { so.push_back(colors); // 找到一个可行解，将其存入解集 return; } for (int color = 1; color <= kind; color++) { // 尝试颜色 if (isValid( colors, node, color)) { colors[node] = color; // 着色 backtrack(colors, node + 1, so); // 递归探索下一个节点 colors[node] = 0; // 撤销着色 sum++; } } } void solveGraphColoring() { vector<int> colors(l, 0); // 存储节点的颜色，初始都为0 backtrack( colors, 0, solutions); } /* 效率提升方案 MRV 优先选择具有可填图颜色较少的变量 DH 选择当前约束最多的变量 */ }; /* int main() { graph a; a.start(); return 0; } */