1-5算法设计常用思想之穷举法(代码片段)

关键词：

穷举法又称穷举搜索法，是一种在问题域的解空间中对所有可能的解穷举搜索，并根据条件选择最优解的方法的总称。数学上也把穷举法称为枚举法，就是在一个由有限个元素构成的集合中，把所有元素一一枚举研究的方法。

使用穷举法解决问题，基本上就是以下两个步骤：
　　• 确定问题的解（或状态）的定义、解空间的范围以及正确解的判定条件；
　　• 根据解空间的特点来选择搜索策略，逐个检验解空间中的候选解是否正确；

解空间的定义
解空间就是全部可能的候选解的一个约束范围，确定问题的解就在这个约束范围内，将搜索策略应用到这个约束范围就可以找到问题的解。要确定解空间，首先要定义问题的解并建立解的数据模型。如果解的数据模型选择错误或不合适，则会导致解空间结构繁杂、范围难以界定，甚至无法设计穷举算法。
穷举解空间的策略
穷举解空间的策略就是搜索算法的设计策略，根据问题的类型，解空间的结构可能是线性表、集合、树或者图，对于不同类型的解空间，需要设计与之相适应的穷举搜索算法。简单的问题可以用通用的搜索算法，比如线性搜索算法用于对线性解空间的搜索，广度优先和深度优先的递归搜索算法适用于树型解空间或更复杂的图型解空间。

盲目搜索和启发式搜索
对于线性问题的盲目搜索，就是把线性表中的所有算法按照一定的顺序遍历一遍，对于复杂问题的盲目搜索，常用广度优先搜索和深度优先搜索这两种盲目搜索算法。
如果搜索能够智能化一点，利用搜索过程中出现的额外信息直接跳过一些状态，避免盲目的、机械式的搜索，就可以加快搜索算法的收敛，这就是启发性搜索。启发性搜索需要一些额外信息和操作来“启发”搜索算法，根据这些信息的不同，启发的方式也不同。

剪枝策略
对解空间穷举搜索时，如果有一些状态节点可以根据问题提供的信息明确地被判定为不可能演化出最优解，也就是说，从此节点开始遍历得到的子树，可能存在正确的解，但是肯定不是最优解，就可以跳过此状态节点的遍历，这将极大地提高算法的执行效率，这就是剪枝策略，应用剪枝策略的难点在于如何找到一个评价方法（估值函数）对状态节点进行评估。特定的评价方法都附着在特定的搜索算法中，比如博弈树算法中常用的极大极小值算法和“α-β”算法，都伴随着相应的剪枝算法。

剪枝和启发
剪枝不是启发性搜索。剪枝的原理是在结果已经搜索出来或部分搜索出来（比如树的根节点已经搜索出来了，但是叶子节点还没有搜索出来）的情况下，根据最优解的判断条件，确定这个方向上不可能存在最优解，从而放弃对这个方向的继续搜索。而启发性搜索通常是根据启发函数给出的评估值，在结果出来之前就朝着最可能出现最优解的方向搜索。它们的差异点在于是根据结果进行判断还是根据启发函数的评估值进行判断。

搜索算法的评估和收敛
收敛原则是只要能找到一个比较好的解就返回（不求最好），根据解的评估判断是否需要继续下一次搜索。大型棋类游戏通常面临这种问题，比如国际象棋和围棋的求解算法，想要搜索整个解空间得到最优解目前是不可能的，所以此类搜索算法通常都通过一个搜索深度参数来控制搜索算法的收敛，当搜索到指定的深度时（相当于走了若干步棋）就返回当前已经找到的最好的结果，这种退而求其次的策略也是不得已而为之

百钱买鸡问题
一百个钱买一百只鸡，是个典型的穷举法应用。问题描述：每只大公鸡值 5 个钱，每只母鸡值 3 个钱，每 3 只小鸡值 1 个钱，现在有 100 个钱，想买 100 只鸡，问如何买？有多少种方法？

void Buy()

    int count = 0;

    for (int roosters = 0; roosters <= 20; roosters++)   //枚举大公鸡数量
    
        for (int hens = 0; hens <= 33; hens++) //枚举母鸡数量
        
            int chicks = 100 - roosters - hens;  //剩下的就是小鸡数量
            if (((chicks % 3) == 0) //小鸡个数应该是 3 的整数倍，算是个小小的剪枝
                && ((5 * roosters + 3 * hens + chicks / 3) == 100)) //是否凑够 100 钱
            
                count++;
                std::cout << "买法 " << count << "：公鸡 " << roosters
                                              << ", 母鸡 " << hens
                                              << ", 小鸡 " << chicks << std::endl;
            
        
    

    std::cout << "共有 " << count << " 种买法" << std::endl;

-- lua实现
function bug()
    local count = 0
    for roosters = 0, 20 do
        for hens = 0, 33 do
            local chicks = 100 - roosters - hens
             if (((chicks % 3) == 0) and ((5 * roosters + 3 * hens + chicks / 3) == 100)) then
                 count = count + 1
                 print("====买法", count, roosters, hens, chicks)
             end
        end
    end
    print("====共有买法", count)
end

鸡兔同笼问题

有鸡和兔在一个笼子中，数头共 50 个头，数脚共 120 只脚，问：鸡和兔分别有多少只？

for ji = 1, 50 do
    local tu = 50 - ji
    if (tu * 4 + ji * 2) == 120 then
        print("===========鸡 兔各", ji, tu)
        break
    end
