绪论体育录像/图片

在初始拔擢算法之前，先跟公共聊一下我（往日）的两大羡慕：棋战和打乒乓球。

棋战的时候，咱们不仅要洽商现时这一步何如走，还要洽商接下来的几步致使数十步棋的情况。举一个外洋象棋中的例子，比如当今轮到你走棋，而接下来的这一步你不错吃掉对方的后（子力价值最高的棋子），这看起来是现时事势下最优的走法，然则几步之后你可能会因为被对方将死而输掉比赛，这应该不是你想要的成果。事实上，这么的弃子战术在外洋象棋早期讲理观念对局中陆续出现。被后东谈主称为“不灭的对局”中，其时全国最顶尖的棋手阿谈夫·安德森就弃掉了通盘的重子（两个车和一个皇后），终末用一个象和两个马将死了对方。这局棋止境的精彩，对于像我这么的入门者也有着教科书般的意旨，对局如下图所示。

诠释

：外洋象棋中的棋子包括兵（Pawn）、车（Rook）、马（Knight）、象（Bishop）、后（Queen）、王（King）六种，这种称号其实是参照了中国象棋中棋子的名字。事实上，Knight应该译为骑士愈加精确，而Bishop凡俗被称为主教。从子力价值来看，兵、车、马、象、后别离为1分、4-5分、3分、3分、8-10分，诚然这仅仅一个参考值，当马处于棋盘中心位置或象处于怒放的对角线上时，子力价值会发生一定的变化，而兵还不错通过升变酿成除国王除外的其他棋子。

伸开剩余78%

打乒乓球跟棋战就不太相同了。当咱们在击球的时候，只需要作念出现时情况下最正确的动作就不错了，确切不必去想下一趟合致使下下一个回合的情状。即便你发球的时候就盘算好了一个“调短拉长”的战术，然则敌手的回球的姿色和落点齐偶而跟你的预期一致，是以你能作念的即是处理好现时这个回合。这件事情告诉咱们：在某些情况下，只须保证每一步齐是正确的，就大略得到最优的成果；或者说，咱们可能无法追求最优的成果（举例打乒乓球的时候一个回合就打败敌手），只需要一个令东谈主荒疏的成果，决策法就符合处分这两种类型的问题。

基本战略和运用场景

决策法是分阶段试验的，每一阶段齐凭据现时情况作出判断，不必洽商之后的情况。凡俗咱们每一步找出的解是局部最优解，而凡俗情况下咱们合计全局最优解不错由局部最优解推导出来或者只需要一个荒疏解并不需要最优解。

具有底下两个要求的问题就不错使用决策法进行求解，并且知足这两个要求是不错求出最优解的：

具备贪心选拔性质 - 全局最优解不错由局部最优解推导出来，这个要求凡俗不那么容易知足。

具备最优子结构 - 通盘问题的最优解由子问题的最优解组成。

咱们耳闻则诵的许多算法其实齐是对决策法的运用，举例：

霍夫曼编码压缩算法

图的最小生成树算法（Prim算法和Kruskal算法）

带权图的最短旅途算法（Dijkstra算法）

背包问题

找零问题

决策法的热身题

咱们先给公共来一个热身的题目。其实，口试的时候并莫得那么多不错使用决策法来求解的算法题，然则这种算法却是公共应该了解和掌持的，因为它在许多场景下可能是一种相当好的处分问题的念念路。

题目：小偷有一个背包，最多能装20公斤赃物，他闯入一户东谈主家，发现如下表所示的物品，问他应该拿哪些东西技术使偷到的物品总价值最大。

对于上头这个题目，最为粗拙的念念路即是计较每件物品的价钱分量比，小偷取物品的时候，老是先取剩下的物品中价钱分量比最大的物品先拿，这即是局部最优。诚然，有的时候局部最优偶而大略推导出全局最优。这个题方向参考代码不错在我的Python-100-Days上《Python言语进阶》一文中找到，有风趣的不错自行查阅。

霍夫曼编码问题

霍夫曼编码是一种用于无损数据压缩的熵编码（权编码）算法。霍夫曼编码使用变长编码表对源绚丽（如文献中的一个字母）进行编码，粗拙的说即是出现几率高的字母使用较短的编码，出现几率低的字母使用较长的编码，并且要逃避两个字符编码互为前缀的情况（幸免产生二义性），这就使得编码之后的内容对应的二进制比特减少，从而达到无损压缩数据的方向。

咱们以this is an example of a huffman tree为例，该字符串的长度为36，若是使用utf-8编码，那么需要保存或传输288比特。接下来咱们望望怎样使用霍夫曼编码来压缩数据。咱们不错先统计出每个字母出现的频率，如下表所示。

接下来，咱们为每个字符创建一个节点，最初始的时候，每个节点齐不错视为一棵独一根节点的二叉树，对于上头的例子，一共有16棵树。霍夫曼编码在每一轮中齐要从这些二叉树中找出根节点的值最小的那两棵树，然后创建一个新节点。新节点对应的值是刚才那两棵树的根节点值之和，同期刚才的两棵树别离手脚新节点的左子树和右子树。反复试验这个流程，珍重每次齐是选根节点的值最小的两棵树进行团结创建出新节点，直到终末只剩下一棵树铁心，如下图所示。

把树创建好之后，每个叶子节点就对应某个字符的霍夫曼编码。若是想取得某个字符串的编码，不错从根节点动身，向叶子节点前进，遭遇左子树就记为0，遭遇右子树就记为1，最终的编码如下表所示。

咱们不错粗拙的计较一下，霍夫曼编码的长度为135比特，比之前的288比特减少了一半还多。诚然，本色运用中存储编码的树结构还需要破耗相当的存储空间，然则凡俗情况下相较于要压缩的内容来说，这部分空间确切不错忽略不计。总结一下刚才的算法，每一步咱们齐是优先选拔根节点值最小的两个节点进行团结（决策的作念法），那么很领会，越早团结的节点终末会出当今二叉树越靠底下的位置，这么对应的字符编码就越长；而出现频率高的字符对应的节点在较晚的时候才会进行团结，那么它在二叉树的位置比拟靠上，这么对应的字符编码就很短。

诠释：上头的例子来自于维基百科上对于霍夫曼编码的先容。

粗拙的总结

这里咱们就不再用代码来展示决策算法了，我确信像霍夫曼编码这种代码在网上应该不错找到许多。结束霍夫曼编码的重心即是要有一个优先队伍，确保每次齐不错取出节点值最小的两个节点进行团结（决策就体当今这个地点，因为每次取的齐是剩下节点中值最小的），团结之后的节点再行放入队伍中时体育录像/图片，也大略处在一个稳健的位置。需要珍重的是，霍夫曼编码压缩不错检朴空间（如网罗传输带宽），然则编码息争码齐需要破耗相当的时分，这又是典型的空间跟时分的置换。

发布于：湖南省