TTNT - Áp Dụng Thuật Toán Nhánh Cận Trong Bài Toán Xếp Balo | Đại học Điện lực

lOMoARcPSD| 59629529
TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN
NHẬP MÔN TRÍ TUỆ NHÂN TẠO ĐỀ TÀI:
ÁP DỤNG THUẬT TOÁN NHÁNH CẬN VÀO BÀI TOÁN SẮP XẾP BA LÔ
Sinh viên thực hiện
LÊ HỒNG PHI - 21810310594
Giảng viên hướng dẫn : VŨ VĂN ĐỊNH Ngành
: CÔNG NGHỆ THÔNG TIN Chuyên ngành
: CÔNG NGHỆ PHẦN MỀM Lớp : D16CNPM6 Khóa : 2021-2026
HÀ NỘI , THÁNG 11 NĂM 2023 lOMoARcPSD| 59629529 PHIẾU CHẤM ĐIỂM Sinh viên thực hiện: Họ và tên Chữ Ghi ký chú Lê Hồng Phi- 21810310594 Giảng viên chấm: Họ và tên Chữ Ghi ký chú Giảng viên 1 : Giảng viên 2 : lOMoARcPSD| 59629529 MỤC LỤC
LỜI MỞ ĐẦU..........................................................................................................
CHƯƠNG 1: CƠ SỞ LÝ THUYẾT…………………………………………………
1.1 Tổng quan về trí tuệ nhân tạo……………………………………………....
1.1.1 Định nghĩa trí tuệ nhân tạo.....................................................................
1.1.2 Ứng dụng trí tuệ nhân tạo.......................................................................
1.1.3 Phân loại trí tuệ nhân tạo AL..................................................................
1.1.4 Một số ứng dụng Al điển hình…………………………………………
1.1.5 Hạn Chế Al.............................................................................................
1.2 Thuật toán Nhánh Cận……………………………………………………..
CHƯƠNG 2: ÁP DỤNG THUẬT TOÁN NHÁNH CẬN GIẢI QUYẾT BÀI
TOÁN XẾP BA LÔ……………………………………………………………
2.1 Mô tả bài toán………………………………………………………………
2.1.1 Định nghĩa..............................................................................................
2.1.2 Các bài toán xếp ba lô thường gặp.........................................................
2.2 Mô hình hóa bài toán....................................................................................
2.3 Các bước giải bài toán..................................................................................
2.3.1 Giải bải toán bằng thuật toán nhánh cận................................................
2.3.2 Xây dựng các hàm..................................................................................
2.4 Kết Quả Thực Nghiệm.................................................................................
2.4.1.Giao diện ban đầu..................................................................................
2.4.2 Kết quả...................................................................................................
KẾT LUẬN............................................................................................................. LỜI MỞ ĐẦU
Ngày nay, chúng ta đã bước vào thế kỷ 21, kỷ nguyên của Công nghệ thông
tin, đặc biệt là trí tuệ nhân tạo là yếu tố quan trọng nhất quyết định sự thành công
của mỗi ngành hay mỗi quốc gia. Trí tuệ nhân tạo đã và đang làm thay đổi cuộc lOMoARcPSD| 59629529
sống của chúng ta, với sự phát triển mạnh mẽ của việc áp dụng các nghiên cứu về
trí tuệ nhân tạo áp dụng cho cuộc sống. Tất cả các ngành như: Quân đội, y tế, giáo
dục, kinh tế thương mại, tài chính,... Đều có thể áp dụng trí tuệ nhân một cách
rộng rãi. Việc áp dụng trí tuệ nhân tạo để giải quyết các vấn để trong xã hội và
việc phát triển kinh tế đang được nhà nước khuyến khích và đầu tư rất lớn.
Trên thế giới cũng như Việt Nam, CNTT có ảnh hưởng rất mạnh mẽ đến
sự phát triến của đất nước và thế giới đặc biệt là trí tuệ nhân tạo. Nó trở thành một
yếu tố không thể thiếu và có tính quyết định đến sự thành công hay thất bại của
nhiều ngành ở nước ta, CNTT đang phát triển với tốc độ khá mạnh mẽ và được
ứng dụng rộng rãi trong tất cá các lĩnh vực, đặc biệt là trong công tác ứng dụng
công nghệ vào trong cuộc sống.
Như chúng ta đã biết, sức mạnh của một nên kinh tế phụ thuộc rất lớn vào
các hoạt động trong nước của các doanh nghiệp, vì vậy sự thành công trong kinh
doanh của doanh nghiệp không những là mục tiêu của riêng doanh nghiệp, mà nó
còn là nhân tố quyết định vị thể của đất nước trên trưởng quốc tế. Việc đưa Al
vào áp dụng cho các doanh nghiệp và cá các ngành như y tế, công nghiệp nặng
đang được ưu tiên và phát triển mạnh mẽ.
Tại Việt Nam, Nhà nước đang đi vào phát triển dịch vụ, và đầu tư mạnh mẽ
vào trí tuệ nhân tạo hay còn gọi là AI. Vì thể, việc đó đầu nó và phát triển nó đang
là một xu thế rất họt và rất được ưu chuộng hiện nay.
Chính vì vậy thông qua việc học môn trí tuệ nhân tạo (AI) em đã nghĩ ra
một ý tưởng nhỏ đó là "áp dụng thuật toán nhánh cận vào bài toán sắp xếp balo".
CHƯƠNG 1: CƠ SỞ LÝ THUYẾT
1.1.Tổng quan về trí tuệ nhân tạo.
1.1.1 Định nghĩa trí tuệ nhân tạo.
(AI: Artificial Intelligence) có thể được định nghĩa như một ngành của khoa
học máy tính liên quan đến việc tự động hóa các hành vi thông minh. lOMoARcPSD| 59629529
AI là một bộ phận của khoa học máy tính và đo đó nó phải được đặt trên
những nguyên lý lý thuyết vững chắc, có khả năng ứng dụng được của lĩnh vực này.
AI, trí tuệ nhân tạo là sự mô phóng các quá trình hoạt động trí tuệ của con
người, bao gỗm quá trình học tập (thu thập thông tin và các quy tắc để sử dụng
thông tỉn), lập luận (sử dụng các quy tắc để đạt được kết luận gần đúng), và tự sửa đổi.
1.1.2 Ứng dụng trí tuệ nhân tạo.
Một số ứng dụng sử dụng trí tuệ nhân tạo AI bao gồm hệ chuyên gia (expert
system), các ứng dụng nhận diện giọng nói và các ứng dụng machine vision.
Hình 1.1 AI- Trí tuệ nhân tạo là gì , những ứng dụng.
Thời gian gần đây nổi lên thuật ngữ mới có tên Big Data hay gia tăng tốc độ,
kích thước và thu thập các dữ liệu doanh nghiệp đa dạng. AI có thể thực hiện các
tác vụ như xác định các mẫu trong dữ liệu hiệu quả hơn con người, cho phép các
doanh nghiệp hiểu rõ hơn về dữ liệu của mình.
1.1.3 Phân loại trí tuệ nhân tạo AI. lOMoARcPSD| 59629529
Trí tuệ nhân tạo được phân loại theo nhiều cách khác nhau, dưới đây là 2 ví
dụ điển hình về phân loại trí tuệ nhân tạo.
Đầu tiên là phân loại trí tuệ nhân tạo AI theo hệ thống bao gồm trí tuệ nhân
tạo mạnh hoặc yếu. Trí tuệ nhân tạo yếu hay còn được gọi là Narrow AI, là hệ
thống trí tuệ nhân tạo được thiết kế và đào tạo cho các tác vụ cụ thể. Các trợ lý ảo
chẳng hạn như Siri của Apple là một dạng trí tuệ nhân tạo yếu.
Trí tuệ nhân tạo mạnh còn được gọi là Artificial General Intelligence hay :
trí tuệ nhân tạo tổng hợp, là hệ thống AI được trang bị khả năng nhận thức tổng quát
của con người để khi thực hiện các tác vụ không quen thuộc, nó đủ thông minh để
tìm ra các giái pháp. Phép thử Turing được phát triển bởi nhà toán học Alan Turing
vào năm 1950 là phương pháp được sử dụng để xác thực xem một máy tính có thể
có những suy nghĩ giống con người hay không, mặc dù phương pháp này gây nhiều tranh cãi.
Ví dụ thứ 2 là từ Arend Hintze, một trợ lý giáo sư sinh học hợp nhất và khoa
học máy tính và kỹ thuật tại Đại học bang Michigan. Ông phân loại trí tuệ nhân
tạo Al thành 4 loại, từ loại hệ thống Al hiện nay đến các hệ thống cảm giác, mà chưa tồn tại.
Loại 1: Máy phản ứng. Một ví dụ điển hình là Deep Blue, chương trình
cờ vua của IBM đánh bại Garry Kasparov vào những năm 1990. Deep Blue củ
thể xác định các phần trên bằng cỡ vua và dự đoán, nhưng nó không có bô nhứ
và không thể sử dùng những kinh nghiêm trong quá khứ để thông báo cho con
người trong tương lai. Nó phận tích các động thái của chính minh và đối thú, và
chọn một động thái chiến lược nhất. Deep Blue và AphaGO của Google được
thiết kế cho mục đích hẹp và không thể dễ dàng áp dụng cho tình huống khác.
Loại 2: Bộ nhớ hạn chế. Các hệ thống AI này có thể sử dụng các kinh
nghiệm trong quá khứ để đưa ra các quyết định trong tương lai. Một số chức năng
ra quyết định trong các loại xe tự lái được thiết kể dựa trên cách này. Các quan
sát được sử dụng để thông báo cho các hành động xảy ra trong tương lai không lOMoARcPSD| 59629529
xa, chẳng hạn như một chiếc xe đã thay đổi lần đường. Những quan sát này không
được lưu trữ vĩnh viễn.
Loại 3: Lý thuyết. Đây là một thuật ngữ tâm lý. Thuật ngữ này đề cập đến
việc hiểu được rằng con người có niềm tin, ham muốn và ý định của chính họ ảnh
hướng đến quyết định của họ. Tuy nhiên loại AI này chưa tồn tại.
Loại 4: Tự nhận thức. Với phần loại này, hệ thống AI có ý thức về bản
thân. Các máy có ý thức tự giác hiếu được trạng thái hiện tại của chúng và có thể
sử dụng thông tin để suy ra những gì người khác đang cảm nhận. Loại AI này vẫn chưa tồn tại.
Hình 1.2 Một số ví dụ về công nghệ trí tuệ nhân tạo.
- Tự động hóa là quá trình tạo ra hệ thống hoặc chức năng xử lý tự động.
Ví dụ như tự động hóa quy trình bằng Robot để thực hiện các tác vụ khối lượng
lớn mà con người thường xuyên lặp lại. Tự động hóa quy trình bằng Robot khác
với tự động hóa công nghệ thông tin ở chỗ là nó có thể thích nghi với các hoàn
cảnh thay đổi khác nhau.
- Machine Learning là khoa học để một máy tính thực hiện các hành độngkhông cần
lập trình. Deep Learning là tập hợp con của Machine Learing , với các thuật toán
khá đơn giản, có thể được coi là tự động hóa của các phân tích tiên đoán . lOMoARcPSD| 59629529
Có 3 thuật toán Machine Learning, bao gồm: Supervised Learning (học có giảm
sát), trong đó tập hợp dữ liệu được gắn nhãn sao cho các mẫu được phát hiện và
sử dụng để gắn nhãn các tập dữ liệu mới. Tiếp theo là Unsupervised Learning
(học không có giám sát), trong đó tập hợp dữ liệu không được dán nhãn và được
sắp xếp theo phân loại tương đồng hoặc khác biệt. Và cuối cùng là
Reinforcement Learning (học tăng cường), trong đó tập hợp dữ liệu không được
dán nhãn, nhưng sau khi thực hiện một hành động hoặc một số hành động, hệ
thống AI được phản hồi.
- Machine Vision (hệ thống nhận dạng và điều khiến dựa trên hình ảnh) làkhoa học
làm cho máy tính có thể nhìn thấy được. Machine Vision thu thập và phần tích thị
giác thông tin bằng cách sử dụng một camera, chuyển đổi từ kg thuật số và xử lý
tín hiệu số. Nó thường được so sánh với thị giác của con người, nhưng machine
vision không bị rằng buộc bởi sinh học và có thể được lập trình để xem qua các
bức tường. Ví dụ điển hình là machine vision được sử dụng trong một loạt các ứng
dụng từ nhận dạng chữ ký để phần tích hình ảnh y tế. Machinc Vision tập trung xử
lý hình ảnh dựa trên máy.
- Xử lý ngôn ngữ tự nhiên (Natural Language Processing - NLP) là quátrỉnh xử lý
ngôn ngữ máy tính của con người chứ không phải máy tính. Một trong những ví
dụ nổi tiếng nhất phải kể đến phát hiện thư rác, xem đồng chủ đề và vấn bản của
một email và quyết định xem đó có phải là thư rác hay không. NLP xử lý các tác
vụ bao gồm dịch văn bản, phân tích tình cảm và nhận dạng giong nói.
- Nhận dạng mẫu (Pattern recognition) là một phần của Machine Learningtrong đó
Lập trung vào việc xác định các mẫu trong dữ liệu.
- Robotics là một lĩnh vực kỹ thuật tập trung vào việc thiết kế và sản xuấtrobot.
Robot thường được sử dụng để thực hiện các tác vụ khó khăn cho con người, và
được sự dùng trong dây chuyên lắp ráp để sản xuất ô tô hoặc do NASA vận chuyển
các vật thể to lớn trong không gian . Gần đây hơn, các nhà nghiên cứu đang sử
dụng machine learning để xây dựng các robot có thể tương tác trong môi trường xã hội. lOMoARcPSD| 59629529
1.1.4 Một số ứng dụng AI điển hình.
Dưới đây là một số ứng dụng điển hình của trí tuệ nhân tạo:
- AI trong lĩnh vực chăm sóc sức khỏe: AI góp phần cải thiện tình trạng sức khóe
bênh nhân, đồng thời giảm các chi phí điều trị. Các công ty đang áp dụng Machine
Learning để chấn đoán nhanh hơn và tốt hơn con người. Một trong những công
nghệ chăm sóc sức khốc tốt nhất phải kể đến IBM Watson, có khả năng hiểu được
các ngôn ngữ tự nhiên và có khả năng phản hồi các câu hỏi được yêu cầu. Hệ thống
này khai thác dữ liệu bệnh nhân và các nguồn dữ liệu sẵn có khác để tạo ra giả
thuyết. Sau đó, nó sẽ trình bày một lược đồ điểm tin cậy. Các ứng dụng khác của
AI bao gồm chatbot, chương trình máy tính trực tuyến để trả lời các câu hỏi và hỗ
trợ khách hàng, sắp xếp các cuộc hẹn hoặc trợ giúp bệnh nhân thông qua quá trình
thanh toán và các trợ lý y tế ảo cung cấp phản hỏi y tế cơ bản.
- AI trong lĩnh vực kinh doanh: Tự động hóa quy trình bằng Robot được áp dụng
cho các tác vụ mà con người thực hiện lặp đi lặp lại. Thuật toán Machine Learning
được tích hợp trên các nền tảng phânn tích và CRM để khám phá các thông tin về
cách phục vụ khách hàng tốt hơn. Chatbots được tích hợp trên các trang web để
cung cấp địch vụ ngay lập tức cho khách hàng.
- AI trong lĩnh vực giáo dục: AI có thể tự động phân loại, giúp người làm giáo dục
có thể tiết kiệm một khoảng thời gian đáng kể. AI có thể đánh giá sinh viên và thích
ứng với nhu cầu của họ. Đồng thời AI có thể hỗ trợ thêm cho sinh viên làm thêm
công việc gia sư, đảm bảo rằng họ có thể đi đúng hướng.
- AI trong lĩnh vực tài chính: AI áp dụng cho các ứng dụng tài chính cá nhân như
Mint hay Turbo Tax, tăng cường các định chế tài chính. Một số ứng dụng khác như
IBM Watson được áp dụng AI này cho các giao dịch mua bán nhà.
- AI trong lĩnh vực pháp luật: Quá trình khám phá, chọn lọc thông qua các tài liệu
trong luật pháp thường áp đảo đối với con người. Tự động hóa quá trình này giúp
tiết kiệm thời gian và quả trình làm việc hiệu quả hơn. Startups cũng đang xây dưng lOMoARcPSD| 59629529
các trợ lý ảo cho máy tinh hỏi và trả lời các câu hỏi được lập trình, Hơn nữa , chúng
có thể sàng lọc các câu hỏi được lập trình để trả lời bằng cách kiểm tra phân loại .
- AI trong lĩnh vực sản xuất: Đây là lĩnh vực đi đầu trong việc kết hợp robot vào
luồng công việc , Robot công nghiệp được sử dụng để thực hiện các nhiệm vụ đơn
lẻ và được tách ra khỏi con người . 1.1.5 Hạn Chế AI
Trí tuệ nhân tạo mang lại rất nhiều giá trị cho cuộc sống loài người, nhưng
cũng tiềm ẩn những nguy cơ.
Rất nhiều chuyên gia lo lắng rằng khi trí tuệ nhân tạo đạt tới một ngưỡng tiến
hóa nào đó thì đó cũng là thời điểm loài người bị tận diệt. Rất nhiều các bộ phim
đã khai thác đề tài này với nhiều góc nhìn, nhưng qua đó đều muốn cảnh báo loài
người về mỗi nguy đặc biệt này.
Hình 1.3 1 cảnh trong bộ phim "I, Robot" nói về một Al đã tiến hóa, sau
đó đã dồn con người vào cảnh "nô lệ" với danh nghĩa bảo vệ con người. lOMoARcPSD| 59629529
Dự báo cho rằng từ 5 đến 10 năm nữa, ngành khoa học này sẽ phát triển lên
tới đính cao. Hãy cùng chờ đợi những thành tựu mới nhất của loài người về lĩnh vực này .
1.2 Thuật toán Nhánh Cận.
Cho một hàm mục tiêu f hay còn được gọi là hàm đánh giá và các hàm ràng
buộc logic g1,g2,….gn. Yêu cầu tìm một cấu hình x thỏa mãn tất cả các rằng buộc
g1,g2,….gn và f(x) là tốt nhất. Nghĩa là không tồn tại một cấu hình y thỏa mãn
các điều kiện mà f(y) tốt hơn f(x).
Ví dụ: Tìm (x,y) để x+y=max và thóa mẫn điều kiện x^2+y^2 ≤ 1.
Như vậy hàm mục tiêu f ở đây là xy -> max. Hàm ràng buộc g là x^2+y^2 ≤ 1.
Ta nhận thấy nếu xết trong mặt phẳng toa độ những cặp (x,y) thỏa mãn điều kiện
là tập hợp tất cả những điểm nằm trong và trên biên hình trỏn tâm 0 là góc toa độ và bán kính r=1;
Vậy nghiệm của bài toán là giao của phương trình đường thẳng x+y=c và phương
trình đường tròn x^2+y^2 =1; với c là hằng số và c đạt giá trị max khi đường
thẳng và đường trên tiếp xúc nhau tại tiếp điểm (x,y)=(1/2 ;1/2 ).
Giá trị max khi đó x+y = 2 cầu hình thỏa mãn là (1/2;1/2 ).
Dưới đây ta tìm hiểu kĩ thuật nhánh cận áp dụng cho thuật toán đệ quy và đệ
quy quay lui để tìm nghiệm tối ưu cho bài toán. lOMoARcPSD| 59629529
Mô hình thuật toán đệ quy quay lui trong chương trước chính là việc tìm
kiếm trên cây n cấp sẽ có 2^n nút lá điều đó có nghĩa là nếu dữ liệu đầu vào là n
thì ta phải duyệt 2^n lần trong trường hợp tồii nhất, con số này là quá lớn so với
dữ liệu ban đầu và trong quá trình duyệt có một số thao tác thừa đối với việc chọn
nghiệm xi tối ưu. Tư tưởng của kĩ thuật nhánh cận là loại bỏ đi những thao tác
thừa đó trong quá trình tiến hành gọi thủ tục đệ quy.
Mô hình của kĩ thuật nhánh cận như sau: Procedure Branch(i); Begin i>;
if (việc thử còn hi vọng tìm ra cấu hình tốt hơn) then
if (xi là phần tử cuối cùng trong cấu hình) then else begin
< ghi nhận giá trị j cho xi >; Branch(i+1); i>; end; end;
Như vậy việc bỏ đị thao tác thừa ở mô hình trên chính là việc thêm vào dòng lệnh
if (việc thử còn hi vọng tìm ra cấu hình tốt hơn) then. Điều này có nghĩa là tại
mỗi bước giá trị thử cho xi không còn hi vọng tìm ra cầu hình tốt hơn thì thử giá
trị khác ngay mà không cần gọi đệ quy tiếp theo hay ghi nhận cấu hình đó. Vậy
nghiệm của bài toán sẽ được làm tốt dần, bước sau tối ưu hơn bước trước, như
vậy cấu hình cuối cùng sẽ là cấu hình tối ưu nhất. lOMoARcPSD| 59629529
CHƯƠNG 2: ÁP DỤNG THUẬT TOÁN NHÁNH CẬN GIẢI QUYẾT BÀI TOÁN XẾP BALO
2.1 Mô tả bài toán.
Bài toán ba lô là một vấn đề trong tối ưu hóa tổ hợp : Cho một tập hợp các
mục, mỗi mục có trọng lượng và giá trị, hãy xác định số lượng của mỗi mục để
đưa vào một bộ sưu tập sao cho tổng trọng lượng nhỏ hơn hoặc bằng một giới hạn
nhất định và tổng giá trị càng lớn càng tốt. Tên gọi của nó bắt nguồn từ vấn đề
mà ai đó phải đối mặt là người bị bó buộc bởi một chiếc túi có kích thước cố định
và phải lấp đầy nó với những món đồ có giá trị nhất. Vấn dễ thường nảy sinh
trong việc phân bố nguồn lực trong đó những người ra quyết định phải chọn từ
một tập hợp các dự án hoặc nhiệm vụ không thể phân chia tương ứng với một
ngân sách cố định hoặc hạn chế về thời gian.
Bài toán ba lô dã được nghiên cứu trong hơn một thế kỷ, với những công
trình đầu tiên có niên đại từ năm 1897. Tên gọi "bài toán ba lô" có từ những công
trình dâu tiên của nhà toán học Tobias Dantzig (1884-1956), và đề cập đến vấn
đề phổ biến là đpsnggói những vật dụng có giá trị hoặc hữu ích nhất mà không làm quá tải hành lý. 2.1.1 Định nghĩa.
Dạng bài toán quyết dịnh của bài toán xếp ba lô là câu hỏi "có thể đạt được
một giá trị ít nhất là bao nhiêu theo phát biểu của bài toán".
Ta có n loại đồ vật x1 tới xn. Mỗi đồ vật xi có giá trị pi và một khối lượng
wi. Khối lượng tối đa mà ta có thể mang trong ba lô là C.
2.1.2 Các bài toán sắp xếp ba lô thường gặp.
Bài xếp ba lô không bị chặn: Không có một hạn chế nào về số lượng đồ vật.
Trường hợp đặc biệt lOMoARcPSD| 59629529
Bài toán với các tính chất:
• là một bài toán quyết định. • là một bài toán 0/1.
• với mỗi đồ vật, chi phí bằng giá trị: C = V.
Lưu ý rằng trong trường hợp đặc biệt này, bài toán tương đương với:
Cho một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng C?
Hoặc nếu đồ vật được phép có chi phí âm và C được chọn bằng 0, bài toán có dạng:
Cho trước một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0?
Trường hợp đặc biệt này được gọi là bài toán tổng các tập con (subset
sum problem). Với một số lý do, trong ngành mật mã học, người ta thường dùng
cụm từ "bài toán xếp ba lô" khi thực ra đang có ý nói về "bài toán tổng con".
Bài toán xếp ba lô thường được giải bằng quy hoạch động, tuy chưa có
một thuật toán thời gian đa thức cho bài toán tổng quát. Cả bài xếp ba lô tổng quát
và bài toán tổng con đều là các bài NP-khó, và điều này dẫn đến các cố gắng sử
dụng tổng con làm cơ sở cho các hệ thống mật mã hóa khóa công khai, chẳng hạn
Merkle-Hellman. Các cố gắng này thường dùng nhóm thay vì các số nguyên.
Merkle-Hellman và một số thuật toán tương tự khác dã bị phá, do các bài toán
tổng con cụ thể mà họ tạo ra thực ra lại giải dược bằng các thuật toán thời gian đa thức.
2.2 Mô hình hóa bài toán.
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 dế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). lOMoARcPSD| 59629529
(Giải pháp: nếu mỗi hộp có sẵn số lượng bất kỳ thì có ba hộp màu vàng và ba
hộp màu xám; nếu chỉ có các hộp được hiển thị thì có tất cả trừ hộp màu xanh lục.)
InPut: Loại đồ vật, Số lượng đồ vật mỗi loại, hạn mức balo,cân nặng và giá trị từng vật.
OutPut: Số lượng đồ vật mỗi loại có thể chứa, Tổng giá trị của các vật được chọn
là lớn nhất, tổng cân nặng các vật được chọn.
2.3 Các bước giải bài toán.
Giải ví dụ trên ta có bảng như sau: lOMoARcPSD| 59629529
B1: Hoán đổi vị trí các phần tử sao cho giá trị trên trọng lượng vật đó (giatri /
trongluong) sắp xếp giảm dần.
B2: Lựa chọn các vật vào trong ba lô sao cho tổng giá trị các vật được chọn lớn
nhất mà không vượt quá sức chứa của ba lô.
B3 : Tổng kết lại các vật phẩm đã chọn.
=> Kết quả ta tìm được là : Tổng giá trị là 15$; Vật cần lấy gôm 2,3,4,5 ; Tổng
khối lượng các vật đã lấy là 15kg, Khối lượng balo còn trống 0kg.
2.3.1 Giải bài toán bằng thuật toán nhánh cận.
1. Sắp xếp tất cả các mục theo thứ tự giảm dần của tỷ lệ giá trị trên đơn vị
trọnglượng để có thể tính giới hạn trên bằng cách sử dụng phương pháp tiếp cận Tham lam.
2. Khởi tạo lợi nhuận tối đa, maxProfit = 0
3. Tạo một hàng đợi trống, Q.
4. Tạo một nút giả của cây quyết dịnh và xếp nó vào hàng Q. Lợi nhuận vàtrọng
lượng của nút giả bằng 0.
5. Làm theo sau khi Q không trống.
• Trích xuất một mục từ Q. Gọi mục được trích xuất là u.
• Tính toán lợi nhuận của nút cấp tiếp theo. Nếu lợi nhuận nhiều hơnmaxProfit,
thì hãy cập nhật maxProfit.
• Tính giới hạn của nút cấp tiếp theo. Nếu giới hạn nhiều hơn maxProfit, thìhãy
thêm nút cấp tiếp theo vào Q.
• Hãy xem xét trường hợp khi nút cấp tiếp theo không dược coi là một phầncủa
giải pháp và thêm một nút vào hàng dợi với cấp như tiếp theo, nhưng trọng số
và lợi nhuận mà không tính đến các nút cấp tiếp theo. Đầu vào:
// Điều đầu tiên trong mỗi cặp là trọng lượng của mặt hàng.
// và điều thứ hai là giá trị của item. Ví dụ: lOMoARcPSD| 59629529
Mục arr []= {{2, 40}, {3,14, 50}, {1,98, 100},{5,95}, {3,30}}.
Dung lượng Knapsack W = 10. Đầu ra:
Lợi nhuận tối đa có thể = 235
Sơ dồ dưới dây minh họa. Các mặt hàng là được coi là sắp xếp theo giá trị / trọng lượng.
Hình 2.2 Sơ đồ giải thuật .
2.3.2 Xây dựng các hàm . struct Node {
public float weight, profit, bound; public int level, brand; }; bool comp(Item a, Item b) { lOMoARcPSD| 59629529
float r1 = a.Value / a.Weight;
float r2 = b.Value / b.Weight; return r1 < r2;
} float bound(Node v, float maxItem, float W, Item[] arr)
{ if (v.weight >= W) return 0; float profit_bound =
v.profit; int j = v.level + 1; float totweight = v.weight;
while (j < maxItem) && (totweight + arr[j].Weight <= W))
{ totweight += arr[j].Weight; profit_bound += arr[j].Value; j++; } if
(j < maxltem) profit_bound += (int)((W - totweight) * arr[j].Value /
arr[j].Weight); return profit_bound;
} float Form1(float W, Item[] arr, float maxItem) {
for (int i = 0; i < maxItem - 1; i++) for
(int j = i + 1; j < maxItem; j++) { if (comp(arr[i], arr[j])) Item t = arr[i]; arr[i] = arr[j]; arr[i］= t; } } list = new List(); opt opt = new opt(); int x = 0; Queue Q = new Queue(); Node u = new Node, v = new NodeO; u.level = - 1; u.profit = u.weight = 0; lOMoARcPSD| 59629529 u.brand = 0; Q.Enqueue(u); float maxProfit = 0; while (Q.Count() != 0) { u = Q.Dequeue(); if (u.level == -1) v.level = 0; if (ulevel == maxItem - 1) continue; v.level = u.level + 1:
v.weight = u.weight + arr[v.level].Weight;
v.profit = u.profit + arr[v.level].Value: v.brand = u brand:
if[u.weight == 0 && u.levels >- 1) { x++; v.brand = x; }
2.4. Kết quả thực nghiệm
2.4.1. Giao diện ban đầu lOMoARcPSD| 59629529
Hình 2.3: Giao diện chương trình. 2.4.2.
Kết quả đạt được
Hình 2.4. Kết quả đạt được KẾT LUẬN
Với kiến thức nền tảng đã được học ở trường và bằng sự nỗ lực của mình,
chúng em đã hoàn thành đề tài "Áp dụng thuật toán nhánh cận giải quyết bài
toán xếp ba lô". Mặc dù đã cố gắng rất nhiều nhưng do thời gian và kiến thức
có hạn nên chưa giải quyết được tốt các vấn đề đặt ra. Em rất mong nhận được
sự thông cảm và góp ý của thầy cô để đề tài của em được hoàn thiện hơn.
Đề của nhóm em đã hoàn thành và đã đạt được những kết quả sau:
- Đã xây dựng được một chương trình gồm có các chức năng cơ bản nhất.
- Đã tìm hiểu và năm rõ thêm những kiến thức về ngôn ngữ lập trình C#.
Tuy nhiên, vẫn còn một số hạn chế như:
- Mức độ tìm hiểu còn sơ sài, đơn giản, chưa mang đến tính hiệu quả cao để giải
quyết bài toán triệt để.