人工智能中的穷举搜索

2025年4月1日 | 阅读 15 分钟

穷举搜索是一种暴力破解技术，它通过生成问题域内的所有元素，识别哪些元素满足所有指定的约束条件，然后选择满足特定标准的元素（如优化某个目标函数）来寻找问题的解。

尽管这听起来可能是一个显而易见的穷举搜索思路，但实际执行起来却并不那么简单。它通常需要专门设计的算法来生成特定的组合对象，例如排列组合或子集。这些算法有助于高效地筛选搜索空间，这主要源于组合问题。

例如，考虑一个确定旅行推销员应该如何规划行程以访问一组城市的问题。这种穷举搜索将计算每种可能路线配置的总距离，然后确定最短距离。这种暴力破解方法用于寻找最优解，但随着城市数量的增加，由于可能路线的阶乘增长，它会变得非常不切实际。

虽然穷举搜索的基本原理很直观，但在生成和评估所有解决方案的方法中，实际问题的处理方式却非常棘手。因此，我们将等到下一章再详细讨论这些组合生成算法，并介绍使穷举搜索策略可行的必要方法和技术。

一些展示穷举搜索概念的组合问题包括旅行推销员问题、背包问题和分配问题。它们各自独立地展示了如何使用穷举搜索来获得最优解的不同方面。

Travelling Salesman Problem

旅行推销员问题（TSP）已引起研究人员 150 多年的关注，部分原因是它简单的表述、重要的现实世界应用以及与其他组合问题的有趣联系。其核心在于，TSP 提出了一个非常基本的问题：如何找到一条最短的路线，使旅行者能够访问给定的 n 个城市，即每个城市只访问一次，然后返回出发点？

这可以表示为加权图，其中顶点代表城市，边上的权重代表城市之间的距离。在这种情况下，TSP 可以重构为在图上寻找最短的哈密顿回路。哈密顿回路，以爱尔兰数学家威廉·罗文·汉密尔顿（1805-1865）命名，是一个闭合回路，它恰好遍历图中的每个顶点一次。汉密尔顿的这些研究属于他新代数的一种迷人应用。

TSP 的理论兴趣对现实世界有广泛的影响。例如，在物流和供应链管理中，TSP 通过减少运输货物的路线来最大限度地降低交付成本和时间。它还有助于减少连接电路中一组组件所需的导线长度。此外，TSP 已与其他几种组合问题相关联，例如车辆路径问题和作业调度问题，这些问题展示了所面临的优化挑战的普遍性。

TSP 是一个 NP-hard 问题，这意味着不存在能够在多项式时间内解决该问题所有实例的有效算法。该问题简单的前提催生了许多启发式和近似算法，研究人员可以利用这些算法在合理的时间内为大型数据集找到接近最优的解决方案。

出于实际目的，我们可以做出一个简化的假设，即所有哈密顿回路都从一个选定的顶点开始并在此结束，而不会损失普遍性。这是因为根据定义，所有回路都是环。选择一个顶点作为起点，可以在不牺牲方向感的情况下极大地简化我们的问题。

我们可以生成中间城市的所有排列。这些排列中的每一种都是要访问的城市的不同安排。然后，我们可以系统地计算行程的长度。之后，我们可以从中选择最短的行程，这是通过计算每个排列的总距离来找到的。

这种系统的方法不仅为解决 TSP 提供了清晰的路径，还突显了问题的组合性质，因为随着城市数量的增加，排列的数量会呈阶乘增长。因此，这意味着，尽管这种方法在小数据集上很简单，但在较大的数据集上，由于可能路线的数量呈指数级增长，因此在计算上是不切实际的。这通常促使研究人员和从业者转向更先进的算法和启发式方法来解决更大实例的 TSP。

考虑一个包含 4 个城市的示例，并给出一个包含城市之间距离的距离矩阵。

距离矩阵 = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]，为了找到最小成本，我们应用暴力破解方法来解决问题，该方法生成所有可能的路线并找到每条路线的总距离。由于有 4 个城市，可能的路线数量是 3! = 6，因为起点是固定的。让我们计算每条路线的距离。

