人工智能中的贪婪最佳优先搜索

2025年3月31日 | 阅读10分钟

人工智能发展迅速，因此，在解决复杂问题方面，对开发各种搜索方法的需求巨大。其中，GBFS因其易于使用且在特定条件下有效，尤其在路径查找和问题解决方面备受青睐。

贪婪最佳优先搜索：原理、优点、缺点及更多人工智能中的实际应用。

贪婪最佳优先搜索概述

贪婪最佳优先搜索（GBFS）是一种网络遍历算法，在人工智能中用于解决具有多种可行解的问题，或确定两点之间的最短路径。

由于它使用评估函数来选择下一步，并专注于尽快接近目标，因此被归类为启发式搜索算法。

GBFS被归类为一种有信息搜索算法，这意味着搜索过程在决策阶段受到问题信息的指导。

贪婪最佳优先搜索的过程是什么？

在遍历图的节点时，贪婪最佳优先搜索算法会优先考虑那些最接近目标状态的节点。“贪婪”部分源于其倾向于选择看起来能最快达到目标的节点，通常以启发式函数为指导。

该方法速度很快，但如果它选择的路径未能导向解决方案，则可能不完整，因为它不会回溯或考虑那些看起来不太理想的节点。

贪婪最佳优先搜索算法的步骤

以下是贪婪最佳优先搜索算法的简洁、顺序解释：

开始：从第一个节点开始，通常是根节点或起点。将此节点放入优先级队列。
扩展节点：分析当前节点的所有相邻节点。根据启发式函数，为每个节点分配一个估计到目标距离的值。
选择最佳节点：从优先级队列中选择启发式值最低的节点（看起来最接近目标的节点）。
目标验证：如果选定的节点是目标，则停止搜索。
继续：如果不是，则继续到下一个节点，重复步骤2到4，直到达到目标或队列为空。

贪婪最佳优先搜索启发式

所使用的启发式函数对GBFS的有效性有重大影响。启发式函数是计算当前节点到目标的大致成本的函数。典型的启发式方法包括：

欧几里得距离：从当前节点到目标点的直线距离（用于路径查找问题）。
曼哈顿距离：（在基于网格的环境中）两个位置的坐标之间的绝对差值之和。

启发式的选择会影响算法的行为以及它能否快速找到最佳解决方案。

贪婪最佳优先搜索用于分层路由

步骤1：定义节点类

解释：为了表示图中的每个节点，我们定义了一个Node类。__lt__函数允许根据其启发式值对节点进行比较，并且该类会记录节点的名称和启发式值。维护优先级队列依赖于此。

# Node class to represent a node in the graph
class GraphNode:
    def __init__(self, name, heuristic_value):
        self.name = name
        self.heuristic_value = heuristic_value
    def __lt__(self, other):
        return self.heuristic_value < other.heuristic_value  # For priority queue comparison   

步骤2：实现贪婪最佳优先搜索算法

解释：这个函数实现了贪婪最佳优先搜索算法。它从第一个节点开始，将其加入优先级队列，然后根据节点的启发式值进行探索。它优先处理同一区域内的节点，并在需要时继续探索其他区域的节点。

# Greedy Best-First Search for Region-Based Routing
def region_based_search(city_map, start_point, end_point, cost_map, zone_map):
    queue = []  # Priority queue to explore locations based on heuristic value
    heapq.heappush(queue, GraphNode(start_point, cost_map[start_point]))  # Add starting node
    visited = set()  # Track visited nodes
    path = {start_point: None}  # Track the path
    while queue:
        current_location = heapq.heappop(queue).name  # Get node with the lowest heuristic
        if current_location == end_point:  # If the goal is reached
            return rebuild_path(path, start_point, end_point)
        visited.add(current_location)  # Mark node as visited
        # First, explore neighbors in the same region (zone)
        current_zone = zone_map[current_location]
        for neighbor in city_map[current_location]:
            if neighbor not in visited and zone_map[neighbor] == current_zone:
                heapq.heappush(queue, GraphNode(neighbor, cost_map[neighbor]))
                if neighbor not in path:
                    path[neighbor] = current_location
        # Then, explore neighbors in different zones
        for neighbor in city_map[current_location]:
            if neighbor not in visited and zone_map[neighbor] != current_zone:
                heapq.heappush(queue, GraphNode(neighbor, cost_map[neighbor]))
                if neighbor not in path:
                    path[neighbor] = current_location
    return None  # Return None if no path is found   

