请求生成满足多约束条件的随机公交出行序列方案

核心约束条件 #

• 必须使用Base(3)中所有公交，优先单次使用，必要时可复用
• 需覆盖Base(1)所有出发城市、Base(2)所有到达城市
• 初始城市从Base(1)随机选取，后续行程起点为前一段终点
• 序列需尽可能随机且步骤最少
• 公交不能往返同一城市（起点≠终点）
• 最终序列需满足：所有公交使用完毕、Base(1)城市均作为起点出现、Base(2)城市均作为终点出现

数据库示例 #

Base(1) 格式："City1,City2,City3..." - "CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,MOONSTONE,RIVERDALE,CEDARVILLE,MAPLEWOOD"
Base(2) 格式："City1,City2,City3..." - "CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,MOONSTONE,RIVERDALE,CEDARVILLE,MAPLEWOOD"
Base(3) 格式："BusName1:CityFROM1,CityFROM2...@CityTO1,CityTO2...
BusName2:CityFROM1,CityFROM2...@CityTO1,CityTO2..." 
"TransLink:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
GoBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
SwiftRide:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
SpeedyBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE
CityHopper:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@MOONSTONE
RouteMasters:MOONSTONE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
MetroTrans:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE
MegaBus:MAPLEWOOD,CRYSTALVILLE@MAPLEWOOD,CRYSTALVILLE"

期望序列示例 #

Starting with the city CRYSTALVILLE,
CRYSTALVILLE (CityHopper) - MOONSTONE,
MOONSTONE (RouteMasters) - HARMONYVILLE,
HARMONYVILLE (SpeedyBus) - WILLOWBROOK,
WILLOWBROOK (MetroTrans) - RIVERDALE,
RIVERDALE (MetroTrans) - CEDARVILLE,
CEDARVILLE (MetroTrans) - OCEANVIEW,
OCEANVIEW (GoBus) - SILVERLAKE,
and so on until all BUSES and cities from Base(1) and Base(2) are used.

当前问题 #

自身缺乏序列构建及编程经验，自行尝试时要么生成无限循环序列，要么在3-11步就中断。问题根源在于采用「使用后移除公交/城市」的机制，无可用选项时从初始副本随机选取，导致要么无限循环，要么无法满足「最少步骤」及全覆盖的要求，特此寻求可行解决方案。

可行解决方案思路 #

1. 数据预处理 #

• 将Base(3)的公交数据转换为映射表：每辆公交对应「允许出发城市列表」「允许到达城市列表」，同时标记公交是否已被使用
• 维护三个状态集合：
  • 未使用公交集合
  • 未作为起点的Base(1)城市集合
  • 未作为终点的Base(2)城市集合

2. 贪心+回溯混合策略（优先保证最少步骤） #

• 初始步骤：从Base(1)随机选初始城市，标记该城市已作为起点
• 每一步选择逻辑：
  1. 优先选择未使用过的公交，且该公交允许从当前起点出发，同时到达城市按以下优先级排序：
     • 优先级1：到达城市是未作为终点的Base(2)城市，且该公交出发城市包含未作为起点的Base(1)城市（后续可覆盖更多起点）
     • 优先级2：到达城市是未作为终点的Base(2)城市
     • 优先级3：到达城市已作为终点，但能连接到未使用公交/未覆盖起点的城市
  2. 若没有未使用公交可选，再选择已使用过的公交，但需避免往返同一城市，且优先能推进未覆盖目标的选项
  3. 每次选择后更新状态集合：标记公交为已使用（若首次使用）、标记到达城市为已作为终点（若首次作为终点）、若后续行程能将该到达城市作为起点，标记为已作为起点

3. 避免无限循环的机制 #

• 记录最近5步的「起点-公交-终点」组合，若出现重复则跳过该选项
• 当所有可选选项都进入循环时，回溯到上一步，更换当时的选择

4. 终止条件 #

当满足以下所有条件时停止序列生成：

• 所有Base(3)公交均被使用至少一次
• Base(1)所有城市均作为起点出现过
• Base(2)所有城市均作为终点出现过

简易伪代码示例 #

import random

