LC-检索

简介: line void LC(tree T,float cost) { //为找一个答案结点检索T 0 if(T是答案结点) {输出T;return;} 1 E=T; //E-结点 2 将活结点表初始化为空; 3 while(1) { 4 for(E的每个子结点X) { 5 if(X是...
line void LC(tree T,float cost) {
//为找一个答案结点检索T
0 if(T是答案结点) {输出T;return;}
1 E=T; //E-结点
2 将活结点表初始化为空;
3 while(1) {
4 for(E的每个子结点X) {
5 if(X是答案结点) {输出从X到T的路径;
6 return7 };//endif
8 Add(X); //X是新的活结点
9 Parent(X)=E; //指示到根的路径
10 };//for
11 if(不再有活结点) { print(‘no answer node’);
12 stop;
13 };//if
14 Least(E) ;
15 } //while
16 }//LC

  变量E总是指着当前的E-结点。根结点是第一个E-结点(第1行)。第2行将活结点表置初值。在执行LC的任何时刻,该表含有除了E-结点以外的所有活结点,因此该表最初为空(第2行)。第4~10行的for循环检查E-结点的所有子结点。如果有一个子结点是答案结点,则算法输出由X到T的路径并且终止。如果E的某个子结点不是答案结点,则成为一个活结点,将它加到活结点表(第8行)中且将其Parent信息段置E。当生成了E的全部子结点时,E变成死结点,控制到达第11行。这种情况只有在E的所有子结点都不是答案结点时才会发生,于是检索应更深人地继续进行。在没有活结点剩下的情况下,这整棵状态空间树就被检索完毕,且没有找到答案结点,算法在第12行结束。反之,则通过Least(X)按规定去正确地选择下一个E-结点,并从这里继续进行检索。

  显然LC只有在找到一个答案结点或者在生成并检索了整棵状态空间树时才会终止。因此只有在有限状态空间树下,才能保证LC终止。对于无限状态空间树,在其至少有一个答案结点并假定对成本估计函数c’(·)能作出“适当”的选择时也能保证算法LC终止。

  实际上,,LC算法与状态空间树的宽度优先检索算法和D-检索算法基本相同。如果活结点表作为一个队列来实现,用Least(X)和Add(X)算法从队列中删去或加入元素,则LC就转换成FIFO检索。如果活结点表作为一个栈来实现,用Least(X)和Add(X)算法从栈中删去或加入元素,则LC就转换成LIFO检索。唯一的不同之处在于活结点表的构造上,即仅在于得到下一个E-结点所使用的选择规则不同。

相关文章
|
7月前
|
存储 关系型数据库 MySQL
MySQL字段的字符类型该如何选择?千万数据下varchar和char性能竟然相差30%🚀
本篇文章来讨论MySQL字段的字符类型选择并深入实践char与varchar类型的区别以及在千万数据下的性能测试
MySQL字段的字符类型该如何选择?千万数据下varchar和char性能竟然相差30%🚀
|
7月前
|
测试技术 索引
【每日一题Day296】LC833字符串中的查找与替换 | 排序+模拟
【每日一题Day296】LC833字符串中的查找与替换 | 排序+模拟
45 0
|
Java
【LC简单】434. 字符串中的单词数
【LC简单】434. 字符串中的单词数
71 0
【LC简单】434. 字符串中的单词数
|
芯片 SoC
一次小模块的使用过程-LC12S无线模块介绍
一次小模块的使用过程-LC12S无线模块介绍
172 0
一次小模块的使用过程-LC12S无线模块介绍
【每日一题Day81】LC2185统计包含给定前缀的字符串 | 模拟
思路:判断每一个word是否以prefix开头,最后返回满足条件的单词数量。
66 0
|
测试技术
【每日一题Day6】LC915分割数组
实现:使用rightMin数组记录该元素右边的数组的最小值(不包括该元素),使用leftMax记录该元素左边的数组的最大值(包括该元素),当leftMax[i]<=rightMin[i]时,返回i+1
57 0
【每日一题Day11】LC1773统计匹配检索规则的物品数量
给你一个数组 items ,其中 items[i] = [typei, colori, namei] ,描述第 i 件物品的类型、颜色以及名称。
63 0
|
机器学习/深度学习
【每日一题Day102】LC2315统计星号 | 模拟
思路:记录每个'|'的编号,统计第偶数个'|'之后、第奇数个'|'之前的星号,以及末尾剩余字符串的星号个数
82 0
【每日一题DAY21】LC1684统计一致字符串的数目|哈希表
给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中,就称这个字符串是 一致字符串 。
71 0
【每日一题Day86】LC2287 重排字符形成目标字符串 | 哈希表
思路:使用两个哈希表记录两个字符串中字符出现的次数,假设某个字符的在s和target中出现次数分别为a和b ,那么该字母可被重排的次数为⌊ a/ b ⌋ ,target可以被重排的次数为所有字母可被重排的最小值。
74 0