城市：0, 1, 2, 3

假设城市 0 是我们的起点，我们要计算所有可能的路线

路线 1: 0 🡒 1 🡒 2 🡒 3🡒0

0 🡒 1 = 10
1 🡒 2 = 35
2 🡒 3 = 30
3 🡒0 = 20

总距离 = 10 + 35 +_30 + 20 = 95

路线 2: 0🡒1 🡒 3🡒 2 🡒0

0 🡒 1 = 10
1 🡒 3 = 25
3 🡒 2 = 30
2 🡒 0 = 15

总距离 = 10 + 25 + 30 + 15 = 80

路线 3: 0 🡒 2 🡒 1 🡒 3🡒 0

0 🡒 2 = 15
2 🡒 1 = 35
1 🡒 3 = 25
3 🡒 0 = 20

总距离 = 15 + 35 + 25 + 20 = 95

路线 4: 0 🡒 2 🡒 3 🡒 1 🡒 0

0 🡒 2 = 15
2 🡒 3 = 30
3 🡒 1 = 25
1 🡒 0 = 10

总距离 = 15 + 30 + 25 + 10 = 80

路线 5: 0 🡒 3 🡒 1 🡒 2 🡒 0

0 🡒 3 = 20
3 🡒 1 = 25
1 🡒 2 = 35
2 🡒 0 = 15

总距离 = 20 + 25 + 35 + 15 = 95

路线 6: 0 🡒 3 🡒 2 🡒 1 🡒 0

0 🡒 3 = 20

3 🡒 2 = 30

2 🡒 1 = 35

1 🡒 0 = 10

总距离 = 20 + 30 + 35 + 10 = 95

因此，路线 1、2、3、4、5 和 6 的总距离分别为 95、80、95、80、95、95。因此，最小距离或最小成本是 80，最优路径是

路线 2: 0 🡒 1 🡒 3 🡒 2 🡒 0

路线 4: 0 🡒 2 🡒 3 🡒 1 🡒 0

让我们来看一段 Python 实现旅行推销员问题的代码

代码

import itertools
def calculate_route_cost(route, distance_matrix):
    total_cost = 0
    num_cities = len(route)
    for i in range(num_cities - 1):
        total_cost += distance_matrix[route[i]][route[i + 1]]
    total_cost += distance_matrix[route[-1]][route[0]]
    return total_cost

def traveling_salesman_brute_force(distance_matrix):
    num_cities = len(distance_matrix)
    city_indices = list(range(num_cities))
    all_possible_routes = itertools.permutations(city_indices)
    min_cost = float('inf')
    best_route = None

    for the route in all_possible_routes:
        route_cost = calculate_route_cost(route, distance_matrix)
        if route_cost < min_cost:
            min_cost = route_cost
            best_route = route
    
    return best_route, min_cost
if __name__ == "__main__":
    distance_matrix = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]
    
    best_route, min_cost = traveling_salesman_brute_force(distance_matrix)
    
    print("Best route:", best_route)
    print("Minimum cost:", min_cost)   

输出

 
Best route: (0, 1, 3, 2)
Minimum cost: 80

说明

在上述 Python 代码中，旅行推销员问题是通过暴力破解解决方案实现的，该方案计算访问所有城市并返回起点的最小成本路线。该函数根据给定的距离矩阵（包含从一个城市到另一个城市的距离）计算路线成本并评估给定路线的总距离。该函数使用 `itertools.permutations` 生成所有可能的城市路线，然后评估总成本并确定成本最低的路线。最后，程序打印出最佳路线，并给出给定距离矩阵的最小成本。

背包问题

在人工智能中，背包问题用于模拟需要条件下决策的现实世界问题。解决背包问题的一些人工智能方法包括：

