解空间-搜索空间-目标函数-约束条件-限界函数

解空间:就是进行穷举的搜索空间,解空间中包含所有的可能解。

搜索空间:搜索过程中涉及的结点叫做搜索空间,所以搜索空间树是解空间的一部分。在搜索过程中通过约束条件剪去无法得到可行解的子树,通过目标函数的界限剪去得不到最优解的子树。

目标函数:表示我们程序搜索的最优目标。比如用最少的机器人监视nm的矩阵。 min(robot) c>=nm

目标函数的界限:表示最差的解决方法的解。 比如用n个木料肯定能切割出n个木板。

约束条件:表示对搜索过程的限制。比如八皇后的时候棋子不能放在同一行,同一列上。 约束条件是为了去掉不可行解。

限界函数:在搜索过程中对最终结果的一种预测,从而来判断是否需要继续生成。限界函数就是在找,最好可能是什么情况,不同点在于目标函数界限的是一般整个问题全局都是一样的,
但是限界函数是根据每个节点当前的情况进行计算的来的,每个节点的限界函数都可能不一样,也就是说每个节点可能达到的最优值都可能不一样,根据这个可能最优值就行排序(一般就是把这些节点放到一个排好序的数据结构里,比如说小根堆或者大根堆里),谁可能最优值最好,就先遍历谁
比如说博物馆问题,比如现在使用了robot个机器人监视了c个方格。则最少需要robot+(m*n-c)/5个机器人才能完全监视,这就是这个节点可能最优的情况,根据这个节点进行排序,谁小先遍历谁

0%