六个搜索算法及其python实现

2024-06-07 16:52
文章标签 python 实现 搜索算法 六个

本文主要是介绍六个搜索算法及其python实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

搜索算法

搜索算法的含义可以从以下几个方面进行解释和归纳：

  1. 基本定义：搜索算法是利用计算机的高性能来有目的地穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。这本质上是一种穷举算法，旨在列出所有的可能性以找到满足特定条件的解。

  2. 核心目的：搜索算法的核心目的是在给定的问题空间内，通过一定的策略和规则，快速、准确地找到问题的解。这个过程中可能涉及到对解空间的遍历、剪枝（即提前排除不可能成为解的部分），以及利用启发式信息来指导搜索方向。

  3. 应用场景：搜索算法广泛应用于多个领域，包括但不限于数据检索（如在数据库或文件系统中查找特定信息）、图形搜索（如在地图应用中寻找两点之间的最短路径）、路径规划（如机器人导航或自动驾驶中的路径规划）、游戏AI（如棋类游戏中的走棋预测）、问题求解（如解决八皇后问题、数独等约束满足问题）以及机器学习（如神经网络参数优化）等。

  4. 主要类型：搜索算法有多种类型，其中深度优先遍历（DFS）和广度优先遍历（BFS）是两种常用的搜索策略。此外，还有线性搜索、二分查找、插值查找等针对不同数据结构和应用场景的搜索算法。

  5. 算法优化：为了提高搜索效率，搜索算法通常会采用各种优化技术，如剪枝（在搜索过程中提前排除不可能成为解的部分）、启发式搜索（利用问题特定的启发式信息来指导搜索方向，以加快找到解的速度）等。

综上所述，搜索算法能够帮助我们在复杂的问题空间中快速找到满足特定条件的解。

接下去我们将讨论线性搜索、二分搜索、深度优先搜索、广度优先搜索、Dijkstra、A*六个搜索算法。

1.线性搜索（Linear Search）

基本原理

线性搜索是一种非常简单的搜索策略。它从列表的第一个元素开始，逐个检查每个元素，直到找到所需的元素或检查完所有元素。

应用场景

当数据量不大，或者数据无序时，线性搜索是一个不错的选择。

优缺点
  • 优点：实现简单，无需对数据进行预处理。
  • 缺点：效率低下，特别是当数据量很大时。
Python实现
def linear_search(arr, target):for i in range(len(arr)):if arr[i] == target:return i  # 找到目标，返回索引return -1  # 未找到目标，返回-1# 示例
arr = [4, 2, 9, 3, 5, 1, 8, 6, 7]
target = 5
print(linear_search(arr, target))  # 输出：4

2.二分搜索（Binary Search）

基本原理

二分搜索是一种在有序数组中查找特定元素的搜索算法。它首先比较数组中间的元素，如果中间元素正好是目标值，则搜索结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较。这样，每次比较都能将搜索范围缩小一半。

应用场景

适用于有序的数据集，且数据量较大时效率更高。

优缺点
  • 优点：效率高，时间复杂度为O(log n)。
  • 缺点：要求数据必须有序。
Python实现
def binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return mid  # 找到目标，返回索引elif arr[mid] < target:left = mid + 1else:right = mid - 1return -1  # 未找到目标，返回-1# 示例
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
print(binary_search(arr, target))  # 输出：4

3.深度优先搜索（Depth-First Search, DFS）

基本原理

深度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的深度遍历树的节点，尽可能深地搜索树的分支，直到到达叶子节点或无法再深入的节点，然后回溯到上一个节点，继续搜索下一个分支。

应用场景

适用于需要遍历或搜索树或图结构的问题，如迷宫问题、八数码问题等。

优缺点
  • 优点：实现简单，空间效率高（相对于广度优先搜索）。
  • 缺点：可能陷入无限循环（如果图中存在环），且不一定能找到最短路径。
Python实现（以二叉树为例）
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef dfs(root, target):if root is None:return Falseif root.val == target:return Truereturn dfs(root.left, target) or dfs(root.right, target)# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
target = 4
print(dfs(root, target))  # 输出：True

注意：深度优先搜索在图结构中的实现会稍微复杂一些，因为需要记录已经访问过的节点，以避免重复访问和陷入无限循环。在上面的二叉树示例中，我们假设树中没有重复的节点值，因此没有考虑这个问题。

4. 广度优先搜索（Breadth-First Search, BFS）

基本原理

广度优先搜索是一种用于遍历或搜索树或图的算法。它从图的某一节点（源节点）开始，首先访问离源节点最近的邻居节点，然后对这些邻居的未访问邻居节点进行访问，以此类推，直到找到目标节点或遍历完整个图。

