下面问题的第5个小问如何解决，有什么相关算法吗？


问题描述：
设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。
以(Vi ,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点,d表示这两个景点之间的道路距离；该旅游景点图采用邻接链表存储结构。
实现要求：
⑴ 旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。
⑵ 相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。
⑶ 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。
⑷ 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。
⑸ 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。
⑹ 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。

图论。
1.2.3不论
4.最短路径问题
5.接近最优哈密尔顿回路问题

这些都不是一两句话能说清的。自己找本图论书看看，或上网查图论相关资料。

谢谢，前面的几小题都做出来了，只是第5问想不明白，没思路，做不出来，虽说有点与TSP问题相似，但因点和边都可以重复，因而又有很大区别。

关于第5问我也没有很有效的算法，否则我可以写篇论文震惊世界了。将无向图转换成有向图遍历吧。

，，丫丫的，做不出来老师不让我过，，，

呵呵，你这个问题中的n的上限大概是多少？我估算一下时间。

N没设上限，只要大于10就行了，测试的时候小一点也行，其他问题的代码已经完成。

没设上限？计算量随着规模的增大是呈指数级增长的。

这么说吧，如果结点有50个，以目前的算法即使用天河一号全负荷运算也未必能在1万亿年内得到答案。

收到的鲜花

• bbcnjojo 于 2012-06-27 11:56 送鲜花  3朵  

噢，这样子啊。
我的程序里面上限设的值为20，但我输入数据做测试的时候只用7——8个。
谢谢