人工智能中的一致代价搜索

2025年2月1日 | 阅读 7 分钟

在人工智能（AI）中，一种用于在图中找到最便宜路径的搜索策略被称为一致代价搜索（Uniform Cost Search），简称 UCS。这个 Dijkstra 算法的变体特别适用于图中每条边都有不同权重的场景。其目标是找出一条连接起始节点和目标节点，并且总成本最低的路径。

一致代价搜索 (UCS) 概述

“一致代价搜索”是一种路径查找算法，它通过优先扩展成本最低的节点来确保到达目标节点的路径是成本最低的。与广度优先搜索（BFS）等其他搜索算法不同，UCS 考虑了每条路径的成本，因此适用于边成本各异的加权图。

一致代价搜索的关键概念

优先队列：UCS 将节点存储在优先队列中。具有最低累积成本的节点将首先被扩展。这确保了搜索中最有希望的路径被首先探索。
路径成本：从起始节点到某个特定节点的旅行成本。UCS 通过计算从起始节点到当前节点的累积成本，然后优先处理成本较低的节点。
扩展：当 UCS 检查一个节点时，它首先扩展成本最低的节点，并一直进行，直到到达目标节点。这保证了最便宜的路径会导向目标节点。
终止：当目标节点被扩展时，算法终止。这保证了第一次到达目标节点时找到的路径就是最优路径。

如何执行一致代价搜索？

UCS 的基本原则是从起始节点的所有潜在扩展中选择总成本最低的路径。为了维护部分路径根据从根节点开始的总成本排序，这一点通过使用优先队列来实现。

UCS 工作流程的详细步骤如下：

起始点：UCS 从根节点开始。由于尚未执行任何操作，它以累积成本零添加到优先队列中。
节点扩展：从优先队列中移除路径成本最低的节点。接下来，扩展该节点，并检查其邻居节点。
检查邻居：对于已扩展节点的每个邻居，算法会计算从起始节点经由当前节点到达该邻居的总成本。如果邻居节点尚未在队列中，则将其与计算出的成本一起添加到优先队列中。如果邻居节点已在队列中，但发现了更便宜的到达该邻居的路径，则更新队列中的成本。
目标检查：在扩展节点后，算法会检查是否已到达目标节点。如果目标已达成，则返回所经过的路径以及到达该节点的总成本。
重复：此过程会重复进行，直到达成目标或优先队列为空。

使用一致代价搜索解决路径查找问题

步骤 1：导入必要的库。

在此阶段，导入实现一致代价搜索 (UCS) 和可视化图所需的库。

 
import heapq
import networkx as nx
import matplotlib.pyplot as plt   

步骤 2：定义一致代价搜索函数

该函数应用 UCS 方法，用于在加权图中找到从起始节点到目标节点的最低成本路径。

 
def least_cost_search(graph, source, destination):
    # Initialize the queue with the starting node and cost 0
    queue = [(0, source)]
    # Store the minimum cost to reach each node and the previous node on the path
    path_info = {source: (0, None)}
    while queue:
        # Get the node with the lowest cumulative cost
        cost_so_far, current_node = heapq.heappop(queue)
        # If the destination is reached, return the total cost and reconstructed path
        if current_node == destination:
            return cost_so_far, trace_path(path_info, source, destination)
        # Explore adjacent nodes
        for neighbor, weight in graph[current_node]:
            new_cost = cost_so_far + weight
            # Update if a cheaper path to the neighbor is found
            if neighbor not in path_info or new_cost < path_info[neighbor][0]:
                path_info[neighbor] = (new_cost, current_node)
                heapq.heappush(queue, (new_cost, neighbor))   
    # Return None if the destination is unreachable
    return None   

步骤 3：建立路径重构函数

该方法通过回溯访问过的节点来重构从起始节点到目的地节点的路径。

 
def trace_path(records, start, end):
    # Reconstruct the path by backtracking from the end to the start
    path = []
    node = end
    while node is not None:
        path.append(node)
        node = records[node][1]
    return path[::-1]   

步骤 4：定义可视化函数

该函数使用 networkx 创建图，并使用 matplotlib 进行可视化，展示图以及 UCS 找到的路径。

 
import networkx as nx
import matplotlib.pyplot as plt
def plot_graph_with_path(adj_list, route=None):
    # Create a directed graph object
    graph_obj = nx.DiGraph()
    # Add nodes and edges from the adjacency list
    for src, neighbors in adj_list.items():
        for dest, weight in neighbors:
            graph_obj.add_edge(src, dest, weight=weight)
    # Generate positions for the nodes
    layout = nx.spring_layout(graph_obj)  
    # Plotting the graph
    plt.figure(figsize=(8, 6))
    nx.draw(
        graph_obj, layout, with_labels=True, node_color='skyblue', 
        node_size=2200, font_size=14, font_weight='bold', edge_color='black'
    )    
    # Adding weight labels on edges
    edge_labels = nx.get_edge_attributes(graph_obj, 'weight')
    nx.draw_networkx_edge_labels(graph_obj, layout, edge_labels=edge_labels, font_size=12)
    if route:
        # Highlight the given route in red
        highlighted_edges = list(zip(route, route[1:]))
        nx.draw_networkx_edges(graph_obj, layout, edgelist=highlighted_edges, edge_color='crimson', width=3)
    plt.title("Graph with Highlighted Path")
    plt.show()   

步骤 5：实现 UCS 并定义图