应用场景

广度优先搜索常用于无权图的最短路径查找、网络爬虫中的层次遍历等。

优缺点
  • 优点：能找到从源节点到目标节点的最短路径（路径长度以节点数量计）。
  • 缺点：对于大型图，可能会消耗大量内存来存储待访问的节点队列。
Python实现
from collections import dequedef bfs(graph, start, end):visited = set()queue = deque([start])while queue:node = queue.popleft()if node == end:return Trueif node not in visited:visited.add(node)queue.extend(graph[node] - visited)return False# 示例图表示（邻接表）
graph = {'A': {'B', 'C'},'B': {'A', 'D', 'E'},'C': {'A', 'F'},'D': {'B'},'E': {'B', 'F'},'F': {'C', 'E'}
}# 搜索从A到F的路径
print(bfs(graph, 'A', 'F'))  # 输出: True

5. Dijkstra 算法

基本原理

Dijkstra算法用于在加权图中找到从源节点到所有其他节点的最短路径。它通过迭代地选择当前未处理节点中距离最短的节点，并更新其邻居节点的距离。

应用场景

适用于带权重的图，如路由算法、地图导航等。

优缺点
  • 优点：能找到从源点到其他所有点的最短路径。
  • 缺点：不能处理带有负权重的边。
Python实现
import heapqdef dijkstra(graph, start):distances = {node: float('infinity') for node in graph}distances[start] = 0queue = [(0, start)]while queue:current_distance, current_node = heapq.heappop(queue)if current_distance > distances[current_node]:continuefor neighbor, weight in graph[current_node].items():distance = current_distance + weightif distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(queue, (distance, neighbor))return distances# 示例图表示（带权重的邻接表）
graph = {'A': {'B': 7, 'C': 9, 'F': 14},'B': {'A': 7, 'F': 2},'C': {'A': 9, 'F': 10, 'G': 15},'D': {'F': 9},'E': {'H': 15},'F': {'A': 14, 'B': 2, 'C': 10, 'D': 9, 'G': 1, 'H': 11},'G': {'C': 15, 'F': 1, 'H': 6},'H': {'E': 15, 'F': 11, 'G': 6}
}# 找到从A点到所有点的最短路径
print(dijkstra(graph, 'A'))  # 输出各点到A点的最短距离字典

6. A* 搜索算法（A-Star Search）

基本原理

A*搜索算法是一种启发式搜索算法，它结合了最佳优先搜索和Dijkstra算法的优点，使用一个启发式函数来评估从当前节点到目标节点的代价，以此选择下一个要遍历的节点。

应用场景

常用于路径查找、游戏AI、机器人导航等。

优缺点
  • 优点：如果启发式函数选择合适，可以更快地找到最短路径。
  • 缺点：启发式函数的选择对算法效率有很大影响，不合适的启发式可能导致算法性能下降。
Python实现
import heapqdef astar(graph, start, goal, heuristic):frontier = []heapq.heappush(frontier, (0, start))came_from = {start: None}cost_so_far = {start: 0}while frontier:current_priority, current = heapq.heappop(frontier)if current == goal:breakfor next_node, weight in graph[current].items():new_cost = cost_so_far[current] + weightif next_node not in cost_so_far or new_cost < cost_so_far[next_node]:cost_so_far[next_node] = new_costpriority = new_cost + heuristic(goal, next_node)heapq.heappush(frontier, (priority, next_node))came_from[next_node] = currentreturn came_from, cost_so_far# 示例图、启发式函数和主函数调用
graph = { ... }  # 与Dijkstra算法示例相同的图结构def heuristic(a, b):# 这是一个简单的启发式函数示例，实际应用中需要根据具体问题设计return 1  # 假设启发式代价为1（也可以是基于节点间的某种距离度量）came_from, cost_so_far = astar(graph, 'A', 'H', heuristic)
print(came_from)  # 输出到达每个节点的前一个节点字典
print(cost_so_far)  # 输出从起点到每个节点的已知最短距离字典

请注意，上述代码中的图结构、启发式函数以及搜索的具体节点需要根据实际应用场景进行调整。这里提供的只是算法框架和简单示例。

这篇关于六个搜索算法及其python实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

C++对象布局及多态实现探索之内存布局（整理的很多链接）

C++对象布局及多态实现探索之内存布局（整理的很多链接）

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
通过SSH隧道实现通过远程服务器上外网

通过SSH隧道实现通过远程服务器上外网

