从Dijkstra算法分析动态规划与贪心策略

Dijkstra算法是动态规划还是贪心策略？

先说结论，Dijkstra属于贪心策略。 DP每一步递归是基于前一状态的"真"最优，而贪心可能是"伪"最优。贪心算法执行完成后才能知道真正的最优解，而DP其实不需要执行完就可以得到任意状态的最优解。如果说Dijktra算法不是动规，那么如果用动规如何来"重写"Dijkstra算法呢？

Dijkstra动态规划的解决方法

Dijkstra算法解决的是单点最短路径问题，即在一个图中，给定源点s，求到这个源点的最短路径。如果使用动态规划来解决这个问题，按照Dijkstra的思路，我们可以这样写出状态转移方程：

for e in v.edges:
  u = e.to
  dis[v] = min(dis[u] + e.length, dis[v])
  

dis[v]表示节点v到源点s的最短路径，v到s的最短路径是v点所有邻点过来路径中最短的一条，这也是上述状态转移方程的含义。只要知道v的每个邻点u的最短路径，就可以求得v的最短路径。但事实上这是不可能的，因为无法确定到达v节点时，它的每个邻点u的最短路径就已经计算出来了。即该方程只满足最优子结构，但不满足无后效性。

Dijkstra贪心策略的理解

将图中所有节点分为两个集合S和T，S包含确定了最短路径的节点，T是尚未确定最短路径的节点集合。初始S集合只包括源点s，s节点所有邻边中最短那条的邻点u，可以确定<s,u>是u到s的最短路径，因此u可以确定进入S集合，再对u的所有邻点作松弛操作。（松弛操作：将节点u的最短路径效果扩散至其相邻节点）。一般化后，只有T中距离(distance)最短的点，才可以确定它的距离是最短路径。所谓贪心，就在于此，不断选择T集合中距离最短的点加入S集合，直到目标节点t加入S集合。（具体实现参见下面Dijkstra算法实现代码）节点一经确定进入T集合，最短路径就可以计算得出，不再受之后其它节点的松弛操作影响，所以符合无效性原则，因此所得解是全局最优解。

Dijkstra源码

struct Edge
{
    int to; // edge's end node
    int length;
    Edge(int t, int l): to(t), length(l) {}
};

vector<vector<Edge> > graph;    // graph[i][j]:i is node, while j is edge

struct Point
{
    int id;     // id of node
    int distance;    // distant to source node
    Point(): id(), distance() {}
    Point(int i, int d): id(i), distance(d) {}
    bool operator<(const Point& b) const{
        return(distance > b.distance);
    }
};

int Dijkstra(int s, int t)
{
    //vector<int> dis(graph[s].size(), INT_MAX);
    //int dis[MAXN] = {INT_MAX};  // This method only set dis[0]
    int dis[MAXN];  // dis[i]: minium distance between node i and s 
    fill(dis, dis + MAXN, INT_MAX);
    priority_queue<Point> PointQue;     // BST
    // init s
    dis[s] = 0;
    PointQue.push(Point(s, dis[s]));

    //Point curr; 
    while(!PointQue.empty())
    {
        int u = PointQue.top().id;
        if (u == t)
            return dis[u];
        int distance = PointQue.top().distance;
        PointQue.pop();
        for(auto v = graph[u].begin(); v != graph[u].end(); v++)
        {
            if(dis[(*v).to] > dis[u] + (*v).length)   // avoid back and go into dead loop
            {
                dis[(*v).to] = dis[u] + (*v).length;
                PointQue.push(Point((*v).to, dis[(*v).to]));
            }
        }
    }
    # return dis[t];
}
  

动规"一个模型三个特征"

最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面状态推导出来。

无后效性

无后效性，有两层含义，第一层含义是，在推导后面阶段状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。当前状态只与之前的状态相关，不受之后状态的影响。

重复子问题（TODO)

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态

贪心策略是动规的特例

满足无后效性的贪心策略能够得到全局最优解。