TR
NG
I H C BÁCH KHOA HÀ N I
VI N CÔNG NGH THÔNG TIN VÀ TRUY N THÔNG
___***___

BÁO CÁO BÀI

C CHUYÊN

MÔN TRÍ TU NHÂN T O
BÀI
T I

C:

U HĨA BÀI TỐN ĨNG GĨI HÌNH CH
M TH

NH T

NG TI P C N HỒN CH NH

Sinh viên th c hi n

Tr n Bá Tùng
ng V H nh
Nguy n Huy Tri n
Phan Vi t Phong
Nguy n Anh Tu n
Phùng Ng c Duy

Nhóm

2

Hà N i, 7/2013
1

20083041
20080899
20082751
20083429
20102772
20101256


M cL c
1.Gi i thi u ..................................................................................................................... 3
1.1 T ng quan.............................................................................................................. 4
2. Các tiêu chu n ............................................................................................................ 5
3. K thu t gi i ............................................................................................................... 5
3.1 Chi n lư c tìm ki m t ng th ................................................................................ 5
3.2 Bài toán t i thi u “khung gi i h n” ...................................................................... 5
3.4 Bài toán ng n ch n ................................................................................................ 6
3.5 Gán các kho ng x và các t a
x ......................................................................... 6
3.5.1 Nh ng cây con không th c t t a .................................................................... 6
3.5.2 C t t a v i nh ng tr ng thái l n át .................................................................. 6
3.5.3 S p x p bi n .................................................................................................... 6
3.5.4 Xác nh kích thư c kho ng ........................................................................... 7

3.6 Bi n i óng gói hồn tồn ................................................................................. 7
3.7 Gán tr c Y ............................................................................................................. 7
3.7.1 Mơ hình góc tr ng........................................................................................... 8
3.7.2 B n sao hình ch nh t ..................................................................................... 8
4. K t qu th c nghi m................................................................................................... 8
5. S s p x p tương i trong các trư ng h p có
chính xác cao............................... 9
5.1 Cơng vi c trư c ó ................................................................................................ 9
5.2 Chi n lư c chung ................................................................................................ 10
5.3 V n t i thi u “khung gi i h n” ...................................................................... 10
5.3.1 Tính tốn trư c các t ng t p con .................................................................. 10
5.3.2 C t t a s k t h p c!a chi u r ng và chi u cao ............................................ 10
5.4 V n ng n ch n ................................................................................................ 10
5.4.1 Gán các t a
x............................................................................................ 10
5.4.2 Hoàn thi n vi c chuy n i óng gói ........................................................... 10
5.4.3 Gán các t a
y............................................................................................ 11
5.4.4 X" lý các trư ng h p không nh hư ng...................................................... 11
5.5 K t qu th c nghi m ........................................................................................... 11
5.6 Tóm t t v hình ch nh t chính xác cao ............................................................. 11
6. #ng d ng c!a bài tốn óng gói hình ch nh t........................................................ 12
7. K t lu n..................................................................................................................... 12

2


Ý tưởng:
Xem xét vấn đề: tìm kiếm tất cả các hình chữ nhật bao quanh có diện tích nhỏ
nhất mà nó có thể chứa một tập các hình chữ nhật cho trước với điều kiện chúng

