2020-01-15

分而治之算法(divide and conquer)

Views: 4752 | Add Comments

分而治之算法(divide and conquer)是计算机算法领域最常用最有效的算法之一, 体现到编程上就是树(数据结构), 递归函数. 一般的代码模板是这样的:

func recursive(N){
	if(!N){return;}
	a, b = split(N); // divide 
	proc(a);         // conquer a
	recursive(b);      // process b
}

对于寻路, 分段处理最终达成目标这种模式的问题, 一般的代码模板是:

func recursive(N){
	if(!N){return;}
	a, b = split(N); // divide 
	r = proc(a);     // conquer a
	if(r){recursive(r + b);}  // conquer remain + b
	recursive(b);      // process b
}

多了一步:

if(r){recursive(r + b);}

因为前一段的剩余, 要和后一段组成新的问题, 然后被处理.

Related posts:

  1. 消除JavaScript闭包的一般方法
  2. 小心递归次数限制
  3. 接口与实现分离
  4. 开发搜索引擎 – PHP中文分词
  5. 动态规划算法的发现
Posted by ideawu at 2020-01-15 16:36:14 Tags:

Leave a Comment