基本的飞行旅行计划

Question

![基于旅行计划的问题][1] 什么方法最适合解决这个问题？任何形式的帮助都将不胜感激

输入是各个城市之间的航班集合。它作为一个文件给出。文件的每一行都包含 "city1 city2 departure-time arrival-time flight-no. price" 这意味着有一个名为 "flight-no" 的航班（它是一个 XY012 形式的字符串）从 city1 到 city2，它在时间 "departure-time" 离开 city1 并到达时间 "arrival-time" 的城市 2。此外，此航班的价格是 "price"，这是一个积极的整数。所有时间均以 24 小时格式的 4 位数字字符串形式给出，例如1135, 0245, 2210。假设所有城市名称都是介于 1 和 N 之间的整数（其中 N 是城市总数）。

请注意，两个城市之间可能有多个航班（在不同时间）。

您必须回答的查询是：给定两个城市 "A" 和 "B"，乘以 "t1"、"t2"，其中 t1 < t2，找到最便宜的在时间 "t1" 之后离开城市 "A" 并在时间 "t2" 之前到达城市 "B" 的行程。行程是一系列航班，在时间 t1 之后从 A 开始，在时间 t2 之前在 B 结束。此外，从任何中转（中间）城市 C 出发的时间至少为到达 C

后 30 分钟

Answer 1

如果你不在乎效率，你可以这样解决问题：

对于t2之前到达目的地的每个"final leg"个航班，确定航班的出发城市（cityX）和航班的出发时间（tX）。从出发时间 (tX-30) 中减去 30 分钟。然后从 start 递归地找到最便宜的行程，在 t1 之后出发，在 tX-30 之前到达 cityX。将该行程的费用与最后一段的费用相加，以确定行程的总费用。所有这些旅行中最少的是你想要的航班。

也许有更高效的动态规划方法，但我可能会从上面的方法开始（这很容易递归编码）。

Answer 2

你可以用图搜索算法解决这个问题，比如Dijkstra's Algorithm。

图的顶点是位置和（到达）时间的元组。边缘是停留（至少 30 分钟）和离港航班的组合。唯一的困难是标记我们已经访问过的顶点（"closed" 列表），因为在给定时间到达机场不应妨碍考虑较早到达该机场的航班。我的建议是标记我们已经考虑过的出发航班，而不是标记机场。

这是 Python 中的一个快速实现。我假设您已经将航班数据解析为字典，该字典从出发机场名称映射到包含航班信息的 5 元组列表 ((flight_number, cost, destination_airport, departure_time, arrival_time)):

from heapq import heappush, heappop
from datetime import timedelta

def find_cheapest_route(flight_dict, start, start_time, target, target_time):
    queue = []  # a min-heap based priority queue
    taken_flights = set()  # flights that have already been considered
    heappush(queue, (0, start, start_time - timedelta(minutes=30), []))  # start state

    while queue:  # search loop
        cost_so_far, location, time, route = heappop(queue)  # pop the cheapest route

        if location == target and time <= target_time: # see if we've found a solution
            return route, cost

        earliest_departure = time + timedelta(minutes=30)  # minimum layover

        for (flight_number, flight_cost, flight_dest,  # loop on outgoing flights
             flight_departure_time, flight_arrival_time) in flight_dict[location]:
            if (flight_departure_time >= earliest_departure and  # check flight
                    flight_arrival_time <= target_time and
                    flight_number not in taken_flights):
                queue.heappush(queue, (cost_so_far + flight_cost,  # add it to heap
                                       flight_dest, flight_arrival_time,
                                       route + [flight_number]))
                taken_flights.add(flight_number)  # and to the set of seen flights

    # if we got here, there's no timely route to the destination
    return None, None # or raise an exception

基本的飞行旅行计划

rudimentary flight trip planner

algorithm

graph

data-structures