không chồng lên nhau.
Vấn đề được chuyển thành bài tốn đóng gói hồn hảo, khơng có khoảng trống
bằng cách thêm các hình chữ nhật bổ sung. Nói chung, thuật tốn được đưa ra đại
diện cho trạng thái hiện tại của bài toán, tốt hơn các thuật tốn khác về quy mơ
bài tốn, việc đánh giá dựa trên các tiêu chuẩn.
1.Giới thiệu
Chúng ta đề cập đến một hình chữ nhật bao quanh gọi là “khung giới hạn”.
Bài tốn tối ưu là dạng NP-hard.
Tiêu chuẩn hình vng liên tiếp: một tập đơn giản của các tiêu chuẩn ngày càng
khó cho vấn đề này, u cầu tìm các “khung giới hạn” có diện tích nhỏ nhất có thể
chứa một tập các hình vng có kích thước 1x1, 2x2, … , NxN (Korf-2003). Tiêu
chuẩn này được sử dụng để giải thích nhiều ý tưởng trong bài báo này, nhưng kỹ
thuật này khơng giới hạn với chỉ những hình vng, mà cịn áp dụng cho tất cả
các hình chữ nhật.
Đóng gói hình chữ nhật có nhiều ứng dụng thực tế, trong đó có mơ hình một số
vấn đề về lập lịch mà cơng việc địi hỏi nguồn lực được phân bổ trong khối liền kề
nhau.

3


1.1 Tổng quan
- Phần 2: Giới thiệu
u các tiêu chuẩn.
- Phần 3: Xem
em xét các hình thức
t
đóng gói hiện tại và kỹ thuậật của họ.
- Phần 4: Thu thập
p dữ

d liệu và so sánh công việc củaa chúng tôi với
v cách làm
trước đây và các tiêu chuẩn
chu tương ứng.
- Phần 5: Trình
rình bày tiêu chuẩn
ch
hình chữ nhật có kích thướ
ớc chính xác cao,
giải pháp kỹ thuậtt mới
m để giải quyết vấn đề này và kết quảả thực nghiệm. So
sánh các
ác phương pháp để
đ cho thấy phương pháp tiếp cận
n mới
m tốt hơn.
- Các phần còn lại: đưa ra các
c hướng đi khác nhau cho công việc
vi tương lai,
kết thúc bài viết bằng
ng việc
vi tóm tắt tất cả đóng góp và kếtt quả
qu của chúng tôi.
4


2. Các tiêu chuẩn
Các tiêu chuẩn mô tả các trường hợp với tham số duy nhất N, giải pháp tối ưu có
thể dễ dàng xác nhận và định rõ một bộ vô hạn các trường hợp mà cái sau sẽ khó
hơn cái trước.

• Tiêu chuẩn hình vng liên tiếp: như đề cập trong mục 1.
• Tiêu chuẩn hình chữ nhật liên tiếp khơng định hướng: trường hợp này tập
các hình chữ nhật có kích thước 1x2, 2x3, … , đến Nx(N+1) và các hình chữ
nhật có thể xoay 900.
• Tiêu chuẩn chỉ tìm kiếm giải pháp tối ưu đầu tiên được Simonis và
O’Sullivan sử dụng kết hợp với tiêu chuẩn hình chữ nhật liên tiếp khơng
định hướng, chỉ quan tâm đến thời điểm tìm được giải pháp tối ưu đầu
tiên.
• Hình chữ nhật với chu vi bằng nhau:
- Một là các hình chữ nhật có kích thước 1xN, 2x(N-1), …, Nx1 có cùng
chu vi là (2+2N) và các hình chữ nhật khơng xoay được.
- Hai là các hình chữ nhật có kích thước 1x(2N-1), 2x(2N-2),…, (N1)x(N+1), NxN có cùng chu vi là 4N và các hình chữ nhật có thể xoay
được.
3. Kỹ thuật giải
- Sử dụng kỹ thuật tìm kiếm sâu dần.
- Sử dụng kỹ thuật tìm kiếm nhánh và biên.
Các phương pháp cũ cố gắng đóng gói các hình chữ nhật vào trong một “khung
giới hạn” cho trước trong khi phương pháp mới tìm cách tối thiểu kích thước
“khung giới hạn” có thể chứa các hình chữ nhật.
Bài tốn được chia thành hai loại: bài toán ngăn chặn và bài tốn tối thiểu
“khung giới hạn”.
3.1 Chiến lược tìm kiếm tổng thể
Thực hiện một thuật toán thời gian quay lui với trật tự biến năng động. Thuật
toán hoạt động trong 5 giai đoạn được trình bày tiếp theo đây.
3.2 Bài toán tối thiểu “khung giới hạn”
Một cách giải quyết là tìm diện tích tối thiểu và tối đa mơ tả tập các đối tượng và
có khả năng tối ưu “khung giới hạn”.
Một cách khác là cho một chiều rộng của “khung giới hạn” và tìm kích thước cịn
lại.
5