搭建隧道 autossh -M 0 -f -D 1080 -C -N user1@remotehost##验证隧道是否生效，查看1080端口是否启动netstat -tuln | grep 1080## 测试ssh 隧道是否生效curl -x socks5h://127.0.0.1:1080 -I http://www.github.com 将autossh 设置为服务，隧道开机启动
阅读更多...
Python 字符串占位

Python 字符串占位

在Python中，可以使用字符串的格式化方法来实现字符串的占位。常见的方法有百分号操作符 % 以及 str.format() 方法 百分号操作符 % name = "张三"age = 20message = "我叫%s，今年%d岁。" % (name, age)print(message) # 我叫张三，今年20岁。 str.format() 方法 name = "张三"age
阅读更多...
时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测 目录 时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测基本介绍程序设计参考资料 基本介绍 MATLAB实现LSTM时间序列未来多步预测-递归预测。LSTM是一种含有LSTM区块（blocks）或其他的一种类神经网络，文献或其他资料中LSTM区块可能被描述成智能网络单元，因为
阅读更多...
vue项目集成CanvasEditor实现Word在线编辑器

vue项目集成CanvasEditor实现Word在线编辑器

CanvasEditor实现Word在线编辑器 官网文档：https://hufe.club/canvas-editor-docs/guide/schema.html 源码地址：https://github.com/Hufe921/canvas-editor 前提声明： 由于CanvasEditor目前不支持vue、react 等框架开箱即用版，所以需要我们去Git下载源码，拿到其中两个主
阅读更多...
android一键分享功能部分实现

android一键分享功能部分实现

为什么叫做部分实现呢，其实是我只实现一部分的分享。如新浪微博，那还有没去实现的是微信分享。还有一部分奇怪的问题：我QQ分享跟QQ空间的分享功能，我都没配置key那些都是原本集成就有的key也可以实现分享，谁清楚的麻烦详解下。 实现分享功能我们可以去www.mob.com这个网站集成。免费的，而且还有短信验证功能。等这分享研究完后就研究下短信验证功能。 开始实现步骤（新浪分享，以下是本人自己实现
阅读更多...
基于Springboot + vue 的抗疫物质管理系统的设计与实现

基于Springboot + vue 的抗疫物质管理系统的设计与实现

目录 📚 前言 📑摘要 📑系统流程 📚 系统架构设计 📚 数据库设计 📚 系统功能的具体实现    💬 系统登录注册 系统登录 登录界面   用户添加  💬 抗疫列表展示模块     区域信息管理 添加物资详情 抗疫物资列表展示 抗疫物资申请 抗疫物资审核 ✒️ 源码实现 💖 源码获取 😁 联系方式 📚 前言 📑博客主页：
阅读更多...
探索蓝牙协议的奥秘：用ESP32实现高质量蓝牙音频传输

探索蓝牙协议的奥秘：用ESP32实现高质量蓝牙音频传输

蓝牙（Bluetooth）是一种短距离无线通信技术，广泛应用于各种电子设备之间的数据传输。自1994年由爱立信公司首次提出以来，蓝牙技术已经经历了多个版本的更新和改进。本文将详细介绍蓝牙协议，并通过一个具体的项目——使用ESP32实现蓝牙音频传输，来展示蓝牙协议的实际应用及其优点。 蓝牙协议概述 蓝牙协议栈 蓝牙协议栈是蓝牙技术的核心，定义了蓝牙设备之间如何进行通信。蓝牙协议
阅读更多...
一道经典Python程序样例带你飞速掌握Python的字典和列表

一道经典Python程序样例带你飞速掌握Python的字典和列表

Python中的列表（list）和字典（dict）是两种常用的数据结构，它们在数据组织和存储方面有很大的不同。 列表（List） 列表是Python中的一种有序集合，可以随时添加和删除其中的元素。列表中的元素可以是任何数据类型，包括数字、字符串、其他列表等。列表使用方括号[]表示，元素之间用逗号,分隔。 定义和使用 # 定义一个列表 fruits = ['apple', 'banana
阅读更多...
Python应用开发——30天学习Streamlit Python包进行APP的构建（9）

Python应用开发——30天学习Streamlit Python包进行APP的构建（9）

st.area_chart 显示区域图。 这是围绕 st.altair_chart 的语法糖。主要区别在于该命令使用数据自身的列和指数来计算图表的 Altair 规格。因此，在许多 "只需绘制此图 "的情况下，该命令更易于使用，但可定制性较差。 如果 st.area_chart 无法正确猜测数据规格，请尝试使用 st.altair_chart 指定所需的图表。 Function signa
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2