TTUD62-3: Đệ quy, quay lui, nhánh cận

1 bình luận cho TTUD62-3: Đệ quy, quay lui, nhánh cận

• 

  12/10/2022 - 09:02

  admin  says:

  Mã nguồn minh họa bài TSP giải bằng nhánh cận:

  C++

  #include <iostream> using namespace std; const int MAX = 100; int n = 16, a[MAX], b[MAX] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, z = 1000000, cmin = 1; int c[MAX][MAX] = { { 0, 1, 2, 2, 99, 99, 99, 99, 2, 1, 2, 2, 99, 99, 99, 99 }, { 1, 0, 2, 99, 2, 99, 99, 99, 1, 4, 2, 99, 2, 99, 99, 99 }, { 2, 2, 0, 9, 7, 3, 99, 99, 2, 2, 5, 9, 7, 3, 99, 99 }, { 2, 99, 9, 0, 99, 4, 2, 99, 2, 99, 9, 2, 99, 4, 2, 99 }, { 99, 2, 7, 99, 0, 2, 99, 5, 99, 2, 7, 99, 3, 2, 99, 5 }, { 99, 99, 3, 4, 2, 0, 6, 2, 99, 99, 3, 4, 2, 8, 6, 2 }, { 99, 99, 99, 2, 99, 6, 0, 2, 99, 99, 99, 2, 99, 6, 9, 2 }, { 99, 99, 99, 99, 5, 2, 2, 0, 99, 99, 99, 99, 5, 2, 2, 10 }, { 7, 1, 2, 2, 99, 99, 99, 99, 0, 1, 2, 2, 99, 99, 99, 99 }, { 1, 5, 2, 99, 2, 99, 99, 99, 1, 0, 2, 99, 2, 99, 99, 99 }, { 2, 2, 2, 9, 7, 3, 99, 99, 2, 2, 0, 9, 7, 3, 99, 99 }, { 2, 99, 9, 4, 99, 4, 2, 99, 2, 99, 9, 0, 99, 4, 2, 99 }, { 99, 2, 7, 99, 6, 2, 99, 5, 99, 2, 7, 99, 0, 2, 99, 5 }, { 99, 99, 3, 4, 2, 3, 6, 2, 99, 99, 3, 4, 2, 0, 6, 2 }, { 99, 99, 99, 2, 99, 6, 1, 2, 99, 99, 99, 2, 99, 6, 0 , 2 }, { 99, 99, 99, 99, 5, 2, 2, 7, 99, 99, 99, 99, 5, 2, 2, 0 } }; long long dem = 0; void ghi_nhan_ket_qua(int tong) { dem++; int d = tong + c[a[n-1]][a[0]]; if (z <= d) return; z = d; cout << "Duong di thu " << dem << ", do dai = " << d << ": "; for (int i = 0; i < n; i++) cout << a[i] << " => "; cout << "0\n"; } // sinh a[k] void sinh(int k, int tong) { if (tong + cmin * (n-k+1) >= z) return; if (k == n) { ghi_nhan_ket_qua(tong); return; } for (int i = 0; i < n; i++) if (b[i] == 0) { b[i] = 1; a[k] = i; sinh(k + 1, tong + c[a[k-1]][i]); b[i] = 0; } } int main() { a[0] = 0; b[0] = 1; sinh(1, 0); cout << "So duong di xem xet: " << dem << ", ghi nhan duong di ngan nhat = " << z; }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

  #include <iostream> using namespace std;   const int MAX = 100;   int n = 16, a[MAX], b[MAX] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, z = 1000000, cmin = 1;   int c[MAX][MAX] = { {  0,  1,  2,  2, 99, 99, 99, 99,  2,  1,  2,  2, 99, 99, 99, 99 }, {  1,  0,  2, 99,  2, 99, 99, 99,  1,  4,  2, 99,  2, 99, 99, 99 }, {  2,  2,  0,  9,  7,  3, 99, 99,  2,  2,  5,  9,  7,  3, 99, 99 }, {  2, 99,  9,  0, 99,  4,  2, 99,  2, 99,  9,  2, 99,  4,  2, 99 }, { 99,  2,  7, 99,  0,  2, 99,  5, 99,  2,  7, 99,  3,  2, 99,  5 }, { 99, 99,  3,  4,  2,  0,  6,  2, 99, 99,  3,  4,  2,  8,  6,  2 }, { 99, 99, 99,  2, 99,  6,  0,  2, 99, 99, 99,  2, 99,  6,  9,  2 }, { 99, 99, 99, 99,  5,  2,  2,  0, 99, 99, 99, 99,  5,  2,  2, 10 }, {  7,  1,  2,  2, 99, 99, 99, 99,  0,  1,  2,  2, 99, 99, 99, 99 }, {  1,  5,  2, 99,  2, 99, 99, 99,  1,  0,  2, 99,  2, 99, 99, 99 }, {  2,  2,  2,  9,  7,  3, 99, 99,  2,  2,  0,  9,  7,  3, 99, 99 }, {  2, 99,  9,  4, 99,  4,  2, 99,  2, 99,  9,  0, 99,  4,  2, 99 }, { 99,  2,  7, 99,  6,  2, 99,  5, 99,  2,  7, 99,  0,  2, 99,  5 }, { 99, 99,  3,  4,  2,  3,  6,  2, 99, 99,  3,  4,  2,  0,  6,  2 }, { 99, 99, 99,  2, 99,  6,  1,  2, 99, 99, 99,  2, 99,  6, 0 ,  2 }, { 99, 99, 99, 99,  5,  2,  2,  7, 99, 99, 99, 99,  5,  2,  2,  0 } };   long long dem = 0;   void ghi_nhan_ket_qua(int tong) { dem++; int d = tong + c[a[n-1]][a[0]]; if (z <= d) return; z = d; cout << "Duong di thu " << dem << ", do dai = " << d << ": "; for (int i = 0; i < n; i++) cout << a[i] << " => "; cout << "0\n"; }   // sinh a[k] void sinh(int k, int tong) { if (tong + cmin * (n-k+1) >= z) return; if (k == n) { ghi_nhan_ket_qua(tong); return; } for (int i = 0; i < n; i++) if (b[i] == 0) { b[i] = 1; a[k] = i; sinh(k + 1, tong + c[a[k-1]][i]); b[i] = 0; } }   int main() { a[0] = 0; b[0] = 1; sinh(1, 0); cout << "So duong di xem xet: " << dem << ", ghi nhan duong di ngan nhat = " << z; }

  Trả lời