truy cập nhanh hơn trình duyệt!
5 quan hệ: Bài toán người bán hàng, Bài toán xếp ba lô, Lý thuyết độ phức tạp tính toán, NP-đầy đủ, P (độ phức tạp).
Bài toán người bán hàng
Nếu người bán hàng xuất phát từ điểm A, và nếu khoảng cách giữa hai điểm bất kì được biết thì đâu là đường đi ngắn nhất mà người bán hàng có thể thực hiện được sao cho đi hết tất cả các điểm mỗi điểm một lần để quay về lại điểm A ban đầu? Bài toán người bán hàng (tiếng Anh: travelling salesman problem - TSP) là một bài toán NP-khó thuộc thể loại tối ưu rời rạc hay tổ hợp được nghiên cứu trong vận trù học hoặc lý thuyết khoa học máy tính.
Mới!!: NP (độ phức tạp) và Bài toán người bán hàng · Xem thêm »
Bài toán xếp ba lô
Ví dụ về một bài toán xếp ba lô giới hạn 1 chiều: chọn các hộp nào để làm cực đại lượng tiền trong khi giữ được tổng khối lượng dưới 15 kg? Bài toán đa chiều có thể xét đến khối lượng riêng và kích thước của các hộp, đó là bài toán xếp vali điển hình (''packing problem''). (Lời giải là chọn tất cả các hộp trừ hộp xanh lục.) Bài toán xếp ba lô (còn được biết đến với tên gọi bài toán cái túi) là một bài toán tối ưu hóa tổ hợp.
Mới!!: NP (độ phức tạp) và Bài toán xếp ba lô · Xem thêm »
Lý thuyết độ phức tạp tính toán
Lý thuyết độ phức tạp tính toán là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng.
Mới!!: NP (độ phức tạp) và Lý thuyết độ phức tạp tính toán · Xem thêm »
NP-đầy đủ
Trong lý thuyết độ phức tạp tính toán, lớp NP-đầy đủ là một lớp các bài toán quyết định.
Mới!!: NP (độ phức tạp) và NP-đầy đủ · Xem thêm »
P (độ phức tạp)
Trong lý thuyết độ phức tạp tính toán, P, còn được gọi là PTIME hoặc DTIME(n^), là một trong những lớp cơ bản nhất trong các lớp độ phức tạp tính toán.
