程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2023-10(1)

荐最通俗易懂的四种排序算法讲解

发布于2020-03-18 11:13     阅读(1623)     评论(0)     点赞(20)     收藏(4)


算法介绍

算法 1:深度优先算法;
算法 2:宽度优先算法;
算法 3:代价一致算法;
算法 4:A* 算法;

通用搜索算法

算法1-4的不同之处在于用不同的数据结构进行排序。因此可以定义一个通用的搜索算法实现算法1-4,通过配置不同参数来实现DFS,BFS,UCS和A*搜索。

算法 数据结构
DFS
BFS 队列
代价一致 优先队列
A* 优先队列+启发式函数
def genericSearchAlgorithm(problem, open_type):
    """
    param1: problem (搜索算法要解决的问题对象)
    param2: open_type (搜索算法中的open表采用的数据结构)
    return值: actions列表,即,吃豆人吃到豆子所执行的一个action序列
    """
    openTable = open_type()  # 数据结构
    # 将其实例化,创建open表
    openTable.push((problem.getStartState(), []))
    closed = []  # 初始化closed表为空表
    while True:
        if openTable.isEmpty():
            return []
        node,actions = openTable.pop()
        if problem.isGoalState(node):
            return actions
        if node not in closed:
            closed.append(node)
            for successor,action, stepCost in problem.getSuccessors(node):
                openTable.push((successor,actions+[action]))

DFS

深度优先搜索是最常见的搜索算法之一。DFS采用栈作为数据结构进行搜索路径,“先进后出”。

从起点出发,首先判断起点是否是目标节点,若是则返回目标节点。否则,搜索一条分支的所有结点,然后再去搜索其他分支。

首先判断节点是否是目标节点,若是则返回目标节点,否则压入栈中。若栈不为空,选择栈顶弹出的节点作为下一步的节点,依次类推,直至找到目标节点。若栈为空却未搜索到目标节点,则搜索失败。将通用搜索算法中的 open_type 设置为 util.Stack。

def depthFirstSearch(problem):
  return generalSearch(problem, util.Stack)

BFS

广度优先搜索是最常见的搜索算法之一。BFS采用队列作为数据结构进行搜索路径,“先进先出”。

从起点出发,首先判断起点是否是目标节点,若是则返回目标节点。否则,搜索该节点的邻居节点,
首先判断节点是否是目标节点,若是则返回目标节点,否则压入队列中。

若队列不为空,选择队列中的首节点作为下一步的节点,依次类推,直至找到目标节点。若队列为空却未搜索到目标节点,则搜索失败。将通用搜索算法中的 open_type 设置为 util.Queue。

def breadthFirstSearch(problem):
	return generalSearch(problem, util.Queue)

代价一致算法

代价一致搜索是宽度优先搜索的一种推广, 不是沿着等长度路径逐层进行扩展, 而是沿着等代价路径逐层进行扩展。

在代价树中,可以用g(n)表示从初始节点S0到节点 i的代价,用 c(i, n2)表示从父节点 i到 n2的代价,记g(n2) = g(i) + c(i, n2)。

把从起始节点S0到任一节点i的路径代价记为g(i)。从初始节点S0开始扩展,若没有得到目标节点,则优先扩展最少代价g(i)的节点,一直如此向下搜索。将通用搜索算法中的 open_type 设置为util.PriorityQueue。

def uniformCostSearch(problem):
	return generalSearch(problem, util.PriorityQueue, True)

A*算法

  1. A*搜索是最佳优先搜索的一种形式,最先扩展f(n)最小的节点。
  • f(n)是进过节点 n 的最小代价解的估计代价。

  • A*算法的估算函数为 f(n) = g(n) + h(n)。g(n)是到达此节点花费的代价, h(n)是从该节点到目标节点需要花费的代价(的估计值)。

  1. 将通用搜索算法的open_type设置为PriorityQueue,PriorityQueue设置为True,heuristic设置为heuristic,即可实现以曼哈顿距离为启发函数的A*算法
def aStarSearch(problem, heuristic=nullHeuristic):
	return generalSearch(problem, util.PriorityQueue, True, heuristic)


所属网站分类: 技术文章 > 博客

作者:编程gogogo

链接:https://www.pythonheidong.com/blog/article/265284/3c37f6212c5a03b31222/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

20 0
收藏该文
已收藏

评论内容:(最多支持255个字符)