【笔记】搜索策略——Rita_Aloha

2023-10-07 22:49
文章标签 笔记 搜索 策略 aloha rita

本文主要是介绍【笔记】搜索策略——Rita_Aloha，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

 

一、搜索

1.搜索的定义

2.搜索问题的形式化描述

3.搜索的主要过程

4.搜索的方向

二、盲目搜索

1.广度优先搜索

2.深度优先搜索

3.有限深度优先搜索

4.基本回溯策略

5.改进的回溯策略

6.避免多次试探同一个结点的回溯策略

三、启发搜索

1.评价函数（Evaluation Function）f(n)

2.常用算法

（1）分支界限法/有序法

（2）爬山法/代价树的深度优先搜索

（3）动态规划法

（4）A算法/最佳优先搜索算法/全局择优算法

（5）A*算法

（6）模拟退火法

（7）遗传算法

3.其他启发途径

4.在博弈中使用启发

一、搜索

1.搜索的定义

搜索指从大量的事物构成的状态空间中寻找某一特定的对象的过程，本质就是从问题的状态空间中找到从问题的初始状态通向目标状态的路径。

2.搜索问题的形式化描述

（1）初始状态

（2）后继函数：描述智能体可能的行为。

（3）目标测试：用来确定给定的状态是不是目标状态。

（4）路径耗费函数为每条路径分配一个数值化的耗费值

3.搜索的主要过程

（1）从初始状态或目标状态出发，并将其作为当前状态

（2）扫描操作算子集（操作算子用于实现状态的转换），将适用于当前状态的一些操作算子作用于当前状态得到新的状态，并建立指向其父结点的指针

（3）检查所生成的新状态是否满足结束。若满足，则得到问题的一个解，并可以沿着有关指针从结束状态逆向到达开始状态，给出这一解的路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索

4.搜索的方向

（1）正向搜索：从初始状态出发的搜索，也称为数据驱动的搜索

（2）逆向搜索：从目标状态出发的搜索，也称为目标驱动的搜索

二、盲目搜索

1.广度优先搜索

（1）算法描述：

①G:G~0~ (G~0~=S)，OPEN:=(S)，CLOSED:=()

②Loop：If OPEN=() Then Exit(Fail)

③n:=First(OPEN)，Remove(n,OPEN)，Add(n,CLOSED)

④If Goal(n) Then Exit(Success)

⑤Expand(n)，生成一组子结点 M=(m~1~,m~2~,...)，M中不包含n的父辈结点，G:=Add(M,G)

⑥将n的子结点中没有在OPEN表和CLOSED表中出现过的结点，按照生成的次序加入OPEN表的末端，并标记它们到结点n的指针；把刚刚由结点n扩展出来的、以前没有出现过的结点放在OPEN表的最后面，使深度浅的结点优先扩展

⑦Go Loop

（2）算法特点：在单位耗散的情况下，广度优先搜索保证可以找到从初始状态到目标状态的最短路径（耗散值最小的解）；但是它的主要缺点是盲目性比较大，尤其是当目标结点与初始结点的距离比较远时，可能会产生很多无用的点，导致搜索效率低下。

（3）广度优先搜索的评价：

  • 完备性：广度优先搜索是完备的。
  • 最优解：最前的目标结点不一定是最优的目标结点。
  • 时空耗费：广度优先搜索的空间使用量在任何时间都是路径长度的指数函数。

2.深度优先搜索

（1）算法描述：

①G:G~0~ (G~0~=S)，OPEN:=(S)，CLOSED:=()

②Loop：If OPEN=() Then Exit(Fail)

③n:=First(OPEN)，Remove(n,OPEN)，Add(n,CLOSED)

④If Goal(n) Then Exit(Success)

⑤Expand(n)，生成一组子结点 M=(m~1~,m~2~,...)，M中不包含n的父辈结点，G:=Add(M,G)

⑥将n的子结点中没有在OPEN表和CLOSED表中出现过的结点，按照生成的次序加入OPEN表的前端，并标记它们到结点n的指针；把刚刚由结点n扩展出来的、以前没有出现过的结点放在OPEN表的最前面，使深度大的结点优先扩展

⑦Go Loop

（2）算法的特点：深度优先搜索不一定能找到最佳解。在最糟糕的情况下深度优先搜索等同于遍历（穷举）

3.有限深度优先搜索

  • 算法描述：

