有向图指定起止节点下访问节点最多且权重最小路径的算法问询

问题本质界定 #

你描述的是带双优化目标的最长简单路径问题变体：第一优先级最大化访问的不重复节点数量，第二优先级在节点数相同的路径中最小化总权值。
默认假设路径为简单路径（节点不重复访问），如果允许重复访问节点，含环场景下会存在无限增加访问节点数的路径，问题无意义。
这个问题在含环的一般有向图中是NP难问题，和TSP复杂度同级，不存在多项式时间的精确解法，和TSP的核心差异仅在于不要求覆盖全部节点、允许提前终止到终点。 #

前置优化步骤 #

不管选用什么求解算法，先做预处理缩小问题规模：

• 从起点出发做正向BFS/DFS，筛选出所有起点可达的节点
• 反向建图后从终点出发做BFS/DFS，筛选出所有能到达终点的节点
• 取两个节点集合的交集，剩余不在交集中的节点不可能出现在合法路径里，直接从图中剔除

不同场景下的适用算法 #

1. 图规模较小（节点数≤20） #

用状态压缩动态规划（状压DP），效率远高于暴力枚举的精确解法：

• 状态定义：dp[mask][u] 存储从起点出发、访问过的节点集合为mask（二进制位标记节点是否被访问）、当前位于节点u时的最小总权值
• 初始化：dp[1<<start_id][start_id] = 0，其余状态初始化为无穷大
• 状态转移：对每个状态(mask, u)，遍历u的所有出边u->v，若v不在mask中，新状态dp[mask | (1<<v)][v]取原存储值和dp[mask][u] + weight(u,v)的较小值
• 结果提取：按mask中1的数量从大到小遍历，找到第一个存在有效dp[mask][end_id]的状态，对应的权值和路径就是最优解
  该方法时间复杂度为O(2^n * n^2)，n=20时配合剪枝普通设备可正常运行。

2. 图为有向无环图（DAG） #

可通过拓扑排序+线性DP实现多项式时间的精确求解，复杂度仅为O(n+m)（n为节点数，m为边数）：

• 先对DAG做拓扑排序
• 状态定义：dp[u]存储两组值：从起点到u的最多访问节点数、对应节点数下的最小权值
• 状态转移：按拓扑序遍历每个节点u，对每个出边u->v，若走该边能提升v的访问节点数则直接更新；若节点数和当前dp[v]存储的节点数相同，则取更小的权值更新
• 结果直接提取dp[end_id]对应的路径即可

3. 图规模较大（节点数>20）且接受近似解 #

选用启发式搜索或元启发算法：

• 带剪枝的DFS：维护当前已找到的最优路径的节点数，若当前路径长度+剩余可达节点数小于最优节点数直接剪枝；同节点数下当前权值已超过最优解也剪枝，效率远高于暴力枚举
• 也可选用模拟退火、遗传算法等元启发算法，在可接受时间内得到接近最优的解

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