HOÀNG QUỐC VIỆT

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

HỒNG QUỐC VIỆT

CƠNG NGHỆ THƠNG TIN

TÌM HIỂU VÀ ÁP DỤNG GIẢI THUẬT TABU SEARCH

LUẬN VĂN THẠC SĨ KỸ THUẬT
NGÀNH CÔNG NGHỆ THÔNG TIN

2011-2013
Hà Nội - Năm 2013


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------HỒNG QUỐC VIỆT

TÌM HIỂU VÀ ÁP DỤNG GIẢI THUẬT TABU SEARCH

CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN

LUẬN VĂN THẠC SĨ KỸ THUẬT
CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:

PGS. TS. TRẦN ĐÌNH KHANG

Hà Nội – Năm 2013


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------*--------------------

HỒNG QUỐC VIỆT

TÌM HIỂU VÀ ÁP DỤNG GIẢI THUẬT
TABU SEARCH

LUẬN VĂN THẠC SĨ KĨ THUẬT
CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC:
PGS.TS TRẦN ĐÌNH KHANG

1 - 2013
HÀ NỘI


LỜI CẢM ƠN
Để hồn thành luận văn tốt nghiệp “Tìm hiểu và áp dụng giải thuật Tabu
Search” lời đầu tiên tôi xin gửi lời cảm ơn sâu sắc nhất tới PGS.TS Trần Đình
Khang, đã hƣớng dẫn và chỉ bảo tơi tận tình trong suốt thời gian làm khóa luận.
Tơi xin chân thành cảm ơn các thầy cô giáo Viện Công nghệ Thông tin và
Truyền thông Trƣờng ĐH Bách khoa Hà Nội, các giảng viên đã truyền đạt những

kiến thức, kỹ năng, kinh nghiệm nghề nghiệp....
Tôi xin chân thành cảm ơn Ban giám hiệu, tập thể giáo viên khoa Công nghệ
Thông tin trƣờng Đại học Sƣ phạm Kỹ thuật Hƣng Yên, gia đình cùng các bạn trong
lớp cao học Cơng nghệ Thơng tin khố 2011- 2013 đã tạo mọi điều kiện giúp đỡ,
động viên, chia sẻ để tơi hồn thành bản luận văn này.
Bản luận văn chắc cịn nhiều thiếu sót, rất mong đƣợc các thầy cô giáo trong
hội đồng chấm luận văn xem xét, góp ý kiến để luận văn đƣợc hồn thiện hơn.
Tơi xin chân thành cảm ơn!
Hà Nội, tháng 03 năm 2013
HỌC VIÊN

Hoàng Quốc Việt

2


LỜI CAM ĐOAN
Với mục đích học tập, nghiên cứu để nâng cao trình độ chun mơn nên
tơi đã làm luận văn này một cách nghiêm túc và hoàn toàn trung thực.
Trong luận văn, tơi có sử dụng tài liệu tham khảo của một số tác giả, tôi đã
nêu trong phần tài liệu tham khảo ở cuối luận văn.
Tôi xin cam đoan và chịu trách nhiệm về nội dung, sự trung thực trong
luận văn tốt nghiệp Thạc sĩ của mình.
Hà Nội, tháng 03 năm 2013
HỌC VIÊN

Hoàng Quốc Việt

3



MỤC LỤC
LỜI CẢM ƠN ................................................................................................................................ 1
LỜI CAM ĐOAN ......................................................................................................................... 3
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ......................................................... 7
DANH MỤC CÁC BẢNG ......................................................................................................... 8
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ................................................................................. 9
MỞ ĐẦU....................................................................................................................................... 10
1. Lý do chọn đề tài ...............................................................................................10
2. Mục đích nghiên cứu .........................................................................................10
3. Đối tƣợng và phạm vi nghiên cứu .....................................................................11
4. Phƣơng pháp nghiên cứu...................................................................................11
CHƢƠNG 1: TỔNG QUAN VỀ TÌM KIẾM ..................................................................... 12
1.1. Giải quyết vấn đề bằng tìm kiếm .................................................................12
1.2. Bài tốn tìm kiếm trong khơng gian trạng thái ............................................12
1.3. Các kĩ thuật tìm kiếm cơ bản .......................................................................14
1.3.1.

Tìm kiếm khơng có thơng tin ............................................................14

1.3.1.1. Tìm kiếm trên danh sách................................................................15
1.3.1.2. Tìm kiếm trên cây ..........................................................................15
1.3.1.3. Tìm kiếm trên đồ thị ......................................................................16
1.3.2.

Tìm kiếm có thơng tin .......................................................................17

1.4. Bài tốn tối ƣu hóa tổ hợp ...........................................................................18
CHƢƠNG 2: TÌM KIẾM CỤC BỘ ....................................................................................... 20
2.1. Tổng quan ....................................................................................................20

2.2. Giải thuật Tìm kiếm Cục bộ ........................................................................20
2.3. Một số thuật tốn Tìm kiếm Cục bộ cơ bản ................................................22
2.3.1.

Thuật toán Leo đồi ............................................................................22
4


2.3.2.

Thuật tốn Luyện thép .......................................................................24

2.3.3.

Một số thuật tốn tìm kiếm cục bộ khác ...........................................26

2.3.3.1. Giải thuật Di truyền .......................................................................26
2.3.3.2. Giải thuật tìm kiếm Lân cận lớn ....................................................26
2.3.3.3. Giải thuật tìm kiếm Tabu ...............................................................28
CHƢƠNG 3: TÌM KIẾM TABU ........................................................................................... 30
3.1. Tổng quan tìm kiếm Tabu ...........................................................................30
3.2. Nguyên lý chung của tìm kiếm Tabu ..........................................................30
3.3. Sơ đồ giải thuật tìm kiếm Tabu ...................................................................31
3.4. Giải thuật tìm kiếm Tabu .............................................................................32
3.5. Cách sử dụng bộ nhớ ...................................................................................32
3.6. Lập trình với bộ nhớ thích nghi ...................................................................35
3.7. Làm việc với bộ nhớ dài hạn .......................................................................35
3.8. Chiến lƣợc Tăng cƣờng và chiến lƣợc Đa dạng ...........................................36
3.8.1. Các chiến lƣợc tăng cƣờng .......................................................................37
3.8.2. Các chiến lƣợc đa dạng ............................................................................38

