贪心算法，让自己的人生“最优”？(组图)

DFS使用了回溯算法的思想，但实际上回溯也可以用于正则表达式匹配、编译原理中的语法分析等。

还提供数学问题，例如数独、八皇后、0-1 背包、图形着色、旅行商问题、所有排列等。

了解“回溯算法”

如果人生可以重复，如何在岔路口做出最正确的选择，让自己的人生“最优化”？

贪心算法每次面临岔路口都会做出看似最优的选择，希望这组选择能让我们的生活“最优”。但不一定是最好的解决方案。

如何保证最优解？

回溯算法通常用于“搜索”问题：在一组可能的解决方案中，搜索所需的解决方案。处理思路类似于枚举搜索：枚举所有解，找到满足期望的解。

为了有规律地列举所有可能的解决方案，避免遗漏和重复，将问题解决过程分为多个阶段。每一个阶段，你都要面对一个岔路口，随意选择一条路，当你发现这条路过不去（不符合预期的解），你会回到之前的岔路口，并选择另一种方式继续。去。

八皇后

8×8 棋盘，放 8 个棋子（皇后），每一个棋子在行、列或对角线上不能有另一个棋子。

将问题分成8个阶段，将8块放在第一排、第二排、第三排……第八排。在放置过程中贪心算法 背包问题 c，不断检查当前方法是否符合要求

适合递归实现：

0-1 背包

经典的解决方案是动态规划，但也有简单但不那么有效的回溯解决方案。

这个背包问题，物品是不可分割的，要么装不装，所以所谓的0-1背包贪心算法 背包问题 c，是贪婪解决不了的。

这样可以回溯，按顺序排列item，将整个问题分解为n个阶段，每个阶段对应如何选择一个item；

搜索剪枝提示：当发现选中项的重量大于Wkg时，停止检测剩余项。

正则表达式

假设正则表达式只包含 *, ? 通配符，现在指定：

如何使用回溯算法来确定给定文本是否与给定正则表达式匹配？依次检查正则表达式中的每个字符，当为非通配符时，直接与文本的字符匹配：

遇到特殊字符时，有多种处理方法。例如，* 有多种匹配方案，可以匹配任意文本字符串中的字符。先随意选择一个匹配方案，然后继续检查剩下的字符：

总结

回溯算法的思想很简单，大部分用于解决广义搜索问题：从一组可能的解中，选择一个满足要求的解。

回溯非常适合递归实现，剪枝是一种提高回溯效率的技术，无需穷举搜索所有情况。

回溯算法可以解决很多问题，比如我们开篇提到的深度优先搜索、八皇后、0-1背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配， 等等。