一次令人自闭的算法作业

最近一次Data Structure & Algorithm课程的作业是要求实现Dijkstra算法,并且其中的排序部分要使用最小堆来实现。

Dijkstra的基本思路如下

1. 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为”起点s到该顶点的距离”[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。

2.从U中选出”距离最短的顶点k”,并将顶点k加入到S中;同时,从U中移除顶点。

3.更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。

4.重复步骤(2)和(3),直到遍历完所有顶点。

我们的作业要求是在步骤2中的“选出距离最短的顶点”要用堆来实现。也就是说,我们需要维护一个最小堆,里面包含有起点到各个尚未访问到的顶点的(目前为止的)最短距离。每一次更新各个顶点到起点的距离时,都要更新堆中所有顶点的值。这样,每次寻找距离最短的顶点时,直接取出堆的根即可,省去了每次都要遍历一遍来寻找最小值。

我们要求的实现逻辑是这样的:维护一个如下的routing table,其中存储了每个节点的id,是否已经访问过,到出发点的最短距离,和该节点在堆中对应的位置。每次访问图中的一个节点时,都要在routing table中更新该节点及其所有后继节点的距离和其他信息。

node012
is_visitedtruetruefalse
cost013
heap_position012

我写完提交之后,被告知我的solution在小用例上部分正确,大用例上报vector越界的运行时错误。

动态规划算法

动态规划是一种分治(Divide&Conquer)的思想。在将大问题化解为小问题的分治过程中,保存对这些小问题已经处理好的结果,并供后面处理更大规模的问题时直接使用这些结果。

适用于动态规划的问题,需要满足最优子结构和无后效性两种情况。

  • 最优子结构性即如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。
  • 无后效性即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。

动态规划最重要的两个要点在于找到状态和状态转移方程,也就是递推关系。

如果不记录每一步的结果,动态规划的时间复杂度与Brute Force无异。动态规划实质上是一种以空间换时间的方法,通过存储过程中每一步骤的状态来降低时间复杂度。

举个栗子

我们以Leetcode的Climbing Stairs题目为例:

当前位置为第i级台阶时,有两种途径到达当前的状态:

  • 从第i-1级台阶走一步而来
  • 从第i-2级台阶走两步而来

因此,到达第i级台阶的途径为到达第i-1级台阶和到达第i-2级台阶的途径数量之和。我们可以得出如下的状态转移方程:

Leetcode笔记

最近开始刷leetcode,在这里记录一下做题的过程,不定期更新。

GitHub:https://github.com/nyanim/leetcode

Two Sum(Easy)

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

解法1:暴力搜索

题目本身很简单,使用两个for循环遍历即可。需要注意的是同一元素不能使用两次,因此在遍历时,内层循环需要直接从外层循环+1处开始,而不是从头开始。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum.py

解法2:哈希表

新建一个哈希表(Python中使用字典即可),遍历数组,以数组中的值为哈希表的键,以数组中的键为哈希表的值,将数组中的内容存入哈希表。

在遍历的同时检查(target-当前遍历到的值)是否存在哈希表的键中,如果存在则返回哈希表中的值和当前遍历到的键。这样复杂度由O(n^2)降低至O(n)。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum(Hashmap).py