航班时刻表算法
答
基本上,这是遍历一个图的问题,其中每个出发或到达将是一个节点,并且每个飞行都是一个边。您通常会将成本应用于边缘 - 取决于用户的偏好,“成本”可能是机票的成本(以获得最低价格)或飞行时间(以获得最短的飞行时间)。在同一机场的抵达和离开将通过其停留时间(并且从价格角度来看,该边缘通常会具有零成本)的成本边缘来连接。
答
直接航班文件产生一个图。节点是机场。边缘位于有直飞航班的机场之间,并说每条边都有重量。您想要找到A和B之间的所有简单路径,并且可能最终会收集路径集合。您可以只对图形进行深度优先搜索。编码图的一些常见方式是邻接列表(即,对于每个节点,存在边的节点的列表);以及其他编码方法。或N×N矩阵(对于N个节点)位置(i,j)中的值告诉你节点i和节点j之间边缘的成本。
鉴于该数据结构。您可以使用从节点A开始的深度优先搜索并终止于节点B.您需要确保阻止算法重新访问已经在当前路径上的节点以防止循环。
答
经典问题Shortest path problem。如果你正在寻找算法,也有在*页面中列出的几个选项,或者有算法,如ACO的选项,但它取决于使用情况和如何提供解决方案。
为清晰起见,请注意,这是一个在traveling salesman problem的变化,结果是NP-complete。
http://jung.sourceforge.net/ – jball 2010-01-12 20:36:00
您是否关心连接数量,总体旅行时间,最小化停留时间? – jball 2010-01-12 20:38:04
这听起来像是作业问题? – 2010-01-12 20:41:32