在此阶段，设置起始节点和目标节点，执行 UCS 算法，并定义一个作为邻接列表的示例图。然后显示图和找到的路径。

 
# Example graph represented as an adjacency list
adj_list = {
    'X': [('Y', 2), ('Z', 3)],
    'Y': [('P', 2), ('Q', 4)],
    'Z': [('R', 6)],
    'P': [('S', 3)],
    'Q': [('S', 2)],
    'R': [('S', 1)],
    'S': []
}
# Example usage of the least_cost_search function
origin = 'X'
destination = 'S'
result = least_cost_search(adj_list, origin, destination)
if result:
    total_cost, route = result
    print(f"Optimal path from {origin} to {destination}: {' -> '.join(route)} with total cost {total_cost}")
    plot_graph_with_path(adj_list, route)
else:
    print(f"No path found from {origin} to {destination}")   

完整代码

 
import heapq
import networkx as nx
import matplotlib.pyplot as plt
def least_cost_search(graph, source, destination):
    queue = [(0, source)]
    path_info = {source: (0, None)}
    while queue:
        cost_so_far, current_node = heapq.heappop(queue)
        if current_node == destination:
            return cost_so_far, trace_path(path_info, source, destination)
        for neighbor, weight in graph[current_node]:
            new_cost = cost_so_far + weight
            if neighbor not in path_info or new_cost < path_info[neighbor][0]:
                path_info[neighbor] = (new_cost, current_node)
                heapq.heappush(queue, (new_cost, neighbor))
    return None
def trace_path(records, start, end):
    path = []
    node = end
    while node is not None:
        path.append(node)
        node = records[node][1]
    return path[::-1]
def plot_graph_with_path(adj_list, route=None):
    graph_obj = nx.DiGraph()
    for src, neighbors in adj_list.items():
        for dest, weight in neighbors:
            graph_obj.add_edge(src, dest, weight=weight)
    layout = nx.spring_layout(graph_obj)
    plt.figure(figsize=(8, 6))
    nx.draw(
        graph_obj, layout, with_labels=True, node_color='skyblue', 
        node_size=2200, font_size=14, font_weight='bold', edge_color='black'
    )
    edge_labels = nx.get_edge_attributes(graph_obj, 'weight')
    nx.draw_networkx_edge_labels(graph_obj, layout, edge_labels=edge_labels, font_size=12)
    if route:
        highlighted_edges = list(zip(route, route[1:]))
        nx.draw_networkx_edges(graph_obj, layout, edgelist=highlighted_edges, edge_color='crimson', width=3)
    plt.title("Graph with Highlighted Path")
    plt.show()
adj_list = {
    'X': [('Y', 2), ('Z', 3)],
    'Y': [('P', 2), ('Q', 4)],
    'Z': [('R', 6)],
    'P': [('S', 3)],
    'Q': [('S', 2)],
    'R': [('S', 1)],
    'S': []
}
origin = 'X'
destination = 'S'
result = least_cost_search(adj_list, origin, destination)
if result:
    total_cost, route = result
    print(f"Optimal path from {origin} to {destination}: {' -> '.join(route)} with total cost {total_cost}")
    plot_graph_with_path(adj_list, route)
else:
    print(f"No path found from {origin} to {destination}")   

说明

这段代码仅仅实现了 UCS 算法，该算法用于在加权图中找到给定源节点到目标节点的最低成本路径。其中，我们有 least_cost_search() 函数，它使用优先队列根据累积成本探索节点，并返回最优路径及其总成本；trace_path() 通过从目的地追溯到源节点来重构路径。最后，plot_graph_with_path 函数绘制图并高亮显示找到的路径。通过一个简单的图的邻接列表示例，计算并显示了从 'X' 到 'S' 的最优路径。

输出

Uniform Cost Search in Artificial Intelligence

UCS 在人工智能中的应用

一致代价搜索在多个 AI 领域有广泛的应用，包括：

地图导航：在地图上计算两点之间的最短路径，并考虑不同的路径成本。
网络路由：在数据或通信网络中找到最低成本的路径。
解谜：解决滑动拼图等谜题，其中每一步都有成本。
资源分配：涉及有效资源分配的活动，其中不同的分配选项都有相应的成本。

一致代价搜索的优点

最优性：如果每一步的成本都大于零，UCS 保证能找到到达目标状态的最便宜路径。
完备性：如果存在解决方案，该方法是完备的，并且能够找到它。

UCS 的挑战

空间复杂度：UCS 的主要缺点是空间复杂度。特别是在添加大量节点时，优先队列可能会显著增长。
时间复杂度：寻找最低成本路径可能需要很长时间，特别是当状态空间很大时。

结论

当不同的路径具有不同的成本，并且目标是最小化总成本时，一致代价搜索是一种强大的人工智能方法。它在各个领域的应用证明了其适应性和效用。对于实际实现，理解其计算需求至关重要，特别是在处理有限的处理资源或大型数据集的情况下。

下一主题人工智能工作

人工智能中的一致代价搜索

一致代价搜索 (UCS) 概述

如何执行一致代价搜索？

使用一致代价搜索解决路径查找问题

UCS 在人工智能中的应用

一致代价搜索的优点

UCS 的挑战

结论

联系信息

关注我们

教程

面试题

在线编译器

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

人工智能选择题

其他

相关教程

人工智能中的一致代价搜索

一致代价搜索 (UCS) 概述

如何执行一致代价搜索？

使用一致代价搜索解决路径查找问题

UCS 在人工智能中的应用

一致代价搜索的优点

UCS 的挑战

结论

相关帖子

人工智能法

人工智能中的局部搜索算法

AI 中的倒水问题

从事人工智能研究的公司

AI 如何改变工业安全

印度人工智能领域的政府工作

人工智能在社交媒体中的应用

AI 中的问题解决技术

十大动画 AI 工具

人工智能博士

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器