searh算法库
libsearch的Python项目详细描述
libsearch | 
说明
一种搜索算法库，用于State Space Problems中，解决方案基于对不同状态集合的搜索，从初始状态开始，并遵循特定规则从该状态到下一个可能的状态，直到达到目标状态。在
- 初始状态：表示问题当前描述的状态，从 搜索将开始。在
- 状态空间：所有可能状态的集合
- Actions：以一个状态作为参数并返回一组结果状态的函数。在
- 目标状态：由特定规则定义的终止搜索的状态或一组最终状态 并表明找到了可接受的解决方案。在
实现的算法
支持以下算法。在
Blind Search
- 深度优先搜索
- 广度优先搜索
- 迭代深化
- 分界
启发式搜索
- 最佳优先搜索
- 一颗星星
- 迭代深化（A星）
入门
安装最新版本：
pip install libsearch
使用
^{pr2}$将function替换为您希望使用的算法，方法如下：在括号中可以找到每个函数所需的参数。（actions是上面描述的函数，它从父状态返回子状态）
盲搜索算法：
depth_first_search(actions=actions,start=InitialState,goal=GoalState)
breadth_first_search(actions=actions,start=InitialState,goal=GoalState)
iterative_deepening(actions=actions,start=InitialState,goal=GoalState)
For Branch and Bound应提供一个路径成本函数，该函数返回达到某个状态的成本。
branch_and_bound(actions=actions,start=InitialState,goal=GoalState,path_cost=path_cost)
启发式搜索算法：
启发式：为每个问题定义的用户唯一的启发式函数，该函数返回从当前状态到达目标状态的估计成本。
best_first_search(actions=actions,start=InitialState,goal=GoalState,heuristic=heuristic)
a_star(actions=actions,start=InitialState,goal=GoalState,heuristic=heuristic)
iterative_deepening_a_star(actions=actions,start=InitialState,goal=GoalState,heuristic=heuristic)
（可选参数）
为了进行计算，可以将以下参数设置为上面所需的参数，以返回已探索状态的数量或/和算法在达到解之前所探索的状态的数量。
count_states=True#if True it will return the number of explored states too. num_exploredshow_explored=True#if True it will return the explored(closed) set too.
溶液
算法返回的解决方案是一个python 集，由（list_of_actions，list\u states）
list\u actions：到达目标状态路径上的每个状态所采取的操作
list\u states：从初始状态到目标状态的路径
示例
分枝定界算法在著名算法问题Traveling Salesman (TSP).
在以下完整的加权图中，每个城市用字母表示，每条路径都有路径成本：
我们使用字典在python中实现此图：
tspGraph={'A':{'B':8,'C':5,'D':10,'E':8},'B':{'A':8,'C':7,'D':6,'E':6},'C':{'A':5,'B':7,'D':9,'E':3},'D':{'A':10,'B':6,'C':9,'E':4},'E':{'A':8,'B':6,'C':3,'D':4}}
在这个问题中，州是以字母表示的城市，而行为则是从一个城市到另一个城市的移动。 e、 g应用于状态“A”的动作“A-B”将产生新的状态“B”，其代价（权重）为8。在
在我们的模块中，我们导入了分支和绑定函数：
fromlibsearchimportbranch_and_bound
让我们把函数赋给一个变量（如解）：
solution=branch_and_bound(actions=g.fullneighbors,start='A',goal='A',path_cost=g.path_cost)
如果我们要打印solution，我们将得到以下结果：
(['A-B', 'A-B-D', 'A-B-D-E', 'A-B-D-E-C', 'A-B-D-E-C-A'], ['B', 'D', 'E', 'C', 'A'])
第一个列表是操作（从每个字母（状态）移动到下一个字母（状态），后一个列表是表示到达目标状态“a”的路径的状态列表，而在我们的例子中，它与TSP问题中描述的初始状态相同。在
可选参数
如果我们想知道分支定界算法探索了多少个状态：
solution,num_explored=branch_and_bound(actions=g.fullneighbors,start='A',goal='A',path_cost=g.path_cost,count_states=True)
通过检查num_explored的值，我们可以看到在达到目标之前已经探索了68个状态（路径组合）。在
关于返回特定TSP问题的子状态的fullneighbors函数的实现，以及返回分配给每个路径的成本的路径成本函数的实现，可以在examples文件夹中的graph.py上找到。在
注释
这种将搜索算法作为函数的实现实际上可以用于任何可以定义为在状态空间中进行搜索的问题，只要用户定义actions函数从现有状态生成新状态，并且在启发式搜索的情况下，定义启发式函数来估计达到目标状态的成本。在
在examples文件夹中，您可以在迷宫问题上试验不同的算法maze.py。在
- 项目
标签：
欢迎加入QQ群-->： 979659372
