最近遇到的一个题，感觉挺不错的，给大家看看做做

故乡的风 · 发表于 2012-8-10 10:25:26

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

最近一哥们问我的一个问题，我感觉还有点意思，就把题拿出来，大家做做。

场景：某地区有一不法分子犯案后欲逃离此地区，交巡警获悉此事后，决定分派各交巡警平台的人员分别赶往各路口堵截。
已知：此地区有交巡警平台站点M处，路口N处（M〉N），各平台人员赶往各路口的时间已知（自己设置时间，就是一M*N的矩阵），（M，N也自己设置，我遇到的题M=20， N=13，做的时候最好能具有一般性）
要求：每个路口必须有一个平台的人员赶到（当然也只需要一个平台人员赶到即可），求所有满足的情况中，所花时间（所有路口均有人赶到所用的时间）最少为多少，可以把方案给出来。

我是用图来处理这个问题的，代码分享出来。希望大家也能思考下这个问题，把自己的想法说出了，大伙交流下。

source.zip (3.77 KB, 下载次数: 11)

lukelqz · 发表于 2012-8-10 10:50:29

:sleepy:有空看看

cqxcool · 发表于 2012-8-10 19:24:57

第一想法 Dijkstra算法

故乡的风 · 发表于 2012-8-10 21:42:24

cqxcool 发表于 2012-8-10 19:24

登录/注册后可看大图

第一想法 Dijkstra算法

Dijkstra只是找出某点到其他各点的最短距离。但是本题中，并不一定能使得每个路口都可以匹配到最小的距离。我个人觉得，如果是用图来考虑这道题，应该是属于最佳匹配的问题。

woailonglonga · 发表于 2012-8-29 08:49:14

数学建模？？

Cocol · 发表于 2013-7-2 12:09:46

看看老帖，支持下

fishmo · 发表于 2013-7-3 16:37:24

看看，留个脚印

账号		自动登录	找回密码
密码			立即注册

[技术交流] 最近遇到的一个题，感觉挺不错的，给大家看看做做

马上注册，结交更多好友，享用更多功能^_^