最佳优先搜索best-find search

2024-09-05 17:36

本文主要是介绍最佳优先搜索best-find search,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1. 问题

2. 算法

3.代码


1. 问题

考虑下面这个问题:

 我们要找到从Arad到Bucharest的路,最好是最短的路:

2. 算法

这是一个无向有环图,

可以采用最佳优先搜索:

最佳优先搜索的算法可以参考维基百科:

伪代码如下:

// Pseudocode for Best First Search
Best-First-Search(Graph g, Node start)1) Create an empty PriorityQueuePriorityQueue pq;2) Insert "start" in pq.pq.insert(start)3) Until PriorityQueue is emptyu = PriorityQueue.DeleteMinIf u is the goalExitElseForeach neighbor v of uIf v "Unvisited"Mark v "Visited"                    pq.insert(v)Mark u "Examined"                    
End procedure

如果你熟悉广度优先搜索,那么上面的代码也没什么难度。

该算法最关键的点是如何构造优先队列中的“优先”策略,一种简单的办法就是选取当前所有访问点中最近的相邻点:

procedure GBS(start, target) is:mark start as visitedadd start to queuewhile queue is not empty do:current_node ← vertex of queue with min distance to targetremove current_node from queueforeach neighbor n of current_node do:if n not in visited then:if n is target:return nelse:mark n as visitedadd n to queuereturn failure

显然上面的BFS是一种贪婪算法,每次选取最优的近邻点是一种“短视”,虽然如此,他仍是一种可行的算法。

该算法最坏的复杂度是 O(n*logn) ,其中n是节点的总数。在最坏的情况我们需要访问所有节点,然后我们构造的堆,每次添加删除元素时复杂度为:O(logn)   

算法的性能显然与我们选择什么样的代价函数有直接关系。

3.代码

首先是节点类

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  4 15:56:35 2024@author: Paul
"""class Node:def __init__(self,name):self._name=nameself._children=[]def __repr__(self):return 'Node({!r})'.format(self._name)def add_child(self,node):self._children.append(node)def __iter__(self):return iter(self._children)def __eq__(self, other):return self._name==other._namedef Childrens(self):return self._children()

优先队列:

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  4 16:03:33 2024@author: Paul
"""import heapqclass PriorityQueue:def __init__(self):self._queue=[]self._index=0def push(self,item,priority):heapq.heappush(self._queue, (priority,self._index,item))self._index+=1def pop(self):return heapq.heappop(self._queue)[-1]   #弹出itemdef empty(self):              #判断是否为空return True if not self._queue else False

数据节点:

这里只选取到BuCharest城市的数据,该城市是访问Urziceni和Giurgiu后续的点必经之路。

这些城市:

cities=['Arad','Zerind','Oradea','Sibiu','Fagaras','Bucharest',
        'Pitesti','Rimnicu','Craiova','Drobeta','Mehadia','Lugoj',
        'Timisoara']

cities=['Arad','Zerind','Oradea','Sibiu','Fagaras','Bucharest','Pitesti','Rimnicu','Craiova','Drobeta','Mehadia','Lugoj','Timisoara']Nodes=[Node(name) for name in cities]     #12个节点
dist_mat=[[] for i in range(len(cities))]def addedge(start,end,dist):x=cities.index(start)y=cities.index(end)dist_mat[x].append((y,dist))dist_mat[y].append((x,dist))addedge('Arad', 'Zerind', 75)
addedge('Arad', 'Sibiu', 140)
addedge('Arad', 'Timisoara', 118)
addedge('Zerind','Oradea',71)
addedge('Oradea', 'Sibiu', 151)
addedge('Sibiu', 'Fagaras', 99)
addedge('Sibiu', 'Rimnicu',80)
addedge('Fagaras', 'Bucharest', 211)
addedge('Bucharest', 'Pitesti', 101)
addedge('Pitesti', 'Rimnicu', 97)
addedge('Pitesti', 'Craiova', 138)
addedge('Craiova', 'Rimnicu', 146)
addedge('Craiova', 'Drobeta', 120)
addedge('Drobeta', 'Mehadia', 75)
addedge('Mehadia', 'Lugoj', 70)
addedge('Lugoj', 'Timisoara', 111)for index,city in enumerate(Nodes):for t in dist_mat[index]:city.add_child(Nodes[t[0]])

每个节点与其相邻节点关系如下:

Node('Arad') =>[Node('Zerind'), Node('Sibiu'), Node('Timisoara')]
Node('Zerind') =>[Node('Arad'), Node('Oradea')]
Node('Oradea') =>[Node('Zerind'), Node('Sibiu')]
Node('Sibiu') =>[Node('Arad'), Node('Oradea'), Node('Fagaras'), Node('Rimnicu')]
Node('Fagaras') =>[Node('Sibiu'), Node('Bucharest')]
Node('Bucharest') =>[Node('Fagaras'), Node('Pitesti')]
Node('Pitesti') =>[Node('Bucharest'), Node('Rimnicu'), Node('Craiova')]
Node('Rimnicu') =>[Node('Sibiu'), Node('Pitesti'), Node('Craiova')]
Node('Craiova') =>[Node('Pitesti'), Node('Rimnicu'), Node('Drobeta')]
Node('Drobeta') =>[Node('Craiova'), Node('Mehadia')]
Node('Mehadia') =>[Node('Drobeta'), Node('Lugoj')]
Node('Lugoj') =>[Node('Mehadia'), Node('Timisoara')]
Node('Timisoara') =>[Node('Arad'), Node('Lugoj')]

最后BFS如下:

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  4 16:37:37 2024@author: Paul
"""from node import Node
from priorityqueue import PriorityQueuedef BFS(mat,start,dest):q=PriorityQueue()q.push(start, 0)visited=[start]while not q.empty():u=q.pop()print(u)if u==dest:return Trueelse:for city,dist in mat[Nodes.index(u)]:child=Nodes[city]if child not in visited:visited.append(child)q.push(child, dist)return False

运行BFS结果如下:

Node('Arad')
Node('Zerind')
Node('Oradea')
Node('Timisoara')
Node('Lugoj')
Node('Mehadia')
Node('Drobeta')
Node('Craiova')
Node('Pitesti')
Node('Bucharest')

访问路径如下:

     算法每次选取最近的节点,因此我们没有得到最优解,要想得到最优解,需要对算法进行改造,使之称为启发式算法,我会在后续章节介绍一二。

参考链接:

BFS维基百科:Best-first search - Wikipedia

geek for geeks: Best First Search (Informed Search) - GeeksforGeeks

这篇关于最佳优先搜索best-find search的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139618

相关文章

Spring WebFlux 与 WebClient 使用指南及最佳实践

《SpringWebFlux与WebClient使用指南及最佳实践》WebClient是SpringWebFlux模块提供的非阻塞、响应式HTTP客户端,基于ProjectReactor实现,... 目录Spring WebFlux 与 WebClient 使用指南1. WebClient 概述2. 核心依

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

Spring Boot @RestControllerAdvice全局异常处理最佳实践

《SpringBoot@RestControllerAdvice全局异常处理最佳实践》本文详解SpringBoot中通过@RestControllerAdvice实现全局异常处理,强调代码复用、统... 目录前言一、为什么要使用全局异常处理?二、核心注解解析1. @RestControllerAdvice2

Spring事务传播机制最佳实践

《Spring事务传播机制最佳实践》Spring的事务传播机制为我们提供了优雅的解决方案,本文将带您深入理解这一机制,掌握不同场景下的最佳实践,感兴趣的朋友一起看看吧... 目录1. 什么是事务传播行为2. Spring支持的七种事务传播行为2.1 REQUIRED(默认)2.2 SUPPORTS2

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

MySQL 用户创建与授权最佳实践

《MySQL用户创建与授权最佳实践》在MySQL中,用户管理和权限控制是数据库安全的重要组成部分,下面详细介绍如何在MySQL中创建用户并授予适当的权限,感兴趣的朋友跟随小编一起看看吧... 目录mysql 用户创建与授权详解一、MySQL用户管理基础1. 用户账户组成2. 查看现有用户二、创建用户1. 基

MySQL MCP 服务器安装配置最佳实践

《MySQLMCP服务器安装配置最佳实践》本文介绍MySQLMCP服务器的安装配置方法,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下... 目录mysql MCP 服务器安装配置指南简介功能特点安装方法数据库配置使用MCP Inspector进行调试开发指

SQLite3命令行工具最佳实践指南

《SQLite3命令行工具最佳实践指南》SQLite3是轻量级嵌入式数据库,无需服务器支持,具备ACID事务与跨平台特性,适用于小型项目和学习,sqlite3.exe作为命令行工具,支持SQL执行、数... 目录1. SQLite3简介和特点2. sqlite3.exe使用概述2.1 sqlite3.exe

mtu设置多少网速最快? 路由器MTU设置最佳网速的技巧

《mtu设置多少网速最快?路由器MTU设置最佳网速的技巧》mtu设置多少网速最快?想要通过设置路由器mtu获得最佳网速,该怎么设置呢?下面我们就来看看路由器MTU设置最佳网速的技巧... 答:1500 MTU值指的是在网络传输中数据包的最大值,合理的设置MTU 值可以让网络更快!mtu设置可以优化不同的网