问题标签 [heuristics]

如果将游戏地图划分为子图，如何最小化子图之间的边？

我有一个问题，我试图通过像 pacman 或 sokoban 这样的基于网格的游戏进行 A* 搜索，但我需要找到“附件”。我说的外壳是什么意思？给定作为软约束的每个子图的顶点数的最大尺寸和最小尺寸，具有尽可能少的切割边的子图。
或者你可以说我正在寻找子图之间的桥梁，但它通常是同样的问题。

例子

基于网格的游戏地图示例 http://dl.dropbox.com/u/1029671/map1.jpg

给定一个看起来像这样的游戏，我想做的是找到外壳，这样我就可以正确地找到它们的入口，从而获得一个很好的启发式方法来到达这些外壳内的顶点。

替代文字 http://dl.dropbox.com/u/1029671/map.jpg

所以我想要的是在任何给定的地图上找到这些彩色区域。

我的动机

我之所以费心这样做，而不仅仅是满足于简单的曼哈顿距离启发式的性能，是因为封闭启发式可以提供更优化的结果，而且我不必实际执行 A* 来获得一些适当的距离计算和也用于以后在玩推箱子类型游戏时在这些围栏内增加对手的竞争性阻挡。此外，封闭启发式可用于极小极大方法，以更正确地找到目标顶点。

可能的解决方案

该问题的一个可能解决方案是Kernighan Lin 算法：

我对这个算法的问题是它的运行时间为 O(n^2 * lg(n))，我正在考虑将 A1 和 B1 中的节点限制在每个子图的边界，以减少完成的工作量。

我也不理解算法中的 c[a][b] 成本，如果 a 和 b 之间没有边是假定为 0 或无穷大的成本，或者我应该根据一些启发式方法创建边。

你知道当 a 和 b 之间没有边时 c[a][b] 应该是什么吗？您认为我的问题适合使用多级方法吗？为什么或者为什么不？您对如何减少使用 kernighan-lin 算法完成我的问题的工作有一个好主意吗？

我正在尝试对 Stack Overflow 数据转储运行一些统计信息，为此我想知道每个用户的时区。但是，我所要做的只是完全自由格式的“位置”字符串。

我要强调的是，我只是在寻找时区的近似值；当然，一般来说这是一个无法解决的问题。但是，许多人填写了他们的国家、州和/或城市，这应该会给出一个很好的指示。如果它在其他情况下失败也没关系。它不必可靠，不必准确，不必涵盖所有基础。

我不想在这上面浪费太多时间，所以我想知道是否有一些代码可以做出合理的猜测。任何语言、平台、API 或库都可以。有任何想法吗？

我希望就线程管理的使用以及任务并行库的使用获得一些建议，因为我不确定我是否走在正确的道路上。最好的可能是我概述了我正在尝试做的事情。

给定一个问题，我需要使用基于启发式的算法生成解决方案。我从计算一个基本解决方案开始，我认为这个操作不能并行化，所以我们不需要担心。

生成初始解决方案后，我想触发n 个线程，试图找到更好的解决方案。这些线程需要做几件事：

1. 它们需要使用不同的“优化指标”进行初始化。换句话说，他们试图优化不同的东西，在代码中设置优先级。这意味着它们都运行略有不同的计算引擎。我不确定我是否可以用 TPL 做到这一点。
2. 如果其中一个线程找到了比当前最知名的解决方案更好的解决方案（需要在所有线程之间共享），那么它需要更新最佳解决方案，并强制许多其他线程重新启动（这同样取决于优先级的优化指标）。
3. 我可能还希望跨线程组合某些计算（例如，为某种解决问题的方法保留概率的联合）。不过，这可能更可选。
4. 整个系统显然需要是线程安全的，我希望它尽可能快地运行。

我尝试了一个涉及管理我自己的线程并关闭它们等的实现，但它开始变得相当复杂，我现在想知道 TPL 是否会更好。我想知道是否有人可以提供任何一般性指导？

谢谢...

我想找到一个确定性退火代码的开源示例。它几乎可以是任何语言：C、C++、MatLab/Octave、Fortran。我已经找到了用于模拟退火的 MatLab 代码，因此最好使用 MatLab。这是描述该算法的论文。

确定性退火是一种尝试找到成本函数的全局最小值的优化技术。该技术旨在能够使用随机性探索大部分成本表面，同时仍使用本地信息执行优化。该过程首先更改成本函数以引入随机性概念，从而允许探索大面积区域。每次迭代的随机量（由香农熵 [2] 测量）都受到约束，并执行局部优化。逐渐地，施加的随机性降低了，因此在终止时，算法优化了原始成本函数，产生了原始问题的解决方案

当我在这里提出问题时，自动搜索返回的问题的工具提示给出了问题的前一小部分，但是其中相当一部分没有给出比标题。有没有人知道如何制作过滤器以剔除无用的问题？

我的第一个想法是修剪任何仅包含某些列表中的单词的前导句子（例如，停用词，加上标题中的单词，加上与标签相关性非常弱的 SO 语料库中的单词，即同样可能无论标签如何，都会出现在任何问题中）

I'm sure you've all heard of the "Word game", where you try to change one word to another by changing one letter at a time, and only going through valid English words. I'm trying to implement an A* Algorithm to solve it (just to flesh out my understanding of A*) and one of the things that is needed is a minimum-distance heuristic.

That is, the minimum number of one of these three mutations that can turn an arbitrary string a into another string b: 1) Change one letter for another 2) Add one letter at a spot before or after any letter 3) Remove any letter

Examples

I've tried many algorithms out; I can't seem to find one that gives the actual answer every time. In fact, sometimes I'm not sure if even my human reasoning is finding the best answer.

Does anyone know any algorithm for such purpose? Or maybe can help me find one?

(Just to clarify, I'm asking for an algorithm that can turn any arbitrary string to any other, disregarding their English validity-ness.)

我正在寻找一个包/模块/函数等，它大约是 Arc90 的 readability.js 的 Python 等价物

http://lab.arc90.com/experiments/readability

http://lab.arc90.com/experiments/readability/js/readability.js

这样我就可以给它一些 input.html 并且结果是该 html 页面的“主要文本”的清理版本。我想要这个，以便我可以在服务器端使用它（与仅在浏览器端运行的 JS 版本不同）。

有任何想法吗？

PS：我已经尝试过 Rhino + env.js 并且该组合有效，但性能无法接受，清理大部分 html 内容需要几分钟时间 :( （仍然找不到为什么会有如此大的性能差异）。

我正在编写用于生成时间表的遗传算法。

目前我正在使用这两种启发式方法：

1. 一天内讲座之间的孔数（相关）（孔少 -> 分数更高）
2. 每个小时都有一些价值，因此对于每个时间表，我都会对讲座进行时的小时数进行总和。（在更合适的时间上课 -> 更高的分数）

我想平衡这两种启发式方法，因此该算法不会对任何一种都有利。实现这一目标的最佳方法是什么？

假设我有一组对象，S. 有一种算法f，给定一个集合在其上S构建一定的数据结构D：f(S) = D. 如果S很大和/或包含非常不同的对象，则会D变得很大，以至于无法使用（即不适合分配的内存）。为了克服这个问题，我分成S几个不相交的子集：S = S1 + S2 + ... + Sn并为每个子集构建Di。使用n结构比使用结构效率低，但至少这样我可以适应内存限制。由于大小的f(S)增长速度比S自身快，组合大小Di远小于大小D。

然而，仍然希望减少n，即子集的数量；或减小 的组合大小Di。为此，我需要以S每个Si包含“相似”对象的方式进行拆分，因为f如果输入对象彼此“足够相似”，则会产生较小的输出结构。

问题是，虽然对象的“相似性”S和 do 的大小f(S)相关，但除了评估之外，没有办法计算后者f(S)，而且f速度不是很快。

我目前拥有的算法是迭代地将每个下一个对象从 中添加S到其中一个中Si，这样就可以尽可能少地（在这个阶段）增加组合Di大小：

这给出了实际有用的结果，但肯定远非最佳（即最小可能的组合大小）。另外，这很慢。为了加快速度，我只计算size(f(Si + {x})) - size(f(Si))那些i与.xSi

这类问题有什么标准方法吗？

我知道分支和边界算法系列，但它不能在这里应用，因为它会非常慢。我的猜测是，根本不可能在合理的时间内计算S出in 的最佳分布。Si但是有一些常见的迭代改进算法吗？

编辑：

正如评论所指出的，我从未定义过“相似性”。事实上，我想要的只是分割成Si组合大小Di = f(Si)最小或至少足够小的子集。“相似度”仅被定义为这一点，不幸的是，它根本无法轻松计算。我确实有一个简单的近似值，但仅此而已——一个近似值。

所以，我需要的是一个（可能是启发式的）算法，sum f(Si)考虑到没有简单的方法来计算后者——我只需要一个近似值来丢弃不太可能给出好的结果的情况。

关于字符串和字符串生成器之间的区别已经提出了很多问题，并且大多数人认为字符串生成器比字符串更快。我很想知道字符串生成器是否太好了，那么为什么会有字符串呢？此外，有人可以给我一个例子，字符串比字符串生成器更有用吗？