动态规划 (DP): 这是一种最优方法，其中创建一个表，表的每个条目都由具有给定容量可以达到的最佳值表示。该问题的时间复杂度为 O(nW)，其中 n 是物品数量，W 是背包容量。使用动态规划解决此问题的优点是它能给出最优解，而缺点是由于空间和时间复杂度，它对 W 的大值效率不高。
贪心算法（解决分数背包问题）: 在此方法中，按价值重量比对物品进行排序，然后选择最高比率的物品，直到背包装满为止。由于排序，此解决方案的时间复杂度为 O(nlogn)，效率很高。此算法不适用于 0/1 背包问题，因为它可能无法给出最优解。
遗传算法 (GA): 这是一种元启发式方法，基于进化过程。它将潜在解决方案表示为种群中的个体，并通过交叉、变异和选择机制随时间演化它们。遗传算法的优点在于可以轻松处理大型复杂的问题空间，包括各种背包问题。它可能不总是给出最优解，但它可以找到近似最优解。
模拟退火 (SA): 这是另一种元启发式方法，其灵感来自冶金学中的退火过程。它从初始解决方案开始，通过随机变化来寻找解决方案空间，随着冷却过程的进行，搜索空间会缩小。此算法的主要优点是它可以找到局部最优解并逃离它，探索大型解决方案空间。此算法对于复杂问题可能很慢，并且不能保证它能找到全局最优解。
粒子群优化 (PSO): PSO 从鸟类或鱼类的社会行为中获得灵感来寻找最优解。在此算法中，每个粒子代表一个潜在解决方案，粒子根据其个人最佳位置和全局最佳位置在解决方案空间中“飞行”。此算法的主要优点是它适用于连续和大型搜索空间。它需要仔细调整参数，例如惯性、认知和社会成分。

考虑三个物品，它们的价值分别为 60、100 和 120，重量分别为 10、20 和 30。背包的容量为 50。让我们计算价值重量比

物品 1: 60/10 = 6
物品 2: 100/20 = 5
物品 3: 120/20 = 4

根据价值重量比，物品按价值重量比降序排序，因此顺序变为

物品 1 (比率 = 6), 物品 2 (比率 = 5), 物品 3 (比率 = 4)。

让我们将物品添加到背包中

物品 1: 重量 = 10 (到目前为止的总重量 = 10，剩余容量：50 - 10 = 40)。物品 1 的全部重量都可以添加到背包中，贡献其全部价值 60。
物品 2: 重量 = 20 (到目前为止的总重量：10 + 2 = 30，剩余容量：40 - 20 = 20)，物品 2 的全部重量都可以添加，贡献全部价值 100。
物品 3: 重量 = 30。背包中只有 20 单位的重量可用，所以只取物品 3 的一部分。取的部分是 20/30 = 2/3。物品 3 贡献的价值 = 120 x 2/3 = 80。

让我们计算总价值

物品 1 的价值：60
物品 2 的价值：100
物品 3 的价值：80（部分）

背包中的总最大价值 = 60 + 100 + 80 = 240。

让我们在 Python 中实现这个例子。

代码

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value/weight  

def fractional_knapsack(capacity, items):
    items.sort(key=lambda item: item.ratio, reverse=True)
    
    total_value = 0 
    current_weight = 0 
    
    for item in items:
        if current_weight + item.weight <= capacity:
          
            total_value += item.value
            current_weight += item.weight
        else:
            
            remaining_capacity = capacity - current_weight
            fraction = remaining_capacity / item.weight
            total_value += item.value * fraction
            current_weight += item.weight * fraction
            break 
    
    return total_value
if __name__ == "__main__":
    items = [
        Item(60, 10), 
        Item(100, 20),
        Item(120, 30)  
    ]
    knapsack_capacity = 50
    max_value = fractional_knapsack(knapsack_capacity, items)
    print("Maximum value in the knapsack:", max_value)   

输出

 
Maximum value in the Knapsack: 240.0

说明

上面的代码用于实现分数背包问题，使用贪心算法。这里，`Item` 类包含每个物品的价值和重量，并计算价值重量比。它使用 `fraction_knapsack` 函数，该函数按比率降序对物品进行排序。然后，它遍历排序后的物品，如果空间允许，则添加每个物品的全部重量到背包，否则添加一部分，直到达到容量限制。该函数返回给定背包容量的最大可能值。在此示例中，容量为 50，并评估并显示最大价值。

