大型有向无环图路径优化：寻找最小最大节点值路径

问题背景 #

• 存在一个从Level 0流向Level 3500的有向无环图（DAG），仅不同层级间存在边，同层级节点无连接（例如Level 1节点可连接多个Level 2节点，Level 2节点不与同层级节点相连）
• 每个Level N节点与1至9个Level N+1节点相连，节点数量呈指数级增长——Level 3500的节点数约为8^3500个
• 核心目标：找到一条从Level 0到Level 3500的路径，使得路径上的最大节点值最小；仅关注路径的最大节点值，而非总路径值；已拥有一条较优但非最优的初始路径，优先寻找最优解，若无法实现，可接受与最优值相差20%或50%以内的路径

当前方法及瓶颈 #

当前采用回溯式优化方法，步骤如下：

1. 计算一条较优但非最优的路径，得到初始最大节点值
2. 执行深度优先遍历，遍历过程中计算节点值（示例：某右侧路径L0=0.1、L1=0.1、L2=0.2，该路径的最大节点值为0.2）
3. 回溯至节点值小于当前最大节点值的节点（本例中为L1=0.1）
4. 检查该节点的其他子节点，若子节点值（如L2=0.3）不小于当前最大值，则无优化空间
5. 继续回溯至上层节点（如L0），重新向下遍历
6. 遇到节点值不小于当前最大值的节点（如L2=0.2），直接忽略
7. 遇到节点值小于当前最大值的节点（如L2=0.1），则继续向下探索
8. 后续节点值（如L3=0.1）均不超过初始最大值，此时得到最优路径的最大节点值为0.1（因L0节点值已为0.1，无法进一步优化）

瓶颈：由于节点数量过大，即使仅10层的图，优化耗时也过长；单个Level 1节点计算其相连的Level 2节点值约需1/100秒

提问 #

是否存在其他更高效的解决方法？（例如最近邻算法可在约10分钟内得到一个较好的非最优解）

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