启发式改变的最优解

文章/答案/技术大牛

发布

2回答

algorithm、artificial-intelligence、heuristics

假设我有一个启发式h(n)，它是一致的(单调)。那么A* search f(n) = g(n) +3∗h(n)是否给出了最优解？我的理解是它不会，因为3*h(n)可能大于h*(n)

浏览 2提问于2018-02-04得票数 0

2回答

当使用可接受的启发式时，A*需要知道最优解的代价吗？

search、optimization、artificial-intelligence、a-star

我读过一些关于这个话题的堆积如山的文章，以及维基百科关于A*的文章，但是我还是有点困惑。我想这篇文章几乎完全向我解释了：如果你不知道最优路径的代价，这个搜索是否有效并保证了一

浏览 8提问于2016-05-24得票数 0

回答已采纳

1回答

对称TSP中最近邻启发式的最坏情况

greedy、traveling-salesman

实现了求解对称TSP问题的最近邻启发式算法。我想知道启发式找到的解和最优解之间是否有什么关系？在最坏的情况下，我们能从理论上说明路由长度有多高吗？

浏览 1提问于2013-11-17得票数 0

2回答

用星求路径的启发式函数

algorithm、graph-algorithm、path-finding、a-star、heuristics

我正试图为以下问题找到一个最优解表示在每个节点内的数字表示为节点的(x,y).The相邻节点总是有一个y值，即(当前节点y值+1)。当我们从一个节点到其adjacentThere节点时，x值的变化要花费1，如果x.No 2节点的值没有变化，具有相同y值的y2节点的值被认为是相邻的。最优解是成本最低的，我正在考虑用A*路径查找算法来寻找最优解</em

浏览 4提问于2012-02-04得票数 5

回答已采纳

1回答

为什么允许不一致启发式的A找到非最优解？*

algorithm、search、graph-theory、a-star、heuristics

我知道，具有可接受的不一致启发式的A*不会找到最优解，但我很难找到实例，它何时会发生。由于这种思想，我找不到例子--在将目标节点(具有非最优f(n))插入优先级队列后，优先级队列还必须包含节点，例如位于最优路径上的node_1。优先级队列中的node_1的f(n)必须小于目标节点的f(n)，因为我们使用的是允许的启发式。这就是为什么node_1将

浏览 1提问于2018-08-04得票数 10

回答已采纳

2回答

证明了顶点覆盖的启发式解最多是最优解的两倍。

algorithm、graph、graph-algorithm、heuristics、vertex-cover

我得到的启发式解决方案是：我被问到了这样一个问题：“显示这个启发式最多是顶点覆盖的最优解的两倍”。

浏览 5提问于2016-10-25得票数 1

回答已采纳

2回答

AI -启发式函数要求

algorithm、function、search、artificial-intelligence、heuristics

关于人工智能(AI)中的Huristic函数，我有一个问题。我知道我们应该寻找单调和可接受的启发式函数。为什么要求函数为admissible?What是单调启发式函数的优点？

浏览 2提问于2012-02-09得票数 3

回答已采纳

2回答

为什么在算法中使用启发式会失去渐近最优性？

algorithm、heuristics、asymptotic-complexity、computation-theory

我读到了一些几何路由算法，它说当在主算法的一个版本中使用启发式算法时，它可能会提高性能，但会失去渐近最优性。为什么会这样呢？我们应该更喜欢渐近最优性而不是更好的性能吗？有没有一个人应该倾向于渐近最优的典型情况？是否有已知的基准？

浏览 1提问于2013-07-15得票数 0

回答已采纳

3回答

列生成是精确算法还是启发式算法？

optimization

我知道列生成给出了一个最优解，它可以与其他启发式方法一起使用。但是，这是否使它成为一个精确的算法呢？提前谢谢。

浏览 4提问于2017-04-20得票数 2

2回答

旅行商(TSP)性能

algorithm

谁能告诉我，我如何比较TSP最优和启发式？我已经实现了TSP，但不知道如何比较它们。实际上，我如何找到TSP的最优成本？有什么方法或猜测吗？谢谢

浏览 1提问于2011-12-04得票数 1

1回答

在扩展图时求最小生成树(带条件)

math、logic、mathematical-optimization、discrete-mathematics

为此，我已经有了最小生成树，它认为对起始点总是在他的端点之前。现在，我想添加另一对节点。现在，我试图找到解决这一问题的最有效的解决方案。我现在的想法是：找到离新起点最

