Tối ưu hóa kết hợp

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

Tối ưu hóa kết hợp

Branch and Bound for TSP

Thời gian (Time) O(n! / k)
Không gian (Space) O(n^2)

Mô tả nguyên lý

Giải bài toán Người đưa thư (Traveling Salesperson Problem) bằng kỹ thuật nhánh cận tối ưu.

Cài đặt mẫu (Implementation)

// Khám phá cây không gian trạng thái, loại bỏ các nhánh có chi phí vượt quá cận hiện tại.
Tối ưu hóa kết hợp

Memetic Algorithm Hybrid Optimization

Thời gian (Time) O(Iter * Pop * LocalSearch)
Không gian (Space) O(Pop)

Mô tả nguyên lý

Kết hợp thuật toán tiến hóa quần thể với các phương pháp tìm kiếm cục bộ (local search).

Cài đặt mẫu (Implementation)

// Áp dụng tìm kiếm cục bộ cho từng cá thể sau mỗi thế hệ tiến hóa để cải thiện độ chính xác.
Tối ưu hóa kết hợp

Simulated Annealing Metaheuristic

Thời gian (Time) O(Iter)
Không gian (Space) O(1)

Mô tả nguyên lý

Mô phỏng quá trình luyện kim, cho phép chấp nhận bước nhảy xấu hơn theo xác suất để thoát cực trị.

Cài đặt mẫu (Implementation)

// Giảm dần nhiệt độ theo thời gian và chấp nhận trạng thái tồi hơn theo hàm phân phối Boltzmann.
Tối ưu hóa kết hợp

Tabu Search Metaheuristic

Thời gian (Time) O(Iter * Neighborhood)
Không gian (Space) O(Tabu List)

Mô tả nguyên lý

Tìm kiếm cục bộ sử dụng danh sách cấm để tránh lặp lại các trạng thái tối ưu giả cục bộ.

Cài đặt mẫu (Implementation)

// Ghi nhớ các bước di chuyển vừa qua vào danh sách cấm để khuyến khích khám phá vùng không gian mới.
Tối ưu hóa kết hợp

Tabu Search Optimization

Thời gian (Time) O(Iter * Neighborhood)
Không gian (Space) O(Memory Tabu)

Mô tả nguyên lý

Thuật toán tìm kiếm cục bộ sử dụng danh sách cấm (tabu list) để tránh quay lại các trạng thái cũ.

Cài đặt mẫu (Implementation)

// Chấp nhận bước nhảy sang lân cận kém hơn nếu cần thiết và ghi nhớ các trạng thái vừa duyệt vào danh sách cấm.