Đồ thị & Xấp xỉ NP-Hard
Christofides Algorithm (Metric TSP Approx)
ID: #280
Xem trên trang chủ
Thời gian (Time)
O(V^3)
Không gian (Space)
O(V^2)
Mô tả nguyên lý
Thuật toán xấp xỉ đảm bảo tỷ lệ 1.5 cho bài toán Metric TSP trên đồ thị đầy đủ thỏa mãn bất đẳng thức tam giác.
Cài đặt mẫu (Implementation)
// Tìm cây khung nhỏ nhất (MST) -> Tìm tập ghép cặp hoàn hảo trọng số lẻ -> Tạo chu trình Euler và rút gọn.
Đồ thị & Xấp xỉ NP-Hard
Christofides Algorithm (Metric TSP)
ID: #330
Xem trên trang chủ
Thời gian (Time)
O(V^3)
Không gian (Space)
O(V^2)
Mô tả nguyên lý
Thuật toán xấp xỉ tỷ lệ 1.5 cho bài toán Metric TSP thỏa mãn bất đẳng thức tam giác.
Cài đặt mẫu (Implementation)
// Kết hợp cây khung nhỏ nhất (MST) và ghép cặp hoàn hảo trọng số lẻ để tạo chu trình Euler.
Đồ thị & Xấp xỉ NP-Hard
Vertex Cover 2-Approximation
ID: #281
Xem trên trang chủ
Thời gian (Time)
O(V + E)
Không gian (Space)
O(V + E)
Mô tả nguyên lý
Thuật toán xấp xỉ hệ số 2 tìm tập đỉnh phủ (Vertex Cover) nhỏ nhất trong đồ thị vô hướng.
Cài đặt mẫu (Implementation)
// Lặp lại việc chọn liên tục một cạnh bất kỳ và đưa cả hai đầu mút của nó vào tập phủ, sau đó xóa các cạnh kề.