3.4 Bài tốn ngăn chặn
Chúng tơi cải thiện về điềều này bằng cách thăm dò vớii các giá trị
tr tung độ y khác
nhau, mơ hình bố trí vị trí như các biến, và hình chữ nhậtt như các giá trị
tr (Huang &
Korf, 2009), làm cho sự đóng gói
gó của chúng tôi nhanh
hanh hơn so v
với Simonis và
O'Sullivan.
3.5 Gán các khoảng
g x và các tọa
t độ x
Đối với trục x, chúng
húng ta đưa ra những
n
hạn chế khi sử dụng
ng hàm heuristic
heurist tỉa bớt
khơng gian lãng phí củaa Korf, sử
s dụng một biến động để thay thếế và sắp xếp lại và
1 hàm để tối ưu giá trị gán cho biến
bi khoảng x.

3.5.1 Những cây con
n không thể
th cắt tỉa
Thông thường, để đặt đượ

ợc 1 tập hợp hình chữ nhậtt R vào trong 1 khối
kh hộp chiều
cao H thì phải thỏa mãn :

wr x hr là kích thước củaa hình chữ
ch nhật r. Với mỗi hình chữ nhậật chiều cao h thì
khoảng khơng gian trống
ng cịn lại
l phải có cùng chiều cao h hoặc lớn
n hơn.
3.5.2 Cắt tỉa với những
ng trạng
tr
thái lấn át
Ở đây chúng ta cần hiều
u 1 khái niệm
n
đó là một vị trí đặt khốii được
đư coi là lấn át
nếu nó chừa ra 1 khoảng
ng trống
tr
mà tất cả các hình chữ nhậtt cịn lại
l khơng thể đặt
vừa khít theo mọi cách.
3.5.3 Sắp xếp biến
Có 2 cách:
-

Sắp xếp giữa khoảng

ng X và trục X theo diện tích
Sắp xếp tồn bộ các hình chữ
c nhật theo yếu tố phân nhánh

Yếu tố phân nhánh đượcc tính theo cơng thức :
6


−

=

=

.

1

−

1

Với Bw là chiều rộng của khối hộp, rw là chiều rộng của hình chữ nhật và C là hằng
số được chọn bởi các chuyên gia.
Bw – rw là vị trí đặt hình chữ nhật sao cho vừa với khối hộp. Crw là khoảng vị trí
mà ta sẽ đặt hình chữ nhật.
Đối với tiêu chuẩn chu vi vô hướng, đầu tiên chúng ta thử tất cả các giá trị cho
một khoảng x cụ thể, và sau đó xoay hình chữ nhật 90 độ rồi thử một tập hợp các
khoảng x khác. Trong trường hợp này các yếu tố nhánh là :


=

−

−

+

1

=

+

1

−

2

Ở đây sau khi loại bỏ các vecto vô hướng và các hằng số ta thu được :
1

+

1

=

+


