带预算的兴趣最大化Modified TSP：branch-and-bound求解及适配算法问询

一、适用的替代算法 #

• 动态规划（DP）：将状态定义为「当前城市+已访问城市集合+剩余预算」，用DP表存储每个状态的最大兴趣值，适合小规模问题，可直接处理非度量图的路径成本。
• 遗传算法：基于进化思想的启发式算法，通过种群迭代（选择、交叉、变异）寻找近似最优解，适合大规模问题，能在合理时间内输出较好结果。
• 模拟退火：模拟金属退火过程，允许一定概率接受较差解以跳出局部最优，适合求解这类组合优化的近似解，对非度量图兼容性良好。
• 禁忌搜索：通过禁忌表避免重复陷入局部最优区域，搜索过程中可灵活调整路径，适合需要突破局部最优的场景。
• 整数线性规划（ILP）：将问题建模为整数规划模型（变量表示是否经过某条边，目标函数最大化总兴趣，约束包含预算、路径闭环、无重复访问等），调用ILP求解器（如Gurobi、CPLEX）求解，适合小规模场景的精确解需求。

二、分支定界算法Python实现 #

以下是针对该问题的可运行分支定界实现，以示例参数演示：

# 问题参数示例：可根据实际需求修改
cities = ["A", "B", "C", "D"]
interest = {"A": 8, "B": 9, "C": 7, "D": 10}
# cost_matrix[i][j] 代表从城市i到城市j的旅行成本
cost_matrix = [
    [0, 3, 5, 4],
    [3, 0, 2, 6],
    [5, 2, 0, 3],
    [4, 6, 3, 0]
]
budget_limit = 15

# 全局变量存储当前最优解
best_total_interest = 0
best_tour = []

def branch_bound(current_city, visited_set, current_cost, current_interest, current_path):
    global best_total_interest, best_tour
    city_idx = cities.index(current_city)
    
    # 尝试返回起点，检查预算是否符合要求
    return_cost = cost_matrix[city_idx][cities.index(current_path[0])]
    if current_cost + return_cost <= budget_limit:
        if current_interest > best_total_interest:
            best_total_interest = current_interest
            best_tour = current_path + [current_path[0]]
    
    # 计算上界：假设能访问所有未访问城市的最大兴趣值，若上界不超当前最优则剪枝
    unvisited = [city for city in cities if city not in visited_set]
    upper_bound = current_interest + sum(interest[city] for city in unvisited)
    if upper_bound <= best_total_interest:
        return
    
    # 遍历所有未访问城市，扩展分支
    for next_city in unvisited:
        next_idx = cities.index(next_city)
        new_cost = current_cost + cost_matrix[city_idx][next_idx]
        if new_cost > budget_limit:
            continue  # 预算超支，跳过该分支
        branch_bound(
            next_city,
            visited_set | {next_city},
            new_cost,
            current_interest + interest[next_city],
            current_path + [next_city]
        )

# 遍历所有可能的起点，确保找到全局最优解
for start in cities:
    branch_bound(start, {start}, 0, interest[start], [start])

# 输出结果
print(f"最大总兴趣值: {best_total_interest}")
print(f"最优路径: {' -> '.join(best_tour)}")

代码说明 #

1. 剪枝逻辑：通过计算未访问城市的兴趣值总和作为上界，若该上界不超过当前已找到的最优兴趣值，则直接剪去该分支，避免无效搜索。
2. 起点遍历：由于起点可自由选择，遍历所有城市作为起点，确保不会遗漏潜在的最优路径。
3. 非度量图兼容：直接使用给定的成本矩阵，无需额外处理中转成本问题。

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