①G:G~0~ (G~0~=S)，OPEN:=(S)，CLOSED:=()

②Loop：If OPEN=() Then Exit(Fail)

③n:=First(OPEN)，Remove(n,OPEN)，Add(n,CLOSED)

④If Goal(n) Then Exit(Success)

⑤If Depth(n)≥Bound Then Go Loop；Bound是一个事先设置好的常数，表示深度界限，如果n超过了Bound，跳转至Loop标号处，进行下一轮搜索。（迭代深入搜索）

⑥Expand(n)，生成一组子结点 M=(m~1~,m~2~,...)，M中不包含n的父辈结点，G:=Add(M,G)

⑦将n的子结点中没有在OPEN表和CLOSED表中出现过的结点，按照生成的次序加入OPEN表的前端，并标记它们到结点n的指针

⑧Go Loop

4.基本回溯策略

（1）主要思想：

首先将问题所有的规则（操作/操作算子）给出一个固定的排序，在搜索时对当前状态依次检测规则集中的每一条规则，在当前状态未使用过的规则集中找到第一条可以触发的规则，应用于当前状态，得到一个新的状态，新状态设置为当前状态，重复以上搜索。

如果对当前状态而言，没有规则可用，或者所有的规则都已经被试探过但仍然没有找到问题的解，则将当前状态的前一个状态设置为当前状态，重复以上搜索。

（2）递归过程StepTrack(Data)

①If Goal(Data) Then Return Fail；Deadend(Data)返回值为真，表示Data是目标状态，即找到目标，过程返回空表Nil

②If Deadend(Data) Then Return Fail；Deadend(Data)返回值为真，表示状态Data是非法，过程返回Fail，即需要回溯

③Rules:=Apprules(Data)；如果Deadend(Data)返回值为假，执行Apprules函数，计算Data所有可应用的规则，再按照某种原则排列后赋给Rules

④Loop: If Null(Rules) Then Return Fail；Null(Rules)返回值为真，表示规则用完未找到目标或根本没有可应用规则，过程返回Fail，即需要回溯

⑤R:=First(Rules)；取头条可应用的规则

⑥Rules:=Tail(Rules)；删去头条规则，更新未被使用的规则集

⑦Newdata:=Gen(R,Data)：调用规则R作用于当前状态，生成新状态

⑧Path:=StepTrack(Nwedata)；对新状态递归调用本过程

⑨If Path=Fail Then Go Loop Else Return Cons(R,Path)；当Path=Fail时，表示递归调用失败，没有找到从Newdata到目标的解路径，转移到Loop处调用下一条规则进行测试；否则过程返回解路径

（3）算法StepTrack(Data)的注意事项：

①当某一状态t满足结束条件时，算法在第①步结束并返回Nil，此时StepTrack(t)的返回值为Nil，即t到目标状态的解路径是一张空的规则表

②算法返回Fail发生在第②步和第④步，第②步由于不合法状态返回Fail，第④步由于所有规则都试探失败返回Fail。一旦返回Fail意味着过程回溯到上一层继续运行，而在最高层返回Fail则整个过程失败退出。

③如果找到解路径，算法在第⑨步通过Cons函数构造出解路径

5.改进的回溯策略

（1）改进：通过增加回溯点的方法解决‘无限深渊’与‘环路’问题；若深度界限Bound设定不合理时，可以做可变深度限制的处理，即在遍历过深度Bound之内的结点后仍然没有找到问题的解，适当增加Bound的值接着搜索。

（2）递归过程StepTrack1(Datalist)

⑴Data:=First(Datalist)；设置Data为当前状态

◆⑵If Member(Data,Tail(Datalist)) Then Return Fail；函数Tail是取尾操作，Tail(Datalist)表示取Datalist中除了第一个元素以外的所有元素。Member(Data,Tail(Datalist))取值为真，表示Data在Tail(Datalist)中存在，即有环路出现，过程返回Fail，需要回溯

⑶If Goal(Data) Then Return Nil；Goal(Data)返回值为真，表示Data是目标状态，即找到目标，过程返回Nil

⑷If Deadend(Data) Then Return Fail；Data是非法状态，过程返回Fail，即需要回溯

◆⑸If Length(Datalist)>Bound Then Return Fail；函数Length计算Datalist的长度，即搜索的深度，当搜索深度大于给定常数Bound时，返回Fail，即需要回溯