3.8.2.1. Thay đổi các luật lựa chọn ................................................................39
3.8.2.2. Khởi động lại .....................................................................................40
CHƢƠNG 4: ÁP DỤNG GIẢI THUẬT TÌM KIẾM TABU VÀO BÀI TỐN N-QUEENS ........ 43

4.1. Mơ tả bài tốn n-queens...............................................................................43
4.2. Phân tích bài tốn ........................................................................................44
4.3. Xây dựng ứng dụng giải quyết bài tốn n-queens .......................................45
4.3.1.

Giải thuật tìm kiếm tabu cho bài tốn n-queens ................................46

4.3.2.

Cấu trúc chƣơng trình và mối quan hệ giữa các lớp chính ...............46

4.3.2.1. Lớp SolutionTabuSearch ...............................................................47
4.3.2.2. Lớp TabuSearch .............................................................................48
5


4.3.2.3. Lớp frmMain..................................................................................49
4.3.3.

Kết quả khi chạy chƣơng trình ..........................................................49

4.4. Đánh giá hiệu quả của giải thuật tìm kiếm Tabu .........................................51
4.4.1.

Cài đặt bài toán n-queens bằng một số giải thuật ..............................51


4.4.1.1. Cài đặt bằng giải thuật Quay lui ....................................................51
4.4.1.2. Cài đặt bằng giải thuật Luyện thép ................................................52
4.4.2.

Đánh giá hiệu quả của giải thuật tìm kiếm Tabu...............................55

4.4.2.1. Xây dựng phƣơng án đánh giá .......................................................55
4.4.2.2. Kết quả thực nghiệm của đề tài .....................................................55
KẾT LUẬN .................................................................................................................................. 58
1.

Kết quả đạt đƣợc của đề tài ...........................................................................58

2.

Hạn chế của đề tài .........................................................................................58

3.

Hƣớng phát triển của đề tài ...........................................................................59

TÀI LIỆU THAM KHẢO .........................................................................................60

6


DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT
Từ viết tắt

Từ đầy đủ


AI

Artificial Intelligent

Trí tuệ nhân tạo

BFS

Breadth First Search

Tìm kiếm theo chiều rộng

CNTT

Công nghệ Thông tin

CNPM

Công nghệ Phần mềm

DFS

Depth First Search

Tìm kiếm theo chiều sâu

GA

Genetic Algorithms


Giải thuật Di truyền

LNS

Large Neighborhood Search

LS

Local Search

LTM

Long Term Memory

Bộ nhớ dài hạn

SA

Simulated Annealing

Luyện thép

STM

Short Term Memory

Bộ nhớ ngắn hạn

TS


Tabu Search

TTNT

Trí tuệ Nhân tạo

TSP

Travelling Salesman Problem

OR

Operation Research

7

Giải thích

Tìm kiếm Lân cận lớn
Tìm kiếm Cục bộ

Tìm kiếm Tabu

Nghiên cứu tối ƣu


DANH MỤC CÁC BẢNG
Bảng 3.1: bài tốn sắp cơng việc ...............................................................................40
Bảng 3.2: khởi động lại bài toán sắp việc .................................................................41

Bảng 4.1: kết quả chạy bài toán n-queens với giải thuật Quay lui ...........................55
Bảng 4.2: kết quả chạy bài toán n-queens với giải thuật Luyện thép .......................56
Bảng 4.3: kết quả chạy bài tốn n-queens với giải thuật tìm kiếm Tabu ..................56
Bảng 4.4: so sánh thời gian chạy giữa các giải thuật ................................................56

8


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 2.1: bài tốn tìm kiếm cục bộ với khơng gian trạng thái và hàm mục tiêu .....22
Hình 3.1: cấu trúc bộ nhớ tìm kiếm Tabu .................................................................33
Hình 3.2: minh họa bài tốn cây tối ƣu .....................................................................34
Hình 3.3: tăng cƣờng và đa dạng ..............................................................................36
Hình 4.1: một số lời giải cho bài toán 8 quân hậu ....................................................44
Hình 4.2: cấu trúc lớp SolutionTabuSearch ..............................................................47
Hình 4.3: cấu trúc lớp TabuSearch............................................................................48
Hình 4.4: giao diện khi chạy chƣơng trình................................................................49
Hình 4.5: khởi tạo bàn cờ với kích thƣớc đƣợc chọn ................................................50
Hình 4.6: kết quả hiển thị khi tìm thấy kết quả .........................................................50
Hình 4.7: cấu trúc lớp Backtracking .........................................................................51
Hình 4.8: minh họa chạy chƣơng trình với giải thuật quay lui .................................52
Hình 4.9: cấu trúc lớp SoluionSimulatedAnnealing .................................................53
Hình 4.10: cấu trúc lớp SimulatedAnnealing ............................................................54
Hình 4.11: minh họa chạy chƣơng trình với giải thuật Luyện thép ..........................54
Biểu đồ 1: so sánh thời gian chạy giữa ba giải thuật ................................................57
Biểu đồ 2: so sánh thời gian chạy giữa hai giải thuật Luyện Thép và Tabu .............57

9



