一种基于三层滑动状态集的可逆状态空间宽度优先查重搜索方法、电子设备及存储介质与流程

本发明涉及人工智能搜索、图论搜索、路径规划和电子设计自动化，具体涉及一种基于三层滑动状态集的可逆状态空间宽度优先查重搜索方法、电子设备及存储介质。

背景技术：

1、宽度优先搜索（breadth-first search，bfs）是状态空间搜索和图搜索中的基础方法。该方法按照搜索层级逐层扩展，通常能够保证首次到达目标状态时对应最短步数或最短层级。因此，bfs 被广泛应用于迷宫求解、路径规划、滑块类问题、图路由以及芯片迷宫布线等问题中。

2、现有bfs在处理可逆状态空间时，通常需要维护全局已访问状态集合（visitedset），并在每次生成新状态后对全局集合执行查重操作，以避免因状态可逆导致的循环搜索。随着搜索深度增加，所述全局已访问状态集合规模迅速膨胀，进而带来以下技术问题：（1）状态存储空间显著增加，易造成内存瓶颈；（2）查重集合规模增大后，查询效率下降；（3）大规模数据结构难以充分利用处理器缓存，导致访存延迟上升；（4）在资源受限设备或大规模网格搜索场景中，传统方案可扩展性不足。

3、尤其在集成电路布线、迷宫路由和机器人远距离路径规划场景中，搜索空间巨大，而局部状态转移往往具有可逆性。在此类技术场景下，如何降低bfs重复判定所需存储规模与比较代价，是现有技术中亟待解决的问题。然而，在具有单步可逆状态转移特征的宽度优先搜索场景中，当前扩展层状态的一步后继状态与搜索层级之间存在局部邻接关系。现有全局已访问状态集合查重方式通常未充分利用该层级邻接特性，而是对所有历史访问状态进行统一保存和查询，导致部分已经不可能作为当前层一步后继状态再次出现的历史层状态仍被长期保留。由此，现有技术在保证搜索完备性的同时，付出了较高的存储代价和查重代价。

技术实现思路

1、3.1、发明目的

2、本发明的目的在于提供一种基于三层滑动状态集的可逆状态空间宽度优先查重搜索方法、电子设备及存储介质，以解决现有技术中宽度优先搜索依赖全局已访问状态集合所导致的高内存消耗、高查重开销和缓存利用率不足的问题。

3、进一步地，本发明利用单步可逆状态转移所形成的宽度优先搜索层级邻接特性，将历史重复判定范围限制在当前扩展层、前一层和前两层构成的三层状态滑动窗口内，并通过正在构建的下一层状态集的集合化插入或状态编码唯一化插入消除同层生成重复，从而在降低对全局已访问状态集合依赖的同时，保持宽度优先搜索对可达目标状态的完备性和首次到达目标状态时的最短层级性。

4、3.2、技术方案

5、为实现上述目的，本发明采用如下技术方案：

6、在具有单步可逆状态转移特征的状态空间中执行宽度优先搜索时，构建分层搜索结构，并维护由最近三层状态集合构成的三层状态滑动窗口。对于第k层扩展过程，设当前扩展层状态集为lk，前一层状态集为lk−1，前两层状态集为 lk−2，

7、正在构建的下一层状态集为lk+1。所述三层状态滑动窗口表示为：

8、wk=lk∪lk−1∪lk−2，

9、从当前扩展层状态集lk中取出待扩展状态s，并对所述待扩展状态s施加状态转移算子a∈a，生成候选状态：

10、s'=t(s,a), a∈a, s∈lk

11、针对所述候选状态 s'，本发明不再针对历史全部访问状态执行全局查重，而是仅在当前三层状态滑动窗口wk内执行历史重复性判定；同时，对正在构建的下一层状态集lk+1执行集合化插入或状态编码唯一化插入，以消除由同一当前扩展层状态集lk中不同父状态生成的相同候选状态。具体地，重复性判定规则表示为：

