Algorithms : complete 05-advanced_algorithms_and_complexity 04-np-completenessalgos

16 files changed, 163 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)
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/01 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/01
new file mode 100644
index 0000000..0c9a76d
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/01
@@ -0,0 +1,7 @@
+4 6
+1 2 20
+1 3 42
+1 4 35
+2 3 30
+2 4 34
+3 4 12
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/01.a b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/01.a
new file mode 100644
index 0000000..27d0ecd
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/01.a
@@ -0,0 +1,2 @@
+97
+1 4 3 2 
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/02 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/02
new file mode 100644
index 0000000..68e1c9f
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/02
@@ -0,0 +1,5 @@
+4 4
+1 2 1
+2 3 4
+3 4 5
+4 2 1
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/02.a b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/02.a
new file mode 100644
index 0000000..3a2e3f4
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/02.a
@@ -0,0 +1 @@
+-1
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/03 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/03
new file mode 100644
index 0000000..51dbfa3
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/03
@@ -0,0 +1,5 @@
+4 4
+1 3 6
+1 4 2
+2 3 6
+2 4 2
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/03.a b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/03.a
new file mode 100644
index 0000000..a18caef
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/03.a
@@ -0,0 +1,2 @@
+16
+1 4 2 3 
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/04 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/04
new file mode 100644
index 0000000..0e84957
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/04
@@ -0,0 +1,5 @@
+4 4
+1 2 1
+1 4 2
+2 3 2
+3 4 6
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/04.a b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/04.a
new file mode 100644
index 0000000..57181c1
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/04.a
@@ -0,0 +1,2 @@
+11
+1 4 3 2 
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/05 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/05
new file mode 100644
index 0000000..bec5ee5
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/05
@@ -0,0 +1,7 @@
+5 6
+1 2 3
+1 3 1
+1 5 5
+2 5 9
+3 4 8
+4 5 5
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/05.a b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/05.a
new file mode 100644
index 0000000..8229c1a
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/05.a
@@ -0,0 +1,2 @@
+26
+1 3 4 5 2 
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/06 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/06
new file mode 100644
index 0000000..c37302e
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/06
@@ -0,0 +1,8 @@
+5 7
+1 2 1
+1 4 9
+2 4 1
+2 5 9
+3 4 6
+3 5 8
+4 5 1
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/06.a b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/06.a
new file mode 100644
index 0000000..c426ac6
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/06.a
@@ -0,0 +1,2 @@
+33
+1 4 3 5 2 
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/07 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/07
new file mode 100644
index 0000000..f6b5137
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/07
@@ -0,0 +1,4 @@
+3 3
+1 2 2
+2 3 3
+3 1 1
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/08 b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/08
new file mode 100644
index 0000000..4307f22
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/08
@@ -0,0 +1,7 @@
+4 6
+1 2 12
+1 3 30
+1 4 42
+2 3 34
+2 4 35
+3 4 20
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/08.a b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/08.a
new file mode 100644
index 0000000..ea1553b
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/tests/08.a
@@ -0,0 +1,2 @@
+97
+1 3 4 2