分配问题

分配问题是组合数学和人工智能中的一个基本优化问题，该算法的目标是以最高效的方式将一组问题分配给一组代理，通常用于最小化成本或最大化利润。对此问题的完全搜索涉及通过访问所有可能的分配来获得最优解。

分配问题中的人工智能技术

匈牙利算法: 这是一种算法，可以在多项式时间复杂度内解决最优分配问题，而无需实际计算必要的排列。
遗传算法: 这是一种启发式算法，其中一组潜在的分配会随着时间的推移通过交叉和变异而演化，以找到接近最优的解决方案。

N皇后问题

这是组合学中一个经典的难题，要求 N 个皇后以某种方式占据一个 NxN 的棋盘，使得任意两个皇后都不能互相威胁。国际象棋中的皇后可以水平、垂直或对角线向任意方向移动，因此任何两个皇后都不应共享同一行、列或对角线。N 皇后问题有多种应用，它作为人工智能算法设计的基准，包括处理大的解决方案空间、约束和优化。它用于约束满足问题，其中许多实时 AI 问题包含约束，这使得 N 皇后成为一个有用的抽象。它还用于调度和资源分配以及并行计算，其中皇后在棋盘上无冲突地分布。它还有助于设计避免争用共享资源的并行系统。

代码

def print_board(board):
    for row in board:
        print(" ".join("Q" if col else "." for col in row))
    print("\n")

def is_safe(board, row, col, n):
    # Check column
    for i in range(row):
        if board[i][col]:
            return False

    # Check the upper-left diagonal
    i, j = row, col
    while i >= 0 and j >= 0:
        if board[i][j]:
            return False
        i -= 1
        j -= 1

    # Check the upper-right diagonal
    i, j = row, col
    while i >= 0 and j < n:
        if board[i][j]:
            return False
        i -= 1
        j += 1

    return True

def solve_n_queens_util(board, row, n, solutions):
    if row == n:
        solutions.append([row[:] for row in board])  # Copy the board configuration
        return

    for col in range(n):
        if is_safe(board, row, col, n):
            board[row][col] = 1  # Place the queen
            solve_n_queens_util(board, row + 1, n, solutions)
            board[row][col] = 0  # Backtrack

def solve_n_queens(n):
    board = [[0] * n for _ in range(n)]
    solutions = []
    solve_n_queens_util(board, 0, n, solutions)
    return solutions

if __name__ == "__main__":
    n = 4  # You can change this to any value of N
    solutions = solve_n_queens(n)
    print(f"Number of solutions for {n} Queens: {len(solutions)}\n")
    for i, solution in enumerate(solutions, 1):
        print(f"Solution {i}:")
        print_board(solution)   

输出

 
Number of solutions for 4 Queens: 2
Solution 1:
. Q.
. . . Q
Q . . .
. . Q .

Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .

说明

上述代码通过回溯法提供了 N 皇后问题的解决方案。它将 N 个皇后放置在 N x N 的棋盘上，使得没有两个皇后会互相威胁；即，没有两个皇后共享同一行、列或对角线。`is_safe` 函数用于检查某个位置是否可以安全放置皇后。递归函数 `solve_n_queens_util` 尝试逐行放置皇后，并在遇到冲突时回溯。每个有效的排列都存储在 `solutions` 中。最后，`solve_n_queens` 分配棋盘，并评估所有可能的解决方案并以易于理解的格式打印出来。

用于集合打包的穷举搜索算法

集合打包问题是一个组合优化问题，其中给出一组集合，目标是找到这些集合中最大的可能子集，使得该子集中的任何两个集合都不重叠。集合打包问题是一个 NP-hard 问题，这意味着没有已知的多项式时间算法可以解决这个问题。分支限界、整数规划和回溯等算法可以解决小规模示例。对于大规模问题，通常使用启发式和近似算法，如贪心算法、局部搜索或遗传算法。集合打包问题有各种现实世界的应用，例如调度（其中任务必须初始化到没有冲突的时间段）、资源分配（其中有限的资源被分配以满足竞争性需求，以防止冲突）以及网络设计（选择一组不冲突的网络路径或信道）。

