单日单城最大航班搭乘量求解及代码优化技术问询

需求与规则 #

我是航空爱好者，目标是计算单日从单个城市出发可搭乘的最大航班数量，并获取对应的完整航班列表。现有包含以下字段的DataFrame（已按起飞时间排序）：

• DPTR_TIME：起飞时间
• ARRV_TIME：到达时间
• ORIG：出发城市
• DEST：目的城市

核心约束规则：

• 存在枢纽城市HUB：从HUB出发的航班，后续必须搭乘返回HUB的航班（例如HUB为纽约，先飞纽约→匹兹堡，后续需飞匹兹堡→纽约）
• 行程可从非HUB城市启动：先飞抵HUB，再从HUB出发衔接后续航班
• 航班衔接要求：下一航班的起飞时间必须晚于上一航班的到达时间（需预留衔接时长）

现有实现的问题 #

我编写了一个递归函数，但它仅能计算初始时刻表中首个航班的可行衔接数量，无法遍历所有可能的航班组合以找到单日最多的航班序列：

def iter_func(df,sch,conex):
    flt = df.iloc[0]
    df = sch[(sch['ORIG']==flt.DEST) & (sch['DPTR_TIME']>flt.ARRV_TIME+timedelta(hours=conex))]
    if df.shape[0]==0:
        return 1
    else:
        return 1 + iter_func(df,test,conex)

注：代码中test应为sch，属于笔误

高效实现思路与代码 #

这个问题本质是带约束的最长路径问题，可以通过动态规划+回溯的方式高效解决，既保证遍历所有可能的航班组合，又能满足HUB往返约束：

核心逻辑 #

1. 预处理邻接表：为每个航班预计算可衔接的后续航班列表（满足出发城市匹配、起飞时间晚于到达时间+衔接时长）
2. 动态规划记录最长路径：用dp[i]记录以第i个航班结尾的最长航班链长度、前置航班ID、当前所在城市、是否处于「从HUB出发未返回」的状态，确保HUB规则被遵守
3. 回溯生成最优航班列表：遍历所有DP记录找到最长链，再回溯得到完整的航班序列

完整代码实现 #

from datetime import timedelta
import pandas as pd

def find_max_flights(df, hub, conex_hours=1):
    # 为每个航班分配唯一ID
    df = df.reset_index(drop=True).rename_axis('flight_id').reset_index()
    
    # 预构建邻接表：每个航班可衔接的后续航班ID列表
    adjacency = [[] for _ in range(len(df))]
    for idx in range(len(df)):
        current_flight = df.iloc[idx]
        # 筛选符合衔接条件的后续航班
        valid_mask = (df['ORIG'] == current_flight['DEST']) & \
                     (df['DPTR_TIME'] > current_flight['ARRV_TIME'] + timedelta(hours=conex_hours))
        adjacency[idx] = df[valid_mask]['flight_id'].tolist()
    
    # 动态规划数组初始化：(最大航班数, 前置航班ID, 当前所在城市, 是否处于从HUB出发未返回状态)
    dp = [
        (1, None, df.iloc[idx]['DEST'], 
         True if df.iloc[idx]['ORIG'] == hub else False)
        for idx in range(len(df))
    ]
    
    # 从后往前遍历航班，更新DP状态
    for idx in range(len(df)-1, -1, -1):
        current_count, _, current_city, unreturned_hub = dp[idx]
        current_flight = df.iloc[idx]
        
        for next_flight_id in adjacency[idx]:
            next_count, next_prev, next_city, next_unreturned = dp[next_flight_id]
            
            # 验证HUB约束：如果当前处于从HUB出发未返回状态，后续航班必须从当前到达城市出发，且最终需返回HUB
            is_valid = True
            if unreturned_hub:
                # 后续航班的出发城市必须等于当前航班的到达城市
                if df.iloc[next_flight_id]['ORIG'] != current_city:
                    is_valid = False
                # 如果后续路径的终点不是HUB，且仍处于未返回状态，则无效
                if next_city != hub and next_unreturned:
                    is_valid = False
            
            # 更新当前航班的最长链状态
            if is_valid and (next_count + 1 > current_count):
                # 若当前航班是从HUB出发且后续航班返回HUB，则重置未返回状态
                new_unreturned = next_unreturned if not (current_flight['ORIG'] == hub and next_city == hub) else False
                dp[idx] = (next_count + 1, next_flight_id, next_city, new_unreturned)
    
    # 找到最长航班链的起始航班ID
    max_flight_count = -1
    best_start_idx = None
    for idx in range(len(df)):
        count, _, _, _ = dp[idx]
        if count > max_flight_count:
            max_flight_count = count
            best_start_idx = idx
    
    # 回溯生成完整航班列表
    flight_sequence = []
    current_idx = best_start_idx
    while current_idx is not None:
        flight_sequence.append(df.iloc[current_idx])
        current_idx = dp[current_idx][1]
    
    # 反转得到从早到晚的航班顺序
    flight_sequence = flight_sequence[::-1]
    return pd.DataFrame(flight_sequence), max_flight_count

使用示例 #

# 假设df是你的航班数据DataFrame，HUB为'NYC'
best_flights, max_count = find_max_flights(df, hub='NYC', conex_hours=1)
print(f"单日最多可搭乘{max_count}个航班")
print(best_flights[['ORIG', 'DEST', 'DPTR_TIME', 'ARRV_TIME']])

内容的提问来源于stack exchange，提问作者buffalocookies