首页 > 编程语言 >数据结构与算法之回溯法

数据结构与算法之回溯法

时间:2022-11-27 17:22:37浏览次数:38  
标签:return val findSolutions 算法 other params 回溯 数据结构

回溯法通用的解题思路

void findSolutions(n, other params) :
    if (found a solution) :
        solutionsFound = solutionsFound + 1;
        displaySolution();
        if (solutionsFound >= solutionTarget) : 
            System.exit(0);
        return

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            findSolutions(n+1, other params);
            removeValue(val, n);

 

如果只是查找是否存在解决方案

boolean findSolutions(n, other params) :
    if (found a solution) :
        displaySolution();
        return true;

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            if (findSolutions(n+1, other params))
                return true;
            removeValue(val, n);
        return false;

 

常见的回溯法算法题目

老鼠走迷宫

 

 给出一条通路,如下:

 

 输入的数据如下:

 

 输出的数据如下:

 

 一个加强版,允许移动多次

 

 

 

 第二行的第一个位置,允许移动3次,所以会移动到这一行最右侧

打印出所有可能的路径

 

标签:return,val,findSolutions,算法,other,params,回溯,数据结构
From: https://www.cnblogs.com/chenyingzuo/p/16930141.html

相关文章