⑹Rules:=Apprules(Data)；执行Apprules函数，计算Data所有可应用的规则，再按照某种原则排列后赋给Rules

⑺Loop：If Null(Rules) Then Return Fail；Null(Rules)返回值为真，表示规则用完未找到目标或根本没有可应用的规则，返回Fail，即需要回溯

⑻R:=First(Rules)；取头条可应用的规则

⑼Rules:=Tail(Rules)；删去头条规则，更新为被使用的规则集

⑽Newdata:=Gen(R,Data)；调用规则R作用于当前状态，生成新状态

⑾Newdatalist:=Cons(Newdata,Datalist)；将新状态加入到表Datalist前面，构成新的状态列表

⑿Path:=StepTrack1(Newdatalist)；递归调用本过程

⒀If Path=Fail Then Go Loop Else Return Cons(R,Path)；当Path=Fail时，表示递归调用失败，没有找到从Newdata到目标的解路径，转移到Loop处调用下一条规则进行测试；否则过程返回解路径

6.避免多次试探同一个结点的回溯策略

（1）为了处理某个结点被多次试探的问题，通过增加3张保存不同类型结点的表对前面的算法进行改进

①PS(Path State)表，路径状态表，保存当前搜索路径上的状态。如果找到了目标状态，PS就是以状态序列表示的解路径

②NPS(New Path State)表，新路径保存表，保存了等待搜索的状态，其后裔状态还没有被搜索到，即还没有被生成扩展

③NSS(No Solvable State)表，不可解状态表，保存了不可解的结点，即找不到解路径的状态，如果在搜索中扩展出的结点属于NSS表，则可立即排除，不必沿着该结点往下搜索试探

（2）注意事项

①用NPS表使算法回溯到任一状态

②用NSS表来避免算法重复探索无解的路径

③用PS表记录当前搜索的路径，一旦找到目标，就将PS作为解路径返回

④为避免陷入死循环，每次新状态生成后都检查其是否在这3张表中，如果在其中，就不做任何处理

三、启发搜索

1.评价函数（Evaluation Function）f(n)

（1）采用启发搜索的参考情景

  • 因为问题陈述或现有数据中存在固有的模糊性，所以问题可能没有精确解
  • 问题可能有精确解，但是找其状态空间特别大，搜索中生成的状态数会随着搜索深度的增加呈指数级增长

（2）设计参考原则

  • 从概率角度来设计，将f(n)定义为结点n处在最佳路径上的概率，概率值越大，说明越有希望通向目标结点
  • 从距离或差异的角度来设计，将f(n)定义为结点n与目标结点t的距离或差异，其价值越小，说明距目标结点越近（或与目标结点差异越小），越希望通向目标结点
  • 从打分的角度来设计，对结点n所表示的格局进行打分，f(n)表示结点n的得分，得分越高说明越有希望通向目标结点

（3）一般形式：f(n)=g(n)+h(n)

  • g(n)是从初始结点S到结点n的实际路径的耗散值；h(n)是从结点n到目标结点t的最佳路径的耗散值估计

2.常用算法

（1）分支界限法/有序法

①算法描述

Ⅰ G:=G~0~(G~0~=S)，OPEN:=(S)，CLOSED:=()，g(S)=0

Ⅱ Loop：If OPEN=() Then Exit(Fail)

Ⅲ n:=First(OPEN)，Remove(n,OPEN)，Add(n,CLOSED)

Ⅳ If Goal(n) Then Exit(Success)

Ⅴ Expand(n)，生成一组子结点M={m~1~,m~2~,...}，将这些子结点放入OPEN表中，并为它们配上指向父结点n的指针，按g(m_i)=g(n)+c(n,m_i)计算各子结点的代价

Ⅵ 根据g值从小到大，将OPEN表中的结点从小到大重新排序

Ⅶ Go Loop

②分支界限法的特点：分支界限法是代价树的宽度优先搜索算法，其基本思想是，在OPEN表中保留所有已生成而未考查的结点，并用g(n)对它们一一进行评价，按照g的值从小到大进行排列，即每次选择g值最小的结点进行考查，不管该结点出现在搜索树的什么地方。

（2）爬山法/代价树的深度优先搜索

①算法描述

Ⅰ G:=G~0~(G~0~=S)，OPEN:=(S)，CLOSED:=()，g(S)=0

Ⅱ Loop：If OPEN=() Then Exit(Fail)