步骤3：重建路径

解释：一旦到达目标节点，这个辅助函数就会通过路径字典回溯，以重建从起点到目标的路径。

# Helper function to rebuild the path from start to end
def rebuild_path(path, start_point, end_point):
    current = end_point
    result = []
    while current is not None:
        result.append(current)  # Add node to the path
        current = path[current]  # Move to the previous node
    result.reverse()  # Reverse to get the correct order
    return result   

步骤4：可视化图和路径

解释：这个函数使用networkx和matplotlib来突出显示搜索算法找到的路径并可视化图。此外，它还会标记节点以反映其区域。

# Function to visualize the graph and the resulting path
def draw_graph(city_map, result_path, coordinates, zone_map):
    G = nx.Graph()
    # Add edges to the graph
    for node, neighbors in city_map.items():
        for neighbor in neighbors:
            G.add_edge(node, neighbor)
    plt.figure(figsize=(10, 8))  # Set the plot size
    # Draw nodes and edges
    nx.draw(G, coordinates, with_labels=True, node_size=3000, node_color='lightblue', 
            font_size=14, font_weight='bold', edge_color='gray')
    # Highlight the path if one was found
    if result_path:
        path_edges = list(zip(result_path, result_path[1:]))
        nx.draw_networkx_edges(G, coordinates, edgelist=path_edges, edge_color='green', width=3)
        nx.draw_networkx_nodes(G, coordinates, nodelist=result_path, node_color='yellow')
    # Label the zones on the graph
    for node, zone in zone_map.items():
        plt.text(coordinates[node][0], coordinates[node][1] - 0.2, f"Zone {zone}", fontsize=12, color='black')
    plt.title("Greedy Best-First Search for Regional Routing", size=18)
    plt.show()   

步骤5：定义图和启发式值

解释：我们定义了图的结构，其中节点相互连接。为了指导搜索，还为每个节点和区域设置了启发式值。

# Graph structure with hierarchical zones
city_map = {
    'X': ['Y', 'Z'],
    'Y': ['A', 'B'],
    'Z': ['C', 'D'],
    'A': ['E'],
    'B': ['F', 'G'],
    'C': ['H', 'I'],
    'D': ['J'],
    'E': [], 'F': [], 'G': [], 'H': [], 'I': [], 'J': []
}
# Heuristic values (assumed for this example)
cost_map = {
    'X': 10, 'Y': 8, 'Z': 9, 'A': 6, 'B': 5, 'C': 6, 'D': 7, 
    'E': 4, 'F': 2, 'G': 3, 'H': 3, 'I': 1, 'J': 1
}
# Zone mapping for hierarchical routing
zone_map = {
    'X': 1, 'Y': 1, 'Z': 1, 'A': 2, 'B': 2, 'C': 3, 'D': 3, 
    'E': 2, 'F': 2, 'G': 2, 'H': 3, 'I': 3, 'J': 3
}   

步骤6：执行搜索并可视化结果

解释：通过定义起始节点和目标节点，并利用指定的图和启发式来可视化结果路径，我们开始了贪婪最佳优先搜索。

# Define positions for better visualization layout (adjustable)
coordinates = {
    'X': (0, 0), 'Y': (-1, 1), 'Z': (1, 1), 'A': (-1.5, 2), 
    'B': (-0.5, 2), 'C': (0.5, 2), 'D': (1.5, 2), 'E': (-1.5, 3), 
    'F': (-0.5, 3), 'G': (0.5, 3), 'H': (1, 3), 'I': (2, 3), 'J': (3, 3)
}
# Start and goal nodes
start_point = 'X'
end_point = 'I'
# Perform the Greedy Best-First Search for hierarchical routing
result_path = region_based_search(city_map, start_point, end_point, cost_map, zone_map)
# Print the resulting path
print(f"Path from {start_point} to {end_point}: {result_path}")
# Visualize the graph and the discovered path
draw_graph(city_map, result_path, coordinates, zone_map)   

完整代码：分层路由的贪婪最佳优先搜索

import heapq  # For priority queue operations
import networkx as nx  # For graph visualization
import matplotlib.pyplot as plt  # For plotting
# Step 1: Define the Node Class
# Node class to represent a node in the graph
class GraphNode:
    def __init__(self, name, heuristic_value):
        self.name = name
        self.heuristic_value = heuristic_value
    def __lt__(self, other):
        return self.heuristic_value < other.heuristic_value  # For priority queue comparison