MỞ ĐẦU
1. Lý do chọn đề tài
Lớp các bài toán tối ƣu hóa tổ hợp xuất hiện trong nhiều lĩnh vực quan trọng
của cuộc sống: tin sinh học, tài chính, lập lịch, sản xuất…và là lớp bài tốn có nhiều
ứng dụng trên thực tế, một số bài toán kinh điển trong lớp bài toán này: bài toán
ngƣời du lịch, bài tốn n-queens, bài tốn tơ màu đồ thị, bài tốn xếp lịch trực y tá,
bài tốn tìm tập phủ đỉnh của đồ thị…
Lớp các bài toán tối ƣu tổ hợp thƣờng có tập khơng gian trạng thái lớn mà
khơng thể sử dụng các phƣơng pháp tìm kiếm thơng thƣờng để xem xét tất cả khơng
gian trạng thái. Tìm kiếm Cục bộ đƣợc thiết kế cho bài tốn tìm kiếm với khơng
gian trạng thái rất lớn và cho phép tìm kiếm trạng thái tƣơng đối tốt với thời gian
tìm kiếm chấp nhận đƣợc. Tuy nhiên phƣơng pháp tìm kiếm cục bộ, vẫn còn một số
nhƣợc điểm: thời gian giải quyết các bài tốn có thể vẫn cịn dài, thuật tốn có thể khơng
tìm ra lời giải tốt nhất trong một số lần chạy….
Giải thuật tìm kiếm Tabu đƣợc cải tiến từ phƣơng pháp tìm kiếm cục bộ. Bằng kết
quả thực nghiệm đã cho thấy kỹ thuật tìm kiếm Tabu có thể giải quyết hiệu quả các
bái tốn tối ƣu.
Trong khn khổ của khóa luận, đề tài tập trung tìm hiểu các nguyên lý chung và
nền tảng của tìm kiếm Tabu, áp dụng giải thuật này để giải quyết bài toán n-queens, từ
đó đánh giá hiểu quả của giải thuật này so với một số giải thuật khác.

2. Mục đích nghiên cứu
 Tìm hiểu một số giải thuật tìm kiếm cục bộ cho các bài tốn tối ƣu hóa tổ
hợp.
 Nghiên cứu cơ bản giải thuật tìm kiếm Tabu: ngun lí chung của tìm kiếm
Tabu, cách sử dụng bộ nhớ, nền tảng của tìm kiếm Tabu.
 Sử dụng phƣơng pháp tìm kiếm Tabu để giải quyết bài toán n-queens, đánh
giá đƣợc hiệu quả của giải thuật này so với một số giải thuật tìm kiếm khác.

10



3. Đối tƣợng và phạm vi nghiên cứu
Nghiên cứu tìm hiểu lý thuyết về giải thuật tìm kiếm Tabu. Từ đó sử dụng giải
thuật này để giải quyết bài tốn n-queens, sau đó đánh giá đƣợc hiệu quả của giải
thuật này đem lại so với một số giải thuật tìm kiếm khác.

4. Phƣơng pháp nghiên cứu
 Nghiên cứu tài liệu khoa học về các giải thuật tìm kiếm Cục bộ.
 Nghiên cứu tài liệu khoa học về các phƣơng pháp tìm kiếm Cục bộ.
 Nghiên cứu lý thuyết về giải thuật tìm kiếm Tabu.
 Sử dụng giải thuật tìm kiếm Tabu cài đặt cho bài tốn mơ phỏng n-queens.
 Đánh giá hiệu quả của giải thuật này so với một số giải thuật khác.

11


CHƢƠNG 1: TỔNG QUAN VỀ TÌM KIẾM
1.1. Giải quyết vấn đề bằng tìm kiếm
Tìm kiếm là một trong những hƣớng nghiên cứu quan trọng trong CNTT.
Trong thực tế, nhiều bài tốn có thể đƣa về bài tốn tìm kiếm, ví dụ:
 Trị chơi: nhiều trị chơi, ví dụ cờ vua, thực chất là quá trình tìm kiếm nƣớc
đi của các bên trong số những nƣớc mà luật chơi cho phép, để giành lấy ƣu
thế cho bên mình.
 Lập thời khóa biểu: lập thời khóa biểu là lựa chọn thứ tự, thời gian, tài
nguyên (máy móc, địa điểm, con ngƣời) thỏa mãn một số tiêu chí nào đó.
Nhƣ vậy, lập thời khóa biểu có thể coi nhƣ q trình tìm kiếm trong số tổ
hợp phƣơng án sắp xếp phƣơng án đáp ứng yêu cầu đề ra.
 Tìm đƣờng đi: trong số những đƣờng đi, lựa chọn đƣờng đi tới đích, có thể
thỏa mãn một số tiêu chí nào đó nhƣ tiêu chí tối ƣu về độ dài, thời gian, giá

thành…
 Lập kế hoạch: là lựa chọn chuỗi hành động cơ sở cho phép đạt mục tiêu đề
ra đồng thời thỏa mãn các yêu cầu phụ.
Sự phổ biến của các vấn đề có tính chất tìm kiếm dẫn tới u cầu phát biểu bài
tốn tìm kiếm một cách tổng qt, đồng thời xây dựng phƣơng pháp giải bài tốn
tìm kiếm sao cho hiệu quả, thuận lợi. Do vậy, tìm kiếm đã đƣợc nghiên cứu trong
khn khổ tốn rời rạc, lý thuyết thuật tốn. Trong TTNT, tìm kiếm đƣợc đặc biệt
quan tâm từ khía cạnh xây dựng phƣơng pháp cho phép tìm ra kết quả trong trƣờng
hợp khơng gian tìm kiếm có kích thƣớc lớn khiến cho những phƣơng pháp truyền
thống gặp khó khăn.
1.2. Bài tốn tìm kiếm trong khơng gian trạng thái
Một vấn đề có thể giải quyết thơng qua tìm kiếm bằng cách xác định tập hợp
tất cả các phƣơng án, đối tƣợng, hay trạng thái liên quan, gọi chung là khơng gian
trạng thái. Thủ tục tìm kiếm sau đó sẽ khảo sát không gian trạng thái theo một cách

