当前位置: 代码迷 >> C语言 >> [悬赏帖]求最佳旅行路线
  详细解决方案

[悬赏帖]求最佳旅行路线

热度:448   发布时间:2004-11-20 15:44:00.0

大致上没看懂kai的思路

typedef vector<City> VCC; //这里不可行,City类没定义,提示错误


----------------解决方案--------------------------------------------------------
kai的想法好,但太复杂,恩……还有就是没有处理哪条路径最长,不过题目好像也有漏洞,就是说,既然两个城市之间可以飞来飞去,就会使程序进入死循环,因为如果有一条路径刚好是在几个城市之间连通了,那可以死循环,要多长路径就有多长,也就是说,这道题其实不完整,我也觉得太难了,难就难在实现路径比较,分支很难处理,如果按照kai的把分支用回推,如果分支太多,就推不了。个人意见,希望高手想个完整一点的方案。
----------------解决方案--------------------------------------------------------
以下是引用knocker在2004-11-20 14:28:29的发言: 给我1000我就告诉你
钱已经给了,快告诉我,最好把正确的代码也给出,“空前”的代码运行通不过!晕~~!!
----------------解决方案--------------------------------------------------------

我把代码修改如下:

#include<iostream.h> #include<stdlib.h>

void main() { int count=0; float temp; cout<<"input value of money:"; cin>>temp; int value=int(temp*100); for(int h=0; h<=value/50; h++) for(int q=0; q<=value/25; q++) for(int d=0; d<=value/10; d++) for(int n=0; n<=value/5; n++) for(int p=0; p<=value; p++) if(p+5*n+10*d+25*q+50*h==value) count++; cout<<"There are "<<count<<" ways to make $"<<temp<<endl; system("pause"); }

臭knocker,要是你能给出更优的算法,我再给1000你!


----------------解决方案--------------------------------------------------------

我在1楼给出了我们作业的全部题,有两类,每一类挑一题做,而第一类就是硬币那题,很快就解决了,第二类挑这题,因为觉得这题已经是最简单的了,不过还是难啊,难在怎样实现判断路径长短,因为但遇到分支,如果要先储存在判断,就要另外开一个储存的链(暂时假设用链储存一条路径),但是如果这样,但下一条不同路径,又要判断刚才那条的城市哪个已经经过,哪个没有经过,然后再来就是对比,设置一个depth变量来比较,最后得出最长路径,还要找出刚才最长的链表,而且如果有N个链表等长,那就更麻烦了!

在字符(地名用字符储存)比较上我也想了N久,到底用char*还是string呢?郁闷了两天才想到,在两个城市的储存上,完全可以用int,就是单个城市名时的数组下标。

我先这样储存单个城市: int N,V; int start=-1; //第一个起点

//下面打开文件,C++方式打开 fstream file1; file1.open("E:\\travel.in"); file1>>N>>V; //取到城市数和通道数 V*=2; //一条通道有两个城市

string *city=new string[N]; //动态申请数组,C++方式 string *route=new string[V]; for(int i=0;i<N;i++) file1>>city[i]; //先把单个城市名储存,string数组