Ⅲ n:=First(OPEN)，Remove(n,OPEN)，Add(n,CLOSED)

Ⅳ If Goal(n) Then Exit(Success)

Ⅴ Expand(n)，生成一组子结点M={m~1~,m~2~,...}，将这些子结点放入OPEN表，并为它们配上指向父结点n的指针，按g(m_i)=g(n)+c(n,m_i)计算各子结点的代价

Ⅵ 根据g值从小到大，将刚刚生成的子结点从小到大移动至OPEN表前面

Ⅶ Go Loop

②爬山法的特点：爬山策略不是完备策略。爬山策略容易陷入局部最大值，如果没有回溯或其他恢复机制的搜索方法无法辨别局部和全局最大值。甚至当搜索进入无穷分支时，该算法将找不到解。

③爬山法与分支界限法的区别：每次从OPEN表选择待考查结点的范围不同。分支界限法每次从OPEN表的全体结点中选择一个g值最小的结点，而爬山法每次从刚扩展出的子结点中选择一个g值最小的结点。

（3）动态规划法

①算法描述

Ⅰ G:=G~0~(G~0~=S)，OPEN:=(S)，CLOSED:=()，g(S)=0

Ⅱ Loop：If OPEN=() Then Exit(Fail)

Ⅲ n:=First(OPEN)，Remove(n,OPEN)，Add(n,CLOSED)

Ⅳ If Goal(n) Then Exit(Success)

Ⅴ Expand(n)，生成一组子结点M={m~1~,m~2~,...}，将这些子结点放入OPEN表，并为它们配上指向父结点n的指针，按g(m_i)=g(n)+c(n,m_i)计算各子结点的代价。若新生成的子结点是多条路径都能到达的结点，则只选择耗散小的路径，其余路径对应的结点从OPEN表中删除

Ⅵ 根据g值从小到大，将OPEN表中的结点重新排列

Ⅶ Go Loop

②动态规划法的特点

动态规划法有时也称为前前后后(forward-backward)算法，当使用概率时称为Viterbi算法，解决由多个互相影响互相关联的子问题构成的问题中的受限内存搜索。动态规划法实际上也是对分支界限法的改进，使用动态规划法的搜索效率比分支界限法要高。

（4）A算法/最佳优先搜索算法/全局择优算法

①算法描述

Ⅰ OPEN:=(S)，CLOSED:=()，f(S)=g(S)+h(S)；初始化

Ⅱ Loop：If OPEN=() Then Exit(Fail)

Ⅲ n:=First(OPEN)，Remove(n,OPEN)，Add(n,CLOSED)

Ⅳ If Goal(n) Then Exit(Success)

Ⅴ Expand(n)，生成一组子结点M={m~1~,m~2~,...}，M中不包含n的父结点，G:=Add(M,G)，对每个子结点m~i~的计算式

                                                                    f(n,m_i)=g(n,m_i)+h(m_i)

式中，g(n,m~i~)是从初始结点S通过n到达m~i~的耗散值；h(m~i~)是从子结点m~i~到目标结点t的最短路径的耗散值的估计；f(n,m~i~)是以n为父结点的子结点m~i~的评价函数值

Ⅵ 根据M中结点的不同性质，标记和修改它们到父结点的指针

⑴未在OPEN表和CLOSED表中出现过的子结点（即，刚刚由n扩展出来的子结点m~j~）：应将其加入OPEN表，并标记到其父结点n的指针，此时f(m_j)=f(n,m_j)

⑵已在OPEN表中出现的子结点（即，已由其他结点扩展且未被扩展、这次又由结点n扩展出来的子结点m~k~）：

                                                 If f(n,m_k)\leq f(m_k) Then f(m_k)=f(n,m_k)

⑶已在CLOSED表中出现的子结点（已由其他结点扩展出来且已经被扩展、这次又由结点n扩展出来的子结点m~l~）：

                                                 If f(n,m_l)\leq f(m_l) Then f(m_l)=f(n,m_l)

修改其父结点指针指向n，并将该子结点从CLOSED表移到OPEN表中，不必计算是否要修改其后继结点指向父结点的指针

◆Ⅶ OPEN中的结点按评价函数值从小到大排序

Ⅷ Go Loop

②全局择优搜索与局部择优搜索算法的区别：算法第Ⅶ步中，全局择优算法是对OPEN表中的全部结点按评价函数值从小到大排序。而局部择优搜索则具有局部特性，即将n的子结点按照评价函数值从小到大依次放在OPEN表的首部。

