847. 访问所有节点的最短路径

847. 访问所有节点的最短路径

思路:

旅行商问题~真难!

DFS搜索

dfs搜索回溯貌似可行,但是没有明确的停止条件

BFS搜索

bfs搜索状态state(cover, head)可行。其中cover用位状态表示搜索过的节点的集合,head表示当前遍历的头结点。搜索的更新的new cover = cover | 1 << newhead

代码巧妙在于直接存储节点,而非路径,压缩了搜索范围。

实践发现如此简单的思路还是会超时!

考虑用dist[cover][head]记录最短路状态,减少搜索范围。

DAG化DP计算

在上述思路的前提下,dist[cover][head]在更新之后总有newcover>=cover。把dist当成一个图,而这个图保证了DAG的性质成立,那我们可以用DP方法计算最短路。在正向遍历cover1<<N,遍历时尝试用不同的边进行更新。

注意,更新计算可能会更新到相同cover集,即重复遍历了节点,那么需要再次尝试更新!

复杂度说明

一共有$2^N*N$种状态,而每种状态的更新最多N次计算。所以复杂度是O(2^N*N^2)

代码:


class Solution {
    
    queue<pair<int, int>>  que; // queue of statue and head.

public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int times = 0;;
        int n = graph.size(),  visall = (1 << n) - 1;
        vector<vector<int>> dist(1<<n, vector<int>(n, n * n));
        for(int i = 0; i < n; ++i){
            que.push({1 << i, i});
            dist[1 << i][i] = 0;
        }
        while(que.size()){
            auto [cover, head] = que.front();
            que.pop();
            int d = dist[cover][head];
            if(cover == visall) return d;
            
            for(auto v : graph[head]){
                int newcover = cover | 1 << v;
                if(d + 1 < dist[newcover][v]){
                    que.push({newcover, v});
                    dist[newcover][v] = d + 1;
                }
            }
        }
        return 0;
    }

};

class Solution {
    vector<int> trace;
    vector<int> newtrace;
    map<pair<int, int>, int> linker;
    set<int> intarce;
    int n;

public:
    int shortestPathLength(vector<vector<int>>& graph) {
        n = graph.size();
        for(int i = 0; i < n; ++i){
            //  cout << i << ":"  << endl;
            dfs(graph, i);
           
        }
            
        
        return trace.size() - 1;
    }

    inline pair<int, int> minpair(int a, int b){
        if(a > b ) return {b, a};
        return {a, b};
    }
    void dfs(vector<vector<int>>& graph, int u){
        
        newtrace.push_back(u);
        intarce.insert(u);
        // for(auto c : newtrace) cout << c << ' ' ;
        // cout << endl;
        if(intarce.size() == n){
            if(trace.size() == 0 || trace.size() > newtrace.size()){
                trace = newtrace;
            }            
        }else{
            for(auto v : graph[u]){
                if(++linker[minpair(u, v)] <= 4){                    
                    dfs(graph, v);
                }
                --linker[minpair(u, v)];
            }

        }
        
        newtrace.erase(newtrace.end() - 1);
        intarce.erase(u);
    }
};

DAG

class Solution {
    
    queue<pair<int, int>>  que; // queue of statue and head.
    
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int times = 0;;
        int n = graph.size(),  visall = (1 << n) - 1;
        const int maxlen = n * n;
        vector<vector<int>> dist(1<<n, vector<int>(n, maxlen));
        for(int i = 0; i < n; ++i){
            dist[1 << i][i] = 0;
        }
        for(int cover = 1; cover <= visall; ++cover){        
            bool repeat = true;
            while(repeat){
                repeat = false;            
                for(int u = 0; u < n; ++u){
                    if(dist[cover][u] == maxlen) continue; // jump over the states no exist.
                    int d = dist[cover][u];
                    for(auto v : graph[u]){
                        int newcover = cover | (1 << v);
                        if(d + 1 < dist[newcover][v]){           
                            dist[newcover][v] = d + 1;
                            if(newcover == cover) repeat = true; // if visited node set is the same as last set, just update again.
                    }
                }
                }
            }
            
        }
        int minans = maxlen;
        for(auto c : dist[visall]) minans = min(minans, c);
        return minans;
    }

};

Comments