Vì vậy theo tiêu chuẩn vô hướng, ta sẽ đặt chúng theo thứ tự diện tích giảm dần.
3.5.4 Xác định kích thước khoảng
Với tiêu chuẩn hình vng liên tục, chúng ta sẽ dùng kích thước khoảng là 0.35
lần chiều rộng của hình chữ nhật. Ta cũng thấy rằng kích thước lớn sẽ cải thiện
được hiệu suất thực hiện với tiêu chuẩn chu vi đồng đều. Vì vậy ở đây lấy C=0.55.
Ảnh hưởng giữa việc gán khoảng và trạng thái lấn át: Với trường hợp hình vng
liên tục, hầu hết những hình vng sẽ có 1 vài vị trí lấn át. Do đó việc phân nhánh
đầu tiên sẽ gán khoảng x=[0,0] trước khi thực hiện gán tiếp theo để các khoảng
không nằm trong trường hợp bị lấn át.
3.6 Biến đổi đóng gói hồn tồn
Với những giải pháp hoàn chỉnh trên trục x, chúng ta chuyển vấn đề sang việc
biến đổi đóng gói hồn tồn trước khi làm việc trên trục y. Một gói hồn chỉnh là
1 bài tốn đóng gói mà k có khoảng trống nào thừa ra. Sự biến đổi sẽ kết thúc.
3.7 Gán trục Y
Coi hình chữ nhật là 1 biến và vị trí đặt nó là 1 giá trị, ngược lại so với trước đây
khi coi vị trí là biến cịn hình là giá trị. Với trục y ta sẽ tìm kiếm các mẫu gần hơn.
7


Sử dụng mơ hình 2D để kiểm
ki
tra sự chồng chéo và quay lại điểm
m không bị chồng
chéo giống như luật cắt tỉaa không gian của Korf.ởi việc thêm 1 tập
p hình vng
v
1x1
lấp đầy những khoảng trống
ng cịn lại.

l
3.7.1 Mơ hình góc trống
Với mọi giải pháp đóng gói hồn chỉnh thì mọi góc dướii bên trái phải
ph được lấp
đầy. Trong trường hợp
p này, mỗi
m góc ta sẽ có 1 biến. Trong giảii pháp cuối
cu cùng, để
mỗi hình chữ nhậtt đi vào đúng một
m góc trống, số lượng các biến
n góc trống
tr
bằng
với số lượng hình chữ nhậật trong trường hợp đóng gói hoàn chỉnh
nh. Tập các giá trị
chỉ là tập hợp các hình chữ
ữ nhật chưa được đặt vào.
3.7.2 Bản sao hình chữ nhật
nh
Do thêm hình chữ nhậtt 1x1 từ
t việc chuyển đổi đóng gói hồn chỉỉnh, chúng tơi đã
đưa thêm phương án dự phịng vào
v bài tốn. Một cách đơn giản
n để
đ xử lý vấn đề
này là như sau. Đối vớii một
m góc trống đặc biệt, chúng
ng tơi khơng bao gi
giờ đặt một
hình chữ nhật là một bản

n sao của
c một hình mà đã thử ở vị trí đó.
4. Kết quả thực nghiệm
Mơ hình này được thử nghiệm
nghi
trên HDH Linux 2GHz,
z, 2GB RAM. Gói KMP10
KMP (Korf
2010) đã được thử nghiệm
m trên một
m máy tính tương tự.. Gói SS08 của
c Simonis và
Sullivans 2008 cũng đượcc công bố
b với máy Windowss 3GHz RAM 3.25 GB
GB.

Thời gian chạy
y thuật
thu toán với những tiêu chuẩn
n khác nhau
(Vớii N là số
s lượng các hình vng liên tiếp)
8


5. Sự sắp xếp tương đốii trong các trường hợp có độ chính
nh xác cao
Chúng tơi giới thiệu “tiêu chuẩn
chu hình chữ nhật chính xác cao
o khơng đ

định hướng”,
nơi mà yêu cầu là tìm tấtt cả
c các “khung giới hạn” có diện
n tích nhỏ
nh nhất có thể
chứa một tập hữu hạn
n các hình chữ nhật khơng định hướng
ng có các kích
kí thước
× , × … đến ×
!

" "#

.

