Alg*_*lgo 2 artificial-intelligence heuristics
我知道可接受的启发式函数低估了目标的实际成本，但我想得出结论，即两个可允许的启发式函数（h1 和 h2）之和的启发式函数 h3 都可以接受，如果没有关于 h1 的更多信息，则不能接受并给出 h2。你认为这是正确的主张吗？
谢谢
小智 5
可接受的启发式算法永远不会高估从节点到目标节点的最小成本路径的成本。因此，启发式特定于特定状态空间，也特定于该状态空间中的特定目标状态。对于该搜索空间中的所有状态，它必须是可接受的。为了帮助记住它是“从不高估”还是“从不低估”，只需记住可接受的启发式方法过于乐观。它将导致 A* 搜索结果证明比最佳路径成本更高的路径。它不会通过产生过高的启发式 h 值来阻止 A* 扩展处于最佳路径上的节点。对启发式的更强要求是它是一致的，有时称为单调。如果启发式 h 的值沿路径不减少，则它是一致的。在数学上，
我认为最初的问题尚未得到解答 - 也没有出现在之前答案的评论中。
如果 h1 和 h2 是可接受的，则 h3 = h1 + h2 通常是不可接受的，尽管在特殊情况下可能会发生这种情况（即，零启发式是可接受的，并且它可以多次添加到另一个启发式任意值而不违反可接受性）。这很容易看出。想象一个问题，其中所有状态要么是目标状态，要么只需一次成本为 1 的操作即可将它们转变为目标状态。因此，任何为目标状态返回 0、为非目标状态返回 1 的启发式都是可接受的。让我们成为一个非目标状态。那么，h1(s)=h2(s)=1都成立，但h3(s)=2则不成立。
当然，采用最大允许启发式也是允许的（这也很容易看出），因此 h3 = max(h1,h2) 将主导 h1 和 h2 （即，它至少与它们中的任何一个一样好）并且仍然可以被受理。
除了采用一组可接受的启发式的最大值将它们组合成更准确的启发式之外，还有更复杂的方法。我所知道的最突出的技术称为成本分区：当确保没有任何操作可以为h1和h2贡献成本时，将它们的值相加是安全的。利用这一点的基本思想是（我想，你自己检查一下！）通过创建原始问题的n 个问题实例（当针对n 个启发式时）并确保每当一个动作在问题编号i中具有其原始成本m（即用于启发式数字i )，那么该操作在所有其他n-1问题中的成本为0。这样，所有问题/启发式仍然具有所有可用的操作，同时保证其值的总和不会被高估，即可接受（假设所有n启发式也是可接受的）。我认为文章“抽象启发式的最佳可接受的组合”（http://www.sciencedirect.com/science/article/pii/S0004370210000652）详细解释了这个想法。