COS157 · Phân tích và Thiết kế Giải thuật

Bài 15 · Quay lui và cắt nhánh cho bài toán Người bán hàng rong (TSP - Traveling Salesman Problem)

Buổi 9 · Quay lui và cắt nhánh

Câu hỏi neo

Người bán hàng rong phải qua mọi thành phố, làm sao bỏ sớm những đường chắc chắn dài?

Nghĩ một phút rồi hãy bấm phát. Xem xong, quay lại so với câu trả lời của bạn.

Dừng lại thử

Chưa có điểm dừng riêng cho bài này. Trong lúc chờ, hãy tạm dừng video ở chỗ bạn thấy lạ, ghi lại dự đoán của mình, rồi xem tiếp để kiểm.

Bài trước, bài sau

  1. Bài 14
  2. Bài 16
Bài trước và bài sau
LoạiTênThông tinThời lượng
VideoQuay lui và hai luật cắt: xét 281 nút trong cây hơn hai triệu nútKhi nào bỏ được cả một nhánh tìm kiếm mà không sợ mất đáp án?Buổi 8 · Quay lui và cắt nhánh8:28
VideoP và NP: kiểm một đáp án dễ — vậy tìm có dễ không?Kiểm một đáp án thì dễ, vậy tìm ra đáp án có dễ không?Buổi 9 · Độ phức tạp tính toán (P và NP)8:33

← Tất cả bài của COS157