考虑一个示例，其中元素集合 U = {1, 2, 3, 4, 5}，子集 S1 = {1, 2}, S2 = {2, 3}, S3 = {4} 和 S4 = {5}。目标是识别最大的不重叠子集集合。可能的解决方案是选择子集 S3 = {4} 和 S4 = {5}，因为它们不与任何其他子集重叠。在这种情况下，解决方案是 {S3, S4}，总共选择了两个子集。

考虑另一个例子，物品集合为 {1, 2, 3, 4, 5, 6}，子集列表为 S1 = {1, 2, 3}, S2 = {4, 5}, S3 = {5, 6} 和 S4 = {1, 4}，最多可以打包 3 个集合。

解决此问题的方法是遍历每个集合，并检查当前项是否存在于当前集合中。如果项存在，则会增加可打包集合的数量，并更新可打包集合的最大数量。

代码

# Python code for calculating the maximum packed groups
def maxGroupPacks(elements, groups):
    
    # Initialize the maximum number of groups that can be packed to 0
    maxPackedGroups = 0

    # Loop through all the groups
    for group in groups:
        # Initialize the number of groups that can be packed to 0
        packCount = 0

        # Loop through all the elements
        for element in elements:
            # Check if the current element is in the current group
            if element in group:
                # If the element is in the group, increment 
                # the number of groups that can be packed
                packCount += 1

                # Remove the element from the list, 
                # so it is not counted again
                elements = [e for e in elements if e != element]

        # Update the maximum number of groups that can be packed
        maxPackedGroups = max(maxPackedGroups, packCount)

    return maxPackedGroups

# List of elements
elements = [1,2,3,4,5]

# List of groups
groups = [
    [1, 2],
    [2,3],
    [4],
    [5]
]

# Find the maximum number of groups that can be packed
maxPackedGroups = maxGroupPacks(elements, groups)

# Print the result
print(f"Maximum number of groups that can be packed: {maxPackedGroups}")   

输出

 
Maximum number of groups that can be packed: 2

说明

在上述代码中，定义了 `maxGroupPacks` 来根据项目列表评估可以打包的最大组数。它从初始化 `maxPackedGroups` 为零开始。对于每个组，初始化 `packCount` 来跟踪当前组中有多少项可以与 `elements` 中的项匹配。对于 `elements` 中的每个项，如果它在当前组中找到，则 `packCount` 增加，并且该项从 `elements` 中删除以防止在其他组中重复使用。处理完每个组后，代码 `maxPackedGroups` 会更新为存储已打包计数的最大值。最后，该函数输出最大值并显示结果。此方法有助于确定在初始列表中的唯一项中可以构成多少个给定的组。

结论

穷举搜索算法（或暴力搜索）是一种算法技术，它通过系统地检查解决方案空间中的每个选项来检查解决方案空间中的所有可能性，以找到问题的答案。它同时满足完整性和最优性，这意味着如果存在答案，它将找到答案，并且通常是最佳答案。但是，它需要大量的计算，因此通常速度很慢。此外，对于非常大的问题，它会考察所有可能的路径或组合。在许多组合和优化应用中，例如旅行推销员问题或背包问题，需要准确性。

下一个主题软计算中的遗传算法

← 上一个下一个 🡒

人工智能中的穷举搜索

Travelling Salesman Problem

背包问题

分配问题

N皇后问题

用于集合打包的穷举搜索算法

结论

联系信息

关注我们

教程

面试题

在线编译器

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

人工智能选择题

其他

相关教程

人工智能中的穷举搜索

Travelling Salesman Problem

背包问题

分配问题

N皇后问题

用于集合打包的穷举搜索算法

结论

相关帖子

AI 在网络安全中的应用

人工智能的范围

最佳人工智能游戏

什么是 OpenAI

人工智能在文学中的作用

绿色科技革命

什么是人工智能中的自然语言处理

数据漂移检测的重要性

深度学习在人工智能中的应用

关于人工智能的口试问题

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器