truy cập nhanh hơn trình duyệt!Những điểm tương đồng giữa NP (độ phức tạp) và NP-đầy đủ
NP (độ phức tạp) và NP-đầy đủ có 4 điểm chung (trong Unionpedia): 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, 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.
Bài toán người bán hàng và NP (độ phức tạp) · Bài toán người bán hàng và NP-đầy đủ ·
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.
Bài toán xếp ba lô và NP (độ phức tạp) · Bài toán xếp ba lô và NP-đầy đủ ·
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.
Lý thuyết độ phức tạp tính toán và NP (độ phức tạp) · Lý thuyết độ phức tạp tính toán và NP-đầy đủ ·
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.
NP (độ phức tạp) và P (độ phức tạp) · NP-đầy đủ và P (độ phức tạp) ·
Danh sách trên trả lời các câu hỏi sau
- Trong những gì dường như NP (độ phức tạp) và NP-đầy đủ
- Những gì họ có trong NP (độ phức tạp) và NP-đầy đủ chung
- Những điểm tương đồng giữa NP (độ phức tạp) và NP-đầy đủ
So sánh giữa NP (độ phức tạp) và NP-đầy đủ
NP (độ phức tạp) có 5 mối quan hệ, trong khi NP-đầy đủ có 15. Khi họ có chung 4, chỉ số Jaccard là 20.00% = 4 / (5 + 15).
Tài liệu tham khảo
Bài viết này cho thấy mối quan hệ giữa NP (độ phức tạp) và NP-đầy đủ. Để truy cập mỗi bài viết mà từ đó các thông tin được trích xuất, vui lòng truy cập:
