问题标签 [heuristics]

http://lab.arc90.com/experiments/readability/是一个非常方便的工具，可以以非常易读的方式查看杂乱的报纸、期刊和博客页面。它通过使用一些启发式方法并找到网页的相关正文来做到这一点。它的源代码也可以在http://lab.arc90.com/experiments/readability/js/readability.js获得

我的一些同事引起了我的注意，因为我正在努力使用 jQuery 来获取任何报纸的“正文” | 期刊 | 博客 | 等网站。我当前的启发式（和 jQuery 中的实现）使用类似的东西（这是在 Firefox Jetpack 包中完成的）：

所以它就像“去抓取 DIV 中的段落并检查不相关的字符串，如'script'”。我已经尝试过了，大多数时候它可以抓取网络文章的正文，但是我想要一个更好的启发式或者更好的 jQuery 选择机制（甚至更短？）。

你有更好的建议吗？

PS：也许“找到最里面的DIV（即没有任何DIV类型的子元素）并去抓住他们的

s only”对于我目前的目的来说是一个更好的启发式方法，但我不知道如何在 jQuery 中表达这一点。

对于具有用户名/密码文本输入字段的网站，浏览器通常会方便地为您记住它们（在我的情况下，Safari 将它们放在我的 OS X 钥匙串中）。

某些网站根本不会发生这种情况。想到的第一个例子是 vBulletin 论坛。这意味着您不能使用复杂/随机密码，除非您愿意每次都从某个地方复制和粘贴它。

浏览器是否通过“这看起来像用户名/密码”启发式方法检测何时提供记住这些信息并且有时会失败？

这在幕后是如何运作的？

编辑：Safari 用户，看看这个组合：

http://8-p.info/greasekit/

http://userscripts.org/scripts/show/8021

http://userscripts.org/scripts/show/28696

无论如何，是否可以确保除了广度优先搜索之外的任何东西都能满足最少数量的启发式算法？也许更多的解释会有所帮助。

我有一个随机图，很像这样：

从左上角开始，我需要知道到达右下角所需的最少步数。每组连接的颜色被假定为单个节点，因此例如在这个随机图中，顶行的三个 1 都被视为单个节点，并且每个相邻（非对角线）连接的节点都是可能的下一个状态。所以从一开始，可能的下一个状态是第一行中的 1 或第二行中的 3。

目前我使用双向搜索，但树大小的爆炸性增长很快。在我的一生中，我一直无法调整问题，以便我可以安全地为节点分配权重并让它们确保最少的状态更改数量以达到目标，而不会变成广度优先搜索。将此视为城市地图，启发式将是达到目标的最少转弯次数。

最少的转数是该搜索的结果，这一点非常重要，因为该值是更复杂问题的启发式算法的一部分。

我知道那里有一些调度问题是 NP-hard/NP-complete ......但是，没有一个是这样说明的，以表明这种情况也是 NP。

如果您有一组任务受限于startAfter、startBy和duration都试图使用单个资源......您能否解决计划或确定如果不进行详尽搜索就无法解决？

如果答案是“对不起，朋友，但这是 NP-complete”，那么最好的启发式方法是什么？有没有办法减少 a) 解决计划和 b) 确定无法解决的时间日程。

我已经（在序言中）通过实现“最小窗口优先”启发式的递归实现了基本的冲突解决目标。这实际上很快就能找到解决方案，但在寻找无效时间表方面却异常缓慢。有没有办法克服这个问题？

耶复合问题！

抱歉，如果这似乎是一个模糊的问题，但它一直困扰着我一段时间。

在我的日常工作中，我编写的一些代码变得非常复杂。并不是说它通常是非常技术性的，而是问题域本身是一个复杂的问题，处理空间数据以及许多其他事情。我很确定我的 NDA 会禁止我提供任何关于我正在做的事情的细节，所以很遗憾，我必须保持这个非常笼统。