Tiêu chuẩn củaa chúng tơi bổ
b sung thay vì thay thế các tiêu chuẩn chính xác thấp
hiện tại, mà cho đến
n bây giờ
gi đã bị bỏ qua các trường hợp
p chính xác cao.
Phần còn lại của mụcc này được
đư tổ chức như sau. Đầu
u tiên chúng tôi xem xét một
số công việc trước khi đề xuất các giải pháp kỹ thuật có thể khơng bị
b ảnh hưởng
bởi sự chính xác củaa kích thước
thư hình chữ nhật. Sau đó chúng tơi mơ ttả các chuyển
thể khác nhau của các kỹ

ỹ thuật chính xác thấp củaa chúng tơi sang trường
trư
hợp
chính xác cao, cùng vớii một
m số kỹ thuật mới được phát triển
n đặc
đ biệt cho các
trường hợp hình chữ nhậật chính xác cao, và cuối cùng là theo dõi k
kết quả thực
nghiệm.
5.1 Công việc trước đó
Cách tiếp cận vị trí tương đối
đ của Moffitt và Pollack (2006) cho vi
việc đóng gói hình
chữ nhật, và các loạii tương tự
t của khơng gian tìm kiếm được sử
s dụng trong kế
hoạch hạn chế tài nguyên (Weglagz,
(Wegl
1999), hứa hẹn sẽ đượcc miễn
mi dịch với các
vấn đề của trường hợp
p hình chữ
ch nhật có độ chính xác
ác cao. Tuy nhiên, kể
k từ khi có
nhiều kỹ thuậtt mà chúng ta đã
đ mô tả trong các mục trướcc không thể
th được mở
rộng cho một cơng việcc đóng gói

gó trong khơng gian tìm kiếm
m vị
v trí tương đối,
chúng tơi đã quyết định
nh trong khn
khu khổ các vị trí tuyệt đối và cố
ố gắng giảm thiểu
các vấn đề đưa ra bởii các con số
s chính xác cao.

Một ví dụ về phương pháp sắp
s xếp với vị trí các hình chữ nhật hầu
u hết
h nằm ở phía
trái, và bên dưới.
9


5.2 Chiến lược chung
Đưa ra một ví dụ cho tiêu chuẩn chính xác cao của chúng tơi mơ tả trong các số
hữu tỉ, chúng ta nhân tất cả các giá trị với bội chung nhỏ nhất của các mẫu số để
có được một trường hợp với các kích thước ngun. Sau đó chúng ta áp dụng các
giải pháp kỹ thuật vị trí tuyệt đối, với các cải tiến chúng ta sẽ giải thích sau, để tìm
các giải pháp tối ưu. Mỗi lần tìm thấy, chúng ta chia tất cả tọa độ x- và y- mô tả
giải pháp tối ưu cho hằng số tỉ lệ ban đầu để có được những giải pháp tối ưu cho
các vấn đề ban đầu.
Lưu ý rằng chúng ta có thể lập bản đồ mỗi giải pháp đến một nơi mà tất cả các
hình chữ nhật trượt về phía trái hay phía dưới càng nhiều càng tốt (Chazelle,
1983).
5.3 Vấn đề tối thiểu “khung giới hạn”

5.3.1 Tính tốn trước các tổng tập con
Chúng ta tính tập tất cả các tổng tập con trước khi tìm kiếm. Để định hướng các
hình chữ nhật mà khơng thể ln chuyển chúng, chúng ta tính hai tập: một chỉ
dựa trên các chiều cao của các hình chữ nhật đại diện tọa độ y tương ứng, một chỉ
dựa trên các chiều rộng của các hình chữ nhật đại diện tọa độ x tương ứng. Điều
khác biệt này tạo ra các tổng tập con nhỏ hơn so với một mình tập tổng các tập
con tạo ra từ cả chiều rộng và chiều cao.
5.3.2 Cắt tỉa sự kết hợp của chiều rộng và chiều cao
Nhớ lại rằng thuật toán để giải quyết vấn đề tối thiểu “khung giới hạn” liên tục
gọi là thuật toán giải quyết vấn đề ngăn chặn. Các “khung giới hạn” được kiểm tra
theo thứ tự không giảm cho đến khi các trường hợp đầu tiên với các giải pháp
được tìm thấy.
5.4 Vấn đề ngăn chặn
5.4.1 Gán các tọa độ x
Với các hình chữ nhật định hướng, chúng ta chọn các tọa độ x từ tập các tổng tập
con của hình chữ nhật. Thay vì tính tốn trước tập hợp như chúng ta đã làm trong
vấn đề tối thiểu “khung giới hạn”, ở đây chúng ta tạo ra nó tự động tại mỗi nốt
trong suốt việc tìm kiếm trước khi phân nhánh trên các giá trị tọa độ x khác nhau
được gán.
5.4.2 Hồn thiện việc chuyển đổi đóng gói
Sau khi gán các tọa độ x, chúng ta tạo một con số của các hình chữ nhật 1x1 để
lấp đầy cho mọi không gian trống trong trường hợp ban đầu. Việc chuyển đổi dẫn
đến một trường hợp mới, khơng có khơng gian trống, bao gồm các hinh chữ nhật
10


ban đầu cộng với các hình chữ nhật 1x1 mới. Sau đó đưa ra một góc trống trong
một giải pháp từng phần, chúng ta u cầu có các hình chữ nhật chưa được đặt
ban đầu có thể phù hợp ở đó, hoặc một hình chữ nhật 1x1, về cơ bản mơ hình các
góc trống như là các biến và các hình chữ nhật là các giá trị.

Có 2 giải pháp: một là mở rộng các hình chữ nhật hiện có, hai là chuyển khơng
gian trống vào trong các hình chữ nhật lớn.
5.4.3 Gán các tọa độ y
Sau khi hoàn thiện việc chuyển đổi đóng gói, chúng ta gán các tọa độ y bằng cách
u cầu hình chữ nhật nào có thể được đặt vào một góc có khuynh hướng rỗng.
Như trước đó, chúng ta thực thi ràng buộc mà tọa độ y của mỗi hình chữ nhật
phải là tổng tập con của các chiều cao hình chữ nhật. Lưu ý rằng các hình chữ
nhật chúng ta tạo ra thơng qua hồn thiện việc chuyển đổi đóng gói khơng bao
gồm trong việc tính tốn tổng tập con, vì chúng đại diện không gian rỗng.
5.4.4 Xử lý các trường hợp không định hướng
Với các trường hợp khơng định hướng, khi tính tốn các chiều cao và chiều rộng
của “khung giới hạn” ban đầu, chúng ta sinh ra một tập tổng tập con đơn sử dụng
cả chiều cao và chiều rộng của tất cả các hình chữ nhật trong trường hợp này thay
vì giữ chiều rộng tách ra khỏi chiều cao. Tương tự như vậy, khi tạo ra tập các tọa
độ x và y tương ứng, chúng ta phải thêm một bước thứ tư với danh sách liệt kê
trong mục con 5.4.1 và chúng ta thêm chiều cao của mọi hình chữ nhật chưa từng
được đặt vào mọi phần tử trong tập các tổng tập con, vì điều này thể hiện khả
năng quay của hình chữ nhật.
5.5 Kết quả thực nghiệm
Chúng ta đưa ra hai bảng dữ liệu khác nhau, một liên quan đến các cải tiến trong
vấn đề tối thiểu “khung giới hạn” đo bằng số lượng “khung giới hạn” đã kiểm tra,
và một cái khác là tổng thời gian CPU để giải quyết vấn đề đóng gói hình chữ nhật.
5.6 Tóm tắt về hình chữ nhật chính xác cao
Trong phần này, chúng tôi đề xuất một tiêu chuẩn mới bao gồm các trường hợp
với hình chữ nhật kích thước chính xác cao cũng như các kỹ thuật cho việc sử
dụng tổng tập con đến giới hạn số vị trí phải được xem xét, các quy tắc để lọc ra
các tổng tập con cho cả vấn đề tối thiểu “khung giới hạn” và chính sách ngăn chặn,
các giải pháp học hỏi từ các cây con không khả thi, và cách để giảm số lượng hình
chữ nhật tạo ra trong hồn thiện việc chuyển đổi đóng gói. Các kỹ thuật này khai
thác khơng có tính chất đặc biệt của tiêu chuẩn, nhưng là hữu ích cho các hình

chữ nhật kích thước chính xác cao.

11


6. Ứng dụng của bài tốn đóng gói hình chữ nhật
Một trong những ứng dụng chính của bài tốn đóng gói hình chữ nhật là lập lịch.
Vấn đề đóng gói hình chữ nhật là một khái niệm trừu tượng của vấn đề lập lịch
nơi mà yêu cầu khác nhau có lượng thời gian khác nhau, và tất cả yêu cầu số
lượng khác nhau của một nguồn một chiều phải được phân bố liên tiếp nhau,
chẳng hạn như bộ nhớ máy tính. Chiều rộng của hộp ranh giới trở thành tổng thời
gian, chiều cao là tổng nguồn lực sẵn có, và mỗi cơng việc trở thành một hình chữ
nhật với chiều rộng tương đương với khoảng thời gian và chiều cao tương đương
với số lượng tài nguyên cần thiết.
Đó là phần lớn thời gian nhà đóng gói hình chữ nhật sử dụng chỉ để gán tọa độ x
của hình chữ nhật, tùy thuộc vào tích lũy ràng buộc, mà với mỗi tọa độ x trong
hộp ranh giới, tổng chiều cao các hình chữ nhật chồng lên tọa độ x khơng được
vượt quá chiều cao hộp ranh giới. Đây là phần nhỏ quan trọng của vấn đề đóng
gói hình chữ nhật mơ hình lên một vấn đề chung hơn được biết đến như vấn đề
lập lịch ràng buộc tài nguyên. Điều này tương tự như vấn đề lập lịch mô tả ở trên,
nhưng khơng có ràng buộc về tài ngun được phân bố liên tiếp nhau. Ví dụ, lập
lịch yêu cầu trên một xe thăm dò hành tinh với một ngân sách năng lượng hạn
chế, tổng nhu cầu năng lượng của tất cả các nhiệm vụ đang hoạt động tại bất kỳ
thời gian nhất định không thể vượt quá ngân sách năng lượng của cỗ xe. Như vậy,
phần nhỏ của đóng gói hình chữ nhật có thể được sử dụng để giải quyết vấn đề
lập lịch tổng quát hơn.
7. Kết luận
Vấn đề đóng gói hình chữ nhật là cực kỳ đơn giản, có thể hiểu được và chơi như
một trị chơi trẻ con. Tuy nhiên, các nghiên cứu trong thập kỷ qua mơ tả ở đây
cho thấy các thuật tốn hiệu quả nhất là khá phức tạp. Nếu các thuật toán tốt nhất

cho một vấn đề đơn giản là rất phức tạp, có khả năng là các thuật tốn tốt nhất
cho các vấn đề phức tạp cịn phức tạp hơn nữa, đó là phần khơng khích lệ. Phần
khích lệ là lịch sử nghiên cứu này đã chỉ ra rằng mỗi ý tưởng mới có thể dẫn đến
một thứ tự cường độ cải thiện hơn so với trạng thái trước trong các vấn đề lớn,
cho thấy vẫn cịn tiến trình rất quan trọng cần được thực hiện trong vấn đề này,
và những phần mở rộng khác như nó.

Tài liệu tham khảo:
E. Huang and R. E. Korf (2013) "Optimal Rectangle Packing: An Absolute Placement
Approach", Volume 46, pages 47-87

12