运维开发网

有效编写航空公司路由算法

运维开发网 https://www.qedev.com 2020-06-13 20:54 出处:网络 作者:运维开发网整理
鉴于: >航班数据库(出发城市,到达城市,出发时间,到达时间). 问题: >如果出发时间不重要,那么在两个城市之间列出服务的最有效算法是什么?考虑到我们希望最小化停留时间(但仍然高于标称最小值,即20分钟),并最小化中途停留次数(如果有不间断路线,这是微不足道的,但如果没有,则找到一个连接路线超过两个连接等,合理的停留时间,不那么琐碎). >如果可能的话,我不想特别将任何机场标记为集线器,以便留下
鉴于:

>航班数据库(出发城市,到达城市,出发时间,到达时间).

问题:

>如果出发时间不重要,那么在两个城市之间列出服务的最有效算法是什么?考虑到我们希望最小化停留时间(但仍然高于标称最小值,即20分钟),并最小化中途停留次数(如果有不间断路线,这是微不足道的,但如果没有,则找到一个连接路线超过两个连接等,合理的停留时间,不那么琐碎).

>如果可能的话,我不想特别将任何机场标记为集线器,以便留下点对点路由网络的可能性.

>应该有一个选项来指定所需的(近似的)出发时间.如果它有自己的算法与第一个算法分开,那就没关系.

尚未选择此项目的代码语言(可能是.NET语言,因为快速表单将派上用场),因此首选伪代码算法.如果添加的信息可能有帮助,我会留意后续问题.

在基地,您将以树为单位查看您的城市网络,以离开的城市为根,每个离开的航班都是指向孩子的指针.您将在树中执行递归深度优先搜索以查找到目标的所有路径,但是在您前进时检查一个循环并中止导致循环的任何路径.

当你找到可行的路径时,你可以保持最短但是找到一个单一的解决方案;或保留更大的路径子集,如果您想在此基础上选择,则按出发时间的某些标准进行分层.

根据数据库和节点的具体情况,您还可以引入其他规则来缩短路径搜索时间,例如,如果您碰巧知道出发地和目的地相距1000英里,并且您到目前为止的路径已经飞行了3000英里,你仍然不在那里,拧紧它,继续前进到下一个路径搜索.

0

精彩评论

暂无评论...
验证码 换一张
取 消