百度360必应搜狗淘宝本站头条
wireshark怎么抓包c++ base64for_eachwxsqlite3qt sleep
当前位置：网站首页 > 技术分析 > 正文

贪婪算法、统一成本搜索及A*搜索算法

liebian365 2025-03-04 12:59 10 浏览 0 评论

背景

在计算机科学中，搜索算法用来在图结构中找到目标节点。

本文会介绍几种关键的搜索算法：贪婪算法、统一成本搜索（UCS），以及A*搜索算法，并对它们进行比较，说明各自的特点和适用场景。

1、介绍和图形表示

在搜索算法中，我们通常处理的是一个图形结构，图形由节点和连接节点的边组成。

在这种结构中，搜索算法的目标是从一个起始节点找到一个目标节点。每种搜索算法都有自己独特的策略和优劣势。

2、贪婪算法

贪婪算法是一种简单且高效的搜索策略。它在每一步选择当前看起来最有希望的节点，即选择那些距离目标节点最近的节点。

贪婪算法的核心思想是“局部最优解”，即在每一步都选择局部的最优选择。然而，这种算法并不总能找到全局最优解。贪婪算法通常在处理问题时速度较快，但其结果可能不是最优的。

最符合这句话，一个精致的利己主义者，不一定会获得一个成功的人生。

贪婪算法只考虑当前节点到目标节点的启发式估计值。

import heapq

def greedy_search(graph, start, goal, heuristic):
    # 使用启发式值初始化优先队列 (open_list)
    open_list = [(heuristic[start], start)]  # 优先队列，按启发式值排序
    came_from = {}  # 记录路径
    
    while open_list:
        # 从优先队列中取出启发式值最小的节点
        _, current = heapq.heappop(open_list)
        
        # 如果当前节点是目标节点，则构建路径并返回
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]  # 返回从起点到目标的路径
        
        # 遍历当前节点的邻居节点
        for neighbor in graph[current]:
            # 如果邻居节点尚未被访问过
            if neighbor not in came_from:
                came_from[neighbor] = current  # 记录路径
                heapq.heappush(open_list, (heuristic[neighbor], neighbor))  # 将邻居节点加入优先队列
    
    return None  # 如果未找到路径，返回 None

# 示例图：邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['D', 'E'],
    'D': ['E'],
    'E': []
}

# 启发式值（到目标节点的直线距离）
heuristic = {
    'A': 10,
    'B': 6,
    'C': 4,
    'D': 2,
    'E': 0
}

# 执行贪婪搜索算法，寻找从 A 到 E 的路径
path = greedy_search(graph, 'A', 'E', heuristic)
print("贪婪路径:", path)

# 输出
# 贪婪路径: ['A', 'C', 'E']

3、统一成本搜索（UCS）

统一成本搜索（UCS）是一种基于代价的搜索算法，它考虑从起始节点到当前节点的总成本。UCS在搜索过程中选择总成本最低的节点进行扩展，因此它总是能够找到成本最低的路径。与贪婪算法相比，UCS能保证找到全局最优解，但在处理复杂的图形时可能需要更多的计算资源。

统一成本搜索算法考虑从起点到当前节点的实际成本。

import heapq

def ucs(graph, costs, start, goal):
    open_list = [(0, start)]  # 优先队列，存储当前节点及其成本
    came_from = {}
    g_costs = {start: 0}
    
    while open_list:
        current_cost, current = heapq.heappop(open_list)
        
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        for neighbor in graph[current]:
            cost = costs[(current, neighbor)]
            new_cost = current_cost + cost
            
            if neighbor not in g_costs or new_cost < g_costs[neighbor]:
                g_costs[neighbor] = new_cost
                came_from[neighbor] = current
                heapq.heappush(open_list, (new_cost, neighbor))
    
    return None

# 示例图：邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['D', 'E'],
    'D': ['E'],
    'E': []
}

# 节点之间的旅行成本
costs = {
    ('A', 'B'): 1,
    ('A', 'C'): 4,
    ('B', 'D'): 2,
    ('B', 'E'): 5,
    ('C', 'D'): 1,
    ('C', 'E'): 2,
    ('D', 'E'): 3
}

path = ucs(graph, costs, 'A', 'E')
print("UCS path:", path)

4、贪婪算法 vs UCS

贪婪算法和UCS各有优劣。

贪婪算法速度较快，但不一定能找到最优解；而UCS虽然能找到最优解，但计算复杂度较高。

选择哪种算法取决于具体的应用场景。

如果需要快速找到一个可能的解且不一定要求最优，可以选择贪婪算法；如果对解的最优性有严格要求，可以选择UCS。

贪婪算法可视化：

import matplotlib.pyplot as plt
import networkx as nx