12


nào đó để tìm ra lời giải cho vấn đề. Tùy vào cách thức khảo sát không gian trạng
thái cụ thể, ta sẽ có những phƣơng pháp tìm kiếm khác nhau.
Để có thể khảo sát khơng gian trạng thái, thuật tốn tìm kiếm bắt đầu từ một
trạng thái xuất phát nào đó, sau đó sử dụng những phép biến đổi trạng thái để nhận
biết và chuyển sang trạng thái khác. Quá trình tìm kiếm kết thúc khi tìm ra lời giải,
tức là khi đạt tới trạng thái đích.
Bài tốn tìm kiếm về cơ bản có thể phát biểu thơng qua năm thành phần chính
sau:
 Tập các trạng thái Q. Đây chính là khơng gian trạng thái của bài tốn.
 Tập (không rỗng) các trạng thái xuất phát S (S  Q). Thuật tốn tìm kiếm sẽ
xuất phát từ một trong những trạng thái này để khảo sát khơng gian tìm
kiếm.

 Tập (khơng rỗng) các trạng thái đích G (G  Q). Trạng thái đích có thể
đƣợc cho một cách tƣờng minh, tức là chỉ ra cụ thể đó là trạng thái nào,
hoặc không tƣờng minh. Trong trƣờng hợp sau, thay vì trạng thái cụ thể, bài
tốn sẽ quy định một số điều kiện mà trạng thái đích cần thỏa mãn. Ví dụ,
khi chơi cờ vua, thay vì chỉ ra vị trí cụ thể qn cờ, ta chỉ có quy tắc cho biết
trạng thái chiếu hết.
 Các tốn tử, cịn gọi là hành động hay chuyển động. Thực chất đây là một
ánh xạ P:Q Q, cho phép chuyển từ trạng thái hiện thời sang các trạng thái
khác. Với mỗi trạng thái n, P(n) là tập các trạng thái đƣợc sinh ra khi áp
dụng toán tử hay chuyển động P.
 Giá thành c: Q x Q  R. Trong một số trƣờng hợp, quá trình tìm kiếm cần
quan tâm tới giá thành đƣờng đi. Giá thành để di chuyển từ nút x tới nút
hàng xóm y đƣợc cho dƣới dạng số dƣơng c(x, y).
Hiệu quả của việc tìm kiếm thể hiện qua việc đánh giá theo 4 tiêu chuẩn:
 Độ phức tạp tính tốn: đƣợc xác định bằng khối lƣợng tính tốn cần thực
hiện để tìm ra lời giải. Thơng thƣờng, khối lƣợng tính tốn đƣợc xác định
bằng số lƣợng trạng thái cần xem xét trong suốt quá trình tìm ra lời giải.
13


 Bộ nhớ: đƣợc xác định bằng số lƣợng trạng thái cần lƣu trữ khi thực hiện
thuật tốn.
 Tính đầy đủ: nếu bài tốn có lời giải thì thuật tốn có khả năng tìm ra lời
giải đó khơng? Nếu có, ta nói rằng thuật tốn có tính đầy đủ, trong trƣờng
hợp ngƣợc lại ta nói thuật tốn khơng có tính đầy đủ.
 Tính tối ưu: nếu bài tốn có nhiều lời giải thì thuật tốn có cho phép tìm ra
lời giải tốt nhất khơng? Nếu có, ta nói lời giải đảm bảo tính tối ƣu.
1.3. Các kĩ thuật tìm kiếm cơ bản
Ý tƣởng của thuật tốn tìm kiếm: xem xét trạng thái, sử dụng các hàm biến
đổi trạng thái để di chuyển trong không gian trạng thái cho tới khi đạt đến trạng

thái mong muốn
Thuật tốn tìm kiếm tổng qt sinh ra một cây tìm kiếm, trong đó mỗi trạng
thái tƣơng ứng với một nút trên cây. Trạng thái xuất phát tƣơng ứng với gốc cây,
những trạng thái đƣợc mở rộng tạo thành các nút thế hệ tiếp theo.
Trên thực tế, việc di chuyển trong không gian trạng thái sẽ dẫn tới những nút
đã duyệt qua và tạo thành vòng lặp. Trong trƣờng hợp nhƣ vậy, cây tìm kiếm có thể
là vơ tận và cần có cách kiểm tra để khơng xem xét lại nút đã duyệt.
Các kỹ thuật tìm kiếm đuợc áp dụng rộng rãi hiện nay:
 Tìm kiếm khơng có thơng tin.
 Tìm kiếm có thơng tin.
1.3.1. Tìm kiếm khơng có thơng tin
Tìm kiếm khơng có thơng tin (hay tìm kiếm mù) là tìm kiếm khơng có hiểu biết
gì về các đối tƣợng để hƣớng dẫn tìm kiếm, khơng có sự hƣớng dẫn nào cho tìm
kiếm, chỉ phát triển các trạng thái từ trạng thái ban đầu cho tới khi gặp một trạng thái
đích nào đó. Nhƣợc điểm của các giải thuật này là phần lớn các không gian tìm kiếm
có kích thƣớc cực kì lớn, và một quá trình tìm kiếm (đặc biệt tìm kiếm theo cây) sẽ
cần một khoảng thời gian đáng kể cho các ví dụ nhỏ. Một số dạng tìm kiếm khơng có
thơng tin nổi bật ứng với các cách tổ chức dữ liệu:
14


1.3.1.1.

Tìm kiếm trên danh sách

Các giải thuật tìm kiếm trên danh sách [8] là loại giải thuật tìm kiếm cơ bản
nhất. Mục đích là tìm trong một tập hợp một phần tử chứa một khóa nào đó. Các
giải thuật tìm kiếm tiêu biểu nhất trên danh sách là: Tìm kiếm tuần tự (hay tìm kiếm
tuyến tính), tìm kiếm nhị phân.
Tìm kiếm tuần tự kiểm tra từng phần tử trong danh sách theo thứ tự của danh

sách đó. Nó có thời gian chạy khá lớn: O(n), trong đó n là số phần tử trong danh
sách, nhƣng có thể sử dụng cho một danh sách bất kỳ mà không cần tiền xử lý.
Tìm kiếm nhị phân là một thuật tốn cao cấp hơn so với thuật tốn tìm kiếm
tuần tự với thời gian chạy là O(log n). Đối với các danh sách lớn, thuật tốn này tốt
hơn hẳn tìm kiếm tuyến tính nhƣng nó địi hỏi danh sách phải đƣợc sắp xếp từ trƣớc
và đòi hỏi khả năng truy cập ngẫu nhiên. Thuật tốn tìm kiếm nội suy tốt hơn so với
thuật tốn tìm kiếm nhị phân đối với danh sách rất lớn và với phân bố gần đều.
Ngoài ra bảng băm (Hash Table) cũng đƣợc dùng cho tìm kiếm trên danh sách.
Nó địi hỏi thời gian hằng số trong trƣờng hợp trung bình, nhƣng lại cần nhiều chi phí
về khơng gian bộ nhớ và thời gian chạy O(n) cho trƣờng hợp xấu nhất. Một phƣơng
pháp tìm kiếm khác dựa trên các cấu trúc dữ liệu chuyên biệt sử dụng cây tìm kiếm
nhị phân cân bằng và đòi hỏi thời gian chạy O(log n). Các giải thuật loại này có thể
coi là mở rộng của tƣ tƣởng chính về tìm kiếm nhị phân để cho phép chèn và xóa
nhanh.
1.3.1.2.

Tìm kiếm trên cây

Tìm kiếm trên cây là trung tâm của các kỹ thuật tìm kiếm. Các thuật tốn này
tìm kiếm trên các cây gồm các nút, cây này có thể là cây tƣờng minh hoặc đƣợc xây
dựng dần trong quá trình tìm kiếm.
Nguyên lý cơ bản là: một nút đƣợc lấy ra từ một cấu trúc dữ liệu, các nút con
của nó đƣợc xem xét và bổ sung vào cấu trúc dữ liệu đó. Bằng cách thao tác trên
cấu trúc dữ liệu này, cây tìm kiếm đƣợc duyệt theo các thứ tự khác nhau, chẳng hạn
theo từng mức (tìm kiếm theo chiều rộng) hoặc đi tới một nút lá trƣớc rồi quay lui
(tìm kiếm theo chiều sâu).
15


Tìm kiếm theo chiều rộng (BFS)

Tìm kiếm chiều rộng mang hình ảnh của vết dầu loang. Từ trạng thái ban đầu,
ta xây dựng tập hợp S bao gồm các trạng thái kế tiếp (mà từ trạng thái ban đầu có
thể biến đổi thành). Sau đó, ứng với mỗi trạng thái Tk trong tập S, ta xây dựng tập Sk
bao gồm các trạng thái kế tiếp của Tk rồi lần lƣợt bổ sung các Sk vào S. Quá trình
này cứ lặp lại cho đến lúc S có chứa trạng thái kết thúc hoặc S không thay đổi sau
khi đã bổ sung tất cả Sk.
Tìm kiếm theo chiều sâu (DFS)
Trong tìm kiếm theo chiều sâu, tại trạng thái (đỉnh) hiện hành, ta chọn một
trạng thái kế tiếp (trong tập các trạng thái có thể biến đổi thành từ trạng thái hiện
hành) làm trạng thái hiện hành cho đến lúc trạng thái hiện hành là trạng thái đích.
Trong trƣờng hợp tại trạng thái hiện hành, ta không thể biến đổi thành trạng thái kế
tiếp thì ta sẽ quay lui (Backtracking) lại trạng thái trƣớc trạng thái hiện hành (trạng
thái biến đổi thành trạng thái hiện hành) để chọn đƣờng khác. Nếu ở trạng thái trƣớc
này mà cũng không thể biến đổi đƣợc nữa thì ta quay lui lại trạng thái trƣớc nữa và
cứ thế. Nếu đã quay lui đến trạng thái khởi đầu mà vẫn thất bại thì kết luận là khơng
có lời giải.
Tìm kiếm chiều sâu và tìm kiếm chiều rộng đều là các phƣơng pháp tìm kiếm
có hệ thống và chắc chắn tìm ra lời giải. Tuy nhiên, do bản chất là vét cạn nên với
những bài tốn có khơng gian lớn thì ta khơng thể dùng hai chiến lƣợc này đƣợc.
Hơn nữa, hai chiến lƣợc này đều có tính chất "mù" vì chúng khơng chú ý đến những
thơng tin (tri thức) ở trạng thái hiện thời và thông tin về đích cần đạt tới cùng mối
quan hệ giữa chúng. Các tri thức này vơ cùng quan trọng và rất có ý nghĩa để thiết
kế các giải thuật hiệu quả hơn. Do đó, hai chiến lƣợc trên đƣợc cải tiến thành một số
thuật tốn tìm kiếm mới trên cây bao gồm: tìm kiếm lặp sâu dần, tìm kiếm chiều sâu
giới hạn, tìm kiếm hai chiều và tìm kiếm chi phí đều.
1.3.1.3.

Tìm kiếm trên đồ thị

Nhiều dạng bài tốn tìm kiếm cụ thể trên đồ thị nhƣ: tìm đƣờng đi ngắn nhất,

