Python约束满足问题(CSP)：通过数组元素查找字典键与时间约束实现

你当前的timeDomain结构存在核心问题：它以时间为键、可选人员列表为值，但所有值完全相同，导致无法通过人员反向绑定对应时间。要实现"Amber比Brian早到5分钟"的约束，需要先调整数据结构，把时间转为数值方便计算，再建立人员与可选时间的映射。

步骤1：时间字符串转数值 #

将"HH:MM"格式的时间转为总分钟数，差值计算会更直观：

def time_to_minutes(time_str):
    hours, minutes = map(int, time_str.split(":"))
    return hours * 60 + minutes

def minutes_to_time(total_minutes):
    hours = total_minutes // 60
    minutes = total_minutes % 60
    return f"{hours}:{minutes:02d}"

步骤2：调整数据结构为人员-时间域映射 #

提取原时间列表并转为数值后，为每个人员分配可选时间域：

timeDomain = {"4:30" : ["brian", "amber", "chris", "diane"],
              "4:35" : ["brian", "amber", "chris", "diane"],
              "4:40" : ["brian", "amber", "chris", "diane"],
              "4:45" : ["brian", "amber", "chris", "diane"]}

# 提取所有时间并转为分钟数
time_minutes = [time_to_minutes(t) for t in timeDomain.keys()]

# 建立每个人员的可选时间域
person_domains = {
    "amber": time_minutes.copy(),
    "brian": time_minutes.copy(),
    "chris": time_minutes.copy(),
    "diane": time_minutes.copy()
}

步骤3：实现约束判断 #

约束条件amber的时间 == brian的时间 -5可直接通过数值比较实现：

# 筛选符合约束的Amber和Brian时间组合
valid_combinations = []
for amber_t in person_domains["amber"]:
    for brian_t in person_domains["brian"]:
        if amber_t == brian_t - 5:
            valid_combinations.append(
                (minutes_to_time(amber_t), minutes_to_time(brian_t))
            )

print("符合约束的时间组合：", valid_combinations)

运行后会输出：符合约束的时间组合： [('4:30', '4:35'), ('4:35', '4:40'), ('4:40', '4:45')]

步骤4：在CSP求解中应用约束 #

如果用回溯法等CSP求解框架，可将约束作为赋值时的检查条件。比如在给Brian分配时间后，过滤Amber的可选时间：

# 假设已给Brian分配时间brian_assigned（分钟数）
brian_assigned = time_to_minutes("4:35")
# 过滤Amber的可选时间，只保留符合约束的选项
person_domains["amber"] = [t for t in person_domains["amber"] if t == brian_assigned -5]

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