Bài toán NP

Bài viết Tìm hiểu một số phương pháp giải quyết bài toán NP - khó trình bày các nội dung: Bài toán NP-khó; Khái niệm quy dẫn; Lớp bài toán NP-đầy đủ và NP-khó; Một số phương pháp giải quyết bài toán NP khó.

3p vijaychest 16-05-2024 3 1   Download

Bài giảng "Thuật toán ứng dụng: Lý thuyết NP-đầy-đủ" trình bày các nội dung chính sau đây: Giới thiệu; Các lớp bài toán P, NP, NPC; Bài toán quyết định và bài toán tối ưu; Phép qui dẫn; Chứng minh NP-đầy-đủ; Các hướng tiếp cận giải bài toán NP-khó. Mời các bạn cùng tham khảo!

53p gaupanda031 20-05-2024 12 4   Download

Bài viết đề xuất phương pháp tìm lời giải cho Bài toán MS-RCPSP (Multi Skill-Resource Constrained Project Scheduling Problem). MS-RCPSP đã được chứng minh là bài toán NP-Khó, do vậy cần sử dụng các phương pháp tính toán tiến hóa, cận tối ưu nhằm tìm được lời giải phù hợp trong thời gian chấp nhận được.

8p visystrom 22-11-2023 13 7   Download

Bài viết Đề xuất, kiến nghị nâng cao nhận thức của sinh viên trường Đại học Điện lực về tội phạm xâm phạm danh dự và nhân phẩm trình bày việc xác định vai trò quan trọng trong việc nâng cao nhận thức của SV về tội phạm XPDD&NP, tình hình nhận thức của SV tại Trường ĐHĐL, cuối cùng đưa ra các giải pháp giáo dục và khuyến nghị cải thiện trong thời gian tới.

3p vimulcahy 02-10-2023 9 2   Download

Bài viết Ứng dụng giải thuật di truyền trong xử lý bài toán định tuyến xe nghiên cứu thuật toán di truyền và kỹ thuật tìm kiếm để tìm ra giải pháp đúng hoặc gần đúng đến các vấn đề tối ưu hóa và tìm kiếm để giải bài toán định tuyến xe.

6p vilexus 05-10-2022 45 6   Download

Bài viết Lập lịch trong môi trường tính toán đám mây dựa trên ràng buộc thời hạn tập trung lập lịch hướng đến hiệu năng về hệ thống. Bởi vì bài toán lập lịch tác vụ việc trên tính toán đám mây là một bài toán NP - đầy đủ, do đó cần thiết phải xây dựng các thuật toán heuristic để giải quyết vấn đề này. Bài viết này sử dụng thuật toán ACO để đưa ra một thuật toán heuristic mới về lập lịch trên các tác vụ trong môi trường tính toán đám mây.

5p vilexus 05-10-2022 21 5   Download

Bài viết Định vị tài nguyên cho các tác vụ trên tính toán đám mây dựa trên ràng buộc Deadline và ngân sách đưa ra một thuật toán để ánh xạ tập các tác vụ với các tham số đầu vào như thời gian đến, deadline, ngân sách và khối lượng công việc vào tập con của tài nguyên có chi phí và tốc độ khác nhau.

5p vilexus 30-09-2022 20 5   Download

Luận văn "Ứng dụng thuật toán di truyền giải bài toán đóng thùng" tập trung vào xây dựng một thuật toán di truyền để giải bài toán đóng thùng (bin packing problem), một bài toán tối ưu tổ hợp thuộc lớp bài toán NP – khó có nhiều ứng dụng trong thực tế như thiết kế lập lịch tối ưu cho công việc; sắp xếp hàng hóa kho chứa và container tối ưu; cấp phát bộ nhớ hiệu quả; hỗ trợ thiết kế các vi mạch điện tử.

123p bakerboys08 15-07-2022 27 7   Download

Bài viết Một cách giải bài toán suy diễn hậu nghiệm trong mô hình chủ đề trình bày bài toán suy diễn hậu nghiệm này thường đưa về một bài toán tối ưu không lồi thuộc lớp bài toán NP-Hard. Để giải bài toán suy diễn hậu nghiệm trong mô hình chủ đề, có nhiều phương pháp đã được đề xuất như: Phương pháp biến phân Variational Bayes (VB), collapsed variational Bayes (CVB) hay phương pháp collapsed Gibbs sampling (CGS).

3p vimegwhitman 10-06-2022 19 2   Download

Bài viết đề xuất phương pháp loại bỏ nhiễu dữ liệu LiDAR sử dụng khoảng cách danh nghĩa (NPS) trong quá trình tiền xử lý. Phương pháp đã được thử nghiệm với đám mây điểm LiDAR được thu nhận tại Bắc Ninh cho độ chính xác 93,6%.

