应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 应用数学与力学 » 【求助】一个经典的数模问题求解！！！！急
51/1返回列表
查看: 1657  |  回复: 7
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

风之子8319

银虫 (小有名气)

[交流] 【求助】一个经典的数模问题求解！！！！急 已有4人参与

下面的是一个数模竞赛的完整题目：
***************************************************************

南京王先生想到各地旅游。计划走遍中国大陆的省会城市、直辖市。请你为他按下面要求制定出行方案：
1．按地理位置（经纬度）设计最短路旅行方案。
2．如果2010年6月1日王先生从南京市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案。
3．        要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案。
4．对你的算法作复杂性、可行性及误差分析。
5．关于旅行商问题提出对你自己所采用的算法的理解及评价。

*************************************************************
各位高手帮忙分析一下，有没有好的思路以及算法，或者其他领域的可以用来解决这个方面的知识

有一个思路是利用任意两点之间的最短路线作为该两点的权构造一个完全图，然后再找最小的哈密顿圈，。。。。。关键的地方就是画出了图之后用什么样的算法来解决的问题。。。。。主要还是算法啊

由于时间紧急，还望大家多帮帮忙啊
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
书山有路勤为径
1楼 2010-05-15 23:17:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

风之子8319

银虫 (小有名气)
引用回帖:
Originally posted by 再见北极雪 at 2010-05-16 13:21:39:
这个问题确实很经典！1996年左右的全国数学建模题可能就是这个类型的。这是一种最优遍历问题，也成为旅行商问题。数据结构和图论现在都一把这个问题当做例题来讨论。实际上如二楼所言，现在的算法几乎都是近似算法 ...

98年的国赛。。。。我知道，一般的算法是不行。。。。看来只能是近似的。。。。想算法创新是不行了的。。。。遍历算法是个什么。。。能不能详细说一下
赞一下 回复此楼
书山有路勤为径
7楼2010-05-16 14:21:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 8 个回答

dye

木虫 (小有名气)
★ ★
javeey(金币+2):谢谢解答，一语中的 2010-05-15 23:58:46
风之子8319(金币+3): 2010-05-16 13:04:22
1. TSP（Traveling Salesman Problem）---也就是旅行商问题---是一个NP-hard问题。精确算法的复杂性为O(n!)。城市个数目大与20就很难实现。

2. 所以必须用近似算法。下面连接是关于TSP问题的一些近似算法，可以参考。

http://math.wvu.edu/~dye/TSP.pdf
赞一下(1人) 回复此楼
2楼2010-05-15 23:56:49
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

luomingqi

木虫 (正式写手)
风之子8319(金币+1): 2010-05-16 13:07:01
风之子8319(金币+6): 2010-05-18 22:14:39
图论之中就有这个算法的啊。或者使用运筹学的方法也可以求解的啊
赞一下 回复此楼
跟踪
3楼2010-05-16 08:29:31
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

风之子8319

银虫 (小有名气)
引用回帖:
Originally posted by dye at 2010-05-15 23:56:49:
1. TSP（Traveling Salesman Problem）---也就是旅行商问题---是一个NP-hard问题。精确算法的复杂性为O(n!)。城市个数目大与20就很难实现。

2. 所以必须用近似算法。下面连接是关于TSP问题的一些近似算法，可以 ...

这个我知道，用TSP，就是类似的。。。。关键是那个文献是英文的。。。。
赞一下 回复此楼
书山有路勤为径
4楼2010-05-16 13:05:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 8 个回答
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[硕博家园] 极限拉扯，如何抉择 +10 Isak0320 2026-10-12 14/700 2026-10-14 11:39 by thegarfield
[基金申请] 申请科研项目纯靠实力能成功吗？ 200+3 David1982 2026-10-13 6/300 2026-10-14 11:14 by 北京莱茵编辑
[教师之家] 课题组会帮你通过考核么？ +4 好运来～9527 2026-10-10 7/350 2026-10-13 08:41 by xli1984
[基金申请] 入职后第一次管课题组的专利缴费，对账才发现官费比别人多掏了一倍 +6 13108017953 2026-10-08 6/300 2026-10-12 20:07 by w3w3y3
[公派出国] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 9/450 2026-10-11 22:34 by XQNyDCa1Tk5n
[公派出国] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 22:26 by XQNyDCa1Tk5n
[找工作] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 22:26 by XQNyDCa1Tk5n
[考博] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 9/450 2026-10-11 22:15 by XQNyDCa1Tk5n
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 22:11 by XQNyDCa1Tk5n
[教师之家] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 (EPI+-1)(金币-50) +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 22:06 by XQNyDCa1Tk5n
[教师之家] 售SCI一区T0P文章，我:8.O.55.1.O.5.4,科目全,可+急 (EPI+-1)(金币-50) +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 14:25 by VOMexwnDzOFZ
[教师之家] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 (EPI+-1)(金币-50) +4 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 14:05 by VOMexwnDzOFZ
[考研] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 13:51 by VOMexwnDzOFZ
[硕博家园] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 13:45 by VOMexwnDzOFZ
[找工作] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +3 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 10:54 by VOMexwnDzOFZ
[找工作] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +4 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 10:34 by VOMexwnDzOFZ
[考博] 招收博士生一名 +3 mandolin 2026-10-10 3/150 2026-10-11 10:21 by 不是山谷！
[公派出国] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +4 qR2AdCWTVtkw 2026-10-09 4/200 2026-10-11 03:14 by M0zrYVSAnxpE
[有机交流] 各位大佬，路线设计求助 +6 zapen 2026-10-08 8/400 2026-10-10 15:59 by zapen
[有机交流] 我应该选哪条合成路线让实验成功率高一些？ +5 jing816y 2026-10-08 9/450 2026-10-10 09:05 by zapen
信息提示
关闭
请填处理意见
关闭