tìm cây bao trùm nhỏ nhất, tìm bao đóng bắc cầu…Tuy nhiên ứng với mỗi dạng bài
tốn có một số giải thuật tìm kiếm thích hợp để giải quyết. Chẳng hạn thuật toán
16


Dijkstra, thuật toán Kruskal, giải thuật láng giềng gần nhất và giải thuật Prim [8].
Các thuật tốn này có thể đƣợc coi là các mở rộng của các thuật toán tìm kiếm trên
cây: tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng.
Thuật toán Dijkstra là một thuật toán giải quyết bài toán đƣờng đi ngắn nhất
nguồn đơn trong một đồ thị có hƣớng khơng có cạnh mang trọng số âm. Thuật tốn
này có thể tính tốn tất cả các đƣờng đi ngắn nhất từ một đỉnh xuất phát cho trƣớc
tới mọi đỉnh khác mà không làm tăng thời gian chạy.
Thuật toán Kruskal là thuật toán xây dựng cây bao trùm ngắn nhất bằng cách
chọn thêm dần các cung vào cây.
Thuật toán Prim: là thuật toán nhằm xây dựng cây bao trùm ngắn nhất. Tƣ
tƣởng của thuật giải Prim là chọn đƣa dần vào cây T các đỉnh kề “tốt nhất” trong số
các đỉnh còn lại. Thời gian thực hiện giải thuật Prim là O(n2).
1.3.2. Tìm kiếm có thơng tin
Các kỹ thuật tìm kiếm khơng có thơng tin trong một số trƣờng hợp rất kém
hiệu quả và thậm chí khơng áp dụng đƣợc. Để tăng tốc độ của các quá trình tìm
kiếm ta có thể dùng các giải thuật tìm kiếm có thơng tin. Một số chiến lƣợc tìm
kiếm có thơng tin hay cịn gọi là chiến lƣợc tìm kiếm heuristic (tìm kiếm kinh
nghiệm), đó là các phƣơng pháp sử dụng hàm đánh giá để hƣớng dẫn sự tìm kiếm.
Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về
vấn đề để đánh giá các trạng thái của vấn đề. Với mỗi trạng thái u ta xác định một
giá trị số h(u), số này đánh giá “sự gần đích” của trạng thái u. Hàm h(u) đƣợc gọi là
hàm đánh giá. Trong tìm kiếm có thông tin ngƣời ta sử dụng hàm đánh giá này nhƣ
một đánh giá heuristic đặc thù cho bài toán cần giải quyết với vai trị hƣớng dẫn cho
q trình tìm kiếm. Một cách đánh giá heuristic tốt sẽ làm cho q trình tìm kiếm có
thơng tin hoạt động hiệu quả hơn hẳn một phƣơng pháp tìm kiếm khơng có thơng

tin bất kỳ. Trong quá trình tìm kiếm, tại mỗi bƣớc ta sẽ chọn trạng thái để phát triển
là trạng thái có giá trị hàm đánh giá là nhỏ nhất, trạng thái này đƣợc xem là trạng
thái có nhiều hứa hẹn nhất hƣớng tới đích.
Các kỹ thuật tìm kiếm sử dụng hàm đánh giá để hƣớng dẫn sự tìm kiếm đƣợc
gọi chung là các kỹ thuật tìm kiếm có thơng tin hay tìm kiếm kinh nghiệm (tìm
17


kiếm heuristic). Các giai đoạn cơ bản để giải quyết vấn đề bằng tìm kiếm heuristic
nhƣ sau:
 Tìm biểu diễn thích hợp mơ tả các trạng thái và các tốn tử hay phép chuyển
của vấn đề.
 Xây dựng hàm đánh giá.
 Thiết kế chiến lƣợc chọn trạng thái để phát triển ở mỗi bƣớc.
1.4. Bài tốn tối ƣu hóa tổ hợp
Bài tốn tối ƣu hóa tổ hợp (Combinatorial Optimization) liên quan tới việc tìm
giá trị cho các biến số rời rạc nhƣ lời giải tối ƣu mà có lƣu ý tới hàm đánh giá cho
trƣớc. Bài tốn có thể là bài tốn tìm cực đại hoặc tìm cực tiểu. Một cách thơng
thƣờng, bài tốn tối ƣu hố tổ hợp đƣợc cho dƣới dạng bộ ba (S, f, Ω). Trong đó:
 S là tập các lời giải ứng cử viên.
 f là hàm đánh giá (hàm gán giá trị f(s) cho mỗi lời giải ứng viên s S).
 Ω là tập các ràng buộc của bài toán.
Các lời giải thuộc tập S*S thỏa mãn tập các ràng buộc Ω gọi là lời giải khả
thi. Mục tiêu bài tốn là tìm ra một lời giải khả thi tối ƣu toàn cục s*. Với các bài
tốn tối ƣu hóa cực tiểu là tìm lời giải s* với giá nhỏ nhất, nghĩa là f(s*) ≤ f(s) với
mọi lời giải s S. Ngƣợc lại bài tốn tối ƣu hóa cực đại là tìm lời giải s* với giá lớn
nhất, nghĩa là f(s*) ≥ f(s) với mọi lời giải sS. Bài tốn tối ƣu hóa tổ hợp có thể chia
2 loại: Bài tốn tĩnh và bài tốn động.
Bài tốn tối ƣu hóa tổ hợp tĩnh (Static Combinatorial optimization):
Là bài tốn tối ƣu hóa tổ hợp trong đó cấu trúc (Topology) và giá (Cost)

khơng thay đổi khi bài tốn đang đƣợc giải quyết. Ví dụ bài tốn ngƣời du lịch
(TSP). Khi thực hiện thuật toán để giải bài tốn vị trí các thành phố, khoảng cách
giữa các thành phố là không thay đổi.

