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

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

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

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

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


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 static/image/common/back.gif
第一想法       Dijkstra算法

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

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

数学建模？？

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

看看老帖，支持下

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

看看，留个脚印
页: [1]
查看完整版本: 最近遇到的一个题，感觉挺不错的，给大家看看做做