diff options
Diffstat (limited to '05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus')
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 |