当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
即一种分目标完成程序算法，简单问题可用二分法完成。
Java有ForkJoin模式，MongoDB有MapReduce模式，这些都是分而治之的思想。
分治法解题的一般步骤：
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。
这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。
多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。
动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。
因此在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。
给定一本英语单词词典，请找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。
例如，“pots”,”stop”和“tops”互为变位词，因为每个单词都可以通过改变其他单词中字母的顺序来得到。
编程珠玑的变位词程序要按照三个步骤来执行，其中前一个步骤程序的输出作为下一个步骤程序的输入：
单词的字典的处理过程：
由以上可看出需要三个程序的处理。
假设输入单词的长度不超过100，对每个输入的单词依照字母进行排序，将结果输入这个单词所对应的“签名”。
程序排序后的输出的“签名”，对其输出的结果排序，如上图。
将同一个变位词类中的各个单词放到同一行中。
转帖：A*寻路算法介绍
你是否在做一款游戏的时候想创造一些怪兽或者游戏主角，让它们移动到特定的位置，避开墙壁和障碍物呢？
如果是的话，请看这篇教程，我们会展示如何使用A寻路算法来实现它！
在网上已经有很多篇关于A寻路算法的文章，但是大部分都是提供给已经解基本原理的高级开发者的。
本篇教程将从最基本的原理讲起。我们会一步步讲解A寻路算法，幷配有很多图解和例子。
不管你使用的是什么编程语言或者操作平台，你会发现本篇教程很有帮助，因为它在非编程语言的层面上解释算法的原理。稍后，会有一篇教程，展示如何在Cocos2D iPhone 游戏中实现A算法。
现在找下到达一杯咖啡因饮料和美味的零食的最短路径，开始吧！
让我们想象一下，有一款游戏，游戏中一只猫想要找到获取骨头的路线。
“为什么会有一只猫想要骨头？！”你可能会这么想。在本游戏中， 这是一只狡猾的猫，他想捡起骨头给狗，以防止被咬死！
现在想像一下下图中的猫想找到到达骨头的最短路径。
不幸的是，猫不能直接从它当前的位置走到骨头的位置，因为有面墙挡住去路，而且它在游戏中不是一只幽灵猫！
游戏中的猫同样懒惰，它总是想找到最短路径，这样当他回家看望它的女朋友时不会太累。
但是我们如何编写一个算法计算出猫要选择的那条路径呢？A*算法拯救我们！
寻路的第一步是简化成容易控制的搜索区域。
怎么处理要根据游戏来决定。例如，我们可以将搜索区域划分成像素点，但是这样的划分粒度对于我们这款基于方块的游戏来说太高（没必要）。
作为代替，我们使用方块（一个正方形）作为寻路算法的单元。其他的形状类型也是可能的（比如三角形或者六边形），但是正方形是最简单并且最适合我们需求的。
像那样去划分，我们的搜索区域可以简单的用一个地图大小的二维数组去表示。所以如果是25*25方块大小的地图，我们的搜索区域将会是一个有625个正方形的数组。如果我们把地图划分成像素点，搜索区域就是一个有640，000个正方形的数组（一个方块是32*32像素）！
现在让我们基于目前的区域，把区域划分成多个方块来代表搜索空间（在这个简单的例子中，7*6个方块 = 42 个方块）。
1 | 针对目前火爆的2048游戏，有人实现了一个AI程序，可以以较大概率（高于90%）赢得游戏，并且作者在stackoverflow上简要介绍了AI的算法框架和实现思路。但是这个回答主要集中在启发函数的选取上 |
针对目前火爆的2048游戏，有人实现了一个AI程序，可以以较大概率（高于90%）赢得游戏，并且作者在stackoverflow上简要介绍了AI的算法框架和实现思路。但是这个回答主要集中在启发函数的选取上，对AI用到的核心算法并没有仔细说明。这篇文章将主要分为两个部分，第一部分介绍其中用到的基础算法，即Minimax和Alpha-beta剪枝；第二部分分析作者具体的实现。
有一批共n个集装箱要装上2艘载重量分别为c1，c2的轮船，其中集装箱i的重量为wi，且要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。可证明，采用如下策略可以得到一个最优装载方案：先尽可能的将第一艘船装满，其次将剩余的集装箱装到第二艘船上。
在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。
活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。
节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r<bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。
为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。
找到最优值后，可以根据parent回溯到根节点，找到最优解。
Update your browser to view this website correctly. Update my browser now
