Traveling Salesman Problem
HoldKỹ thuật
Bài toán tối ưu kinh điển về việc ghé thăm mỗi thành phố một lần với tổng quãng đường ngắn nhất.
Vì sao ở đây
Xếp vào Hold: 2 bài bằng chứng từ 1 nguồn, chủ yếu là tin nghiên cứu, 0 bài trong 30 ngày qua. Độ tin cậy 31%.
Bằng chứng (2)
- 4Hacker News·13/8/2026researchPhản biện quan điểm bi quan về bài toán NP-khó
Bài viết cho rằng tính NP-khó thường bị thổi phồng trong thực tế, vì nhiều khối lượng công việc đời thực không rơi vào trường hợp xấu nhất và vẫn có thể được giải quyết hiệu quả bằng thuật toán tốt và heuristic. Bài viết nêu các ví dụ như phân giải phụ thuộc gói, kiểm tra kiểu, lập lịch, TSP và giải SAT/SMT ở quy mô lớn để cho thấy lý thuyết không phải lúc nào cũng phản ánh đúng hiệu năng thực tế.
- 4Hacker News·4/8/2026researchVì sao có người cắt cỏ hiệu quả hơn người khác
Bài viết mô tả một thí nghiệm trong đó hơn 30.000 người giải bài toán lập lộ trình cắt cỏ, với nhiều người đạt gần phương án tối ưu và 16% thực hiện hoàn hảo. Kết quả được dùng để minh họa bài toán lập kế hoạch quét phủ và cách con người dựa vào các heuristics khi đối mặt với các bài toán tổ hợp ngày càng khó đối với máy tính.