问题标签 [heuristics]

我正在用星算法做 8 个谜题求解器。我在这个求解器中实现了曼哈顿和错位的启发式函数。在某些情况下，求解器可以正常工作。但在某些情况下，找到解决方案需要花费大量时间。我认为我的问题之一是在打开列表中查找具有最低值的节点的函数（等待扩展）。

那么找到最低 f_score 值的最佳方法是什么？只需找到最小值，否则我们必须在有状态要添加时修改列表（添加状态时对列表进行排序），以便最小值将位于第一个位置。

您有一张方形瓷砖地图，您可以在其中向 8 个方向中的任何一个方向移动。假设你调用了一个函数cost(tile1, tile2)，它告诉你从一个相邻的瓦片移动到另一个瓦片的成本，你如何找到一个既可接受又一致的启发式函数 h(y,goal)？给定这个设置，寻找启发式的方法是否可以概括，或者它会根据cost功能而有所不同？

我想代表游戏 connect6 wiki（也许谓词石头（P，X，Y），其中 P 是玩家，X，Y 是坐标很好）。我也想用任何好的启发式方法来解决问题（制造对手）。你能给我一些关于 Prolog 中游戏 AI 的文章的提示吗？谢谢

我正在对医疗内容交付系统进行可用性研究，并计划使用 CHI 论文中的一些启发式方法进行启发式评估。但是，由于关注的领域与论文略有不同，我不确定是否所有启发式方法是否适用以及我是否应该将它们用作指导方针。

您将如何处理这种情况，您会创建自己的启发式方法还是使用现有的启发式方法并对其进行调整以适应您的流程？

谢谢

我很难让 H 和 G 正常工作。发生的事情是，当我运行程序时，它有时会找到最佳路径，有时会避开到达该位置的路。

以下是正在发生的事情的一些屏幕截图：

找路好

错误的路径查找

这是我目前对 F、H 和 G 的设置：

谢谢！

我有一个问题已被有效地简化为多个推销员的旅行推销员问题。我有一个从初始位置访问的城市列表，并且必须访问所有销售人员有限的城市。

我正在尝试提出一种启发式方法，并想知道是否有人可以伸出援手。例如，如果我有 20 个城市和 2 个推销员，我想到的方法是两步法。首先，将 20 个城市随机划分为 10 个城市，每个城市有 2 个推销员，我会发现每个城市的旅行好像对于几个迭代都是独立的。之后，我想交换或分配一个城市给另一个推销员并找到旅行。实际上，这将是一个 TSP，然后是最小制造时间问题。这样做的问题是它太慢了，而且交换或分配一个城市的好邻居生成是困难的。

任何人都可以就我如何改进上述内容提出建议吗？谢谢。

我有一个问题已被有效地简化为多个推销员的旅行推销员问题。我有一个从初始位置访问的城市列表，并且必须访问所有销售人员数量有限的城市。

我正在尝试提出一种启发式方法，并想知道是否有人可以伸出援手。例如，如果我有 20 个城市，有 2 个销售员，我想到的方法是两步法。首先，将 20 个城市随机分成 10 个城市，每个城市有 2 个推销员，我会发现每个城市的巡演好像是独立的几次迭代。之后，我想交换或分配一个城市给另一个推销员并找到旅行。实际上，这将是一个 TSP，然后是最小制造时间问题。这样做的问题是它太慢了，而且交换或分配一个城市的好邻居生成是困难的。

任何人都可以就我如何改进上述内容提出建议吗？

编辑：

每个城市的地理位置都是已知的，销售人员在同一个地方开始和结束。目标是最小化最大旅行时间，使这种最小制造时间问题。因此，例如，如果 salesman1 需要 10 小时，而 salesman2 需要 20 小时，则最长行程时间为 20 小时。

我将现实世界的问题抽象为以下问题：

• X 是所有可能的字母排列的池。
• Y 是一个字符串池。
• F 是一个函数，它从 X 中获取一个候选 x，并根据 x 是否属于 Y 返回一个布尔值。

F 很贵，X 很大。从 Y 中提取尽可能多的结果的最有效方法是什么？误报是可以的。

概括

我正在尝试设计一种启发式方法来匹配翻译中的句子（从原始语言到翻译语言），并希望得到指导和提示。也许有一个启发式已经做了类似的事情？所以给定两个文本文件，我希望能够匹配句子（所以我可以挑选一个句子并说这是那个句子的翻译）。

细节

输入文本将是翻译小说。所以我不希望翻译是字面的，尽管使用谷歌翻译之类的东西可能是测试启发式准确性的好方法。

为了帮助我，我有一个库，它可以修饰翻译文本的内容，并为我提供句子中单词的定义。我知道的其他事情：

• 保留章节和顺序；我知道第三章的第一句话会与翻译的第三章的第一句匹配（注意，这并不完全正确；第一句可能会匹配前两句，甚至第二句）
• 我可以计算整体大小（字符、句子、段落）；这可以让我了解句子大小的平均差异（例如，翻译可能长 30%）。

看看我的一些书，翻译版的句子比原文多出 30% 左右。

执行

（如果重要的话）

• 我打算用 Java 来做这件事——但我并不那么大惊小怪——任何语言都可以。
• 我不太关心速度。

我想为了确保匹配，可能需要一些用户反馈。就像说“是的，这句话肯定和那句话匹配”。这将为启发式提供更多立足点。这意味着用户需要对语言有一点熟练程度。

背景

（对于那些有兴趣的人）

我想做这个的原因是我希望它有助于我的外语学习。我正在学习日语，发现很难找到“好”的材料（其中“好”是由我喜欢的东西定义的）。已经有工具可以对视频中的字幕做类似的事情（更简单的任务 - 使用视频的时间信息）。但据我所知，没有任何文本。

有一个包含 N 个整数的集合 S，每个整数的值 1<=X<=10^6。问题是将集合 S 划分为 k 个分区。分区的值是其中存在的元素的总和。分区是以这样的方式完成的，集合 S 的总值在 k 个分区中公平分布。还需要定义公平的数学含义（例如，目标可以是最小化分区值与集合 S 的平均值的标准偏差（即 sum(S)/k)）

例如 S = {10, 15, 12, 13, 30, 5}, k=3

一个好的分区是 {30}, {10, 15}, {12, 13, 5}

一个坏的分区是 {30, 5}, {10, 15}, {12, 13}

第一个问题是在数学上表达一个分区优于另一个分区的条件。第二个问题是如何解决问题。问题是NP-Hard。有什么启发式方法吗？

在我试图解决 N <= (k*logX)^2 的问题中，K 从 2 到 7 不等。

==================================================== =================================

基于其他相关的 SO 问题，评估分布有两个合理的函数：

a) 最小化具有最大值的分区的值。

再想一想，这不是一个好的指标。考虑，一组 {100, 40, 40} 被划分为三个子集。该指标不区分以下两种分布，即使其中一种明显优于另一种。

分布 1：{100}、{40}、{40} 和分布 2：{100}、{40、40}、{}

b) 最小化给定分区中任意两个值之差的最大值，即最小化 max|AB| 对于任何 A、B