学习随记 - 深度优先搜索

标签：状态 优先 option tmpState state depth 搜索 stack 随记

深度优先搜索

Depth-First Search（DFS）或 Backtracking（回溯法）

算法特点：

1. “一条道走到黑”；

2. “碰壁后，会回溯到上一步，尝试选择其他选项继续搜索”；

算法优势：

只需要存储搜索树上“从起点到当前状态”这个链条上的信息，被回溯的状态无需保存，所以比较节省空间。

实现方法：

1. 递归；2. 非递归；

 

DFS的递归模版

 1 初始化状态哈希表 hashState;
 2 初始化状态扩展哈希表 hashOption;
 3 生成起始状态 initState;
 4 
 5 var dfs = function(state) {
 6     // 终止
 7     if (state 达到边界) {
 8         返回;
 9     }
10     // 达到预期值
11     if (state 符合预期条件) {
12         更新结果值;
13     } 
14     // 迭代所有可选项
15     for (当前可选项 in 所有可选项) {
16         tmpState = state按当前项进行扩展;
17         if (tmpState 状态非法) {
18             continue;
19         }
20         对tmpState判重并更新hashState;
21         如果当前项会影响后续选项，则更新hashOption;
22         // 核心，递归调用
23         dfs(tmpState);
24         将hashOption回复原状;
25     }
26 };
27 
28 dfs(initState);

 

递归实现 存在的问题：

栈溢出，使用栈空间存储每1层函数的临时变量，而栈空间本身非常小（1～8MB，不同的语言/操作系统有所不同）

解决方案：

1. 采用非递归方式实现（使用显式栈模拟系统栈）；

2. 采用其他搜索算法；

 

判重的策略

任意解+不包含扩展过程：（重复）丢弃

任意解+包含扩展过程：（重复）丢弃

最优解+不包含扩展过程：（重复）丢弃

//// =========================

最优解+包含扩展过程：判断当前状态和之前的记录哪个更优，如果当前状态更优，则更新记录，并继续搜索；否则，丢弃

解的总数+不包含扩展过程：认为是重复状态，对当前状态的计数进行累加，并继续搜索

解的总数+包含扩展过程：认为是不重复状态，继续搜索

 

判重的哈希表设计

1. 对于求任意解：用 True/False，记录是否出现过；

2. 对于求最优解：“最优”的判断标准；

3. 对于求解的总数：用 计数器（记录出现的次数）；

 

DFS的非递归模版

初始化状态哈希表 hashState;
初始化状态扩展哈希表 hashOption;
生成起始状态 initState;

var dfs = function() {
    初始化栈stack
    将{ 起始状态, option, restrict }插入stack，并将depth置为1；
    while (depth) {
        state = stack[depth].state；
        option = stack[depth].option;
        如果stack[depth].restrict不为空，则可尝试恢复hashOption；
        if (option === k) {
            stack.pop();
            depth--;
        }
        else {
            option++;
            stack[depth].option = option;
            tmpState = state按第option种扩展选项进行扩展；
            if (tmpState 状态非法) {
                continue;
            }
            对tmpState进行判重并更新hashState；
            如果当前选项会影响后续选项，则更新hashOption，并更新stack[depth].restrict以便恢复；
            depth++;
            stack[depth] = tmpState;
            stack[option] = 0;
        }
    }
};

 

标签：状态,优先,option,tmpState,state,depth,搜索,stack,随记
From： https://www.cnblogs.com/fanqshun/p/16597033.html