2015-09-01

算法

9 分钟读完 (大约 1413 个字)

迷宫(回溯算法)

概述
解题思路
程序代码
- 代码1
- 代码2

概述

以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。

解题思路

可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。

2015-08-27

算法

6 分钟读完 (大约 959 个字)

最佳调度问题(回溯算法)

概述
解题思路
程序代码

概述

掌握调度问题的处理方法，实现最佳调度问题的回溯解决。

解题思路

一个深度为N的M叉树。
基本思路：

搜索从开始结点（根结点）出发，以DFS搜索整个解空间。
每搜索完一条路径则记录下besttime和bestx[]序列
开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，并成为一个新的活结点，也成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。

2015-08-22

算法

33 分钟读完 (大约 5018 个字)

八皇后(回溯算法)

概述
解题思路
- 解题思路
程序代码
- 代码1
- 代码2
- 代码3
- 代码4
- 代码5
- 代码6

概述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上（反斜线），问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n × n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

2015-08-19

算法

8 分钟读完 (大约 1129 个字)

回溯算法

引言
概念
基本思想
步骤

引言

寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。
不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。
对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。

概念

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法（一种选优搜索法，按选优条件向前搜索，以达到目标）。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为：回溯法，而满足回溯条件的某个状态的点称为：“回溯点”。
回溯法实际是穷举算法，按问题某种变化趋势穷举下去，如某状态的变化用完还没有得到最优解，则返回上一种状态继续穷举。
许多复杂的，规模较大的问题都可以使用回溯法，回溯算法有“通用解题方法”的美称，其采用了一种“走不通就掉头”思想作为其控制结构，用它可以求出问题的所有解和任意解。
它的应用很广泛，很多算法都用到回溯法，例如，迷宫，八皇后问题，图的m着色总是等都用到回溯法，当然其中还使用了其他策略。

迷宫(回溯算法)

概述

解题思路

最佳调度问题(回溯算法)

概述

解题思路

八皇后(回溯算法)

概述

回溯算法

引言

概念

链接

分类

标签云

最新文章

归档

标签

最新文章

归档

标签

Your browser is out-of-date!