基本的飞行旅行计划-Java 学习之路

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

输入是各个城市之间的航班集 . 它以文件形式提供 . 该文件的每一行包含“city1 city2出发时间到达时间航班 - 没有价格”这意味着从city1到city2有一个名为“flight-no”的飞行（这是一个XY012形式的字符串） city1在时间“出发时间”并且在“到达时间”到达city2 . 此航班的价格是“价格”，这是一个整数 . 所有时间都以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分钟

2 回答

您可以使用图形搜索算法解决此问题，例如Dijkstra's Algorithm .

图的顶点是位置和（到达）时间的元组 . 边缘是中途停留（至少30分钟）和外出飞行的组合 . 唯一的困难是标记我们已经访问过的顶点（“关闭”列表），因为在给定时间到达机场不应该阻止考虑到达之前到达的机场的航班 . 我的建议是标记我们已经考虑过的离港航班，而不是标记机场 .

这里's a quick implementation in Python. I assume that you' ve已经将航班数据解析为字典，该字典从出发的机场名称映射到包含航班信息的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

回复于 2024-04-29T18:52:33+08:00

0

如果你不关心效率，你可以解决这个问题：

对于在t2之前到达目的地的每条“最后一站”航班，确定航班的出发城市（cityX）和航班的起飞时间（tX） . 从出发时间（tX-30）减去30分钟 . 然后递归地找到最便宜的旅程从开始，在t1之后离开，在tX-30之前到达cityX . 将该行程的成本加到最后一段的成本中，以确定行程的总成本 . 所有这些旅行的最低限度是您想要的航班 .

可能有一种更有效的动态编程方法，但我可能从上面开始（这很容易递归编码） .

回复于 2024-04-29T18:52:33+08:00

基本的飞行旅行计划

2 回答

相关问题