Algorithms : complete 05-advanced_algorithms_and_complexity 04-np-completenessalgos

1 files changed, 102 insertions, 1 deletions

diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/school_bus.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/school_bus.cpp
index 26bd942..14848e0 100644
--- a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/school_bus.cpp
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/school_bus.cpp
@@ -20,7 +20,7 @@ Matrix read_data() {
     return graph;
 }
 
-std::pair<int, vector<int> > optimal_path(const Matrix& graph) {
+std::pair<int, vector<int> > optimal_path_(const Matrix& graph) {
     // This solution tries all the possible sequences of stops.
     // It is too slow to pass the problem.
     // Implement a more efficient algorithm here.
@@ -60,6 +60,107 @@ std::pair<int, vector<int> > optimal_path(const Matrix& graph) {
     return std::make_pair(best_ans, best_path);
 }
 
+struct Memory {
+    int w; int c; int r;
+};
+
+std::pair<int, vector<int> > optimal_path(const Matrix& graph) {
+
+    int n = graph.size();   // edges
+    int m = (1 << n);       // max combinations
+    vector<vector<Memory>> cost(m, vector<Memory>(n, {INF, 0, 0}));
+    cost[0][0] = {0, -1, -1};
+
+    // C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i.
+    // If size of S is 2, then S must be {1, i},
+    //    C(S, i) = dist(1, i)
+    for (int i = 1; i < n; i++) {
+        int sid = (1 << i) + 1;
+        int v = graph[0][i];
+        if (v != INF) {
+            cost[sid][i] = {v, 0, 0};
+            // std::cout << "   set : ["<< sid << "][" << i << "] = " << cost[sid][i].w << std::endl;
+        }
+    }
+
+    // Else if size of S is greater than 2.
+    //    C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.
+    // Note that 1 must be present in every subset S, so 1 less bit:
+    m = (1 << (n - 1));
+    for (int s = 2; s <= n; s++) {
+        // std::cout << " size : " << s << std::endl;
+        // loop from 0 ..m, with n=5, s=2 => 110, 101, 011
+        for (int b = 0; b < m; b++) {
+            int nb = 0;
+            int v = b;
+            while(v) {
+                nb += (v & 1);  // check last bit
+                v >>= 1;        // shift
+            }
+            if (nb != s) {
+                continue;
+            }
+            // shift them and add 1 -> 1100, 1010, 0110
+            int bits = (b << 1);
+            // std::cout << "   bits : " << bits << std::endl;
+            for (int i = 1; i < n; i++) { // not 0 it's our start
+                if (bits & (1 << i)) {
+                    for (int j = 0; j < n; j++) {
+                        if (j != i && (bits & (1 << j))) {  // do not stay on the same vertex
+                            int k = bits + 1;
+                            int nk = (bits ^ (1 << i)) + 1;
+                            // std::cout << "       try : " << nk << "->" << j << "->" << i <<std::endl;
+                            int c = cost[nk][j].w + graph[j][i];
+                            if (c < cost[k][i].w) {
+                                cost[k][i] = {c, nk, j};
+                                // std::cout << "   set : ["<< k << "][" << i << "] = " << c << std::endl;
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+    // std::cout << std::endl;
+    // for (auto &row : cost) {
+    //     for(auto &m : row) {
+    //         std::cout << "   " << (m.w == INF ? 0 : m.w) << " (" << m.c << ";" << m.r << ") ";
+    //     }
+    //     std::cout << std::endl;
+    // }
+    // std::cout << std::endl;
+
+    int best = INF;
+    vector<int> path;
+
+    auto &last_row = cost[(1 << n) - 1];
+    Memory& last_m = cost[0][0];
+    int j;
+    for (int i = 0; i < cost[0].size(); i++) {
+        auto &cell = last_row[i];
+        int c = cell.w + graph[i][0];
+        if (c < best) {
+            j = i;
+            best = c;
+            last_m = cell;
+        }
+    }
+    if (best == INF) {
+        best = -1;
+    } else {
+        path.push_back(j + 1);
+        while(last_m.r > 0) {
+            // std::cout << last_m.w << " " << last_m.c << " " << last_m.r << std::endl;
+            path.push_back(last_m.r + 1);
+            last_m = cost[last_m.c][last_m.r];
+        }
+        path.push_back(1);
+    }
+    std::reverse(std::begin(path), std::end(path));
+
+    return std::make_pair(best, path);
+}
+
 void print_answer(const std::pair<int, vector<int> >& answer) {
     std::cout << answer.first << "\n";
     if (answer.first == -1)