def visualize_greedy_search(graph, heuristic, path):
    G = nx.Graph()
    for node in graph:
        for neighbor in graph[node]:
            G.add_edge(node, neighbor)
    
    pos = nx.spring_layout(G)
    
    plt.figure(figsize=(10, 7))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=16, font_weight='bold', edge_color='gray')
    nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{costs.get((u, v), 1)}' for u, v in G.edges()}, font_color='red')

    path_edges = list(zip(path, path[1:]))
    nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)
    
    plt.title('Greedy Search Path')
    plt.show()

# Example graph and heuristic
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['D', 'E'],
    'D': ['E'],
    'E': []
}
heuristic = {
    'A': 10,
    'B': 6,
    'C': 4,
    'D': 2,
    'E': 0
}

# 贪婪搜索找到的路径
path = ['A', 'C', 'E']

visualize_greedy_search(graph, heuristic, path)

统一成本搜索（UCS）可视化

def visualize_ucs(graph, costs, path):
    G = nx.Graph()
    for node in graph:
        for neighbor in graph[node]:
            G.add_edge(node, neighbor)
    
    pos = nx.spring_layout(G)
    
    plt.figure(figsize=(10, 7))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=16, font_weight='bold', edge_color='gray')
    nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{costs.get((u, v), 1)}' for u, v in G.edges()}, font_color='red')

    path_edges = list(zip(path, path[1:]))
    nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='g', width=2)
    
    plt.title('UCS Path')
    plt.show()

# 示例图和成本
costs = {
    ('A', 'B'): 1,
    ('A', 'C'): 4,
    ('B', 'D'): 2,
    ('B', 'E'): 5,
    ('C', 'D'): 1,
    ('C', 'E'): 2,
    ('D', 'E'): 3
}

# UCS找到的路径
path = ['A', 'C', 'D', 'E']

visualize_ucs(graph, costs, path)

5、A* 搜索算法

A搜索算法结合了贪婪算法和UCS的优点。它在搜索过程中同时考虑了从起始节点到当前节点的实际成本和从当前节点到目标节点的估计成本（启发式函数）。

这种方法可以显著提高搜索效率，并且在大多数情况下能找到最优解。A搜索算法的关键在于选择一个合适的启发式函数，常用的启发式函数包括曼哈顿距离和欧几里得距离。

结合实际成本和启发式信息来决定下一个节点，通常在效率和最优性之间取得良好平衡。

import heapq

def astar_search(graph, costs, start, goal, heuristic):
    open_list = [(heuristic[start], 0, start)]  # Priority queue with f(n) = g(n) + h(n)
    came_from = {}
    g_costs = {start: 0}
    
    while open_list:
        _, current_cost, current = heapq.heappop(open_list)
        
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        for neighbor in graph[current]:
            cost = costs[(current, neighbor)]
            new_cost = current_cost + cost
            
            if neighbor not in g_costs or new_cost < g_costs[neighbor]:
                g_costs[neighbor] = new_cost
                f_cost = new_cost + heuristic[neighbor]
                came_from[neighbor] = current
                heapq.heappush(open_list, (f_cost, new_cost, neighbor))
    
    return None

# 邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['D', 'E'],
    'D': ['E'],
    'E': []
}

# 节点之间的旅行成本
costs = {
    ('A', 'B'): 1,
    ('A', 'C'): 4,
    ('B', 'D'): 2,
    ('B', 'E'): 5,
    ('C', 'D'): 1,
    ('C', 'E'): 2,
    ('D', 'E'): 3
}

# 发式值（到目标的直线距离）
heuristic = {
    'A': 10,
    'B': 6,
    'C': 4,
    'D': 2,
    'E': 0
}

path = astar_search(graph, costs, 'A', 'E', heuristic)
print("A* path:", path)

# 输出
# A* path: ['A', 'B', 'E']

6、A* 搜索的最优性

A搜索算法的最优性依赖于启发式函数的设计。

如果启发式函数是“可接受的”（即从当前节点到目标节点的实际成本不大于启发式函数的估计成本），那么A搜索算法能保证找到最优解。

可接受的启发式函数包括欧几里得距离和曼哈顿距离等。

A* 搜索算法可视化

def visualize_astar_search(graph, costs, heuristic, path):
    G = nx.Graph()
    for node in graph:
        for neighbor in graph[node]:
            G.add_edge(node, neighbor)
    
    pos = nx.spring_layout(G)
    
    plt.figure(figsize=(10, 7))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=16, font_weight='bold', edge_color='gray')
    nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{costs.get((u, v), 1)}' for u, v in G.edges()}, font_color='red')

    path_edges = list(zip(path, path[1:]))
    nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='b', width=2)
    
    plt.title('A* Search Path')
    plt.show()

# 示例数据
heuristic = {
    'A': 10,
    'B': 6,
    'C': 4,
    'D': 2,
    'E': 0
}

# A*搜索找到的路径
path = ['A', 'C', 'D', 'E']

visualize_astar_search(graph, costs, heuristic, path)

结论

选择搜索算法时，可以根据问题的具体需求来决定：

  • 贪婪算法：适合时间和计算资源有限的情况，速度较快但不保证找到最优解。
  • UCS（统一代价搜索）：适用于需要找到最优解的情况，但可能计算开销较大。
  • A*搜索算法：在搜索效率和解的最优性之间取得良好平衡，适合大多数实际应用。