12、d(s')=1,s'∈lk∪lk−1∪lk−2∪lk+1,

13、=0,s'∉lk∪lk−1∪lk−2∪lk+1.

14、其中，d(s')=1表示所述候选状态 s'为重复状态，d(s')=0表示所述候选状态s'为待保留状态；lk+1表示正在构建的下一层状态集。当d(s')=0时，将候选状态s'加入下一层状态集lk+1；当d(s')=1时，将候选状态s'判定为重复状态并丢弃。

15、进一步地，若状态转移算子a为单步可逆状态转移算子，则对任一状态si经算子a转移到状态sj后，存在逆算子a−1，使得：

16、t(t(si,a),a−1)=si

17、其中，所述算子a和所述逆算子a−1均对应宽度优先搜索中的一个搜索层级步长。

18、在满足单步可逆状态转移、宽度优先按层扩展以及下一层状态集唯一化插入的条件下，当前扩展层状态集 lk中任一状态的一步后继状态，不属于三层状态滑动窗口之前的历史层状态集合。所述三层状态滑动窗口之前的历史层状态集合可表示为：

19、l0∪l1∪⋯∪lk−3

20、因此，对于状态s∈lk及其一次状态转移生成的候选状态s'=t(s,a)，具有如下层级剪枝关系：

21、s∈lk, s'=t(s,a) ⇒ s'∉l0∪l1∪⋯∪lk−3

22、由此，三层状态滑动窗口之前的历史层状态集合无需参与当前候选状态s'的历史重复性判定，可以在层级推进过程中被丢弃。

23、当当前扩展层状态集 lk完成全部扩展后，将三层状态滑动窗口更新为：

24、{lk+1,lk,lk−1}

25、对应的层级更新关系为：

26、lk−2←lk−1, lk−1←lk, lk←lk+1

27、通过上述方式，本发明仅保留与当前宽度优先扩展相关的三层状态集合，并通过正在构建的下一层状态集lk+1实现同层生成重复的唯一化处理，从而减少对全局已访问状态集合的依赖，降低状态存储规模和重复判定开销。

28、进一步地，在满足单步可逆状态转移、宽度优先按层扩展以及下一层状态集唯一化插入的条件下，三层状态滑动窗口之前的历史层状态集合不会作为当前扩展层状态的一步后继状态重新出现。因此，丢弃三层状态滑动窗口之前的历史层状态集合，不会导致尚未发现的可达状态被错误丢弃，也不会改变宽度优先搜索首次到达目标状态时对应的最短层级。由此，本发明能够在降低内存占用和查重开销的同时，保持宽度优先搜索对可达目标状态的完备性和最短层级性。

29、3.3、有益效果

30、与现有技术相比，本发明至少具有以下有益效果：（1）降低存储开销：由维护全局已访问状态集合，转变为仅维护三层状态滑动窗口，减小查重数据规模；（2）提升查询效率：三层局部集合规模相对较小，有利于快速相等比较和哈希检索；（3）改善缓存友好性：状态表更易驻留于高速缓存，降低随机访存成本；（4）增强可扩展性：在大规模网格、布线和路径规划问题中，能够延缓传统bfs所面临的内存耗尽；（5）适用于工程部署：适用于eda布线、机器人路径规划和嵌入式设备本地搜索等场景；（6）消除同层生成重复：通过对正在构建的下一层状态集lk+1执行集合化插入或状态编码唯一化插入，可以消除同一当前扩展层中不同父状态生成的相同候选状态；（7）保持搜索性质：在满足单步可逆状态转移、宽度优先按层扩展以及下一层状态集唯一化插入的条件下，三层状态滑动窗口的重复性判定能够对三层状态滑动窗口之前的历史层状态集合实现与全局已访问状态集合相同的历史重复排除效果，且不改变宽度优先搜索对可达目标状态的完备性，并保持首次到达目标状态时对应的最短层级性。