③最佳优先搜索与爬山法的区别：爬山策略不维护用来选取“下一个”状态的优先队列，所以无法从错误中恢复；而最佳优先搜索策略可以从这个错误中恢复并找到正确解

④最佳优先搜索策略的特点

最佳优先搜索是一种启发式搜索任何状态空间的通用算法，既适用于数据驱动搜索也适用于目标驱动搜索，而且支持不同的启发评估函数。因此可以把它和很多种不同的启发方法一起使用。

（5）A*算法

①A*算法是一种对评价函数进行了一定限制后的A算法

A*算法实际是A算法的一个特例，f*(n)定义为

                                                                       f^{*} (n)=g^{*}(n)+h^{*}(n)

其中，g*(n)表示从初始结点S到结点n的最短路径的耗散值；h*(n)表示从结点n到目标结点t的最短路径的耗散值；f*(n)表示从初始结点S经过结点n到目标结点t的最短路径的耗散值。具有f*(n)策略的启发算法能称为A*算法的充分条件是：

Ⅰ 搜索树上存在从起始点到终止点的最优路径

Ⅱ 问题域是有限的

Ⅲ 所有结点的子结点的搜索代价值大于0

Ⅳ h(n)≤h*(n)（h*(n)为实际问题的代价值）

当4个条件都满足时，就可称该启发算法为A*算法，并一定能找到最优解。

此外，对一个好的h(n)的评价是：h(n)在h*(n)的下界之下，并且尽量接近h*(n)。

②算法描述

Ⅰ 首先，将源点作为初始结点，并在后续的过程中对其进行扩展

Ⅱ 以初始结点进行扩展，通过计算其评价函数的值，选取其中值最小的结点作为下一个待扩展的结点

Ⅲ 对上面选取的结点进行扩展，同样也计算每个扩展后的结点的评价函数值。从中选取值最小的结点作为待扩展结点

Ⅳ 将上面选取的结点进行扩展，并对扩展的结点计算其评估函数的值。若其中最小的值比上一层扩展的结点中评估函数的值还大，那么就在上一层的结点中选取合适的结点作为待扩展的结点

Ⅴ 完成上面的过程后，在当前的层次中选取评估函数值最小的结点

Ⅵ 重复上述过程，直到找到目标结点

③A*算法的可采纳性、信息性及单调性

Ⅰ 可采纳性

一般地说，对任意一个图，当初始结点S到目标结点t有一条路径存在时，如果搜索算法总是在找到一条从S到t的最佳路径上结束，则称该搜索算法是可采纳的。

所有的A*算法都具有可采纳性。

【在以下定理中，隐含了两个假设：i.任何两个结点之间的耗散值都大于某个给定的大于零的常量；ii.h(n)对任何n都有h(n)≥0】

定理1：对有限图，如果从初始结点S到目标结点t有路径存在，则算法A*一定成功结束。

引理1-1：对无限图，若有从初始结点S到目标结点t的一条路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增大到任意大，或有f(n)>f*(s)。

引理1-2：在A*算法终止之前的任何时刻，OPEN表总存在结点n'，它是从初始结点到目标结点的最佳路径上的结点，满足f(n')≤f*(s)

定理2：对无限图，若从初始结点S到目标结点t有路径存在，则算法A*必然成功结束。

定理3：A*算法是可采纳的，即如果存在初始结点S到目标结点t的路径，则A*算法必能找到最佳解结束，或者说A*算法必能结束在最佳路径上。

Ⅱ 信息性

对于两个A*启发h~1~和h~2~，如果对于搜索空间中的所有状态n都满足h_{1}(n)\leq h_{2}(n)，那么说h~2~比h~1~具有更高的信息度。

定理4：假设有两个A*算法，即A*~1~和A*~2~。若A*~2~比A*~1~有较多的启发信息，即对所有非目标结点均有h_{2}(n)>h_{1}(n)，则在搜索过程中，被A*~2~扩展的结点也必然被A*~1~扩展，即A*~1~扩展的结点数不会比A*~2~扩展的结点数少，亦即A*~2~扩展的结点集是A*~1~扩展的结点集的子集。