# Step 2: Implement Greedy Best-First Search Algorithm
# Greedy Best-First Search for Region-Based Routing
def region_based_search(city_map, start_point, end_point, cost_map, zone_map):
    queue = []  # Priority queue to explore locations based on heuristic value
    heapq.heappush(queue, GraphNode(start_point, cost_map[start_point]))  # Add starting node
    visited = set()  # Track visited nodes
    path = {start_point: None}  # Track the path
    while queue:
        current_location = heapq.heappop(queue).name  # Get node with the lowest heuristic
        if current_location == end_point:  # If the goal is reached
            return rebuild_path(path, start_point, end_point)
        visited.add(current_location)  # Mark node as visited
        # First, explore neighbors in the same region (zone)
        current_zone = zone_map[current_location]
        for neighbor in city_map[current_location]:
            if neighbor not in visited and zone_map[neighbor] == current_zone:
                heapq.heappush(queue, GraphNode(neighbor, cost_map[neighbor]))
                if neighbor not in path:
                    path[neighbor] = current_location
        # Then, explore neighbors in different zones
        for neighbor in city_map[current_location]:
            if neighbor not in visited and zone_map[neighbor] != current_zone:
                heapq.heappush(queue, GraphNode(neighbor, cost_map[neighbor]))
                if neighbor not in path:
                    path[neighbor] = current_location
    return None  # Return None if no path is found
# Step 3: Reconstruct the Path
# Helper function to rebuild the path from start to end
def rebuild_path(path, start_point, end_point):
    current = end_point
    result = []
    while current is not None:
        result.append(current)  # Add node to the path
        current = path[current]  # Move to the previous node
    result.reverse()  # Reverse to get the correct order
    return result
# Step 4: Visualize the Graph and Path
# Function to visualize the graph and the resulting path
def draw_graph(city_map, result_path, coordinates, zone_map):
    G = nx.Graph()
    # Add edges to the graph
    for node, neighbors in city_map.items():
        for neighbor in neighbors:
            G.add_edge(node, neighbor)
    plt.figure(figsize=(10, 8))  # Set the plot size
    # Draw nodes and edges
    nx.draw(G, coordinates, with_labels=True, node_size=3000, node_color='lightblue',
            font_size=14, font_weight='bold', edge_color='gray')
    # Highlight the path if one was found
    if result_path:
        path_edges = list(zip(result_path, result_path[1:]))
        nx.draw_networkx_edges(G, coordinates, edgelist=path_edges, edge_color='green', width=3)
        nx.draw_networkx_nodes(G, coordinates, nodelist=result_path, node_color='yellow')
    # Label the zones on the graph
    for node, zone in zone_map.items():
        plt.text(coordinates[node][0], coordinates[node][1] - 0.2, f"Zone {zone}", fontsize=12, color='black')
    plt.title("Greedy Best-First Search for Regional Routing", size=18)
    plt.show()
# Step 5: Define the Graph and Heuristic Values
# Graph structure with hierarchical zones
city_map = {
    'X': ['Y', 'Z'],
    'Y': ['A', 'B'],
    'Z': ['C', 'D'],
    'A': ['E'],
    'B': ['F', 'G'],
    'C': ['H', 'I'],
    'D': ['J'],
    'E': [], 'F': [], 'G': [], 'H': [], 'I': [], 'J': []
}
# Heuristic values (assumed for this example)
cost_map = {
    'X': 10, 'Y': 8, 'Z': 9, 'A': 6, 'B': 5, 'C': 6, 'D': 7,
    'E': 4, 'F': 2, 'G': 3, 'H': 3, 'I': 1, 'J': 1
}
# Zone mapping for hierarchical routing
zone_map = {
    'X': 1, 'Y': 1, 'Z': 1, 'A': 2, 'B': 2, 'C': 3, 'D': 3,
    'E': 2, 'F': 2, 'G': 2, 'H': 3, 'I': 3, 'J': 3
}
# Step 6: Execute the Search and Visualize the Result
# Define positions for better visualization layout (adjustable)
coordinates = {
    'X': (0, 0), 'Y': (-1, 1), 'Z': (1, 1), 'A': (-1.5, 2),
    'B': (-0.5, 2), 'C': (0.5, 2), 'D': (1.5, 2), 'E': (-1.5, 3),
    'F': (-0.5, 3), 'G': (0.5, 3), 'H': (1, 3), 'I': (2, 3), 'J': (3, 3)
}
# Start and goal nodes
start_point = 'X'
end_point = 'I'
# Perform the Greedy Best-First Search for hierarchical routing
result_path = region_based_search(city_map, start_point, end_point, cost_map, zone_map)
# Print the resulting path
print(f"Path from {start_point} to {end_point}: {result_path}")
# Visualize the graph and the discovered path
draw_graph(city_map, result_path, coordinates, zone_map)   