18


Bài tốn tối ƣu hóa tổ hợp động (Dynamic Combinatorial optimization):
Là bài tốn tối ƣu hóa tổ hợp trong đó cấu trúc và giá có thể thay đổi khi bài
tốn đang đƣợc giải quyết. Ví dụ bài tốn định hƣớng trong mạng viễn thơng, trong
đó mơ hình mạng và dung lƣợng u cầu ln thay đổi.
Lớp bài tốn tối ƣu hóa tổ hợp có những đặc điểm sau:
 Tìm trạng thái tối ƣu cực đại hóa hoặc cực tiểu hóa hàm mục tiêu. Không
quan tâm tới đƣờng đi.
 Không gian trạng thái lớn.
 Không thể sử dụng các phƣơng pháp tìm kiếm thơng thƣờng để xem xét tất
cả khơng gian trạng thái.
 Thuật tốn cho phép tìm lời giải tốt nhất với độ phức tạp tính tốn nhỏ.
Thuật tốn cũng chấp nhận lời giải tƣơng đối tốt.
Tối ƣu hóa tổ hợp là lớp bài tốn có nhiều ứng dụng trên thực tế, một số bài
toán kinh điển trong lớp bài toán này: bài toán ngƣời du lịch, bài toán n-queens, bài
tốn tơ màu đồ thị, bài tốn xếp lịch trực y tá…

19


CHƢƠNG 2: TÌM KIẾM CỤC BỘ
2.1. Tổng quan
Các thuật tốn tìm kiếm thơng thƣờng (tìm kiếm theo chiều sâu, tìm kiếm theo
chiều rộng…) dựa trên việc khảo sát không gian tìm kiếm một cách hệ thống bằng

cách ghi lại những đƣờng đi đã qua cùng với thông tin về phƣơng án đã hoặc chƣa
đƣợc xem xét tại mỗi trạng thái trên đƣờng đi. Vấn đề của thuật toán nhƣ vậy là
việc sử dụng đƣờng đi để khảo sát không gian tìm kiếm một cách hệ thống làm
tăng số lƣợng trạng thái cần xem xét đồng thời đòi hỏi ghi nhớ nhiều trạng thái và
do vậy khơng thích hợp với bài tốn có khơng gian trạng thái lớn.
Tìm kiếm Cục bộ (Local Search – LS) [9] là một hƣớng tiếp cận gần đúng để
tìm lời giải cho các bài tốn tối ƣu hóa tổ hợp (lớp bài tốn có khơng gian trạng thái
lớn). Hƣớng tiếp cận này khơng đảm bảo tìm ra lời giải tối ƣu nhƣng đổi lại, nó có
thể tìm đƣợc lời giải tốt trong thời gian chấp nhận đƣợc. Tìm kiếm Cục bộ xuất phát
từ một lời giải ban đầu (Initial Solution) và liên tục chuyển từ một lời giải (lời giải
hiện tại) sang một lời giải lân cận cho đến khi một điều kiện kết thúc nào đó xảy ra.
2.2. Giải thuật Tìm kiếm Cục bộ
Giải thuật Tìm kiếm Cục bộ là giải pháp Metaheuristic [11] cho việc giải các
bài tốn bài tốn tối ƣu hóa tổ hợp hoặc tối ƣu hóa rời rạc trên máy tính, tức là
những bài tốn trong đó cần tìm trạng thái tối ƣu hoặc tổ hợp tối ƣu trong không
gian rời rạc các trạng thái, và không quan tâm tới đƣờng đi dẫn tới trạng thái đó.
Giải thuật này có thể đƣợc áp dụng cho các bài tốn tìm kiếm lời giải gần đúng tối
ƣu trong một loạt các lời giải ứng viên. Phƣơng pháp tìm kiếm sẽ duyệt qua các lời
giải trong khơng gian tìm kiếm cho đến khi lời tìm ra lời giải đƣợc cho là tối ƣu
hoặc vƣợt quá thời gian tìm kiếm cho phép.
Tìm kiếm cục bộ đƣợc thiết kế cho bài tốn tìm kiếm với khơng gian trạng
thái rất lớn và cho phép tìm kiếm trạng thái tƣơng đối tốt với thời gian tìm kiếm
chấp nhận đƣợc.
Ý tƣởng chung của tìm kiếm cục bộ:
 Chỉ quan tâm đến trạng thái đích, khơng quan tâm đến đƣờng đi.

20


 Mỗi trạng thái tƣơng ứng với một lời giải (chƣa tối ƣu) → cải thiện dần

bằng cách chỉ quan tâm tới một trạng thái hiện thời, sau đó xem xét để để
chuyển sang trạng thái lân cận của trạng thái hiện thời (thƣờng là trạng thái
có hàm mục tiêu tốt hơn).
 Thay đổi trạng thái bằng cách thực hiện các chuyển động (trạng thái nhận
đƣợc từ trạng thái n bằng cách thực hiện các chuyển động đƣợc gọi là lân
cận của n).
Do tìm kiếm cục bộ chỉ quan tâm tới trạng thái hiện thời và lân cận nên cần ít
bộ nhớ hơn nhiều so với các phƣơng pháp tìm kiếm thơng thƣờng. Tìm kiếm cục bộ
thƣờng cho phép tìm đƣợc lời giải chấp nhận đƣợc kể cả khi bài tốn lớn đến mức
khơng dùng đƣợc những phƣơng pháp tìm kiếm thơng thƣờng.
Phát biểu bài tốn: bài tốn tìm kiếm cục bộ đƣợc cho bởi những thành phần
sau:
 Không gian trạng thái X
 Tập chuyển động để sinh ra lân cận.
 Hàm mục tiêu Obj: X → R
 Yêu cầu: tìm trạng thái X* sao cho Obj(X*) là min hoặc max.
