1

考虑一棵树，其中每个节点都与系统状态相关联，并包含在系统上执行的一系列操作。

根是与系统的原始状态相关联的空节点。与节点关联的状态n是通过将包含在原始系统状态中的动作序列应用n到原始系统状态而获得的。节点的动作序列n是通过将新动作排队到父动作序列来获得的。

从一个节点移动到另一个节点（即，将一个新动作添加到动作序列中）会产生一个增益，该增益附加到连接两个节点的边上。

一些“数学”：

  • 每个系统状态S都与一个值相关联U(S)
  • n与状态相关的节点所获得的增益S不能大于U(S)和小于0
  • 如果n和m是树中的节点 并且n是 , 的父节点m，即和U(n) - U(m) = g(n,m)之间的边上的增益表示从到的减少nmUnm

请参见图中的示例。 树的例子

我的目标是在树中找到保证最高增益的路径（其中路径的增益是通过将路径上边缘的所有增益相加来计算的）：

Path* = arg max_{path}  (sum g(n,m), for each adjacent n,m in path)

请注意，树在一开始是未知的，因此不需要访问整个树的解决方案（丢弃肯定不会带来最佳解决方案的那些路径）以找到最佳解决方案将是最佳选择。

注意：我在这里和这里获得了一个答案，用于离线模式下的类似问题，即当图形已知时。但是，在这种情况下，树是未知的，因此诸如 Bellman-Ford 之类的算法的性能不会比蛮力方法（如建议的那样）好。相反，我想构建类似于回溯的东西，而不是构建整个树来找到最佳解决方案（分支和绑定？）。

编辑：随着深度的增加，U(S) 变得越来越小。

4

1 回答 1

0

正如您所注意到的，可以使用分支定界来解决您的问题。只需扩展看起来最有希望的节点，直到找到完整的解决方案，同时跟踪最知名的解决方案。如果在此过程中某个节点的 U(S) 低于最知名的解决方案，则跳过它。当您没有更多节点时，您就完成了。

这是一个算法：

pending_nodes <- (root)
best_solution <- nothing

while pending_nodes is not empty
    Drop the node n from pending_nodes having the highest U(n) + gain(n)

    if n is a leaf
        if best_solution = nothing
            best_solution <- n
        else if gain( best_solution ) < gain( n )
            best_solution <- n
        end if
    else
        if best_solution ≠ nothing
            if U(n) + gain(n) < gain(best_solution)
                stop. best_solution is the best
            end if
        end if

        append the children of n to pending_nodes
    end if
end while
于 2013-06-17T14:19:51.323 回答