truy cập nhanh hơn trình duyệt!
15 quan hệ: Đường đi Hamilton, Bài toán đồ thị con đẳng cấu, Bài toán người bán hàng, Bài toán P so với NP, Bài toán xếp ba lô, Clique, Heuristic, Không gian Euclide, Khoa học máy tính, Lý thuyết độ phức tạp tính toán, NP (độ phức tạp), NP-khó, P (độ phức tạp), Phương pháp Monte Carlo, Thuật toán xấp xỉ.
Đường đi Hamilton
Đường đi Hamilton có nguồn gốc từ bài toán: "Xuất phát từ một đỉnh của khối thập nhị diện đều hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh khác, mỗi đỉnh đúng một lần sau đó quay về đỉnh xuất phát." là gọi theo tên của William Rowan Hamilton phát biểu vào năm 1859.
Mới!!: NP-đầy đủ và Đường đi Hamilton · Xem thêm »
Bài toán đồ thị con đẳng cấu
Trong lý thuyết độ phức tạp tính toán (Computational complexity theory), Đồ thị con đẳng cấu là một bài toán quyết định (decision problem) thuộc loại NP-đầy đủ (NP-complete).
Mới!!: NP-đầy đủ và Bài toán đồ thị con đẳng cấu · Xem thêm »
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-đầy đủ và Bài toán người bán hàng · Xem thêm »
Bài toán P so với NP
Bài toán P so với NP là một bài toán mở quan trọng trong lý thuyết khoa học máy tính.
Mới!!: NP-đầy đủ và Bài toán P so với NP · 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-đầy đủ và Bài toán xếp ba lô · Xem thêm »
Clique
Một đồ thị đầy đủ K5 (5 đỉnh). Nếu đây là một đồ thị con thì tập đỉnh của nó sẽ tạo nên một clique kích thước 5. Đồ thị ''G'' có: 23 clique 1 đỉnh (bằng số đỉnh của ''G''), 42 clique 2 đỉnh (bằng số cạnh của ''G''), 19 clique 3 đỉnh (tô bởi màu xanh nhạt), và 2 clique 4 đỉnh (tô bởi màu xanh sẫm). ''G'' có 6 clique cực đại 2 đỉnh và 11 clique cực đại 3 đỉnh. 2 clique 4 đỉnh đồng thời là các clique cực đại và lớn nhất của ''G'', như thế chỉ số clique của ''G'' là 4. Trong lý thuyết đồ thị, một clique (tiếng Anh, phát âm là) trong đồ thị vô hướng G là tập các đỉnh V (V là tập con của tập các đỉnh của G) thoả mãn: với mỗi cặp đỉnh thuộc V luôn tồn tại một cạnh của G nối chúng.
Mới!!: NP-đầy đủ và Clique · Xem thêm »
Heuristic
Heuristic (Dấu phụ Hy Lạp: "Εὑρίσκω", "tìm kiếm" hoặc "khám phá") là các kỹ thuật dựa trên kinh nghiệm để giải quyết vấn đề, học hỏi hay khám phá nhằm đưa ra một giải pháp mà không được đảm bảo là tối ưu.
Mới!!: NP-đầy đủ và Heuristic · Xem thêm »
Không gian Euclide
Descartes Khoảng 300 năm TCN, nhà toán học Hy Lạp Euclide đã tiến hành nghiên cứu các quan hệ về khoảng cách và góc, trước hết trong mặt phẳng và sau đó là trong không gian.
Mới!!: NP-đầy đủ và Không gian Euclide · Xem thêm »
Khoa học máy tính
Khoa học máy tính nghiên cứu các cơ sở lý thuyết của thông tin và tính toán, cùng với các kỹ thuật thực tiễn để thực hiện và áp dụng các cơ sở này.
Mới!!: NP-đầy đủ và Khoa học máy tính · 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-đầy đủ và Lý thuyết độ phức tạp tính toán · Xem thêm »
NP (độ phức tạp)
Trong lý thuyết độ phức tạp tính toán, NP là viết tắt của "nondeterministic polynomial time" (thuật toán bất định trong thời gian đa thức).
Mới!!: NP-đầy đủ và NP (độ phức tạp) · Xem thêm »
NP-khó
NP-khó là một tập hợp các bài toán trong lý thuyết độ phức tạp tính toán "ít nhất là khó ngang bất kì bài toán nào trong NP".
Mới!!: NP-đầy đủ và NP-khó · 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.
Mới!!: NP-đầy đủ và P (độ phức tạp) · Xem thêm »
Phương pháp Monte Carlo
Các phương pháp Monte Carlo là một lớp các thuật toán để giải quyết nhiều bài toán trên máy tính theo kiểu không tất định, thường bằng cách sử dụng các số ngẫu nhiên (thường là các số giả ngẫu nhiên), ngược lại với các thuật toán tất định.
Mới!!: NP-đầy đủ và Phương pháp Monte Carlo · Xem thêm »
Thuật toán xấp xỉ
Trong khoa học máy tính và vận trù học, thuật toán xấp xỉ là các thuật toán tìm lời giải xấp xỉ cho các bài toán tối ưu hóa.
Mới!!: NP-đầy đủ và Thuật toán xấp xỉ · Xem thêm »
