Bài toán lớp 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 Ứ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 47 6   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

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 36 6   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

Luận văn trình bày về bài toán Clique Editing, và chứng minh tính NP-đầy đủ của bài toán, sau đó sẽ tìm hiểu lớp bài toán FPT và chứng minh bài toán Clique Editing thuộc lớp FPT. Mời các bạn tham khảo!

53p elephantcarrot 02-07-2021 47 4   Download

Bài viết giới thiệu một số bài toán thuộc lớp NP – khó (NP – Hard) và đề xuất một thuật toán xấp xỉ tìm lời giải cho bài toán tìm tập con lớn nhất, tập con có số phần tử xác định trước. Đối với mỗi bài toán tối ưu tổ hợp, hiện nay có khá nhiều phương pháp hữu hiệu với chi phí khá thấp về thời gian tính toán để tìm lời giải, có thể kể đến như thuật toán xấp xỉ nhanh.

7p vilichae2711 12-06-2021 59 3   Download

Bài giảng NP - Complete trình bày một số bài toán tối ưu rời rạc; lớp P; lớp NP; NP-đầy đủ; bài toán CNF-SAT. Để nắm chi tiết nội dung nghiên cứu mời các bạn cùng tham khảo bài giảng.

28p cothumenhmong7 05-09-2020 39 4   Download

Bài toán xếp thời khóa biểu đại học là bài toán xuất phát từ nhu cầu rất cấp thiết của thực tế. Do thuộc lớp bài toán khó NP, bài toán hiện được quan tâm nghiên cứu và phát triển bởi rất nhiều nhà khoa học trên thế giới. Một trong những hướng tiếp cận hiệu quả nhất hiện nay là hướng tiếp cận sử dụng các metaheuristic.

9p vichoji2711 04-05-2020 80 5   Download

Nội dung chính của luận văn được chia thành 3 chương như sau: Chương 1/ Tìm hiểu tổng quan về các kiến thức cơ sở về độ phức tạp thuật toán, lớp các bài toán P, NP và NP-khó và các bài toán thuộc lớp bài toán vị trí cơ sở cũng như các công bố gần đây. Chương 2/ Trình bày chi tiết về thuật toán tối ưu hóa đàn kiến. Chương 3/ Trình bày về cài đặt chương trình, thử nghiệm và so sánh kết quả với một số công trình đã công bố gần đây.

72p hanh_tv26 03-04-2019 75 8   Download

Luận văn được tác giả hệ thống hóa các kiến thức cơ sở về lý thuyết độ phức tạp thuật toán, lớp các bài toán P, NP, NP-khó và NP đầy đủ, và trình bày các bài toán điển hình trong lớp các bài toán vị trí cơ sở cùng các nghiên cứu đã được công bố gần đây. Tiếp theo, tác giả đề xuất thuật toán dựa trên giải thuật tối ưu đàn kiến giải một số bài toán vị trí cơ sở hiện nay. Mời các bạn cùng tìm hiểu luận văn để nhận được kết quả nghiên cứu của tác giả.

23p hanh_tv26 03-04-2019 57 3   Download

Mục tiêu nghiên cứu của luận văn nhằm đóng góp: Thứ nhất-đề xuất một mô hình ngưỡng tuyến tính cho bài toán Cực tiểu hóa thiệt hại do thông tin sai lệch gây ra, đồng thời chứng mình bài toán này thuộc lớp bài toán NP-khó, thứ hai-đề xuất hai thuật toán tham lam nhằm giải quyết bài toán đặt ra, thứ ba-kết quả thực nghiệm cho thấy ưu điểm nổi trội của hai thuật toán đề xuất so với các thuật toán thông dụng khác như thuật toán bậc cực đại (Max Degree) và thuật toán ngẫu nhiên (Random) trong việc hạn chế thông tin sai lệch lan truyền trên mạng.

69p hanh_tv25 02-04-2019 73 13   Download

Đề tài được thực hiện nhằm đề xuất một mô hình ngưỡng tuyến tính cho bài toán cực tiểu hóa thiệt hại do thông tin sai lệch gây ra, đồng thời chứng mình bài toán này thuộc lớp bài toán NP-khó; đề xuất hai thuật toán tham lam nhằm giải quyết bài toán đặt ra; kết quả thực nghiệm cho thấy ưu điểm nổi trội của hai thuật toán đề xuất so với các thuật toán thông dụng khác như thuật toán bậc cực đại (Max Degree) và thuật toán ngẫu nhiên (Random) trong việc hạn chế thông tin sai lệch lan truyền trên mạng.

37p hanh_tv25 02-04-2019 49 4   Download