有效地写一个航空公司路由算法 [英] Writing an Airline Routing Algorithm Efficiently

问题描述

由于：

• 航班（出发城市，到达城市，出发时间，到达时间）的数据库中。

问题：

• 什么是最有效的算法，两个城市之间的上市服务，如果发车时间是不重要的？考虑，我们希望尽量减少临时滞留时间（但仍然高于额定最小，即20分钟），并尽量减少中途停留的数目（如果有一个直达路由，这是微不足道的，但如果没有，找到一个连接路由通过两个-connection等，以合理的停留时间，没有价值的）。
• 如果可能的话，我不希望有明确标签的任何机场为枢纽，以保持开放点至点航线网络的可能性。
• 应该有一个选项来指定所需的（近似）发车时间。这是确定的，如果这有自己的算法独立于第一。

这个项目code语言尚未选定，但（可能是一个.NET语言，因为快速表单能派上用场），所以伪code算法是preferred。我会留意的后续问题，如果添加的信息可能有帮助。

Code language for this project hasn't been chosen yet (probably a .NET language, since quick forms will come in handy), so pseudocode algorithms are preferred. I'll keep an eye out for follow-up questions if added info might help.

推荐答案

目前的基础上，你要查看你所在的城市网络为一棵树，与出发城市为根，每一个离港航班被指向一个孩子。您将通过树做递归深度优先搜索找到的所有路径到目的地，但检查你去一个周期，中止，结果在一个周期内的任何路径。

At the base, you're going to view your city network as a tree, with departing city as root, and each departing flight being a pointer to a child. You'll do a recursive depth-first search through the tree to find all paths to the destination, but checking for a cycle as you go and aborting any path that results in a cycle.

当你找到可行的路径，你可以只让尚未找到一个单一的解决方案中最短;或者，如果你想在这个基础上选择保持找到路径较大的子集，由各地出发时间的一些标准进行分层。

As you find feasible paths, you can either just keep the shortest yet found as a singular solution; or keep a larger subset of paths found, stratified by some criteria around departure time if you want to select on that basis.

根据数据库和节点的具体情况，还可以扔在其他规则的短切的路径搜索，例如，如果你碰巧知道，出发地和目的地1000英里之外，和你的路径追踪迄今已你飞3000英里，你还在不在那里，拧，移动到下一个路径搜索。

Depending on the specifics of the database and nodes, you can also throw in other rules for cutting short your path searches, e.g., if you happen to know that departure and destination are 1000 miles apart, and your path traced so far has you flying 3000 miles and you're still not there, screw it, move on to the next path search.

这篇关于有效地写一个航空公司路由算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！