带节点任务的图枚举可行路径并求最优解：回溯法应用或替代方案咨询

核心作业需求 #

• 图结构基础设定：每个顶点对应一座城市，城市下以LinkedList形式存储可接任务列表
• 任务属性：单任务包含赏金Price、危险等级DangerLevel两个核心参数
• 时间消耗规则：城市间跨区域移动消耗1天，完成单个任务消耗1天
• 优化目标：在给定的总可用天数限制下，优先最大化获取的总赏金，同赏金前提下尽可能降低路线的总危险等级
• 当前方案疑问：最初考虑用回溯法遍历图中所有可行路径求解，但不确定回溯法是否是最简单的实现路径，尤其不清楚如何在带多层子属性（城市嵌套任务列表）的图结构上落地回溯逻辑

已定义的类结构 #

// 图结构类
class Graph
    {
        List<Cities> Cities;
        List<List<Edge>> Neigbours;

        public class Edge
        {
            public Cities to;
            public int weight;
            public Edge()
            {
                weight= 1;
            }
        } 
    }

// 城市类
class Cities
{
    public string Name { get; set; }
    public LinkedList Quests { get; set; }

}

// 任务类
class Contract
{
    public string Type { get; set; }
    public int Price { get; set; }
    public int DangerLevel { get; set; }
}

回溯法落地的实操逻辑 #

针对城市嵌套任务的多层结构，回溯法不需要修改图的基础遍历逻辑，只需要在常规图遍历的状态中扩展城市内任务的选择分支即可：

需维护的回溯状态 #

除了常规图遍历记录的“当前所在城市、已消耗天数”之外，需要额外维护三类状态：

• 当前累计获得的总赏金、累计产生的总危险等级（用于和全局最优解做对比）
• 当前城市下已经完成的任务集合（避免重复领取同一任务）
• 全局最优值记录：因为是双目标排序，规则为“先比较总赏金，赏金更高的更优；赏金相同时比较总危险等级，等级更低的更优”，需要实时更新找到的最优路径、任务组合及对应的数值

递归分支设计 #

每个递归节点的可选动作分为两类，只要累计消耗天数超过可用上限就直接剪枝返回：

1. 选择当前城市的未完成任务：消耗1天时间，累计对应任务的赏金和危险等级，标记该任务为已完成，继续向下递归
2. 移动到相邻城市：沿邻接边走到目标城市，消耗1天时间，切换当前所在城市，继续向下递归

可优化的剪枝规则：如果当前状态下，哪怕把所有剩余可接触的任务赏金全部拿到，也追不上当前已记录的最高赏金，直接剪枝不再递归；如果当前累计赏金已经追平最高赏金，但哪怕后续完全不新增危险值，也没法低于当前记录的最低危险等级，同样可以剪枝

实现复杂度提示 #

• 带剪枝的回溯法可以在中小规模测试用例（城市数<10、单城市任务数<5、总可用天数<15）下拿到精确最优解，是作业场景下实现门槛最低的方案
• 如果测试用例规模稍大，可以替换为状态压缩动态规划，将状态定义为(当前所在城市, 已用天数, 已完成的任务集合)，记录每个状态下对应的最高赏金、最低危险等级，比无剪枝的纯回溯效率提升明显

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