问题标签 [heuristics]

我有一组 N 个对象，我想计算一个 NxN 距离矩阵。有时我的 N 个对象集非常大，我想通过仅计算距离比较的子集来计算 NxN 距离矩阵的近似值。

谁能指出我计算全距离矩阵近似值的方向？我有一些想法，但我想避免重新发明轮子。

编辑：算法类型的一个示例将利用这样一个事实，即如果对象 A 和对象 B 之间的距离非常小，并且对象 B 和对象 C 之间的距离非常小，则必须有一些物体 A 和 C 之间的距离很短。

我有一个简单的问题：

• 我在 div 中有一个图像。
• 为了使页面更美观，我将为图像添加一些额外的填充。

与其盯着它看，我想知道：

我可以遵循任何 CSS 填充启发式方法吗？

我在想像 Jakob Nielsen 这样的人可能已经建立了一些关于页面布局和填充（即最小像素填充或比例）的最佳实践。

• 我并不是说这是一个特别难以解决的问题。
• 但这是一个很可能会再次出现的问题。
• 而且我想要一些启发式方法来指导我将来的填充选择。

任何帮助，将不胜感激。

我在 Pacman 中找到了很多关于鬼魂 AI 的参考资料，但没有一个提到在 Pacman 吃掉一个鬼魂后，眼睛是如何回到中央鬼洞的。

在我的实现中，我实现了一个简单但糟糕的解决方案。我只是在每个角落硬编码应该采取哪个方向。

有没有更好/或最好的解决方案？也许是一个通用的，适用于不同的关卡设计？

对于我正在制作的游戏，我有一个数字列表——比如 [7, 4, 9, 1, 15, 2]（以此命名A）——还有另一个数字列表——比如 [11, 18 , 14, 8, 3]（命名为B）——提供给我。目标是找到所有数字组合A，加起来等于B. 例如：

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

...等等。（为此，1 + 2与 相同2 + 1。）

对于像这样的小列表，仅暴力组合是微不足道的，但我面临着看到数千到数万个这样的数字的可能性，并且将在应用程序的生命周期内重复使用此例程。是否有任何优雅的算法可以在合理的时间内以 100% 的覆盖率完成此任务？如果做不到这一点，我能找到任何一种体面的启发式方法，可以在合理的时间内给我一个“足够好”的组合吗？

我正在寻找一种伪代码或任何相当流行且可读的语言的算法（注意那里的“和”......；），甚至只是关于如何实施这种搜索的英文描述。

编辑添加：

到目前为止提供了很多很好的信息。谢了，兄弟们！暂时总结一下：

• 问题是 NP-Complete，所以要在合理的时间内获得 100% 的准确率，没有任何办法。
• 该问题可以看作是子集和或背包问题的变体。两者都有众所周知的启发式方法，它们可能适用于这个问题。

让想法不断涌现！再次感谢！

我正在寻找一个启发式列表，给定一个 HTML 文档和/或网页上的一组 URL，这将给出一组来自该页面的上一个/下一个链接的 URL。此外，假设您获得了基本 URL。我不需要知道链接是具体是下一个还是上一个 URL，只要它是这两个 URL 之一即可。

我已经有了一个简短的清单：

• 与 URL 相同的域和路径，但查询参数不同。
  • 基地：abc.com/story
  • 下一个/上一个：abc.com/story?p=2
    • 或者
  • 基地：abc.com/story.html?p=5
  • 下一个/上一个：abc.com/story.html?p=3
• 除了数字路径元素之外，URL 与基本 URL 相同。
  • 基地：abc.com/story
  • 下一个/上一个：abc.com/story/2
• 在 DOM/HTML 中相邻的几个链接。
  • 我知道这也可能像页眉/页脚，我必须以某种方式解释这一点......有什么想法吗？
• 文本为数字或测试为“Next”、“Previous”、“First”、“Last”、“Back”、“Forward”等单词的链接...

我知道我在这方面永远无法做到完美，但我希望获得尽可能多的覆盖范围和尽可能多的启发式方法，以期获得良好的组合或数量和质量。谢谢。

给定一个 URL、第一个 URL 所在网页的 URL、网页的 DOM 以及网页上其余 URL 的列表，我如何可靠地确定 URL 是否在页面的页眉/页脚中或者如果两者都不在？

我正在使用 C#/.NET。

我知道没有解决方案是完美的，因为网页没有语义表达，也因为一些网站/页面专门混淆了他们的页面，但我想建立一些适用于 75% 网页的逻辑。