浏览 3提问于2014-01-15得票数 1

6回答

三维装箱算法

algorithm、language-agnostic、mathematical-optimization、np-hard、bin-packing

我面临着一个三维装箱问题，目前正在进行一些初步研究，看看哪些算法/启发式算法目前能产生最好的结果。由于这个问题是NP困难的，我不希望在每种情况下都能找到最优解，但我想知道：2)最好的启发式求解器是什么？3)有哪些现成的解决方案可以进行一些实验？

浏览 7提问于2010-02-03得票数 40

2回答

8谜题:可解性与最短解

java、algorithm、artificial-intelligence、sliding-tile-puzzle

我现在想要修改代码以使用启发式。如果有人能回答以下两个问题，我将不胜感激：我们如何决定一个8的谜题是否可以解？有人能用一种简单的语言来解释吗？给定一个启发式算法，它是否保证使用A*算法给出最短解？更具体地说，开放列表中的第一个节点是否总是有一个深度(或如此胖的移动次数)，即打开列表中所有节点的最小深度？编辑:为什么一个可接受

浏览 2提问于2013-02-17得票数 8

1回答

A算法中的星星是什么意思？*

search、artificial-intelligence、graph-algorithm、a-star、heuristics

我确信，(星形)在A*算法中意味着该算法是可接受的，也就是说，如果存在该路径(当所使用的启发式是乐观的)，则保证该算法在图中找到最短路径。我说的对吗？我没有成功地寻找任何关于这个主题的信息，但我找不到任何参考。希望这个社区中大多数有经验的用户比我更了解A*的历史。顺便说一下，我认为其他算法如IDA*，D*，SMA*，MOA*，NAMOA*，.它基于A*遵循相同的名称约定。

浏览 2提问于2016-03-05得票数 4

回答已采纳

2回答

使用贪心算法进行优化

algorithm、optimization、greedy

如果一个优化问题可以用贪心方法解决，那么它的所有最优解是否都必须包含第一个选择(即贪婪选择)？

浏览 2提问于2013-06-17得票数 2

回答已采纳

1回答

如何证明A搜索法中的可容许/一致启发式方法会导致最优解？*

graph-algorithm、a-star

我们已经在类中证明了如果树搜索中的A*是最优的，则h(n)是可容许的(可容许启发式)。如果在图搜索中使用A*找到最优解，则h(n)是一致的。如果我们假设A*可以找到最优解，我们证明了它的可容许性和相合性。这表明在图/树搜索中，一致性/admissible是最优的必要条件。然而，我不太确定如何证明它们也都是充分条件。我试着找出它，但我仍然找不到

浏览 6提问于2020-08-28得票数 3

2回答

A搜索给出的次优解*

search、artificial-intelligence、heuristics

我不明白下面的图是如何给出一个A*搜索的次优解的。上面的图是一个例子，其中A*搜索给出了一个次优解，即启发式是可接受的，但不一致。每个节点都有一个与之对应的启发式值，并给出了遍历节点的权重。我不明白A* search如何扩展节点。

浏览 1提问于2014-09-13得票数 5

3回答

预置一种遗传算法

genetic-algorithm

我正在研究一个非常大规模的问题，我有一个启发式算法，它给出了一个相当好的解决方案，此外，遗传算法的启发式效果也很好。我想知道是否有任何增益的预播种遗传算法与启发式解决方案，如果是的话，如何。

浏览 4提问于2013-10-23得票数 2

回答已采纳

2回答

来自点列表c++的最佳路径

c++、algorithm、path、euclidean-distance

我有一个请求:我有一个点的列表，对于每个点，我都有X，Y坐标。A (xa，ya)，B (xb，yb)，C (xc，yc)，D (xd，yd)，E (x，y)我使用计算两点之间的欧几里得距离我该怎么做呢？

浏览 0提问于2012-04-15得票数 1

1回答

8-拼图的复合启发式

math、artificial-intelligence、mathematical-optimization、sliding-tile-puzzle

在阅读“人工智能”(一种现代方法)时，我遇到了从给定问题的子问题的解决成本中得出启发式的概念。此外，与简单的启发式方法(如 )相比，这种方法的性能有了很大的提高。我一直试图把我的头脑集中在复合启发式算

浏览 3提问于2016-03-18得票数 1

回答已采纳

点击加载更多