现在，我完全赞成降低复杂性，所以我尽量找到正确的抽象，但是有没有办法通过明确地不处理手头的实际问题，而是一些可以操作的隐喻来进一步减少它翻译成我以后想要的实际结果？

当然，由于这个领域本身就很复杂，..我试过但失败了（很多次！）找到正确的比喻:-(

所以我的问题是，是否有人已经完成了这项工作并找到（甚至一半找到）一种结构化的方法来推断一组给定的编程问题的适当隐喻或启发式方法？

如果这看起来有点奇怪，我再次道歉。我只是想找到成为更好程序员的新方法。

提前致谢。

我对整个旅行推销员问题以及stackoverflow都是新手，所以如果我说的一些不太正确的话，请告诉我。

介绍：

我正在尝试为涉及多个国家（地区）内的多个城市（节点）的游戏编写利润/时间优化的多交易算法，其中：

• 在两个相连的城市之间旅行的实际时间总是相同的；
• 城市不是线性连接的（你可以同时在一些城市之间传送）；
• 一些国家（地区）有传送路线，使通过其他国家的最短路径可用。
• 旅行者（或商人）对他的钱包、他的货物的重量以及在某个贸易路线上可交易的数量都有限制。贸易路线可以跨越多个城市。

问题参数：

内存中已经存在一个数据库（python：sqlite），它根据源城市和目的地城市保存交易，中间的最短路径城市作为数组和数量，以及总资本回报率的限制因素（或在没有任何因素限制的情况下，那么只有总资本回报率最高的方法）。

• 我正在尝试在某个预设的时间段（即 30 分钟）内找到最佳利润
• 穿越到一个新城市的行为实际上是同时发生的
• 穿越城市地图通常需要相同的定义时间（即 2 分钟）
• 发起第一个或任何新交易的行为与穿越一个城市地图所需的时间相同（即 2 分钟）
• 我的起点可能实际上没有有效的交易（我必须前往第一个/最近/最好的交易）

到目前为止的伪解决方案

优化

首先，我意识到因为我对所花费的时间有限制，并且我知道每一跳需要多长时间（包括启动交易的 -1），我可以将图表限制为跳数小于或等于 的所有交易max_hops=int(max_time/route_time) -1。我删除了贸易数据库中不属于这个时间限制的元素，修剪了最短路径长度大于max_hops.

我再次进入交易数据库，其中包括我当前城市和不是我当前城市的所有现有交易的起始城市之间的最短路径，并给它们 0% 的回报。我会将这些限制在城市跳数少于 的地方max_hops，并且我还将计算当前城市到起始城市加上交易最短路径跳数的城市是否会超过max_hops并删除那些超过此限制的城市。

然后我采取剩余的交易，(current_city->starting_city)并在所有目的地和起始城市之间添加回报为 0% 的贸易路线，其中啤酒花不超过max_hops

然后，我对所有不在交易数据库中的城市作为起始城市、目的地城市或最短路径城市阵列的一部分进行最后一次修剪。

图表搜索 我留下了一个在时间限制（即 30 分钟）内可行的（小得多的）交易图表。

因为所有连接的节点都是相邻的，所以默认情况下，连接的权重都是 1。我将 %return 除以交易中的跳数，然后取倒数并加上 + 1（这意味着一个权重为 1.01 100％返回路线）。在收益率为 0% 的情况下，我添加 ... 2？

然后它应该返回最有利可图的路线......

问题：

大多，

1. 当我有多余的钱或空间时，如何增加走多条路线的能力，并通过离散的路径寻找单条贸易路线的路线？由于商品在城市内以多种价格和数量销售的性质，会有很多重叠的路线。

2. 我如何惩罚启动新的贸易路线？

3. 在这种情况下，图形搜索甚至有用吗？

在旁注中，

3. 我应该（或不应该）对图表进行哪些类型的修剪/优化？
4. 我的加权方法正确吗？我有一种感觉，它会给我不成​​比例的重量。我应该使用实际回报而不是百分比回报吗？
5. 如果我在 python 中编码，那么python-graph之类的库是否适合我的需求？或者它会为我节省很多开销（据我所知，图形搜索算法可能是计算密集型的）来编写一个专门的函数？
6. 我最好使用 A* 搜索吗？
7. 我应该预先计算交易数据库中的最短路径点并最大化优化，还是应该将其全部留给图形搜索？
8. 你能注意到我可以改进的地方吗？

启发式和算法之间有什么区别？

今天我读到有一个名为WinCalibra的软件（向下滚动一点），它可以将带有属性的文本文件作为输入。

然后，该程序可以根据算法的输出值优化输入属性。有关更多信息，请参阅本文或用户文档（请参阅上面的链接；遗憾的是 doc 是一个压缩的 exe）。

你知道在 Linux 下运行的其他软件可以做同样的事情吗？（首选开源）

编辑：因为我需要这个用于 java 应用程序：我应该将我的研究投资于像gaul或watchmaker这样的 java 库吗？问题是我不想推出自己的解决方案，也没有时间这样做。您是否有指向 Calibra 等开箱即用应用程序的指针？（互联网搜索不成功；我只找到图书馆）

尽管我没有找到令人满意的解决方案，但我决定放弃赏金（否则没有人会受益）:-(（开箱即用的应用程序）

这是为http://cssfingerprint.com

我有一个系统（有关详细信息，请参见网站上的页面），其中：

• 我需要输出与特定特征向量匹配的类别的排序列表，并带有置信度
• 二进制特征向量是站点 ID 的列表以及此会话是否检测到命中
• 对于给定的分类，特征向量有些嘈杂（网站会从历史中消失，人们会访问他们通常不访问的网站）
• 类别是一个大的、非封闭的集合（用户 ID）
• 我的总特征空间大约有 5000 万个项目（URL）
• 对于任何给定的测试，我只能查询大约。该空间的 0.2%
• 我只能根据迄今为止的结果决定查询什么，大约 10-30 次，并且必须在 <~100 毫秒内完成（尽管我可能需要更长的时间来进行后处理、相关聚合等）
• 根据目前的结果获得人工智能对类别的概率排名有点贵；理想情况下，决定将主要取决于一些廉价的 sql 查询
• 我有训练数据可以权威地说任何两个特征向量是同一类别但不是不同的（人们有时会忘记他们的代码并使用新的代码，从而创建一个新的用户 ID）

我需要一种算法来确定哪些特征（站点）最有可能具有高 ROI 进行查询（即更好地区分目前看来合理的类别 [用户]，并增加确定它是任何给定的类别）。

这需要平衡开发（基于先前的测试数据的测试）和探索（测试的东西没有经过足够的测试来了解它的性能）。

还有一个关于先验排名的问题。这一个专门关于基于迄今为止收集的结果的后验排名。

现在，我没有足够的数据来测试任何其他人曾经受到打击的所有东西，但最终情况并非如此，此时需要解决这个问题。

我想这是 AI 中一个相当标准的问题——对于要进行的昂贵查询有一个廉价的启发式方法——但我的 AI 课程没有涵盖它，所以我实际上不知道是否有标准答案。因此，数学不太重的相关阅读以及对特定算法的建议会有所帮助。

解决这个问题的好方法是什么？

我正在开发一个多线程程序，其中有许多工作线程执行长度不等的任务。我想对任务进行负载平衡，以确保它们完成大致相同的工作量。对于每个任务 T _i 我都有一个数字 c _i ，它提供了该任务所需工作量的良好近似值。

_{我正在寻找一种有效的（O(N) N = 任务数或更好的）算法，考虑到 c i}的值，它会给我“大致”一个良好的负载平衡。它不一定是最优的，但我希望能够对结果分配的糟糕程度有一些理论界限。

有任何想法吗？