人工智能搜索

Question

所有人。我正在做一个大学课程表计划项目。我主要是使用禁忌搜索，但我想问一下：

在一般的搜索中，你可以探索当前状态的所有邻居，然后根据适应度或评估函数选择最佳状态，但在这样的项目中，生成所有邻居会降低性能，所以有什么方法可以让我绕过这样的问题吗？例如，我是否可以只为一个州生成子对象，然后在搜索过程中从所有其他州的子代中受益？

如果有人有这样的算法专家，请告诉我，因为我在这样的问题上努力工作过。

Answer 1

shoosh评论的附录:你正在寻找剪枝吗(http://en.wikipedia.org/wiki/Pruning_(algorithm%29)?有很多这样的策略，包括this one。请记住，一种尺寸并不适合所有的尺寸。因此，您可能必须设计一个启发式方法来满足您的需求。

Answer 2

我不是专家，但对于这样的计算进行优化通常并不难。

这真的取决于你使用的适应度函数。通常，知道节点的适应度可以推断出子节点的适应度范围，甚至是最差到最好的范围。

有了一个足够简单的函数，您实际上可能能够计算子对象的适应度，即使不显式地生成它们，然后只在值得的情况下才生成它们。

Answer 3

对之前评论的补充:根据您的性能和内存限制，还可以在多个级别上进行剪枝。例如：

1. 将初始状态放入优先级队列。
2. 直到终止(例如队列为空、找到足够的解决方案、时间限制已过期等)，重复以下操作：

2.1。从队列中取出顶部的条目。

2.2。生成它的子对象(如果可能，首先使用估计器获取最高值的子对象)。

2.3。生成每个子对象时，将其放入优先级队列中。一旦队列达到一个大小限制(您可能根据经验通过反复试验来确定)，每次插入到队列中都应该伴随着删除队列中最低值的元素。

显然，拥有良好的估计/评估函数对于完成这项工作非常重要。您可以调整队列评估函数以将“生成”考虑在内(例如，在较浅的深度向更接近初始状态的状态提供加权奖励)，以调整其在深度偏好和广度偏好之间的偏差。