分治法与回溯法的思考

共同的递归性质在广义上来说,所有递归的算法都属于分治法。无非是将问题分解成一个规模更小的问题,还是将问题分解成若干个,甚至和输入规模多项式级别的子问题。那么对于前者,有些作者称作是减治法,后者称作分治法。那么对于回溯法(以深度优先搜搜方式进行)来说,目前为止我见过的都是通过递归的形式来实现的,那么从这个意义上来讲,回溯算法就是分治法的一种。回溯状态的有无再说,之所以称作是回溯法,是因为在搜索的过程中需要回溯到问题的某个状态,所以这往往需要保存回溯时的一些状态属性。然而,分治法通常并不需要考虑回溯状态的保存。分解问题的规模分治法往往是将问题分解成若干个子问题的形式,然而回溯法往往是将问题分解成规模更小的一个子问题。由于分治法将问题分解成若干个子问题,故当前问题的解需要依赖于若干个子问题,也就是若干个搜索路径的解,所以重点在于如何合并子问题的解;而然回溯法问题规模就为1个,当前的搜索路径的问题... Read More

Codeforces Round #345 (Div. 1) C. Table Compression

原题C. Table Compressiotime limit per tes4 secondmemory limit per tes256 megabyteinpustandard inpuoutpustandard outpuLittle Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.Petya decided to compress tables. He is give... Read More

深度优先搜索之栈解迷宫(C++)

在之前的一篇关于搜索的文章中《广度优先搜索算法队解迷宫问题》有提到深度优先搜索(dfs)算法,其中有一种就是本篇文章提到的实现方法:利用栈解迷宫;《广度优先搜索算法队解迷宫问题》中利用栈解迷宫有一个bug,比如:在x点出发,向右走直到尽头回到x点,此时在向其他方向(比如上),那么不能再走曾经向右走过的路(坐标)。这次,我们增加一个direct_mark数组,来标记在每一个坐标上曾经走过的方向。程序范例[code lang="cpp"/** 栈解迷宫 - 深度优先搜索.* @authur genialx <admin@ihuxu.com>*#include <iostr#include <st#define LEFT #define RIGHT #define UP #define DOWN using namespace std;struct Path int x;... Read More