枚举算法（Enumeration Algorithm）是一种简单而直接的问题解决方法，它通过“穷举所有可能的解”，来找到问题的答案。其基本思想是：系统地列举问题的所有可能解，然后逐一检查这些解，找到符合条件的解或者最优解。
可以看到，因为是从所有候选答案中去搜索正确的解，所以，使用该算法需要满足2个条件：
1、可预先确定候选答案的数量；
2、候选答案的范围在求解之前必须有一个确定的集合（确保不会遗漏任何可能的解）。
因此，枚举算法只适合问题的解空间相对较小时，比如说一些组合优化、排列组合、子集生成等问题，这个时候的计算成本是可以接受的。而一旦解空间较大、计算成本较高时，就需要再考虑更高效的算法思想了。
排列和组合生成： 给定一组元素，求这些元素的所有排列或组合。比如说，解决密码破解、电话号码的字母组合等问题。
图的全排列： 给定一个图，求图中所有节点的排列。图着色问题，求解图的哈密顿回路等。
穷举法解决优化：在某范围内搜索满足某条件的最优解，如搜索函数的最大值或最小值。
贪心算法（Greedy Algorithm）是一种基于贪心策略的问题解决方法。它在每一步都做出当前情况下的最优选择，希望通过一系列局部最优选择，达到全局最优解。贪心算法通常不会回退，即一旦做出了某个选择，就不会撤销或修改。
总结起来，贪心算法需要重点注意以下3点：
1、选择当下最优
贪心算法选择的都是当下情况的最优解，也就是选择局部最优，而不会考虑全局的情况。
2、不回退
一旦做出选择，贪心算法就不会回退。这是它和动态规划的主要区别，动态规划可能会回退，会重新考虑之前的决策。
3、局部最优达到全局最优
这个是贪心算法希望达成的局面，也就是说通过局部最优达到全局最优。
最小生成树算法： 如Prim算法和Kruskal算法。
最短路径算法： 如Dijkstra算法。
背包问题：背包问题的部分分数背包解法。
def greedy_change(coins, target_amount):
coins.sort(reverse=True) # 按面额从大到小排序
change = []
remaining_amount = target_amount
for coin in coins:
while remaining_amount >= coin:
# 尽可能多地使用当前面额的硬币
change.append(coin)
remaining_amount -= coin
return change
# 测试
coins_available = [25, 10, 5, 1]
target_amount = 63
result = greedy_change(coins_available, target_amount)
print(result) # 输出找零钱的硬币组合
在这个例子中，greedy_change函数使用贪心算法来找零钱。首先，按照硬币的面额从大到小进行排序。然后，从面额最大的硬币开始，尽可能多地使用当前面额的硬币，直到达到或接近目标金额。这样，就能够使用最少数量的硬币找零。
需要注意的是，贪心算法不一定对所有问题都能得到最优解。在找零钱问题中，贪心算法得到的解是近似最优解，但并不一定是最优解。有些问题需要更复杂的算法来确保找到全局最优解。在实际应用中，需要根据具体问题的性质来判断是否适用贪心算法。
递归算法是一种解决问题的方法，其特点是在解决问题的过程中，调用自身来处理子问题。递归算法通常将一个大问题划分为规模较小但类似于原问题的子问题，通过递归地解决这些子问题，来最终解决整个问题。
递归算法需要重点注意2点：
1、基本情况
递归算法必须包含至少一个基本情况，即一个问题规模足够小，可以直接求解而不再进行递归调用。基本情况避免了递归的无限循环。
2、递归关系
递归关系描述了如何将原问题分解为更小的相似问题，直到达到基本情况。
阶乘计算、斐波那契数列的计算、二叉树的遍历等。
def factorial(n):
# 基本情况
if n == 0:
return 1
# 递归关系
else:
return n * factorial(n-1)
在这个例子中，当n为0时，就是基本情况，返回1。否则，递归关系是 n 的阶乘等于 n 乘以 (n-1) 的阶乘。
虽然，递归算法提供了一种清晰、简洁的问题解决思路，但需要小心避免无限递归和递归深度过大可能导致的栈溢出问题。
回溯算法是一种通过尝试所有可能的候选解并在找到可行解或遍历所有候选解空间后退回的算法。它基于深度优先搜索的策略，逐步地尝试构建问题的解，如果发现当前的解不能满足问题的要求，就进行回溯，撤销上一步的选择，尝试其他的可能性。
回溯算法包含以下5个关键步骤：
1、选择：从问题的候选解集合中选择一个元素，尝试将其添加到当前部分解中。
2、路径记录：记录当前选择，形成当前的部分解。
3、验证：检查当前部分解是否满足问题的要求，如果满足则继续，否则进行回溯。
4、撤销选择：如果当前部分解无法满足问题要求，就撤销上一步的选择，尝试其他的可能性。
5、循环迭代：重复以上步骤，直到得到最终的解或者遍历完所有的可能性。
八皇后问题：在8x8的棋盘上放置8个皇后，使得它们互相不攻击。
0-1背包问题：在给定容量的背包中，选择一些物品放置到背包中，使得总价值最大。
图的着色问题：为图的节点着色，使得相邻节点具有不同颜色。
数独问题：填充数独格子，使得每一行、每一列和每个小九宫格中的数字都是1到9。
在八皇后问题中，目标是将8个皇后放置在8x8的棋盘上，使得它们互相不攻击（不在同一行、同一列或同一斜线上）。
以下，是一个简单的 Python 代码示例：
def solve_n_queens(n):
def is_not_under_attack(row, col):
for prev_row in range(row):
# 检查同一列是否有皇后
if board[prev_row] == col or
# 检查左上到右下对角线是否有皇后
board[prev_row] - prev_row == col - row or
# 检查左下到右上对角线是否有皇后
board[prev_row] + prev_row == col + row:
return False
return True
def place_queen(row):
if row == n:
# 当前布局是有效解，加入结果集
result.append(board[:])
return
for col in range(n):
if is_not_under_attack(row, col):
board[row] = col
# 递归处理下一行
place_queen(row + 1)
# 回溯，撤销当前选择
board[row] = -1
result = []
board = [-1] * n # 棋盘的每一行只能放一个皇后，用一维数组表示，值表示列索引
place_queen(0)
return result
# 测试
n_queens_solutions = solve_n_queens(8)
for solution in n_queens_solutions:
print(solution)
这个代码会输出八皇后问题的所有解，每个解都是一个包含八个元素的列表，表示每个皇后在每行的列索引位置。
回溯算法常常用于解决一些组合优化、排列组合、子集生成等问题。在实现回溯算法时，需要注意在递归调用之前和之后对状态的变化进行合适的操作，以确保正确的回溯。同时，为了提高效率，可以通过一些剪枝策略来减少搜索空间。
动态规划（Dynamic Programming，简称DP）是一种通过将原问题分解为更小的子问题，并将子问题的解存储起来，避免重复计算，从而有效解决问题的方法。动态规划主要用于优化问题，其核心思想是将：问题的解决过程转化为一个阶段性决策过程，并使用递推关系来描述问题的最优解。
动态规划需要重点注意以下4点：
1、定义子问题：将原问题分解为若干子问题，这些子问题通常是原问题的规模较小或结构相似的问题。
2、建立状态转移方程：描述子问题之间的递推关系，即如何通过子问题的解得到原问题的解。
3、确定边界条件：确定子问题的最小规模，通常是一些简单问题的解，称为边界条件。
4、自底向上求解：通过迭代计算，从子问题的边界条件开始，逐步求解原问题，将子问题的解存储起来，避免重复计算。
动态规划广泛应用于解决一些最优化问题，如最短路径、背包问题、字符串编辑距离等。
斐波那契数列、最长递增子序列、0-1背包......
def fibonacci_dp(n):
# 创建一个数组用于存储子问题的解
dp = [0] * (n + 1)
# 初始化边界条件
dp[0] = 0
dp[1] = 1
# 自底向上求解
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
# 返回最终问题的解
return dp[n]
# 测试
result = fibonacci_dp(10)
print(result) # 输出斐波那契数列的第10项
在这个例子中，fibonacci_dp函数使用动态规划来计算斐波那契数列的第n项。通过创建一个数组 dp，存储子问题的解，避免了递归中的重复计算。循环迭代的方式从底向上计算，最终得到原问题的解。
这是一个简单的动态规划问题，但体现了动态规划的核心思想：将问题拆分为子问题，通过保存子问题的解来避免重复计算，最终得到整个问题的最优解。
动态规划是一种强有力的问题解决方法，但也需要注意一些问题的状态转移方程的设计和边界条件的确定。虽然，动态规划可以在某些情况下提供高效的解决方案，但并非所有问题都适用于动态规划。
推荐站内搜索：最好用的开发软件、免费开源系统、渗透测试工具云盘下载、最新渗透测试资料、最新黑客工具下载……
还没有评论，来说两句吧...