# 预处理Base数据（示例）
Base1_cities = ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW", "MOONSTONE", "RIVERDALE", "CEDARVILLE", "MAPLEWOOD"]
Base2_cities = Base1_cities.copy()
buses = {
    "TransLink": {"from": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "to": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "used": False},
    "GoBus": {"from": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "to": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "used": False},
    "SwiftRide": {"from": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "to": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "used": False},
    "SpeedyBus": {"from": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE"], "to": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE"], "used": False},
    "CityHopper": {"from": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "to": ["MOONSTONE"], "used": False},
    "RouteMasters": {"from": ["MOONSTONE"], "to": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW"], "used": False},
    "MetroTrans": {"from": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW", "RIVERDALE", "CEDARVILLE"], "to": ["CRYSTALVILLE", "WILLOWBROOK", "HARMONYVILLE", "SILVERLAKE", "OCEANVIEW", "RIVERDALE", "CEDARVILLE"], "used": False},
    "MegaBus": {"from": ["MAPLEWOOD", "CRYSTALVILLE"], "to": ["MAPLEWOOD", "CRYSTALVILLE"], "used": False}
}

# 初始化状态
unused_buses = set(buses.keys())
unvisited_starts = set(Base1_cities)
unvisited_ends = set(Base2_cities)
current_city = random.choice(Base1_cities)
unvisited_starts.remove(current_city)
sequence = [f"Starting with the city {current_city},"]
recent_steps = []  # 记录最近5步避免循环

while unused_buses or unvisited_starts or unvisited_ends:
    # 筛选当前起点可乘坐的公交，排除起点=终点的情况
    valid_buses = []
    for bus_name, bus_data in buses.items():
        if current_city not in bus_data["from"]:
            continue
        # 检查该公交是否有非当前城市的终点
        has_valid_end = any(to != current_city for to in bus_data["to"])
        if has_valid_end:
            valid_buses.append(bus_name)
    
    if not valid_buses:
        # 无可用选项，回溯到上一步（此处简化，实际需实现完整回溯逻辑）
        if len(sequence) <= 1:
            break  # 初始城市就无可用公交，无法生成
        # 回溯：移除最后一步，恢复状态
        last_step = sequence.pop()
        prev_city, bus_used, end_city = last_step.split(" (", 1)[0], last_step.split("(")[1].split(")")[0], last_step.split(" - ")[1].rstrip(",")
        current_city = prev_city
        # 恢复公交状态（如果是首次使用）
        if buses[bus_used]["used"]:
            buses[bus_used]["used"] = False
            unused_buses.add(bus_used)
        # 恢复终点状态（如果是首次作为终点）
        if end_city not in [s.split(" - ")[1].rstrip(",") for s in sequence[1:]]:
            unvisited_ends.add(end_city)
        # 恢复起点状态（如果该城市仅在最后一步作为起点）
        if prev_city not in [s.split(" (")[0] for s in sequence[1:]]:
            unvisited_starts.add(prev_city)
        recent_steps.pop()
        continue
    
    # 优先选未使用的公交
    preferred_buses = [bus for bus in valid_buses if bus in unused_buses]
    if preferred_buses:
        valid_buses = preferred_buses
    
    # 按优先级排序候选公交
    def sort_bus(bus_name):
        score = 0
        bus_data = buses[bus_name]
        # 能到达未访问终点加2分
        if any(to in unvisited_ends for to in bus_data["to"] if to != current_city):
            score += 2
        # 公交能覆盖未访问起点加1分
        if any(f in unvisited_starts for f in bus_data["from"]):
            score += 1
        return -score  # 降序排列
    
    valid_buses.sort(key=sort_bus)
    # 随机选一个高优先级的公交
    selected_bus = random.choice(valid_buses)
    bus_data = buses[selected_bus]
    
    # 随机选一个符合条件的终点（排除当前城市）
    valid_ends = [to for to in bus_data["to"] if to != current_city]
    # 优先选未访问的终点
    preferred_ends = [to for to in valid_ends if to in unvisited_ends]
    if preferred_ends:
        selected_end = random.choice(preferred_ends)
    else:
        selected_end = random.choice(valid_ends)
    
    # 检查是否进入循环
    step_key = (current_city, selected_bus, selected_end)
    if step_key in recent_steps:
        continue  # 跳过重复步骤
    recent_steps.append(step_key)
    if len(recent_steps) > 5:
        recent_steps.pop(0)
    
    # 更新状态
    if selected_bus in unused_buses:
        unused_buses.remove(selected_bus)
        buses[selected_bus]["used"] = True
    if selected_end in unvisited_ends:
        unvisited_ends.remove(selected_end)
    # 标记该城市为已作为起点（后续会用到）
    if selected_end in unvisited_starts:
        unvisited_starts.remove(selected_end)
    
    # 添加到序列
    sequence.append(f"{current_city} ({selected_bus}) - {selected_end},")
    current_city = selected_end

# 输出最终序列
print("\n".join(sequence))

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