Đồ thị & Xấp xỉ NP-Hard

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 3)

Đồ thị & Xấp xỉ NP-Hard

Christofides Algorithm (Metric TSP Approx)

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)

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

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ề.