algorithm - 最长路径 A*、可采纳启发式算法和最优性

Question

我正在研究一种改进的 A-Star 算法。它试图找到权重最高的路径，而不是试图找到最短路径。

我有一些类，每个类都有一个唯一节点列表。每个节点都有自己的值(value)。我正在尝试确定每个类中节点的最佳可能组合，以确定具有最大权重的组合或路径。为此，我将这些类视为一棵树，每个级别都包含单个类中的节点。

然后我使用 A-Star 搜索这棵树，或者更具体地说，我基于搜索堆栈搜索我的树。一旦探索了一个节点，它的 child 就会根据它们的权重(加上它们的祖先权重)加上可能的 future 权重(我的启发式)按排序顺序插入。然后选择堆栈顶部具有最高值的进行下一步搜索。

为了做到这一点，我有一个高估的启发式方法；它永远不会低估最优解。

如果我正在寻找最高权重而不是最低权重，这种启发式是否可接受，因此我的算法是否最优？

我还应该说我的算法目前正在运行，而且它的运行速度比暴力破解所有可能的路径快得多，我只是想知道我的解决方案是否是最优的。

PS:当前算法的正式定义。

令 S = {S₁, S₂, ... , S_n}

并且每个 S_i 都有一组项和一个 NULL，它表示未从该集合中选择的项。

S_i = {I₁, I₂, ..., I_m, NULL}

而且每个项目只存在于一个集合中，IE S_i U S_j = S_i + S_j

每个项目，I_i 都有一个相关联的值，V_i。

问题是从每组中选择最多 M 个报价，当总和产生最高值时。我将此选择称为路径 P_i。路径可以是完整的，这意味着它可以从所有 S 中进行选择，也可以是部分的，其中只包含 x 个提议。还有米

此外，存在一个函数 IsCompatable(path)，如果路径兼容则返回 true。路径是兼容的还是完全任意的。最大值路径必须兼容。这就是为什么我不能简单地从每个集合中选择 M 个最大的项目。

此外，每个集合都包含一个 NULL 项目，因此无需从该集合中选择一个项目。

平凡算法将创建一个搜索树并生成 S 中所有可能的项目组合，每条到树叶的路径都被称为一条路径。

设G(P)为部分路径的当前值(每一项的求和值)。设 H(P) 是对 future 路径值(value)的估计(启发式)。H(P) = 来自 Y S_i in S 的 Y 项的 Y 值。每个项目是 S_i 中具有最大值的项目，其中 i > len(P ). Y = M - 部分路径P的当前长度。

为了找到具有最大值的路径，我保留了一个部分路径的排序队列，按它们的值+它们可能的 future 值排序，即 G(P_i) + H(P_{我 )。我通过添加 S1 中包含的路径来初始化此队列。}

While the Queue is not empty or a path has not been found:
    p = Pop the path from the top of Q
    if p is Complete:
        A full path has been found
        return p
    find the possible children of p by adding an item to p from the next set.
    for child in Children:
        if IsCompatable(child):
            add child back to Q in sorted order on G(child) + H(child)

好了，现在我的启发式可以接受了吗？

问题描述

(这是为了使问题描述形式化而添加的。它是不完整的。)

考虑一个集合 U，划分为不相交的子集 S₁, ..., S_n。

设 f : U → ℝ 是一个为 U 中的每一项赋值的函数。

设 V 是 U 的所有子集的集合，其中最多包含来自每个 S_i 的一项，并设 V' ⊂ V 是允许解的集合。 V' 中的成员资格很容易计算。

目标是找到使 ∑_x∈P f(x) 最大化的解 P ∈ V'。

Answer 1

A* 不是为此设计的。这样的启发式方法不会起作用，因为您必须拒绝循环(否则没有解决方案)，并且如果没有到目标的路径不会创建循环，则启发式方法总是会低估与给定节点的距离......但是没有办法知道这一点。

没有解决此问题的已知通用方法，因为最长路径问题是 NP 难问题，如哈密顿路径问题的归约所示(参见 Wikipedia)。