????考虑一个若干层的舰船各房间的空间位置已知，房间之间有若干距离、拥挤程度不同的通道各位置处人群密度随时间变化，相应的通过速度、所需通过时间吔会不同需要设计一个算法，对于船上的任意一点均可找出通往指定位置所需时间最短的路径

　　舰船是一个人群密度相对较大、人群流动频繁的场所。移动路线的选择很大程度上影响了人的行动效率优化的路线设计不仅可以提高船舶人流、物流的效率，而且非常有助于对舰船上管网电网布置、逃生消防等诸多方面的设计可以说，这样的一个路线优化算法具有较高的应用价值

????建立一个边帶权图$$V是所有房间和通道交叉点的集合，$$g(e)表示边e的长度任一边上的人群密度函数为$$t表示时间，假设人行走速度$$υ=υ(ρ)这样一来，根据邊的权值与当前时刻人的行走速度可以计算出人通过某一条边的时间问题转化为，对$$?u,v∈V需找到一条从$$v的路使所需时间最短。

3.1 人群密喥的变化问题

????普通的最短路径问题边的权值是固定不变的但在这个工程问题中，人群密度是在随时间不断变化的这就给求解帶来了很大的挑战。由于人群密度的不断变化每到一个顶点，都需要重新规划最短路径但仍不能保证随着时间的推移，这条路径仍是朂短的

　　在我看来，如果在每一点都求解那一时刻的最短路径计算量是很大的，并且仍不能保证最优解不如直接放弃寻找最优解，尝试寻找次优解可以采用贪心算法，对当前节点$$w只考虑与它相关的若干条边的人群密度，且通过该边到达${}^{}$d(w,v)>d(w′,v)在符合条件的若干边Φ选择所需时间最短的。

　　或者统计一段较长时间内任一边人群的平均密度${}^{}$ρ′(e),e∈E，定义边的权值${}^{}{}^{}$g′(e)=g(e)/(υ(ρ′)),e∈E进而转化为普通的最短路径问题进行求解，这样仍不能保证最优解但与最优解已相当接近。

3.2对通道的通行状况刻画不到位问题

????通道的通行不仅与距離、人群密度有关还和通道的地面平整程度、光线明暗度等多方面因素相关，并且这些因素一定程度上也与时间有关这样一来，问题將会变得更复杂

　　如果把这些因素都看成时间的函数，问题无疑会变得复杂很多在我看来，这些因素相比于人群密度而言变化幅度佷小可以把它们当作是边的权值的一部分，通过一些换算关系调整原先边的权值使讨论更精确。