说明

这个Python脚本实现了图中分层路由的贪婪最佳优先搜索技术。首先需要定义一个GraphNode类来表示具有启发式值的网络中的节点。region_based_search函数在启发式成本的指导下，优先处理同一区域内的节点，然后再分支到其他区域来探索图。rebuild_path方法在到达目标节点后，从起点重建到目标的路径。draw_graph函数使用Matplotlib和NetworkX可视化图，并突出显示找到的路径。然后，脚本从节点'X'到'I'执行搜索并显示结果。

输出

Greedy Best-First Search in Artificial Intelligence

贪婪最佳优先搜索的优点

速度：由于GBFS利用启发式知识，通常比广度优先搜索等无信息搜索算法更快。
简单性：当速度比最优性更重要时，该算法因其易于构建和理解而成为一个受欢迎的选择。
资源效率：它可能比A*等算法使用更少的内存，因为它专注于最有希望的路径。

贪婪最佳优先搜索的局限性

不完整：由于GBFS不考虑回溯，如果它陷入局部最优或死胡同，可能无法找到解决方案。
非最优：不能保证算法会找到最佳或最短的路径。它可能导致次优解决方案，因为它主要考虑短期利益（贪婪地选择最近的节点）。
依赖于启发式：启发式的质量对GBFS的有效性和成功率有重大影响。糟糕的启发式可能导致搜索效率低下。

贪婪最佳优先搜索在人工智能中的应用

贪婪最佳优先搜索在多个计算机科学和人工智能领域都有应用：

路径查找：用于在视频游戏AI和地图导航系统中，从一个位置到另一个位置的有效路径查找。
拼图解决：常用于需要将磁贴按特定顺序排列的游戏，例如8数码问题或15数码问题。
机器人导航：协助自主机器人导航其环境，将它们引导到目标的最直接路径。
人工智能规划：当问题有多种可能解决方案且需要有效路径来达到目标时，会使用GBFS。

结论

当时间和资源限制是首要考虑因素时，贪婪最佳优先搜索是一种强大而有效的搜索算法，可以快速找到问题解决方案。然而，有时它的贪婪可能会误导它，导致它在复杂情况下失败或错过最佳答案。它有多大用处取决于具体问题，尤其是在与正确的启发式函数配合使用时。

下一主题人工智能的未来想法

人工智能中的贪婪最佳优先搜索

贪婪最佳优先搜索概述

贪婪最佳优先搜索的过程是什么？

贪婪最佳优先搜索算法的步骤

贪婪最佳优先搜索启发式

贪婪最佳优先搜索用于分层路由

贪婪最佳优先搜索的优点

贪婪最佳优先搜索的局限性

贪婪最佳优先搜索在人工智能中的应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

人工智能

智能体

解决问题

对抗性搜索

知识表示

不确定知识 R.

AI 的子集

现实世界中的 AI

人工智能选择题

其他

相关教程

人工智能中的贪婪最佳优先搜索

贪婪最佳优先搜索概述

贪婪最佳优先搜索的过程是什么？

贪婪最佳优先搜索算法的步骤

贪婪最佳优先搜索启发式

贪婪最佳优先搜索用于分层路由

贪婪最佳优先搜索的优点

贪婪最佳优先搜索的局限性

贪婪最佳优先搜索在人工智能中的应用

结论

相关帖子

孟买的人工智能工作

从事人工智能研究的公司

人工智能中有多少命题符号？

5 种展示人工智能偏见的算法

人工智能艺术

加拿大的人工智能课程

人工智能回归阅读答案

2025 年最佳儿童 AI 学习工具

AI 生成内容的优缺点

十大人工智能迷你项目

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器