Help!Help!图论：最短路径?
若干点，求一条路径，每个点必须经过，且经过一次，任意点为开始，任意点为结束。
谁有算法？急！
shenxjun@163.net
问题点数：50、回复次数：73Top
1 楼starfish（海星）回复于 2002-03-27 22:07:12 得分 0
这是哈密尔顿路径问题呀,NPC的
没有多项式时间的解法：（
只有搜索了～Top
2 楼szlbyou（无里头）回复于 2002-03-28 11:10:45 得分 1
一个非常笨的办法，效率低：（见笑了）
假设有：1~N 个点，那么可用d[N][N]来保存任两点间的距离；
采用栈来保存路径；
如果从第starti点开始，到第endi点；
那么starti点的下一个点：
不在栈中且未曾被搜索过的最近点，如此下去最终可找到一路径，
但不一定是最短的，因此须退栈回朔，在回朔中寻找下一个点时，
同样必须满足：不在栈中且未曾被搜索过的最近点，最后可找到
所有的路径。
然后再逐一比较各路径大小即可。
Top
3 楼guojun007（guojun）回复于 2002-03-29 17:35:43 得分 0
upTop
4 楼cchmx（沧海一熊）回复于 2002-03-29 17:55:34 得分 0
用人工智能中的A*算法呀。
不过，不能保证一定有解哟。（本来这个问题就不一定有解嘛）
嘿嘿Top
5 楼guojun007（guojun）回复于 2002-04-01 21:12:10 得分 0
upTop
6 楼guojun007（guojun）回复于 2002-04-01 21:14:15 得分 0
难道没有人学图论吗？这是图论中一个很基本的问题嘛！
我只是有些细节没有清楚。Top
7 楼colacoca（我是一瓶倒过来的可口可乐）回复于 2002-04-02 09:10:33 得分 0
基本同意 szlbyou(无里头)
他的思路是正确的阿
Top
8 楼starfish（海星）回复于 2002-04-02 14:50:28 得分 0
这个问题没有高效的算法，只能剪枝搜索Top
9 楼guojun007（guojun）回复于 2002-04-02 15:44:51 得分 0
to starfish(海星)
什么是剪枝搜索Top
10 楼winfit（最后一口可乐）回复于 2002-04-03 10:15:02 得分 10
#ifndef _H_SHORTPATH
#define _H_SHORTPATH
class ShortPath {
enum { size = 20 };
bool m_bDirect; //whether has direction
int path[size]; //save the shorest path
int graph[size][size];
int m_nMaxVex;
int m_nMinPath;
public:
ShortPath(bool direct = 0) : m_bDirect(direct), m_nMaxVex(0), m_nMinPath(INT_MAX) {
memset(path, 0, size);
for(int i=0; i<size; i++)
memset(graph[i], 0, size);
}
~ShortPath() {}
bool Read();
void Find(int pos);
};
bool ShortPath::Read()
{
FILE *fd;
if((fd = fopen("text.txt", "r")) == NULL) {
cout << "open file error";
return false;
}
fscanf(fd, "%d\n", &m_nMaxVex);
int nline, row, col;
fscanf(fd, "%d\n", &nline);
for(int i=0; i<nline; i++) {
fscanf(fd, "%d%d", &row, &col);
fscanf(fd, "%d\n", &graph[row-1][col-1]);
if(m_bDirect)
graph[col-1][row-1] = graph[row-1][col-1];
}
return m_nMaxVex==0 ? false:true;
}
void ShortPath::Find(int pos)
{
int total;
bool bflag;
for(int i=0; i<m_nMaxVex; i++)
{
if(pos != 0 && graph[path[pos-1]][i] == 0)
continue;
bflag = false;
for(int j=0; j<pos; j++)
if(path[j] == i) {
bflag = true;
break;
}
if(bflag) continue;
path[pos] = i;
if(pos < m_nMaxVex-1)
Find(pos+1);
if(pos == m_nMaxVex-1) {
total = 0;
for(int t=0; t<m_nMaxVex-1; t++)
total += graph[path[t]][path[t+1]];
if(total < m_nMinPath)
m_nMinPath = total;
}
}
}
#endif _H_SHORTPATHTop
11 楼winfit（最后一口可乐）回复于 2002-04-03 10:18:58 得分 0
///////////////////////////////text.txt
5 //5个节点
4 //4行
1 5 10 //输入1节点到5节点距离10
2 4 56
5 3 12
3 2 16
//////////////////////////////
调用
ShortPath sp;
if(sp.Read())
sp.Find(0);
Top
12 楼garth008（菜鸟）回复于 2002-04-03 21:30:48 得分 0
很典型的问题马!一般称为担货郎问题,或旅行家问题
很多书上都有介绍
可以用遗传算法,启发式算法等等实现Top
13 楼lingjingqiu（空明流转）回复于 2002-04-06 09:57:17 得分 0
首先，得根据所给数据判断是否有解（根据欧拉定理），在通过对邻接表的遍历及
回朔来实现。Top
14 楼sdp（雨尘）回复于 2002-04-06 16:14:11 得分 0
可以用Dijkstra算法吧？最短路径一般用这种算法！Top
15 楼LeeMaRS（小菜虎，仍需努力）回复于 2002-04-06 16:51:26 得分 0
看起来有点像一笔画??Top
16 楼guojun007（guojun）回复于 2002-04-16 10:31:13 得分 0
谢谢各位的关心，我2.26出差广州刚回武汉，才看到，不能及时和大家交流，很抱歉。
请问garth008(菜鸟) 告诉我，什么是遗传算法,启发式算法？
请问lingjingqiu(天使) 什么是对邻接表的遍历及
回朔？
s请问dp(sdp) 什么是Dijkstra算法?
关键是在什么书上可以看到。
再次谢谢大家的关注！Top
17 楼JedyChen（Jedy.Chen）回复于 2002-04-16 16:37:10 得分 0
最短路径在数据结构的书里有Top
18 楼LeeMaRS（小菜虎，仍需努力）回复于 2002-04-16 23:23:50 得分 0
这个不是最短路径的问题呀.
是一笔画的问题.
同意天使的说法,先判断有没有解.按分情况选初始点进行搜索.Top
19 楼guojun007（guojun）回复于 2002-04-17 17:20:59 得分 0
1.先判断有没有解.
肯定有解.
因为：每个点之间都是双向连通的。
最短路径在数据结构的书里有
书里只有，给定点到给定点的最短路径,其它的点是否完全通过，它是忽略的。
所以这个问题是一笔画+最短路径
Top
20 楼Lawrence444（胖子）回复于 2002-04-17 19:04:27 得分 30
这是欧拉道路啊，很多算法书上都有的。Top
21 楼Lawrence444（胖子）回复于 2002-04-17 19:08:06 得分 0
对不起，看错了，确实是Hamilton道路。
用ANN，GA或贪心，Graham凸包都可以求解
要是求最短的话，就只有用剪枝搜索了Top
22 楼guojun007（guojun）回复于 2002-04-18 14:23:31 得分 0
工程实例：
平面上25x16个格子里放400个瓶子，任意取30个瓶子，可以从任何一个瓶子开始，可以从任何一个瓶子结束，从一个瓶子到另一个瓶子任意走直线。求路径。
显然：肯定是有解。
因为依任意次序走，都是一条路径。
总共有30x29x....x2x1种可能路径。
把所有的路径走到求最短即可。
这也可以算一种算法把。
Lawrence444(胖子) ANN，GA或贪心，Graham凸包都是什么东东？
Top
23 楼guojun007（guojun）回复于 2002-04-19 16:28:21 得分 0
up
Top
24 楼Lawrence444（胖子）回复于 2002-04-19 22:04:43 得分 0
如果你是要求最短路径的话，上面那些办法就都没有用了，那些都是求近似最短路径的方法。
只能用限界剪枝搜，去借/买一本算法分析看看吧。Top
25 楼guojun007（guojun）回复于 2002-04-22 09:37:37 得分 0
Lawrence444(胖子)：你好，我看见的都是数据结构的书，没有看见算法分析的书，你有电子版的吗？Top
26 楼Lawrence444（胖子）回复于 2002-04-22 10:52:05 得分 0
没，你可以去看看有没有这本
《算法与数据结构》，电子工业出版社
这本里面就讲了LCBBTop
27 楼guojun007（guojun）回复于 2002-04-22 11:15:32 得分 0
谢谢Lawrence444(胖子)Top
28 楼limdaidai（阿呆(看不清楚路的猪)）回复于 2002-04-22 17:11:43 得分 0
关注，曾在斑竹帮助下做过，但水平有限，没有做出来！好象点太多（>20)就没法算出来！复杂度是指数级！另请楼主，要是搞定了，能不能请教一下！Top
29 楼wtzyb4446（不死鸟）回复于 2002-04-23 00:22:59 得分 0
图的深度搜索。看看数据结构的书，上面都有Top
30 楼guojun007（guojun）回复于 2002-04-26 11:17:10 得分 0
教科书上的：
1：求点到点的最短路径。图中有若干点，点与点之间有连通，但其中的某个点到其他各个点之间并不一定都是连通的，所以点到点之间是不是有一条通过去的路径，是需要搜索，才知道，这个在教科书中已经有算法了。而且这个题目求的是点到点的路径，没有要求这个路径走过每一个点，所以这个算法不适用于我的题目。
2：求最小树。树连接了每一个点，但是求出来的是树，不是路径，也就是说，树有根结点，然后有可能有分叉，但是对某一些图来讲，有可能求出来的最小树就是最短的连通所有点的路径,这个最小树在教科书中已经有算法了。
3：我按照求最小树的算法来求最短路径，先给出最小树的教科书上的算法如下：
a)找出最短的一条点与点之间的直接的路径。加入到树中来。
b)找出次短的路径。
c)看这个路径是否在树中构成回路，如果不构成，将这个路径加入到树中。如果构成回路，则放弃这个路径，在回到b)找下一条路经。
d)直到所有的点都已经加入到这个树中来。
e)或者所有的路径都已经找完，如果没有加入所有的点，则这个最小树是不存在的。
4：我的最短路径的算法如下：
a)找出最短的一条点与点之间的直接的路径。加入到目标路径中来。
b)找出次短的路径。
c)看这个路径是否在目标路径中构成回路，如果不构成，将这个路径加入到目标路径中。如果构成回路，则放弃这个路径，在回到b)找下一条路经。
d)直到所有的点都已经加入到这个目标路径中来。
e)或者所有的路径都已经找完，如果没有加入所有的点，则这个最短的目标路径是不存在的。
5：问题是：我不能从理论上证明我的算法是正确的。谁能告诉我呢？Top
31 楼Lawrence444（胖子）回复于 2002-04-26 21:48:50 得分 0
??我看你的算法就是找了个最小生成树嘛。
如果你看的是我告诉你的那本书，请看第六章。最后一节详细的介绍了用限界剪枝法搜索旅行商问题（就是Hamilton回路）的方法。Top
32 楼guojun007（guojun）回复于 2002-04-27 10:16:28 得分 0
Lawrence444(胖子) ( ) 很高兴你能继续关注我的问题，
我的算法在步骤c的判断时是不允许路径分叉的，而最小生成树是可以分叉的。
by the way,《算法与数据结构》，电子工业出版社，正在寻找中...Top
33 楼Lawrence444（胖子）回复于 2002-04-28 21:08:28 得分 0
如果我理解的对的话，你的算法就是上面说的“贪心”，可以生成一个近似最短Hamilton回路。Top
34 楼limdaidai（阿呆(看不清楚路的猪)）回复于 2002-05-14 17:14:18 得分 0
关注中！Top
35 楼quickmouse（快鼠）回复于 2002-05-27 15:02:52 得分 0
这是很经典的问题，在这里贴出来不合适吧！Top
36 楼guojun007（guojun）回复于 2002-05-28 15:15:40 得分 0
可是我还没有找到答案。Top
37 楼mrunix（深水蔚蓝...）回复于 2002-05-29 12:59:43 得分 0
用分支定界算法，或者说策略是最好的！Top
38 楼guojun007（guojun）回复于 2002-05-29 14:12:44 得分 0
,《算法与数据结构》，电子工业出版社
我还没有找道，谁能帮我！Top
39 楼Lawrence444（胖子）回复于 2002-05-29 16:43:58 得分 0
你在什么地方啊？Top
40 楼NewStarSE（看见就跑）回复于 2002-05-29 17:52:53 得分 0
各位不必找了，这个题目目前还没有多项式时间内的精确解法，（估计以后也不会有），只有一些近似算法，比较经典的有：启发式算法、模拟退火式算法、改进遗传算法等。数据量少的话（<15)可以用穷举搜索，另外贪心法也可以勉强凑数。你可到普林斯顿大学的TSP专题网站上找相关算法和数据。
注：Dijkstra算法是求一点到其余各点的最短距离，跟这个无关。这也不是一笔画问题，一笔画属于E图，这是H图。Top
41 楼guojun007（guojun）回复于 2002-05-30 10:26:43 得分 0
谢谢，Lawrence444(胖子)，newstarse(新星) ，一直的关心， 我在武汉。Top
42 楼xiaoluoli（C/C++思考）回复于 2002-05-30 13:57:27 得分 0
看看数据结构图那章吧!可能有答案,你当热、Top
43 楼guojun007（guojun）回复于 2002-05-31 08:36:11 得分 0
谢谢，xiaoluoli(小理) ，是什么书啊？Top
44 楼wulj99（helloworld）回复于 2002-06-01 10:34:09 得分 0
我想应该用A*算法,不过效率不高Top
45 楼imagex（<<<<<<★>>>>>>）回复于 2002-06-01 15:50:52 得分 0
如果有五个节点:12345.
1.编写一个函数:int count(char *s)s表示字符串"12345","23145"...
这个函数可以计算出不同节点顺序下路径长度.
2.改变12345的顺序.
Top
46 楼imagex（<<<<<<★>>>>>>）回复于 2002-06-01 15:54:11 得分 0
上面的太烦,你也可以用邻接矩阵.这样比较简单,不过说起来比较烦,所以不说了.Top
47 楼guojun007（guojun）回复于 2002-06-02 13:06:30 得分 0
imagex(明月双)
谢谢，Top
48 楼cxjddd（又是花开时）回复于 2002-06-02 14:23:03 得分 0
我不不明白。Top
49 楼luguanhui（）回复于 2002-06-03 21:38:10 得分 0
看书吧，自己动脑，那才会记得牢，才会有提高Top
50 楼adua（冒险家）回复于 2002-06-05 21:08:40 得分 0
guojun哥哥，
弟弟不才认为您的最小生成树算法不对，因为最小生成树没法保证每个结点只经过一次；而且，最短路径也不恰当。
有不少中国的、外国的大叔、大伯正在研究，如果构成回路的话称之为《中国货郎担问题》（国产货）。
2000年之前一直没有找到多项式级的精确算法。但是有一些很好的多项式级近似算法（如Hopfield神经网络算法），和指数阶的精确算法（几何分块）。
2000年一位姓周的伯伯，提出了《中国货郎担问题》的多项式阶算法。不过实现起来挺麻烦。
弟弟提醒guojun哥哥，如果这些点构成一个凸多边形，就可以用动态规划解决（很好实现呦~~)。
小弟太懒‘敲’的不全，包涵:)
我的邮箱是：adua1983@sohu.com ,请哥哥们指教。
3ks
Top
51 楼adua（冒险家）回复于 2002-06-05 21:09:59 得分 0
不对不对，邮箱是：adua1983@yahoo.com (粗心！！！！哎！）Top
52 楼guojun007（guojun）回复于 2002-06-06 14:15:49 得分 0
adua(冒险家) :谢谢你，你说的很对，最小生成树算法是不对，我也是想问一下。
另外，你说的那些人和算法，他们的资料在哪里？Top
53 楼Lawrence444（胖子）回复于 2002-06-06 19:21:21 得分 0
周的算法也是一个近似算法
他要求精确算法，只能限界剪枝Top
54 楼Lawrence444（胖子）回复于 2002-06-06 19:24:28 得分 0
我觉得武汉也算是大城市啊，不可能买不到一本算法分析的书的！
你仔细找找，也许没有我说的那本，但是只要名字有“算法”的书就拿起来看看，有没有介绍“限界剪枝”的章节，如果有，应该会介绍的。Top
55 楼guojun007（guojun）回复于 2002-06-06 21:47:07 得分 0
谢谢Lawrence444(胖子) ，Top
56 楼zhoukun666（我喜欢==〉{ 。}{ 。}）回复于 2002-06-11 18:21:24 得分 0
就是最短路径问题：
程序构思：
首先，你应该把图形建立成加权图性的邻接数组，在申明一个一维数组来纪录已经查找的的数组(Visited)和一个一维数组来用来纪录顶点间距离综合的变化(Distant)
取原来的距离总和于新加入顶点后的距离总和的最小值作为新的距离的总和，
Top
57 楼QXLEE（Jh）回复于 2002-06-13 14:17:12 得分 0
nodTop
58 楼aibren（aibren）回复于 2002-06-14 19:30:52 得分 0
同意 NewStarSE(新星) 。
但是这是个很典型的货郎担问题，有很多种解法。但是就像货郎担问题要求的那样，你这个问题首先要有一条汉密尔顿路，然后再优化。至于优化的方法就非常多了，很多关于这方面的书里都有。Top
59 楼guojun007（guojun）回复于 2002-06-17 08:48:41 得分 0
同志们！
汉密尔顿路，它的每个顶点，不是都互相连接的！所以，它才可能是，不存在这样的一条路经。最典型的例子：一个n方体，顶点只有相邻的点才连接，而，我这里每个顶点，都是可以互相直接连接的。请千万注意这点！
了不起，我就是做个排列组合，最多30个点，30!
可这样的话，要什么算法呢？Top
60 楼xiaoluoli（C/C++思考）回复于 2002-06-17 14:30:10 得分 0
<<数据结构>>-------->清华大学出版社,Top
61 楼molester（）回复于 2002-06-17 14:48:34 得分 0
这个绝对是汉密尔顿回路问题，现在还没有好的方法判断那些图是汉密尔顿图，只能 判定某些图不是汉密尔顿图Top
62 楼mountainfrank（wood）回复于 2002-06-17 14:57:07 得分 0
这是一个简单的遍历问题，而不是最短路径问题，任意一本算法书上都有Top
63 楼molester（）回复于 2002-06-17 15:04:51 得分 0
经过且只经过一次，就不是简单的遍历问题了，这确实是汉密尔顿问题，边经过且只经过一次的是欧拉路，而点的就是汉密尔顿路，给定一个图，是不能保证一定能找到汉密尔顿路的。Top
64 楼guojun007（guojun）回复于 2002-06-17 20:53:10 得分 0
同志们：
典型的汉密尔顿问题：n方体的顶点，及边。边经过且只经过一次的是欧拉路，而点的就是汉密尔顿路，给定一个图，是不能保证一定能找到汉密尔顿路的。
我的条件：平面上的点，每个点，都互相联接的。
最笨的办法：n个点，n!排列组合，这是毫无疑问的！Top
65 楼guojun007（guojun）回复于 2002-06-19 21:02:15 得分 0
n方体的顶点,只是相邻的点，才连接。所以，可能，没有这样的一笔画的路径，要找。这个才是汉密尔顿路的，问题。
而，我这里，不是这个问题，路径存在，n个点，n!排列组合个路径。Top
66 楼laughcry2002（LaughCry）回复于 2002-06-20 10:37:24 得分 9
我觉得首先必须确定问题的性质,以下是我从MIT的一本教材上摘录下来的:
Hamiltonian Cycle Problem
-------------------------
The problem of finding a hamiltonian cycle in an undirected graph has been studied for over a hundred years. Formally, a HAMILTONIAN CYCLE of an undirected graph G=(V, E) is a simple cycle that contains each vertex in V. A graph taht contains a hamiltonian cycle is said to be HAMILTONIAN; otherwise, it is NONHAMILTONIAN.
Traveling-Salesman Problem
--------------------------
In the traveling-salesman problem(TSP), hich is closely related to the hamiltonian-cycle problem, a salesman must visit n cities. Modeling the problem as a complete graph with n vertices, we can say that the salesman wishes to make a tour, or hamiltonian cycle, visiting each city exactly once and finishing at the city he starts from. There is a cost c(i, j) to travel from city i to city j, and the salesman wishes to make the tour whose total cost in minimus, where the total cost is the sum of the individual costs along the edges of the tour.
Theorem
-------
1. The hamiltonian cycle problem is NP-complete(NPC).
2. The traveling-salesman problem is NPC.
至于最短路径问题则不要求回路，欧拉回路则不考虑代价（费用）因素。
结论：
所提的问题是TSP（旅行商问题、货郎担问题等等），而且此问题是NP完全的（即至今尚没找到多项式时间复杂度的解法）。
所以我比较同意 NewStarSE(新星) 的看法：“这个题目目前还没有多项式时间内的精确解法，……，只有一些近似算法，比较经典的有：启发式算法、模拟退火式算法、改进遗传算法等。数据量少的话（<15)可以用穷举搜索，另外贪心法也可以勉强凑数。”
除了NewStarSE(新星)提到的几种近似算法外，还有用人工智能方法求解的。
我有一些用模拟退火和遗传算法写出的TSP程序，若需要的话可联系:
LaughCry2002@yahoo.com.cnTop
67 楼clamp_chen（燕归来）回复于 2002-06-20 12:23:06 得分 0
ft，这个问题根本不是旅行家问题。大家不要走错了方向，嘿嘿。
这道题目不是很难
参见：guojun007
工程实例：
平面上25x16个格子里放400个瓶子，任意取30个瓶子，可以从任何一个瓶子开始，可以从任何一个瓶子结束，从一个瓶子到另一个瓶子任意走直线。求路径。
显然：肯定是有解。
因为依任意次序走，都是一条路径。
总共有30x29x....x2x1种可能路径。
把所有的路径走到求最短即可。
这也可以算一种算法把。
Top
68 楼guojun007（guojun）回复于 2002-06-23 14:43:28 得分 0
upTop
69 楼countryroad（宁静致远）回复于 2002-06-25 14:42:12 得分 0
关注
up!Top
70 楼guojun0718（guojun）回复于 2002-06-25 15:34:25 得分 0
upTop
71 楼guojun0718（guojun）回复于 2002-06-25 15:39:48 得分 0
upTop
72 楼guojun0718（guojun）回复于 2002-06-25 15:45:03 得分 0
up!Top
73 楼Lawrence444（胖子）回复于 2002-06-25 17:31:25 得分 0
干吗还要up阿，真的要我们把两节的课文敲进去阿
Top
74 楼Lawrence444（胖子）回复于 2002-06-25 17:37:50 得分 0
好了，借花献佛，去这个网址看看
http://61.136.0.239/oibh/newcomer/ebook.html
然后去想办法弄个超星的破解，然后去下载那里介绍的书
超星的破解在www.crackbest.com，搜“超星”Top
75 楼zhoukun666（我喜欢==〉{ 。}{ 。}）回复于 2002-06-26 10:19:56 得分 0
谁有源代码？--三百分购买！！！！Top
76 楼zhoukun666（我喜欢==〉{ 。}{ 。}）回复于 2002-06-26 10:21:33 得分 0
谁有完整的源代码？--三百分购买！！！！------zhoukun6666@hotmail.com
谢谢·！Top