理解这些算法的特点可以帮助我们选择最适合的解决方案。

相关推荐

精品博文嵌入式6410中蓝牙的使用

BluetoothUSB适配器拥有一个BluetoothCSR芯片组，并使用USB传输器来传输HCI数据分组。因此，LinuxUSB层、BlueZUSB传输器驱动程序以及B...

win10跟这台计算机连接的前一个usb设备工作不正常怎么办?

前几天小编闲来无事就跑到网站底下查看粉丝朋友给小编我留言询问的问题，还真的就给小编看到一个问题，那就是win10跟这台计算机连接的一个usb设备运行不正常怎么办，其实这个问题的解决方法时十分简单的，接...

制作成本上千元的键盘，厉害在哪?

这是稚晖君亲自写的开源资料！下方超长超详细教程预警！！全文导航：项目简介、项目原理说明、硬件说明、软件说明项目简介瀚文智能键盘是一把我为自己设计的——多功能、模块化机械键盘。键盘使用模块化设计。左侧的...

E-Marker芯片，USB数据线的“性能中枢”?

根据线缆行业的研究数据，在2019年搭载Type-C接口的设备出货量已达到20亿台，其中80%的笔记本电脑和台式电脑采用Type-C接口，50%的智能手机和平板电脑也使用Type-C接口。我们都知道，...

ZQWL-USBCANFD二次开发通讯协议V1.04

修订历史：1.功能介绍1.1型号说明本文档适用以下型号：　　ZQWL-CAN(FD)系列产品，USB通讯采用CDC类实现，可以在PC机上虚拟出一个串口，串口参数N,8,1格式，波特率可以根据需要设置（...

win10系统无法识别usb设备怎么办（win10不能识别usb）

从驱动入手，那么win10系统无法识别usb设备怎么办呢?今天就为大家分享win10系统无法识别usb设备的解决方法。1、右键选择设备管理器，如图：　　2、点击更新驱动程序，如图：　　3、选择浏览...

微软七月Win8.1可选补丁有内涵，含大量修复

IT之家（www.ithome.com）：微软七月Win8.1可选补丁有内涵，含大量修复昨日，微软如期为Win7、Win8.1发布7月份安全更新，累计为6枚安全补丁，分别修复总计29枚安全漏洞，其中2...

如何从零开始做一个 USB 键盘?（怎么制作usb）

分两种情况：1、做一个真正的USB键盘，这种设计基本上不涉及大量的软件编码。2、做一个模拟的USB键盘，实际上可以没有按键功能，这种的需要考虑大量的软件编码，实际上是一个单片机。第一种设计：买现成的U...

电脑识别U盘失败?5个实用小技巧，让你轻松搞定USB识别难题

电脑识别U盘失败？5个实用小技巧，让你轻松搞定USB识别难题注意：有些方法会清除USB设备里的数据，请谨慎操作，如果不想丢失数据，可以先连接到其他电脑，看能否将数据复制出来，或者用一些数据恢复软件去扫...

未知usb设备设备描述符请求失败怎么解决

出现未知daousb设备设备描述符请求失du败解决办zhi法如下：1、按下Windows+R打开【运行】；2、在版本运行的权限输入框中输入：services.msc按下回车键打开【服务】；2、在服务...

读《飘》47章20（飘每章概括）

AndAhwouldn'tleaveMissEllen'sgrandchildrenfornotrashystep-patobringup,never.Here,Ah...

英翻中 消失的过去 37（消失的英文怎么说?）

翻译（三十七）：消失的过去/茱迪o皮考特VanishingActs/JodiPicoult”我能做什么？“直到听到了狄利亚轻柔的声音，我才意识到她已经在厨房里站了好一会儿了。当她说话的时候，...

RabbitMQ 延迟消息实战（rabbitmq如何保证消息不被重复消费）

现实生活中有一些场景需要延迟或在特定时间发送消息，例如智能热水器需要30分钟后打开，未支付的订单或发送短信、电子邮件和推送通知下午2:00开始的促销活动。RabbitMQ本身没有直接支持延迟...

Java对象拷贝原理剖析及最佳实践（java对象拷贝方法）

作者：宁海翔1前言对象拷贝，是我们在开发过程中，绕不开的过程，既存在于Po、Dto、Do、Vo各个表现层数据的转换，也存在于系统交互如序列化、反序列化。Java对象拷贝分为深拷贝和浅拷贝，目前常用的...

如何将 Qt 3D 渲染与 Qt Quick 2D 元素结合创建太阳系行星元素?

Qt组件推荐：QtitanRibbon:遵循MicrosoftRibbonUIParadigmforQt技术的RibbonUI组件，致力于为Windows、Linux和MacOSX提...

取消回复欢迎 你 发表评论:

一周热门
最近发表
标签列表
Copyright Your WebSite.Some Rights Reserved.