精华内容
下载资源
问答
  • 2022-04-27 20:30:18

    目录

    一. 顺序搜寻

    二. 二分搜寻法

    算法技巧专栏 


    一. 顺序搜寻

            顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。顺序查找的基本原理是对于任意一个序列以及一个给定的元素,将给定元素与序列中元素依次比较,直到找出与给定关键字相同的元素,或者将序列中的元素与其都比较完为止。

    1.1 代码如下:

    # 顺序搜寻-----------------------------------------------------------
    def sequential_search(nlist,key):
        for i in range(len(nlist)):
            if nlist[i]==key:
                return i
        return -1
    
    data = [3,8,5,9,1,4,2,6,7]
    key = eval(input('搜寻值为:'))
    index = sequential_search(data,key)
    if index != -1:
        print('在',index,'索引位置找到了。\n共找了',index+1,'次。')
    else:
        print('查无此搜寻字数!')

    1.2 算法分析

            找寻过程中很困会需要找寻n次,平均是找寻n/2次,时间复杂度是O(n)。


    二. 二分搜寻法

            要执行二分搜寻法(binary search),首先要将数据排序,然后将搜寻值(key)与中间值比较,如果搜寻值大于中间值,则下一次往右边(较大值边)搜寻,否则往左边(较小值边)搜寻。上述动作持续进行,直到找到搜寻值或是所有数据搜寻结束才停止。

    2.1 代码如下:

    # 二分搜寻法(binary search)-----------------------------------------------------------
    def binary_search(nlist, key):
        print('搜寻列表为:', nlist)
        low = 0
        high = len(nlist)-1
        middle = int((low+high)/2)
        times = 0
        while True:
            times += 1
            if key == nlist[middle]:
                rtn = middle
                break
            elif key >nlist[middle]:
                low = middle+1
            else:
                high = middle-1
            middle = int((low+high)/2)
            if low > high:
                rtn = -1
                break
        return rtn, times
    
    data = [3,8,5,9,1,4,2,6,7]
    data.sort()
    key = eval(input('搜寻值为:'))
    index,times = binary_search(data,key)
    if index != -1:
        print('在',index,'索引位置找到了。\n共找了',times,'次。')
    else:
        print('查无此搜寻字数!')

     2.2 算法分析

            每次搜寻可以让搜寻范围减半,当搜寻log n 次时,搜寻范围就剩下一个数据,此时可以判断所搜寻的数据是否存在,所以搜寻的时间复杂度为O(log n)。 


    算法技巧专栏 

    https://blog.csdn.net/weixin_53919192/category_11761989.htmlhttps://blog.csdn.net/weixin_53919192/category_11761989.html

    更多相关内容
  • 深度优先搜索算法 深度优先搜索 Depth-First-Search 总是扩展搜索树的当前边缘结点中最深的节点。搜索很快的推进到搜索树的最深处的结点,该结点称之为叶子结点,它没有后继,当这些结点扩展完之后,就从边缘结点中...

    N皇后问题
    N皇后问题是国际象棋的扩展,在N×N的棋盘上放置N个皇后,使得每一个皇后都不会攻击到其余的任一皇后(皇后可以攻击和它在同一行、同一列或同一对角线上的任何棋子)。
    在这里插入图片描述
    深度优先搜索算法
    深度优先搜索 Depth-First-Search 总是扩展搜索树的当前边缘结点中最深的节点。搜索很快的推进到搜索树的最深处的结点,该结点称之为叶子结点,它没有后继,当这些结点扩展完之后,就从边缘结点中去掉,然后回溯到下一个未扩展后继的深度稍浅的结点,搜索过程如下图所示。
    在这里插入图片描述
    与宽度优先搜索使用 FIFO 队列不同,深度优先搜索使用 LIFO, Last In First Out 的队列结构,即最新生成的结点最早被选择扩展,因此,为了实现方便,深度优先搜索算法一般抛弃 LIFO 队列而采用递归式结构实现。

    求解思路:
    棋盘的行可以用树的深度来表达,因此每一行只有一个皇后,她们不会同行。棋盘的列可以用一个长度为N的一维数组来记录是否放置过皇后。观察棋盘的行和列的特点,可以发现如下规律:
    在这里插入图片描述
    棋盘的左斜线\可以用一个数字表达,因此所有的左斜线可以用一个长度为2N−1的一维数组来记录是否放置过皇后,同理,右斜线/也可以用一个长度为2N−1的一维数组来记录是否放置过皇后。

    具体实现
    代码给了详细的注释

    
    ```python
    # -*- coding:utf-8 -*-
    
    class Solution:
    
        def __init__(self, n=0):
            self.vis = [[]]             #用于标记是否存在皇后的二维列表(初始值全为0)
            self.ans = 0                #用于存储答案(N皇后方案数,初始值0)
            self.n = n                  #用于存储皇后数量n
    
    
        def solveNQueens(self):
            """求解N皇后问题(调用self.DFS函数)
            :rtype: self.ans: int    #返回N皇后放置方案数
            """
            # 产生一个3行50列的数组,第一行代表左斜线,第二行代表所在的列,第三行代表有索引,初始值都为0
            self.vis = [[0 for j in range(50)] for i in range(3)]
            self.DFS(1,self.n)  # 递归
            return self.ans
    
        def DFS(self, row, n):
            """深度优先搜索N皇后问题的解空间
            :type: row: int      #NxN棋盘的第row行
            :type: n: int        #皇后数量n
            :rtype: None         #无返回值
            """
            if row == n+1:   # 行数大于皇后的个数,说明这个方案可行,方案数加1,递归结束(递归结束条件),
                self.ans += 1
                return
            for i in range(1,n+1,1):
                # vis[0][row-i+n] == 0 row-i即行的索引减去列的索引,左斜线等于0,左斜线没有放置皇后,+n是为了防止产生负数
                # vis[1][i] == 0 第i列为0
                # vis[2][row+i] == 0  即所在的右斜线上并没有存放皇后,row+i即行索引加上列索引,同一右斜线的行索引加列索引所得的值相等。
                if self.vis[0][row-i+n] == 0 and self.vis[1][i] == 0 and self.vis[2][row+i] == 0: # 第row行第i列可以存放皇后
                    self.vis[0][row-i+n] = self.vis[1][i] = self.vis[2][row+i] = 1  # 将对应的列,左斜线、右斜线都置为1
                    self.DFS(row+1,n)  # 存放下一个皇后
                    # 如果下一个皇后的位置无法正确放置,则调整当前皇后的放置位置
                    self.vis[0][row-i+n] = self.vis[1][i] = self.vis[2][row+i] = 0
                    # 继续本次循环,知道找到本行的列中有合适的存放位置为止,如果本行无合适位置,则继续返回上一层
    
    if __name__ == '__main__':
        queen = Solution()
        queen.__init__(8)
        ans = queen.solveNQueens()
        print(ans)
    

    以八皇后为例,最后输出92种方案数。
    在这里插入图片描述

    展开全文
  • 一、搜索算法 搜索算法又叫查找算法。在日常生活中,几乎每天都要进行一些查找的工作,在电话簿中查阅某个人的电话 在电脑的文件夹中查找某个具体的文件等等。 查找表是由同一类型的数据元素构成的集合。例如电话...

    一、搜索算法

    搜索算法又叫查找算法。在日常生活中,几乎每天都要进行一些查找的工作,在电话簿中查阅某个人的电话,在电脑的文件夹中查找某个具体的文件等等。
    查找表是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。

    一般对于查找表有以下几种操作:

    在查找表中查找某个具体的数据元素;
    在查找表中插入数据元素;
    从查找表中删除数据元素;

    静态查找表和动态查找表
    在查找表中只做查找操作,而不改动表中数据元素,称此类查找表为静态查找表;
    在查找表中做查找操作的同时进行插入数据或者删除数据的操作,称此类表为动态查找表。
    关键字又细分为主关键字和次关键字
    若某个关键字可以唯一地识别一个数据元素时,称这个关键字为主关键字,例如学生的学号就具有唯一性;
    像学生姓名、年龄这类的关键字,由于不具有唯一性,称为次关键字。

    当然,我们的搜索算法比较常用的就是顺序查找和折半查找,下面我们一一介绍。

    顺序查找算法

    从表中的最后一个数据元素开始,逐个同记录的关键字做比较, 如果匹配成功,则查找成功;
    如果直到表中第一个关键字查找完也没有成功匹配,则查找失败。
    具体实现和结果如下:

    def sequence_search(array,key):
        """
        顺序查找
        """
        for i in range(len(array)):
            if array[i]==key:
                return i
        return False
    
    array=[1,5,7,4,6,3]
    print(sequence_search(array,4))
    

    这个结果就会返回4这个元素在表中的索引下标。

    折半查找算法

    折半查找又叫二分法。
    在这里插入图片描述
    具体实现和结果如下:

    def halffind(nums,key,low,high):
    	"""
        :param nums: 查找的对象
        :param key: 查找的元素
    	"""
        mid = (low+high)//2
        if key == nums[mid]:
            return mid
        if low >high:
            return False
        if key>nums[mid]:
            return halffind(nums,key,mid +1,high)
        else:
            return halffind(nums, key, low, mid - 1)
    nums=[1,2,3,4,5,6,7,8]
    print(halffind(nums,3,0,(len(nums)-1)))
    

    这个算法我们主要是用递归来实现的,每次需要查找的元素和中间值mid进行比较。最终找到元素位置,返回3这个元素在表中的索引下标。

    二、贪心算法

    在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。
    我们平时其实也有不觉中使用了贪心算法,只是我们没有发觉。下面我们通过两个问题来具体理解贪心算法。
    最优装载问题
    有一天海盗们截获了一艘装满各种各样古董的货船,每一件都价值连城,一旦打碎就是去了价值,海盗船载重量为C,每件固定的重量为wi,海盗们该如何尽可能装载最多数量的古董呢?

    1. 船载重量固定为C,只要每次选择重量最小的古董,直到不能再装为止,这样装载的古董数量最大,
      这就是贪心策略;
    2. 把古董按重量从小到大排序,根据策略选出尽可能多的古董。

    具体实现和结果如下:

    def max_ans(antique,key):
        anti_sort =sorted(antique)
        ans,tmp=0,0
        ship=[]
        for a in anti_sort:
            tmp +=a
            if tmp <=key:
                ans +=1
                ship.append(a)
        print("装载的古董数量:",ans)
        print("装载的古董:",ship)
    
    antique=[4,3,15,5,12,6,7,8]
    max_ans(antique,40)
    

    在这里插入图片描述
    背包问题
    假设山洞中有n种宝物,每种宝物有一定重量w和相应的价值v,毛驴运载能力一种宝物只能拿一样,宝物可分割。怎样才能使毛驴运走宝物的价值最大呢?
    可以尝试三种贪心策略:
    3. 每次挑选价值最大的装东西入背包;
    4. 每次挑选最重的东西;
    5. 每次选取单位重量价值最大的东西。
    我们现在来看下我们的算法设计:

    1. 计算出每件宝物的性价比,按照从高到低排序;
    2. 根据贪心策略,按性价比从大到小选取宝物,直到达到毛驴的运载能力。每次选择宝物后判断是否
      小于m,如果不小于则取走宝物的一部分,程序结束

    具体实现和结果如下:

    # datas中每个元素代表一个古董,每个列表第一个元素代表古董重量,第二个元素代表古董价值
    datas = [[4, 3], [2, 8], [9, 18], [5, 6], [5, 8], [8, 20], [5, 5], [4, 6], [5, 7], [5, 15]]
    m = 30 # 毛驴运载能力
    w = 0 # 获取的总价值
    # 计算出每件宝物的性价比,按照从高到低排序
    for i in range(len(datas)):
    	price = datas[i][1] / datas[i][0]
    	datas[i].append(price)  # 增加性价比
    datas.sort(key=lambda data: data[2], reverse=True) # 按性价比排序
    # 按性价比从大到小选取宝物,直到达到毛驴的运载能力
    for data in datas:
    	if data[0] <= m:
    		w += data[1]
    		m -= data[0]
    	else:
    		w += data[2] * m  # 取走宝物的一部分
    		break
    print('总价值:',w)
    

    在这里插入图片描述
    这个问题的难点就在于分割宝物,理解起来有些困难。
    我们试想一下如果宝物不可分割,贪心算法得到的是否是最优解?
    注意: 物品可分割的装载问题称为背包问题,不可分割问题的装载问题称为0-1背包问题。
    0-1背包问题不具有贪心选择性质,贪心算法不能得到全局最优解,仅仅是最优解的近似解。
    0-1背包问题可用动态规划算法求解。

    动态规划

    动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
    通过两个实例来具体了解动态规划。
    动态规划之Fib数列
    问题: 有个小孩上楼梯,共有N阶楼梯,小孩一次可以上1阶,2阶。走到N阶楼梯,一共有多少种走法?
    DP之自顶向下分析方式:
    爬到第N阶楼梯,一共只有2种情况(全划分,加法原理),从第N-1阶爬1阶到第N阶;从第N-2阶爬2阶到第N阶;
    故:way(N)=way(N-1)+way(N-2)
    具体实现和结果如下:

    def fib2(n):
        memo=[-1 for x in range(n+1)]
        memo[0]=0
        memo[1]=1
        memo[2]=2
        for i in range(3,n+1):
            memo[i]=memo[i-1]+memo[i-2]
        return memo[n]
    
    print(fib2(5))
    

    运行结果就是3+5=8种走法。

    不相邻数最大和
    问题: 给定数组A=[1,2,4,1,7,8,3],求出数组A中互不相邻的数的最大和。
    例如:如果选择了8,则不能选择7和3,在本例中最大的和为1+4+7+3=15
    具体实现和结果如下:

    arr=[1,2,4,1,7,8,3]
    def dp_opt(arr):
        len_arr=len(arr)
        opt = [0 for i in range(len_arr)]
        opt[0]=arr[0]
        opt[1]=max(arr[0],arr[1])
        for  i in range(0,len(arr)):
            A=opt[i-1]
            B=arr[i]+opt[i-2]
            opt[i]=max(A,B)
        return opt
    
    print(dp_opt(arr))
    

    在这里插入图片描述
    返回的是我们选择每一个数字的最大和,很明显最后一个的时候最大。也就是我们的预期结果1+4+7+3=15。

    展开全文
  • 贪婪算法简介 假设你办了个广播节目,要让全美国50个州的听众都能听得到,为此, 你需要决定在哪些广播台播出。每个广播台台播出都需要费用,所以你需要尽可能地在更少的广播台播出节目。现有广播台名单如下: ...

    贪婪算法简介

    假设你办了个广播节目,要让全美国50个州的听众都能听得到,为此, 你需要决定在哪些广播台播出。每个广播台台播出都需要费用,所以你需要尽可能地在更少的广播台播出节目。现有广播台名单如下:
    这里写图片描述
    每个广播台都覆盖不同的范围,但是有些是重复的
    这里写图片描述
    如何才能找出覆盖全美50个州的最小广播台集和呢?先提供一种方法:
    (1)列出每种可能的广播台集和,称之为幂集,总共有2^n种集和
    (2)找出这2^n种集和中覆盖全美50个州的最小集合。
    以上算法的问题是计算所有集和的时间需要很多,假如有100个广播台,那么集和一共2^100次方,这可是一个非常大的数!
    那么,有没有一种算法可以快速的解决这种类似的问题呢?有,就是贪婪算法。
    贪婪算法是近似算法的一种,它的解决方法如下:
    (1)选出一个广播台,这个广播台覆盖了最多的未覆盖州,即便这个广播台覆盖了一些已经覆盖的州也没有关系。
    (2)重复第一步,直到覆盖了所有的州
    只要简单的两步!而且贪婪算法的时间复杂度为O(n^2),其中n为广播台数量,在n比较大的时候远比第一种方法速度快。

    但是贪婪算法并不一定能得到最优解,它获取的只是近似的最优解。很多时候,对于难以计算的问题,才会使用贪婪算法,快速的得到近似解。衡量贪婪算法有两点:
    (1)速度有多快
    (2)得到的近似解与最优解的接近程度

    最后,总结一下贪婪算法的实现步骤:
    (1)找到局部最优解
    (2)到一个新的局部,重复上一步

    代码实现:

    """
    假设你办了个广播节目,要让全美50个州的听众都收听得到,为此,
    你需要决定在哪些广播台播出,出于预算,你要力图在尽可能少的
    广播台播出,现在广播台名单和其覆盖位置如下:
    {'KONE': ID,NV,UT}{'KTWO': WA,ID,MT},{KTHREE : OR,NV,CA}
    {KFOUR : NV,UT},{KFIVE : CA, AZ}
    """
    # 要覆盖的州
    states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])
    
    # 广播台清单
    stations = dict()
    stations['KONE'] = set(['id', 'nv', 'ut'])
    stations['KTWO'] = set(['wa', 'id', 'mt'])
    stations['KTHREE'] = set(['or', 'nv', 'ca'])
    stations['KFOUR'] = set(['nv', 'ut'])
    stations['KFIVE'] = set(['ca', 'az'])
    
    # 最终使用的广播台
    final_stations = set()
    
    while states_needed:  # 当还有需要的州未覆盖的时候循环
        best_station = None  # 覆盖了最多未覆盖的州的广播台
        states_covered = set()  # 已经覆盖了的州的集合
        # 遍历所有广播台,找出最佳广播台并且将他的覆盖州加入已覆盖的州的集合
        for station, states_for_station in stations.items(): 
            # 计算需要覆盖的州和每个广播台覆盖的州的交集 
            covered = states_needed & states_for_station  
            # 如果交集的州数量比已经覆盖的州的数量多
            if len(covered) > len(states_covered):  
                best_station = station  # 最佳广播台更新为这个广播台
                states_covered = covered  # 已覆盖的州更新为交集
        states_needed -= states_covered  # 更新为覆盖的州
        final_stations.add(best_station)  # 更新最终结果
    
    print(final_stations)
    
    展开全文
  • 本文实例讲述了Python解决走迷宫问题算法。分享给大家供大家参考,具体如下: 问题: 输入n * m 的二维数组 表示一个迷宫 数字0表示障碍 1表示能通行 移动到相邻单元格用1步 思路: 深度优先遍历,到达每一个点,...
  • 大神!!求能用python运行出来的代码,谢谢谢谢,救救孩子吧~
  • 深度优先搜索算法(Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过,搜索将回溯到发现节点 v 的那条边的起始节点...
  • 深度优先搜索算法(Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过,搜索将回溯到发现节点 v 的那条边的起始节点...
  •  之前看过经典的搜索路径方法,印象较深的也就BFS(广度优先),DFS(深度优先)以及A*搜索,但没实践过,就借八数码问题,来通通实现遍,观察下现象呗~~~ 首先,怎么说也得把数码这玩意基本操作实现了呗!上代码~...
  • 一、算法原理 ...宽度优先搜索算法(Breadth First Search,BSF),思想是: 从图中某顶点v出发,首先访问定点v 在访问了v之后依次访问v的各个未曾访问过的邻接点; 然后分别从这些邻接点出发依次访...
  • 一、启发式搜索:A算法1)评价函数的一般形式 : f(n) = g(n) + h(n)g(n):从S0到Sn的实际代价(搜索的横向因子)h(n):从N到目标节点的估计代价,称为启发函数(搜索的纵向因子);特点: 效率高, 无回溯,搜索算法OPEN表 : ...
  • python实现RSA算法

    2020-12-09 13:53:38
    文章最后更新时间为:2018年12月26日 23:07:29RSA是一种公钥密码算法,其影响力我就不多说了,算法原理网上多的是,看了几篇,还是觉得阮一峰写的好懂。要想实现RSA,其关键在于大数运算,无论是大数之间的加减乘除...
  • 为了改进RRT搜索空间的盲目性、节点拓展环节缺乏记忆性的缺点,提高空间搜索速度,在RRT算法的基础上,又有双向RRT算法。双向RRT算法有两棵树,具有双向搜索的引导策略,并且在生长方式的 基础上加上了贪婪策略加快...
  • 解决方法就是很朴素的盲目搜索 # 初始化参数:父状态、当前棋盘、当前棋子坐标 """ start状态开始 如果open_list的当前状态是目标状态: count++ 拓展open_list的当前状态(被拓展状态出栈) 拓展状态列表入栈...
  • 【人工智能】启发式搜索算法,A*和IDA*搜索算法解决十五数码(15-puzzle)问题 Python实现,理论算法分析与实验证明
  • 类型分为有向图,无向图,加权图等,任何问题只要能抽象为图,那么就可以应用相应的图算法。用字典来表示图这里我们以有向图举例,有向图的邻居节点是要顺着箭头方向,逆箭头方向的节点不算作邻居节点。在python中,...
  • 搜索 搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的,因为该项目是否存在。 搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找二分法查找 二分查找又称折半查找...
  • 宽度优先搜索算法python实现本文博客链接:http://blog.csdn.net/jdh99,作者:jdh,转载请注明. 环境:主机:WIN10python版本:3.5开发环境:pyCharm说明:本程序是udp客户端模块。绑定固定端口进行收发。udp接收是一个...
  • python 启发式算法 带有Python的AI –启发式搜索 (AI with Python – Heuristic Search) Advertisements 广告 Previous Page 上一页 Next Page 下一页 Heuristic search plays a key role in ...
  • BFS之所以叫广搜,是因为它具有全面性和盲目性,如果不配合剪枝算法,它可以搜索完所有的可能。这在我们执行寻路等算法的时候,是耗时耗力的。所以BFS常要配合一些剪枝的算法,以降低其时间复杂度。
  • 【原理】PCA算法原理 1.PCA算法 PCA(principal Component Analysis),即主成分分析方法,是一种使用最广泛的数据压缩算法。在PCA中,数据从原来的坐标系转换到新的坐标系,由数据本身决定。转换坐标系时,以方差...
  • 十分钟教你学会蚁群算法求解TSP问题
  • python实现 最短路径算法

    万次阅读 2019-03-11 09:40:14
    一、Floyd-Warshall算法 1.算法简介 Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用,包括有向图、带负权边的图。 存储方式采用邻接矩阵 2.示例 0 1 2 6 3 1 ...
  • 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点...
  • 宽度优先搜索BFS 工作方式: 从根节点开始,由里向外,逐层遍历所有节点——它每次总是扩展深度最浅的节点。 BFS方法,从根节点1开始,下图遍历顺序是:1,2,3,4,5,6 优先访问深度最浅的节点,故,老节点总是...
  • 实验一:搜索算法求解问题 一、实验目的 掌握有信息搜索策略的算法思想; 能够编程实现搜索算法; 应用A*搜索算法求解罗马尼亚问题。 二、实验平台 课程实训平台https://www.educoder.net/paths/369 三、实验内容及...
  • 最低水平线搜索算法的实现(Python) 之前有一篇文章介绍了二维矩形排样基本算法中的最低水平线算法(点击传输门),本文介绍最低水平线搜索算法
  • 如果能走并且之前没有走过就走 #********* End *********# 盲目搜索算法的应用 class Solution: def __init__(self, n=0): self.vis = [0]*n # 用于标记是否存在皇后的二维列表(初始值全为0) self.ans = 0 # 用于...
  • 遗传算法python(含例程代码与详解)

    万次阅读 多人点赞 2020-10-24 11:00:57
    遗传算法1.算法简介2.算法流程3.算法示例4.算法实现5.算法应用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,519
精华内容 1,807
关键字:

python盲目搜索算法

友情链接: convexSets.rar