end

1-6算法设计常用思想之迭代法(代码片段)

...是一种不断用变量的旧值递推新值的过程，其对应的迭代算法也是用计算机解决问题的一种基本方法。 迭代法和递推法的关系迭代法作为很多数学问题的求解算法，是解决数学问题的一种常用的算法模式，可以独立构成解决... 查看详情

六中常用算法设计：穷举法分治法动态规划贪心法回溯法和分支限界法(代码片段)

算法设计之六种常用算法设计方法1.直接遍历态（穷举法）      程序运行状态是可以遍历的，遍历算法执行每一个状态，最终会找到一个最优的可行解；适用于解决极小规模或者复杂度线性增长，而线... 查看详情

常用算法-穷举法

穷举法又称为枚举法，它是在计算机算法设计中用得最多的一种编程思想。它的实现方式是：在已知答案范围的情况下，依次地枚举该范围内所有的取值，并对每个取值进行考查，确定是否满足条件。经过循环遍历之后，筛选出... 查看详情

五大经典算法之回溯法(代码片段)

...，就会退回一步重新选择，这种达不到目的就退回再走的算法称为回溯法。与穷举法的区别和联系：相同点：它们都是基于试探的。区别：穷举法要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃... 查看详情

算法思维之穷举法

穷举法概念：穷举法是利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，因此枚举法是通过牺牲时间来换取答案的全面性。 分析：穷举法主要强调每... 查看详情

常用排序算法总结(代码片段)

排序算法目录排序算法1.排序算法概述1.1什么是排序算法？1.2、排序术语1.3算法总结1.4算法分类1.5比较排序与非比较排序1.5.1比较排序1.5.2非比较排序2.排序算法具体实现2.1冒泡排序2.1.1算法思想2.1.2算法描述2.1.3算法实现（1）数组... 查看详情

重温基础算法内部排序之归并排序法(代码片段)

...程演示递归过程非递归过程JAVA代码非递归实现递归实现算法分析时间复杂度空间复杂度归并排序（Mergingsort）是建立在归并操作上的一种有效的排序算法。是采用分治法的一个非常典型的应用。主要思想2-路归并排序法初... 查看详情

算法设计之分治法策略(代码片段)

...法 ：divideandconquer又称分而治之，是一种非常有用的算法设计策略，它是将一个难以解决的大问题规模划分为一些规模较小的子问题，分别求解每个子问题的解，然后合并子问题的解。理所当然，设计分治法需要分三个步骤... 查看详情

javascript之算法设计思想(代码片段)

数据结构和算法1️⃣排序算法一、冒泡排序二、选择排序三、插入排序四、归并排序五、快速排序2️⃣查找方法一、顺序查找二、二分查找3️⃣算法设计思想一、动态规划二、分而治之三、贪心算法四、回溯算法1️⃣排序算... 查看详情

重温基础算法内部排序之快速排序法(代码片段)

...章目录内部排序之快速排序法主要思想过程演示JAVA代码算法分析时间复杂度分析最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度对冒泡排序的一种优化主要思想快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。... 查看详情

重温基础算法内部排序之快速排序法(代码片段)

...章目录内部排序之快速排序法主要思想过程演示JAVA代码算法分析时间复杂度分析最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度对冒泡排序的一种优化主要思想快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。... 查看详情

重温基础算法内部排序之插入排序法(代码片段)

...章目录内部排序之插入排序法主要思想过程演示JAVA代码算法分析主要思想插入排序(InsertionSort)，一般也被称为直接插入排序。将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（序列的第一个数据ÿ... 查看详情

重温基础算法内部排序之基数排序法(代码片段)

...章目录内部排序之基数排序法主要思想过程演示java实现算法分析基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。一般情况下，假如有nnn个记录的序列R1,R2,...,Rn\\R_1,R_2,...,R_n\\R1​,R2​,...,Rn​且每个... 查看详情

五大经典算法之回溯法及其应用(代码片段)

前言  回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回... 查看详情

算法与程序设计：分支限界法(代码片段)

目录一、概念1.1分支限界法的基本思想1.2分支限界法与回溯法的不同1.3 分支限界法的搜索方式1.4 常见的两种分支限界法二、举例2.1单源最短路径问题三、代码实现3.1源程序3.2运行结果一、概念1.1分支限界法的基本思想1.2分支... 查看详情

串的模式匹配算法之kmp(代码片段)

title:串的模式匹配算法之kmptags:数据结构与算法之美author:辰砂1.引言首先我们需要了解串的模式算法目的：确定主串中所含子串第一次出现的位置（定位）；常见的算法种类：BF算法（又称古典的、经典的、朴素的、穷举的），KM... 查看详情

算法设计与优化之等价转换(代码片段)

等价转换与其说是一种算法的设计方法，更不说是一种算法思想。这种思想能有助于我们把复杂的问题简单化，帮我们理清问题的思路，甚至能直接得出求解问题的方法。下面通过一道具体的题目来像读者介绍这种思想。Gergovia... 查看详情

常用排序算法(代码片段)

简述一些常用算法，并用代码实现它。注：动图是在网上找的。（1）冒泡排序核心思想：交换序列中相邻两个整数。 测试代码：1voidbubble_sort(void)23/*4*冒泡排序：以降序为例进行说明5*比较相邻的元素，将值最小的元素交换... 查看详情