线路的最优化问题 请各位老大给点思路

binxue

5.12汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。通常，每个搜索人员都带有GPS定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数量的卫星电话。GPS可以让搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告搜索情况。 下面是一个简化的搜索问题。有一个平地矩形目标区域，大小为11200米×7200米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米，搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒。每个人带有GPS定位仪、步话机，步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。 现在有如下问题需要解决： 1．假定有一支20人一组的搜索队伍, 拥有1台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成。 2．为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式, 搜索完整个区域的时间是多少?

binxue

请各位老大给点思路 谢谢啊 ······

无心人

应该是一个类似于螺线的线路

binxue

楼上的老哥 可否具体点

无心人

就是围着中心绕圈圈，半径越来越大

mathe

这个题目应该复杂度挺高，很多人可以同时并行搜索的。 我觉得这应该是数学建模问题，通常很难找到最优解，只能找一些较优的答案。

shshsh_0510

刚才帮你想了一下，没有想到啥太好的方案，提一种方法抛砖引玉，看看大家有什么好的方案： 首先，需要先完成任务，一种最笨的方法是，大家先移动到左上角，并排站好，然后一起向右，等到到了最右，大家先一起向下然后向左，。。。，这样逐行扫描整个区间。 这一过程中，可以看出，横着扫描时效率很高，但是在每次到头向下时，是纯耗费。并且开始的向左上角的移动时很大的无用耗费。于是设计的路线力图将这两种消耗尽量减小

shshsh_0510

上边的方案中，只3个画红圈的地方有一些队形整理的消耗，当然，这是一个通用的方案，所以当整个区域的长宽不正好被队长整除的话，在边界处还会产生一些浪费

liangbch

按附图这种方式（以3人为一组为例）可一定程度上减小搜索的浪费。

shshsh_0510

liangbch 的方法很好，如果整个区域的长宽合适的话，比我的少了两次整理队形的耗费，在某些情况下应该是最优的了 这个的本质是构造20条互不相交、等长、等距的曲线去覆盖区域