• 2020-02-13

    龟兔赛跑问题和Floyd环检测算法

    Views: 3258 | No Comments

    例如要检测如下的环, 找出 a 点到 b 点的距离 mu, 以及环的周长 lam.

                    +----------------+
                    |                | 
    +---------------+----------------+
    a    mu         b                c
                    |       v        |
    

    用快慢指针同时遍历. 首先可知, 如果环存在, 快慢指针会在 c 点相遇. c 到 b 点的距离是 v. 那么可知, 相遇时, 快慢指针走过的距离是:

    慢: mu + m * lam + v
    快: mu + n * lam + v
    

    它们是两倍关系, 所以:

    2 * (mu + m * lam + v) = mu + n * lam + v
    2 * mu + 2 * v + 2 * m * lam = mu + n * lam + v
    v = n*lam - 2*m*lam - mu
    

    这时, 两个指针再以同样的速度前进. s 从 a 点出发, f 从 c 点出发. 可以知道, 当 s 走了 mu 距离后, 到达 b 点. 而 f 走了 mu 距离后, 也到达 b 点. 两者相遇.

    n*lam - 2*m*lam - mu + mu = n*lam - 2*m*lam
    
    Posted by ideawu at 2020-02-13 18:12:10
  • 2020-02-12

    动态规划算法的发现

    Views: 3163 | No Comments

    1. 问题可分而治之且 BFS

    首先, 问题必须是可分而治之的, 并在最后合并. 分而治之(递归)是为了穷举, 合并是为了找最优.

    Result r(costs[], target){
    	args = [];
    	for(cost in costs){
    		tmp = r(costs - cost, target - cost) + cost;
    		args += tmp;
    	}
    	return G(args);
    }
    

    虽然上面的代码是 DFS, 但形式上是 BFS, 而且也应该写成 BFS, 只不过 BFS 的代码不简洁而已.

    思考: 与贪婪算法的区别.

    2. 合并函数 G(...) 可迭代处理

    因为 G() 是可以转换成迭代的, 所以代码变成:

    Result r(costs[], target){
    	ret = PRE;
    	for(cost in costs){
    		tmp = r(costs - cost, target - cost) + cost;
    		ret = G(ret, tmp);
    	}
    	return ret;
    }
    

    PRE(开始之前)是引入的边界外的参数, 以便让代码处理逻辑简化, 不然要加 if 条件判断, 就无法在形式化上统一.

    3. 增加缓存

    Result r(costs[], target, dp){
    	cache_key = make_cache_key(costs, target);
    	if(dp[cache_key]){
    		return dp[cache_key];
    	}
    	ret = PRE;
    	for(cost : costs){
    		tmp = r(costs - cost, target - cost, dp) + cost;
    		ret = G(ret, tmp);
    	}
    	dp[cache_key] = ret;
    	return ret;
    }
    

    4. 将递归转成迭代

    #### 推导型

    Result forward(costs, target){
    	init(dp);
    	cc[PRE] = costs;
    	for(curr in range(PRE, target)){
    		costs = cc[curr];
    		for(cost : costs){
    			dp[next] = G(dp[next], dp[curr] + cost);
    			cc[next] = costs - cost if dp[next] updated;
    		}
    	}
    	return dp[target];
    }
    

    #### 回溯型

    Result backtrack(costs[], target){
    	dp[PRE] = PRE;
    	cc[PRE] = costs;
    	for(curr in range(atomic, target)){
    		for(prev in get_prev_list(curr)){
    			costs = cc[prev];
    			cost = costs.link(prev, curr); 
    			dp[curr] = G(dp[curr], dp[prev] + cost);
    			cc[curr] = costs - cost if dp[curr] updated;
    		}
    	}
    	return dp[target];
    }
    

    5. 缓存可淘汰: 滑动窗口

    这一条件不是必须的, 因为很多动态规划解法无法淘汰缓存. 如果缓存可淘汰, 而且是可以用滑动窗口的方式淘汰, 那么就是非常**经典且巧妙的**动态规划解法.

    对于推导型动态规划, 只需要缓存最长的推导距离. 对于回溯型动态规划, 只需要缓存最长的回溯距离.

    这里举的例子是单节点推导, 下一节点只依赖单一的前序节点, 但有些问题需要依赖多个前序节点才能出方案, 例如斐波那契数列. 需要注意.

    Posted by ideawu at 2020-02-12 15:57:31
  • 2020-01-21

    算法题分类及解题思路

    Views: 2788 | No Comments

    * 暴力破解(brute force)

    暴力破解, 就是穷举. 穷举的方式一般用递归, O(n^2). 优化的思路是减少递归步骤:

    1. 更加严格的静态递归条件
    2. 增加 close_list, 动态地判断是否需要进行递归, close_list 根据执行情况动态变化

    另外的一种优化方向是消除递归. 因为递归是可以通过递归栈 open_list 来消除的. 可以对栈进行动态排序, 优先进行最可能成功的下一个步骤(A*). 这种排序优化, 导致可以使用不同的数据结构来存储递归栈: stack, queue, priority_queue.

    有序性, 有序子集: 有一种非常常用的优化思路是利用输入条件的局部有序性(存在有序的子集), 不再穷举这些有序的子集. 在处理这些有序子集时, 采用 O(n) 或者 O(K) 算法, 最差也能采用二分法 O(logN), 而且其它元素与这些有序子集结合时, 也不再需要穷举.

    A* 算法: open_list 根据沉没成本G和未来成本(H)之和来决定下一个处理步骤, 达成即最优.

    * 动态规划(dynamic programming)

    动态规划与暴力破解类似, 都是分而治之的思路, 但又不相同. 动态规划的下一个处理步骤是唯一的, 而且 open_list 初始可以确定, 后续单调递减. 下一个步骤的处理除了依赖自身的静态条件, 还依赖之前的处理结果集, 并维护这个结果集. 有点像消除了递归之后的暴力破解, 但暴力破解的 open_list 不是初始固定的.

    * 直观解法(coding)

    这类问题的解法非常直观, 一般没有算法上的优化空间, 也不需要技巧, 纯粹是为了训练编程能力. 考察做题者对变量的状态判断是否完备充分, 判断路径是否最简, if 分支是否可以合并等等. 所以, 就是考察边界条件的判断, 还有逻辑条件精减, 要求有非常强的逻辑思维能力.

    一般这类题就是链表翻转, 有序链表合并, 删除重复元素, 数组遍历(螺旋向内, 螺旋向外, 蛇形, 等等), partition 等.

    要点是: 边界判断, 分支合并, 简化重合边界的处理, 增加虚拟节点进行辅助.

    Posted by ideawu at 2020-01-21 09:38:57
  • 2020-01-21

    蛇形遍历数组

    Views: 3414 | No Comments

    蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.

    但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.

    Continue reading »

    Posted by ideawu at 01:43:19
  • 2020-01-15

    分而治之算法(divide and conquer)

    Views: 3372 | No 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);}
    

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

    Posted by ideawu at 2020-01-15 16:36:14 Tags:
|<<<1>>>| 1/1 Pages, 5 Results.