Có thể minh họa bài tốn tìm kiếm cục bộ nhƣ Hình 2.1.
 Trục hồnh trên hình vẽ thể hiện không gian các trạng thái (để cho đơn giản,
không gian trạng thái ở đây đƣợc thể hiện trong không gian một chiều dƣới
dạng các điểm trên trục hoành).


Trục tung là độ lớn của hàm mục tiêu.

Yêu cầu bài toán tối ƣu hóa tổ hợp là tìm đƣợc trạng thái (điểm trên trục
hồnh) có hàm mục tiêu lớn nhất. Hình vẽ minh họa trƣờng hợp cần tìm trạng thái
với hàm mục tiêu lớn nhất, tuy nhiên trong một số bài toán khác có thể u cầu tìm
trạng thái với hàm mục tiêu nhỏ nhất.

21



Hình 2.1: bài tốn tìm kiếm cục bộ với khơng gian trạng thái và hàm mục tiêu
2.3. Một số thuật tốn Tìm kiếm Cục bộ cơ bản
2.3.1. Thuật tốn Leo đồi
Leo đồi (Hill climbing) [7] là tên chung để chỉ một họ các thuật toán. Thuật
toán thực hiện bằng cách tạo ra lân cận cho trạng thái hiện thời và di chuyển sang
lân cận có hàm mục tiêu tốt hơn, tức là di chuyển lên cao đối với trƣờng hợp cần
cực đại hóa hàm mục tiêu. Thuật tốn dừng lại khi đạt tới một đỉnh của đồ thị hàm
mục tiêu, tƣơng ứng với trạng thái khơng có lân cận nào tốt hơn. Đỉnh này có thể là
đỉnh cao nhất, hoặc cũng là những đỉnh thấp hơn (Hình 2.1). Trong trƣờng hợp thứ
nhất, thuật tốn tìm đƣợc giá trị cực trị, trong trƣờng hợp thứ hai thuật tốn chỉ tìm
đƣợc cực trị địa phƣơng. Thuật tốn Leo Đồi khơng lƣu lại những trạng thái đã qua,
đồng thời khơng nhìn xa hơn lân cận của trạng thái hiện thời.
2.3.1.1.

Di chuyển sang trạng thái tốt nhất

Có nhiều phiên bản khác nhau của thuật tốn Leo đ ồi. Một trong những
phiên bản thơng dụng nhất có tên là Leo đồi di chuyển sang trạng thái tốt nhất
(Best Improvement Hill Climbing). Phiên bản này của leo đồi lựa chọn trong số lân
cận hiện thời lân cận có hàm mục tiêu tốt nhất. Nếu lân cận đó tốt hơn trạng thái
hiện thời thì di chuyển sang lân cận đó. Nếu ngƣợc lại thì kết thúc và trả về trạng
thái hiện thời. Thuật toán đầy đủ đƣợc thể hiện ở dƣới:
Đầu vào: bài toán tối ƣu tổ hợp
Đầu ra: Trạng thái với hàm mục tiêu lớn nhất (hoặc cực đại địa phƣơng)
22


1. Chọn ngẫu nhiên trạng thái x

2. Gọi Y là tập các trạng thái lân cận của x
3. Nếu yi  Y: Obj (yi) < Obj (x) thì
Kết thúc và trả lại x là kết quả
1. x ← yi , trong đó i = argmaxi (Obj (yi))
2. Chuyển tới bƣớc 2

Đặc điểm của Leo đồi:
 Đơn giản, dễ lập trình, không tốn bộ nhớ do không phải lƣu lại bất kỳ thứ
gì, chỉ lƣu lại trạng thái tạm thời và các lân cận.
 Dễ bị lời giải tối ƣu cục bộ (cực trị địa phƣơng) tƣơng ứng với đỉnh các
“đồi” thấp trong Hình 2.1. Để khắc phục phần nào vấn đề này, thuật toán
đƣợc thực hiện nhiều lần, mỗi lần sử dụng một trạng thái xuất phát sinh
ngẫu nhiên khác với trạng thái xuất phát trong những lần trƣớc đó.
Khi thiết kế thuật toán Leo đ ồi, việc lựa chọn chuyển động rất quan
trọng. Nếu nhiều chuyển động sẽ sinh ra nhiều lân cận, do vậy việc chọn ra lân cận
tốt nhất địi hỏi nhiều thời gian do phải tính hàm mục tiêu cho tất cả lân cận. Ngƣợc
lại, nếu sinh ra tập lân cận nhỏ sẽ dễ dẫn tới cực trị địa phƣơng do không vƣợt qua
đƣợc những “hố” nhỏ trên đƣờng đi.
2.3.1.2.

Leo đồi ngẫu nhiên

Leo dồi ngẫu nhiên (Stochastic Hill Climbing) là một phiên bản khác của
leo đồi. Thay vì tìm ra lân cận tốt nhất, phiên bản này lựa chọn ngẫu nhiên một
lân cận. Nếu lân cận đó tốt hơn trạng thái hiện thời, lân cận đó sẽ đƣợc chọn làm
trạng thái hiện thời và thuật toán lặp lại. Ngƣợc lại, nếu lân cận đƣợc chọn không
tốt hơn, thuật toán sẽ chọn ngẫu nhiên một lân cận khác và so sánh. Thuật toán kết
thúc và trả lại trạng thái hiện thời khi đã quá thời gian. Thông thƣờng, quá thời gian
đƣợc cho bằng số lƣợng tối đa lân cận mà thuật toán xem xét trong mỗi bƣớc lặp
hoặc trong tồn bộ thuật tốn.

Đầu vào: Bài tốn tối ƣu tổ hợp
Đầu ra: Trạng thái với hàm mục tiêu lớn nhất (hoặc cực đại địa phƣơng)
23