此外，是否还有其他有助于确定 URL 在页面中的位置的信息？

我正在编写一个程序，它使用两个启发式来解决一个 24 谜题（5x5 网格）。第一个使用不正确位置的块数，第二个使用块当前位置和所需位置之间的曼哈顿距离。

我在程序中有不同的函数，它们将每个启发式与 A* 和贪婪搜索一起使用并比较结果（总共 4 个不同的部分）。

我很好奇我的程序是否错误，或者是否是拼图的限制。拼图是随机生成的，碎片被移动了几次，大部分时间（~70%）通过大多数搜索找到了解决方案，但有时它们会失败。

我可以理解为什么贪婪会失败，因为它不完整，但是看到 A* 是完整的，这让我相信我的代码中有错误。

那么有人可以告诉我这是我的思维错误还是谜题的限制？对不起，如果这措辞不好，我会在必要时重新措辞。

谢谢

编辑：

所以我相当肯定这是我做错了。这是我如何进行搜索的分步列表，这里有什么问题吗？

• 为边缘创建一个新列表，按使用的启发式排序
• 创建一个集合来存储访问过的节点
• 将拼图的初始状态添加到边缘
• 虽然边缘不是空的..
  • 从边缘弹出第一个元素
  • 如果之前访问过该节点，则跳过它
  • 如果节点是目标，则返回它
  • 将节点添加到我们的访问集中
  • 展开节点并将所有后代添加回边缘

每个人都知道，如果您想串接电子邮件，您可以使用Jamie Zawinski 的算法。但这是一个新世纪，并且有一种新的消息服务。

Twitter 上发布的线程状态更新的最佳算法是什么？

我绝对希望它处理的事情：

• 最简单的部分：使用in_reply_to_status_id, in_reply_to_user_id和in_reply_to_screen_name. （顺便说一句，找到这些值的适当文档本身就很有用！例如，此类文档显然与 from here没有关联。）

• 从提到具有@约定的用户但未明确回复特定消息的消息中推断“回复”关系的良好启发式方法。 如果您要求，这些“提及”现在会在状态的“实体”元素中提供。这些启发式可能会考虑 (a) 两次状态更新之间的时间，(b) 两个用户之间是否有后续回复等。（回复由旧式转发和附加评论组成，如user85509 所述以下 只是这种回复方式的一个例子。）

• 发生在两个以上用户之间的对话。

• 使用一组给算法的推文，或 Twitter 上的所有推文。

...但也许您可以想到更多。

我一直在考虑这个问题，所以我想我会寻求建议：

我有一些爬虫进入某个站点的根目录（可以是来自 www.StackOverFlow.com、www.SomeDudesPersonalSite.se 甚至 www.Facebook.com 的任何内容）。然后我需要确定我正在访问什么“主页”。不同的类型可能是：

• 论坛
• 博客
• 链接目录
• 社交媒体网站
• 新闻网站
• “一个人的网站”

我已经集思广益了一段时间，最好的解决方案似乎是点系统的一些启发式方法。我的意思是不同的趋势对不同的类型给出了一些分数，然后程序会做出猜测。

但这就是我卡住的地方。你如何检测趋势？

• 目录可能很容易：如果站点索引/传出链接非常高，目录应该得到几个点。
• 新闻网站/博客可能很容易：如果索引的大量网站都有日期时间，那么这些类型应该得到几分。

但我真的找不到太多趋势。

SO：我的问题是：关于如何做到这一点的任何想法？

非常感谢..

对于显示产品信息的页面，我们必须从一组显示相同内容但具有不同格式（gif、png、jpg 等）、不同质量（jpeg 压缩）、不同的图像中选择最佳产品图像尺寸（缩略图，小，中，大）等。

选择取决于用户的浏览器、页面的当前大小、图像的用途等。

我们当前的解决方案是根据当前的需求构建一个 sql 查询，可能看起来像这样：

这是一个简单的例子，原来的例子要复杂得多。创建此语句的 java 代码使用了很多 if 和 case，并且开始变得非常难看。

在 Java 中实现这种启发式的最佳方法是什么？有没有图书馆可以提供帮助？也许沿着定义规则对象的路线：

我搜索了规则引擎，甚至有一个 JSR 和一些开源规则引擎，但它们似乎都是在处理商业规则。

我有强烈的感觉，我们正在重新发明轮子，而且我们根本找不到任何解决方案，因为我们不知道这些东西的正确名称;-)

任何帮助将不胜感激！