algorithm - 基本的飞行旅行计划

Question

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

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

请注意，两个城市之间可能有多个航类(在不同时间)。

您必须回答的查询是:给定两个城市“A”和“B”，时间为“t1”、“t2”，其中 t1 < t2，找到时间后离开城市“A”的最便宜的旅行” t1”，并在时间“t2”之前到达城市“B”。行程是一系列航类，在时间 t1 之后从 A 开始，在时间 t2 之前在 B 结束。此外，从任何中转(中间)城市 C 出发的时间至少在到达 C 后 30 分钟

Answer 1

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

图的顶点是位置和(到达)时间的元组。边缘是停留(至少 30 分钟)和离港航类的组合。唯一的困难是标记我们已经访问过的顶点(“关闭”列表)，因为在给定时间到达机场不应阻止考虑较早到达该机场的航类。我的建议是标记我们已经考虑过的出发航类，而不是标记机场。

这是 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