博士家园

查看: 463|回复: 1

[其它题目] 请教一个和图论有关的游戏问题

[复制链接]
发表于 2021-2-1 23:28:00 | 显示全部楼层 |阅读模式
10金币
我在玩一款叫做QuickRoute的手机游戏时突发奇想,想问下这是不是属于图论的题目
玩法很简答,每一关会生成若干个点(图中的气泡),选择出遍历所有点的最短线段就行了,比如这个显示比最短路径长0.4%,所以错误。
后面关卡越来越复杂,纯粹靠人去试有点困难,这个问题有点类似哈密顿回路,旅行商问题,但是又不太一样,因为只是个点集不是那种图论集合。
想问下这个问题有什么解决的思路吗,是不是已经有人研究过这个问题了

附件: 您需要 登录 才可以下载或查看,没有帐号?邀请
发表于 2021-2-3 22:37:51 | 显示全部楼层
这就是个Hamilton路径问题,因为所有的点之间都可以连,可以看成无向完全图,Hamilton路径肯定存在。

至于求解,虽然没有好的算法,保守一点可以穷举,也就$n!$的复杂度。

关于我们|手机版|博士家园 ( 沪ICP备15045866号-1 )(沪公网安备沪公网安备 31011702001868号) 

GMT+8, 2021-4-17 23:40 , Processed in 1.218750 second(s), 16 queries , Gzip On.

Powered by Discuz! X3.2

© 2004-2021 Comsenz Inc.

快速回复 返回顶部 返回列表