关于定理4有以下几点需要注意：

  • 定理4中两个A*算法A*~1~和A*~2~是针对同一个问题的，它们的启发式函数h~1~(n)和h~2~(n)都满足A*算法的条件。
  • 只有当对于任何一个非目标结点n都满足h_{2}(n)>h_{1}(n)，而不是h_{2}(n)\geq h_{1}(n)时，定理4才成立，才能保证被A*~2~扩展的结点也必然被A*~1~扩展。
  • 同一个结点不管被扩展多少次，在计算“扩展的结点数”时都只算作一次。

通常，A*算法的信息度越高，要得到最优解而需要展开的空间就越小。然而必须注意，采用高信息度启发所需的计算量可能会增大，以至于抵消了搜索状态数量降低所带来的优势。

Ⅲ 单调性

（单调性）启发函数h单调的条件是：

  1. 目标状态的启发值为零，即h(Goal)=0
  2. 对于所有的状态n~i~和n~i+1~，都有0\leq h(n_{i})-h(n_{i+1})\leq cost(n_{i},n_{i+1}).其中cost(n~i~,n~i+1~)是从状态n~i~到n~i+1~的实际代价/耗散值（以移动次数为单位）

     即，搜索空间的每一处都与所采用的启发具有局部一致性。

定理5：若h(n)满足单调限制条件，则A*扩展了结点n之后，就已经找到了到达结点n的最佳路径。即在单调限制条件下，若A*选n来扩展，有g(n)=g*(n)

定理6：若h(n)满足单调限制，则由A*所扩展的结点序列，其f值是非递减的，即f(n_{i})\leq f(n_{i+1})

（6）模拟退火法

①算法描述

Ⅰ 初始化：初始温度T（充分大），初始解空间状态S（算法迭代的起点），每个T值的迭代次数L

Ⅱ 对k=1,...,L进行第Ⅲ步至第Ⅵ步

Ⅲ 产生新解S'

Ⅳ 计算增量△t'=C(S')-C(S)，其中C(S)为评价函数

Ⅴ 若△t'<0，则接受S'作为新的当前解，否则以概率exp(-\frac{\Delta t'}{T})接受S'作为新的解

Ⅵ 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法

Ⅶ T逐渐减少，且-T>0，然后转第Ⅱ步

②模拟退火算法新解的产生和接受

Ⅰ由一个产生函数从当前解产生一个位于解空间的新解，通常选择由当前解经过简单变换即可产生新解的方法。

Ⅱ 计算与新解对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差最好按增量计算。

Ⅲ 判断新解是否被接受的依据是一个接受准则。最常用的接受准则是Metropolis准则：若△t'<0，则接受S'作为新的当前解S；否则以概率exp(-\frac{\Delta t'}{T})接受S'作为新的当前解S。

Ⅳ 当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。

③模拟退火算法的特点

  • 模拟退火算法与初始值无关，算法求得的解与初始解状态S无关
  • 模拟退火算法具有渐进收敛性，已在理论上证明是一种以概率1收敛于全局最优解的全局优化算法
  • 模拟退火算法具有并行性

（7）遗传算法

①算法描述

Ⅰ 首先选择初始生命种群，并对其进行初始化

Ⅱ 循环：i.评价种群中的个体适应度；ii.按适应度概率选择产生下一代的种群，并以该选择的种群作为父代，进行杂交和变异

Ⅲ 直到满足停止循环的条件

②遗传算法的特点

遗传算法的本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解

3.其他启发途径

实现启发的另一种有趣途径是专家系统中所使用的用置信度来衡量规则结果。专家系统采用置信度来选取具有最大成功可能性的结论。置信度特别低的状态可能被完全排除。

4.在博弈中使用启发

 

 

 

 

 

 

 

 

整理自：

1.《人工智能：复杂问题求解的结构和策略》 作者：(美国)卢格尔 (Luger.G.F)

2.《人工智能及应用》 作者：鲁斌 刘丽 李继荣 姜丽梅

3.《人工智能实用教程》 作者：罗忠文 杨林权 向秀桥

这篇关于【笔记】搜索策略——Rita_Aloha的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/160950。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲

在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲

1. 单例模式（Singleton Pattern） 确保一个类只有一个实例，并提供一个全局访问点。 示例代码： class Singleton {constructor() {if (Singleton.instance) {return Singleton.instance;}Singleton.instance = this;this.data = [];}addData(value)
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

本章知识考点：         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
hdu4277搜索

hdu4277搜索

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...
论文阅读笔记: Segment Anything

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear
阅读更多...
数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2