本文目录一览：
- 1、求大神改一下这个代码 回溯法的任务分配问题 用C语言
- 2、用动态规划做旅行商问题 用C语言 各位大虾帮帮忙啊
- 3、已知12个地点间的距离，每个地点都要去一次，最后回到起点。求最短距离。TSP旅行商问题。
- 4、什么是商旅问题啊？用c语言设计，是关于图的程序。最好能给出代码
- 5、可运行的c语言程序：旅行商求最短路径问题
- 6、求大神给这个程序做个详细的注释 C语言 回溯法 任务分配问题
求大神改一下这个代码 回溯法的任务分配问题 用C语言
#include stdio.h
#include string.h
int n, a[21][21], sum, best, b[21], c[21], d[21];
void f(int m) {
int i,j;
if(mn) {
if(best==-1||sumbest)
best=sum;
memcpy(d,c,sizeof(d));
return;
}
for(j=1;j=n;j++) {
if(!b[j]) {
sum+=a[m][j]; b[j]=1;
c[m] = j;
if(sumbest||best==-1)
f(m+1);
sum-=a[m][j]; b[j]=0;
}
}
}
int main() {
int i,j;
printf("请输入作业数：");
scanf("%d",n);
printf("作业分配给不同工人所需费用: ");
for(i=1;i=n;i++)
for(j=1;j=n;j++)
scanf("%d",a[i][j]);
sum=0;
best=-1;
f(1);
printf("最小总费用为：%d\n", best);
printf("作业");
for(i=1;i=n;i++) {
printf("%3d", i);
}
printf("分别分给第");
for(i=1;i=n;i++) {
printf("%3d", d[i]);
}
puts("个工人！作业分配完毕！");
return 0;
}
用动态规划做旅行商问题 用C语言 各位大虾帮帮忙啊
#include list
#include iostream
using namespace std ;
typedef listint LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}};
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
// cout"-------------------"n"-start-------"endl;
LISTINT::iterator i;
int minValue;
if(n==1){
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1){
list_result=list_org;
}
//cout"---"*i"-""1""="minValueendl;
}
else{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1){
list_result=list_org;
}
/*
cout"----"temp"--"*(i)"="minValue"--链表里还剩有如下元素";
for (i = list_org.begin(); i != list_org.end(); ++i)
cout *i " ";
cout endl;
*/
for(int j=2;jn;j++)
{
i=list_org.begin();
for(int k=1;kj;k++){
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
/*
cout"----""---"temp"--"*(i)"="tempvalue"--所有的";
for (i = list_org.begin(); i != list_org.end(); ++i)
cout *i " ";
cout endl;
*/
if(tempvalueminValue){
if(list_org.size()==matrix_length-1){
list_result=list_org;
}
minValue=tempvalue;
}
}
}
//cout"-------------------"n"---end-----"endl;
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout"旅行商问题的动态规划算法"endl;
cout"路线长度的矩阵表示如下,-1表示无限大"endl;
for(int j=0;jmatrix_length;j++){
coutendl;
for(int k=0;kmatrix_length;k++){
cout" "d[j][k];
}
}
coutendl;
cout"计算结果:"getPath(4,list_org)endl;
list_result.push_front(1);
list_result.push_back(1);
cout"走的路径:----:";
for (h = list_result.begin(); h != list_result.end(); ++h)
cout *h " ";
cout endl;
int i;
cini;
return 0;
}
已知12个地点间的距离，每个地点都要去一次，最后回到起点。求最短距离。TSP旅行商问题。
这个是NP完全问题，只能求近似解,目前没有简单又高效的方法，最简单的就是穷举算法和最邻近算法了,其它的可以考虑插入算法，回溯法，遗传算法，蚁群算法，模拟退火算法等。。。
什么是商旅问题啊？用c语言设计，是关于图的程序。最好能给出代码
旅行商问题（Traveling Saleman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。
解决TSP问题的思想有回溯法、贪心法、动态规划法等。
如果动态规划法解决TSP问题，可以参考程序代码：
#include list
#include iostream
using namespace std ;
typedef listint LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}};
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
LISTINT::iterator i;
int minValue;
if(n==1)
{
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
}
else
{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
for(int j=2;jn;j++)
{
i=list_org.begin();
for(int k=1;kj;k++)
{
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(tempvalueminValue)
{
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
minValue=tempvalue;
}
}
}
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout"旅行商问题动态规划算法"endl;
cout"路线长度的矩阵表示如下 （-1表示无限大）"endl;
for(int j=0;jmatrix_length;j++){
coutendl;
for(int k=0;kmatrix_length;k++){
cout" "d[j][k];
}
}
coutendl;
cout"计算结果:"getPath(4,list_org)endl;
list_result.push_front(1);
list_result.push_back(1);
cout"要走的路径:----:";
for (h = list_result.begin(); h != list_result.end(); ++h)
cout *h " ";
cout endl;
int i;
cini;
return 0;
}
可运行的c语言程序：旅行商求最短路径问题
在无向完全图中，对于任意两个顶点vi和vj，我们可以在多项式时间内找到vi和vj这两个顶点之间的所有路径，选择其中路程最短的一条，令S[i,j]表示vi和vj这两个顶点之间最短距离的那条路径。搜索路径S[i,j]，找到vi到达的在S[i,j]上的第一个顶点，记该顶点为vk，将其记录在数组中R[][]，递归查找vi到vk和vk到vj的最短路径及其相应权值，最后将数组D[]中的顶点和权值之和打印出来即为所求，并用画图函数将行经过程画出。
求大神给这个程序做个详细的注释 C语言 回溯法 任务分配问题
这个题目分解一下，就是将n个数据排列组合，数学算法可以得到种数为A(n,n)=n!
然后在这n!种可能种找到花费最少的那一种就行了。
以下是我写的程序，验证了一下，好像没有什么问题，你看看。
#include stdio.h
int best,last;
int b[20],c[20],d[20],a[20][20];
void get_best(int n)
{
int j,k;
last = 0;
for(j=0;jn;j++)
last += a[j][c[j]];
if(best == 0)
{
best = last;
for(k=0; kn; k++)
d[k] = c[k];
}
else
{
if(last best)
{
best = last;
for(k=0; kn; k++)
d[k] = c[k];
}
}
}
void f(int n,int count)
{
int i,t,j;
if(n == 1)
{
c[count] = b[0];
get_best(count+1);
}
else
{
for(i=0; in; i++)
{
t = b[i];
b[i] = b[n-1];
b[n-1] = t;
c[count] = t;
f(n-1,count+1);
t = b[i];
b[i] = b[n-1];
b[n-1] = t;
}
}
}
int main()
{
int i,j;
int n;
printf("请输入作业数：");
scanf("%d",n);
printf("作业分配给不同工人所需费用:\n");
for(i=0;in;i++)
{
b[i] = i;
c[i] = -1;
d[i] = -1;
for(j=0;jn;j++)
scanf("%d",a[i][j]);
}
best = last = 0;
f(n,0);
printf("最小总费用为：%d\n", best);
for(i=0;in;i++)
{
printf("第%d人分：",i+1);
printf("第%d工作. ", d[i]+1);
printf("金钱为：%d\n",a[i][d[i]]);
}
puts("\n");
return 0;
}
