急救:一个程序(用什么语言都行)

来源:百度知道 编辑:UC知道 时间:2024/05/05 10:28:19
1.1问题描述
设有n个景点,今从某景点出发不重复遍历各景点,使之旅费最少(即找出一条旅费最少的路径)(对于给出的不同的权,可以是里程最短等)。另外,所有的景点之间都是具有双向路径的,但往返费用可以不一样。
1.2设计要求
⑴输入:各景点间的旅费表由输入文件提供。
⑵输出:旅费最少的一条路径及总费用,并显示查找过程。
例如:输入文件名:m.dat
输出文件名:m..out
其中,输入文件m.dat的内容如下:
0 1 2 3 4 5 6
0 0 17 13 9 15 26 12
1 10 0 5 16 11 24 3
2 15 16 0 14 8 11 3
3 17 19 21 0 15 15 6
4 12 13 26 16 0 11 10
5 18 15 16 12 12 0 11
6 9 16 9 15 12 12 0

输出文件m.out的内容如下:
The path is:{最少旅费路径}
Total: {最少旅费数}
从输入文件的数字可以看出n为7
这个问题从本质上来说应该是一个带权的最短路径问题,但它要求的不是一点到另一点的最小值,而是从任一点出发遍历所有景点,而遍历的路径(此题中为费用)是最短(少)的。

n有多大?
这个是np问题吧??
没有多项式算法的,n小时枚举全部情况,n大时可以用遗传算法或者随机调整这些近似算法。。。

你就直接枚举拉。。。
才n!而已。。。