Bài toán NP

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

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 33 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

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 35 3   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 48 4   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 76 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

Bài giảng Thuật toán nâng cao - Chương 10 trình bày về lớp các bài toán NP đầy đủ (NP-complete). Nội dung trình bày cụ thể gồm có: Đặt vấn đề, bài toán, lớp độ phức tạp NP, lớp NP đầy đủ, rút gọn bài toán, NP khó và NP đầy đủ, chứng minh bài toán NP đầy đủ. Mời các bạn cùng tham khảo.

10p thiendiadaodien_7 12-02-2019 214 4   Download

Bài giảng Thuật toán nâng cao - Chương 11 trình bày về thuật toán xấp sĩ (approximation algorithms). Nội dung trình bày cụ thể gồm có: Giải quyết các bài toán NP đầy đủ, tỉ lệ xấp xỉ, một số thuật toán xấp xỉ,...

9p thiendiadaodien_7 12-02-2019 41 5   Download

Dạng 3: Chứng minh ba điểm thẳng hàng: BÀI TOÁN 3: Cho tam giác ABC nội tiếp trong một đường tròn (O). M ; N ; P lần lượt là cá điểm chính giữa các cung nhỏ AB ; BC ; CA . MN và NP cắt AB và AC theo thứ tự ở R và S. Chứng minh rằng: RS // BC và RS đi qua tâm của đường tròn nội tiếp tam giác ABC. Cách giải 1: (Hình 1) Gợi ý: Đây là một bài toán hình tương đối khó đối với học sinh nếu không có tư duy...

6p paradise10 29-12-2011 485 63   Download

Tham khảo tài liệu 'các bài toán np – khó và np - đầy đủ', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

14p vuthithuy11a 26-11-2011 349 57   Download

Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán tìm rút gon tối thiểu của một hệ thống thông tin nói chung, và bài toán rút gọn của một hệ thống thông tin không đầy đủ nói riêng là một bài toán NP -khó. Lý do chính là do s tổ hợp các thuộc tính. ự Trong bài báo này, chúng tôi ề xuất một thuật toán rút gọn tập thuộc tính. Thuật toán là sự đ phát triển các kết quả của Cheng Degang và cộng sự trong hệ quyết định...

6p phalinh17 13-08-2011 143 18   Download