8p visherylsandberg 18-05-2022 10 2   Download

Bài toán clique lớn nhất (Maximum clique problem) là bài toán tối ưu tổ hợp được ứng dụng trong nhiều lĩnh vực như mạng xã hội, tin sinh học, tài chính, lập lịch và đã được chứng minh là bài toán thuộc lớp NP-Hard. Nghiên cứu này đề xuất giải thuật bầy ong giải bài toán clique lớn nhất dựa trên hệ thống dữ liệu thực nghiệm chuẩn DIMACS gồm 37 bộ dữ liệu thực nghiệm.

9p viedison 13-04-2022 29 2   Download

Khóa tối tiểu và phản khóa là những khái niệm có vai trò quan trọng trong toán tử bao đóng. Bài báo giới thiệu về một bài toán tập không khóa của toán tử bao đóng. Bài toán này được bài viết chứng minh có độ phức tạp là NP-đầy đủ.

6p viplato 05-04-2022 15 2   Download

Nội dung của bản luận văn bao gồm ba chương, trình bày cụ thể như sau: Trình bày tóm tắt những kiến thức cơ bản và trọng tâm về lý thuyết thuật toán như máy Turing đơn định, máy Turing không đơn định, thuật toán, độ phức tạp thuật toán; Gồm có ba phần chính trình bày về khái niệm bài toán, danh sách các bài toán quan trọng và khái niệm độ phức tạp của bài toán; Gồm có hai phần chính trình bày lớp các bài toán P, NP và lớp bài toán NP-đầy đủ.

44p caphesuadathemhanh 02-12-2021 32 6   Download

Mục tiêu nghiên cứu của đề tài là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc. Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân loại thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ ) trong giới hạn thời gian cho phép.

45p tomjerry001 18-10-2021 35 6   Download

Bài viết đưa ra khái niệm tập tựa rút gọn (tập thuộc tính chứa một tập rút gọn nào đó) trong bảng quyết định nhất quán. Tác giả trình bày một bài toán NP- đầy đủ liên quan đến lực lượng của các tập tựa rút gọn.

4p vijihyo2711 25-09-2021 13 3   Download

Luận án trình bày các nội dung chính sau: Kiến thức cơ sở; Tổng quan về xử lý tính không nhất quán và tích hợp tri thức; Phương pháp khôi phục tính nhất quán trong cơ sở tri thức xác suất; Phương pháp tích hợp các cơ sở tri thức xác suất.

26p viyeri2711 14-09-2021 34 3   Download

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 12 có nội dung trình bày về NP-đầy đủ, khái niệm bài toán, hình thức hóa khái niệm bài toán, bài toán trừu tượng, bài toán quyết định, bài toán tối ưu, mã hóa bài toán, mã hóa chuẩn,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

48p bachdangky 16-09-2021 19 2   Download

Bài toán cây khung phân cụm đường đi ngắn nhất được ứng dụng nhiều trong tối ưu hệ thống tưới tiêu nông nghiệp, hệ thống cáp mạng và mạng lưới phân phối hàng hóa, dịch vụ. Do bài toán cây khung phân cụm đường đi ngắn nhất thuộc lớp bài toán NP-Khó nên các hướng tiếp cận gần đây thường sử dụng các thuật toán xấp xỉ để tìm lời giải, trong đó, hướng tiếp cận sử dụng kết hợp giữa thuật toán tiến hóa đa nhân tố và thuật toán tham lam ngẫu nhiên tìm được kết quả tối ưu trên nhiều bộ dữ liệu.

11p vining2711 09-08-2021 34 2   Download

Nội dung chính của luận văn là nghiên cứu cơ sở toán học của các thuật toán gần đúng giải lớp các bài toán thuộc lớp NP và NPC, tìm hiểu chi tiết các bước mô tả thuật toán và các yêu cầu thiết kế các thuật toán. Trên cơ sở các thuật toán đã nghiên cứu, luận văn phân tích một số các bài toán thuộc lớp NP, NPC, xây dựng lời giải đúng và gần đúng, đánh giá kết quả.

72p generallady 24-07-2021 18 3   Download

Cấu trúc luận văn gồm 3 chương: Chương 1 - Trình bày các khái niệm cơ bản, mô hình, các tham số cơ bản, các phép toán, cơ chế thực hiện tổng quát của thuật toán di truyền; Chương 2 - Trình bày khái niệm về thuật toán và độ phức tạp của thuật toán, sự phân lớp các bài toán qua độ phức tạp, một số mô hình bài toán lớp NP; Chương 3 - Trình bày kết quả sử dụng GA xây dựng thuật toán giải bài toán lập lịch phân công giảng dạy tại mô hình trường cao đẳng dạy nghề.

70p generallady 24-07-2021 25 4   Download