啊！[基于旅行计划的问题][1]
什么方法最适合解决这个问题？，任何帮助都将不胜感激
输入是不同城市之间的航班集合它是作为一个文件给出的。文件的每一行都包含“CITY1 CITY2出发时间到达时间航班号价格”这意味着有一个航班名为“航班号”（这是表格XY012的字符串），从CITY1飞往CITY2，在“出发时间”离开CITY1，在“到达时间”到达CITY2。此外，该航班的价格是“价格”，这是一个poive整数。所有时间都以24小时格式的4位数字字符串给出，例如1135、0245、2210。假设所有城市名称都是介于1和数字n（其中n是城市总数）之间的整数。
注意两个城市之间可能有多个航班（在不同的时间）。
您需要回答的问题是：给定两个城市“a”和“b”，乘以“t1”，“t2”，其中t1
最佳答案
可以使用图形搜索算法（如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
关于algorithm - 基本的飞行旅行计划员，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29831154/