for(int j=0;j<V;j++) { file1>>route[j]; //路径,双数是前一个,单数是后一个 if(j%2==0&&start!=0) //判断如果起点航班存在 start=city[0].compare(route[j]); } file1.close(); //关闭文件,C++方式 if(start!=0) //如果连起点航班都没有就退出,例如Vancouver存在 exit(0);

然后接下来,如果每次都判断string字符串是否一样,就真的很烦,一来代码长,二来cpu也忙,三来我用脑记忆字符也烦,所以干脆把航班表示成数字,例如: 0Vancouver 1Yellowknife 2Edmonton 3Calgary 4Winnipeg 5Toronto 6Montreal 7Halifax 0 2 Vancouver Edmonton 0 3 Vancouver Calgary 3 4 Calgary Winnipeg 4 5 Winnipeg Toronto 5 7 Toronto Halifax 6 7 Montreal Halifax 2 6 Edmonton Montreal 2 1 Edmonton Yellowknife 2 3 Edmonton Calgary

这样一来解决,解决掉比较烦人的问题,就是储存,像kai说的用向量容器储存的确是好,就是用到类和模板,太复杂了,我懒去想,,恩……向量的好处是,当储存越过了数组的边界,系统会自动再加大数组容量,就是说存多少都可以,相对的,删除一个就自动减少容量,很好用,但是在类的嵌套上,用了3个类,我是晕晕,始终觉得太多类只用在工程上,一般算法思维是越简单越好,甚至连函数体也最好用少一点,大致上看得懂kai的第一个类,是要用类链。

kai的思路真的很清晰。不过这句可以不用 typedef vector<City> VCC; 其实写多一点也没关系。 er...写得太抽象,类是很清晰,但实现的时候怎么半?实例化的时候,形成一条链吗?

[此贴子已经被作者于2004-11-20 17:17:16编辑过]


----------------解决方案--------------------------------------------------------

我是想像knocker说的用图来储存,但是又很难,储存是可以,但是遍历的时候就麻烦了。

我再给出用图的邻接矩阵来储存航班之间连通的代码:

//下面动态创建二维数组,C++方式 int **connect=new int*[N]; for(i=0; i<N; i++) connect[i]=new int[N];

//先给全部元素赋0值 for(i=0; i<N; i++) for(j=0;j<N;j++) connect[i][j]=0;

//下面循环是处理当遇到连通的两个地点,就赋1值 for(int k=0; k<V; k+=2) { for(i=0; i<N; i++) if(!(route[k].compare(city[i]))) break; for(j=0; j<N; j++) if(!(route[k+1].compare(city[j]))) break;

connect[i][j]=connect[j][i]=1; }

//先把图输出,看看正确否 for(i=0; i<N; i++) { for(j=0; j<N; j++) cout<<connect[i][j]<<" "; cout<<endl; }

[此贴子已经被作者于2004-11-20 17:48:36编辑过]


----------------解决方案--------------------------------------------------------
下面是图的完整代码,帮忙处理一下

#include<string> #include<iostream> #include<fstream> using namespace std;

void travel(int matrix[][],int visited[],int i,int n);

void main() { int N,V;

//下面打开文件,C++方式打开 fstream file1; file1.open("E:\\travel.txt"); file1>>N>>V; //取到城市数和通道数 V*=2; //一条通道有两个城市

string *city=new string[N]; //动态申请数组,C++方式 string *route=new string[V];

for(int i=0;i<N;i++) file1>>city[i]; //先把单个城市名储存,string数组

int start=-1; //第一个起点 for(int j=0;j<V;j++) { file1>>route[j]; //路径,双数是前一个,单数是后一个 if(j%2==0&&start!=0) //判断如果起点航班存在 start=city[0].compare(route[j]); }

file1.close(); //关闭文件,C++方式 if(start!=0) //如果连起点航班都没有就退出,例如Vancouver存在 exit(0); //下面动态创建二维数组,C++方式 int **connect=new int*[N]; for(i=0; i<N; i++) connect[i]=new int[N];

//先给全部元素赋0值 for(i=0; i<N; i++) for(j=0;j<N;j++) connect[i][j]=0;

//下面循环是处理当遇到连通的两个地点,就赋1值 for(int k=0; k<V; k+=2) { for(i=0; i<N; i++) if(!(route[k].compare(city[i]))) break; for(j=0; j<N; j++) if(!(route[k+1].compare(city[j]))) break;

connect[i][j]=connect[j][i]=1; }

//先把图输出,看看正确否 for(i=0; i<N; i++) { for(j=0; j<N; j++) cout<<connect[i][j]<<" "; cout<<endl; }

int *visited=new int[N]; travel(connect[0],visited,0,N);

//清除刚才申请的内存,包括之前申请的字符串内存,C++方式 for(i=0; i<N; i++) delete[] connect[i]; delete[] connect; delete[] route; delete[] city; }

void travel(int **matrix,int visited[],int i,int n) { cout<<i<<endl; visited[i]=true; for(int j=0; j<n; j++) if(matrix[i][j]!=0&&matrix[i][j]!=(N+1)&&!visited[j]) travel(matrix[],visited,j,n); }


----------------解决方案--------------------------------------------------------

这个问题,去看看最优化的书就应该能够解决的!这个好像是最短路径问题!在matlab中比较容易解决! 有个统一的思路的吧!

[此贴子已经被作者于2004-11-20 19:30:11编辑过]


----------------解决方案--------------------------------------------------------
错了,是最长路径的问题,比最短路径难,没有同意思路,我也有最短路径算法。
----------------解决方案--------------------------------------------------------

呵呵,还用说~~~


----------------解决方案--------------------------------------------------------
  相关解决方案