BackTrack 源代码

/* 旅行售货员问题 1.算法描述 旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成1，2，。。。，n 的所有排列的递归算法Perm类似。设开始时x=[1,2,...n]，则相应的排列树由x[1:n]的所有 排列构成 如果每个活动接点…

/* 当i

/* 无向图G的最大团和最大独立子集问题都可以用回溯法在O(n2^n)时间内解决。 子集树就有2^n个结点，n是限界函数时间 图G的最大团和对大独立子集问题都可以看作是图G的顶点集v的子集选取问题 因此可以用子集树表示问题的解空间 与解装载问题很相似…

/* 问题描述： 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点 着一种颜色。试问是否有使得G中任何一条边的2个顶点着有不同颜色的着色法。这个问题 就是一个图的m可着色判定问题。若一个图最少需要m种颜色才能使图中任何一条边…

#include using namespace std; /* 解空空间是完全N叉树 x[i]表示第i个皇后放在第i行的第x[i]列 */ class Queen { friend int nQueen(int); private: …

/* 圆排列问题： 1.问题描述 给定n个大小不等的圆c1,c2,...,cn，现在将这n个圆排进一个矩形框中 要求各个圆与矩形框的底边相切。 圆排列问题要求从n个圆的所有排列找出有最小长度的圆排列。 2.算法设计 圆排列的解空间是一棵排列树。按…

#include #include using namespace std; int sum=0; int n,k; int x[8]; char mg[8][8]; bool place(int f) { for(int j=0;j=…

#include #include using namespace std; int sum=0; int n,k; int x[8]; char mg[8][8]; bool place(int f) { for(int j=0;j=…

#include #include double x[10]; double radius[10]; double min; int n; void Swap(double &a,double &b) { double t = …

#include #include int num[13]; int x[13]; int sum,n; int cw; int result[1000][13]; int count; void backtrack(int t) {…