algorithm - 人工智能搜索

Question

大家。我正在研究一个大学时间表计划项目。主要是我在使用禁忌搜索，但我想问：

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

请，如果有人有此类算法方面的专家，请告诉我，因为我在此类问题上一直在努力。

Answer 1

shoosh 评论的附录：您在寻找修剪吗？存在许多这样的策略，包括这个。请记住，一种尺寸并不适合所有人。因此，您可能必须设计一个启发式来满足您的需求。

Answer 2

我不是专家，但通常不难考虑对此类计算进行优化。
这实际上取决于您使用的适应度函数。通常，知道一个节点的适应度，你可以推断出孩子的适应度范围，甚至是从最坏到最好的情况。
使用一个足够简单的函数，您实际上可以计算孩子的适应度，即使没有显式生成它们，然后只在值得时才生成它们。

Answer 3

对先前评论的补充：修剪也可以在多个级别进行，具体取决于您的性能和内存限制。例如：

1. 将初始状态放入优先级队列。

2. 直到终止（例如队列为空，找到足够的解决方案，时间限制到期，...），重复以下操作：

   2.1。从队列中取出最上面的条目。

   2.2. 生成它的孩子（如果可能，使用估计器首先获得最高价值的孩子）。

   2.3. 生成每个孩子后，将其放入优先级队列。一旦队列达到大小限制（您可能通过反复试验凭经验确定），每次插入队列时都应该删除队列中的最低值元素。

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