..

TRẦN THỊ DƯƠNG

VỀ CÁC BÀI TOÁN NP-C
VÀ MỘT SỐ PHƯƠNG PHÁP GIẢI
Chuyên ngành : Khoa học máy tính
Mã số
: 60480101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2014


1

MỞ ĐẦU
Ngày nay, cùng với sự phát triển mạnh mẽ của khoa học và cơng nghệ,
đặc biệt là máy tính, người ta có khả năng giải quyết được nhiều bài tốn rất
phức tạp.
Tuy nhiên, cịn những vấn đề là ―khơng giải được‖ cho dù kỹ thuật máy
tính có phát triển và cũng có những vấn đề được xem là ―quá phức tạp‖, vượt
mọi khả năng tính tốn thực tế vì mất quá nhiều thời gian. Việc nghiên cứu về
độ phức tạp của thuật toán đã cho phép chúng ta phân loại được các lớp bài
toán theo từng mức độ phức tạp khác nhau, và chỉ ra ranh giới giữa các lớp
bài tốn giải được và những lớp bài tốn khơng thể giải được trong thời gian
đa thức.
Trong lý thuyết độ phức tạp tính tốn, lớp NP - C (NP - đầy đủ) là một
lớp các bài toán quyết định. Một bài tốn L là NP - C nếu nó nằm trong lớp
NP (lời giải cho L có thể được kiểm chứng trong thời gian đa thức) và là NP Hard (mọi bài tốn trong NP đều có thể quy về L trong thời gian đa thức).

Mặc dù bất kì lời giải nào cho mỗi bài tốn đều có thể được kiểm chứng
nhanh chóng, hiện chưa có cách nào tìm ra được lời giải đó một cách hiệu
quả. Thời gian thực thi của tất cả các thuật toán hiện tại cho những bài tốn
này đều tăng rất nhanh theo kích thước bài tốn. Vì vậy ngay cả những trường
hợp có kích thước tương đối lớn đã đòi hỏi thời gian hàng tỷ năm để giải.
Các bài toán lớp NP - C là tập hợp các bài toán NP - Hard trong NP. Các
bài toán lớp NP - C được quan tâm nghiên cứu bởi khả năng kiểm chứng
nhanh chóng lời giải (NP) dường như có liên hệ với khả năng tìm kiếm nhanh
chóng lời giải (P). Hiện vẫn chưa biết được nếu mọi bài tốn trong NP đều có
thể được giải quyết nhanh chóng hay khơng (đây chính là bài tốn P so với


2

NP). Tuy nhiên, nếu bất kì một bài tốn nào trong NP - C có thể được giải
quyết nhanh chóng, thì theo định nghĩa của NP - C, mọi bài tốn trong NP đều
có thể được giải quyết nhanh chóng.
Các bài toán NP- C xuất hiện thường xuyên trong thực tế nên, mặc dù
chưa có giải thuật trong thời gian đa thức cho chúng, các nhà nghiên cứu vẫn
tìm cách giải quyết chúng thông qua các phương pháp khác như thuật tốn
xấp xỉ, thuật tốn gần đúng nhân tử hóa, v.v... Việc tìm hiểu và nghiên cứu
các phương pháp giải bài toán lớp NP- C là một trong những bài tốn
mở của khoa học máy tính hiện nay. Vì vậy em đã chọn đề tài: Về các bài
toán NP-C và một số phương pháp giải để làm luận văn tốt nghiệp.
Cấu trúc của luận văn gồm: Phần mở đầu, phần kết luận và 3 chương nội
dung, cụ thể:
Chương 1: Khái niệm các lớp bài toán P, NP, NP-C.
Trong chương này em giới thiệu chung về các lớp bài toán P, NP, NP –
C, minh họa bằng các ví dụ cụ thể và đưa ra mối quan hệ giữa lớp P, NP và
NP-C

Chương 2: Phương pháp tham và phương pháp nhánh cận giải một số bài
tốn NP-C
Trong chương này em trình bày phương pháp tham giải bài toán về đồ
thị và phương pháp nhánh cận giải bài tốn Ba lơ, bài tốn tìm đường đi ngắn
nhất.
Chương 3: Chương trình thử nghiệm
Chương này thể hiện chương trình cài đặt thuật tốn nhánh cận giải bài tốn
Ba lơ.


3

Chƣơng 1: KHÁI NIỆM CÁC LỚP BÀI TOÁN P, NP, NP – C
1.1. Vài khái niệm cơ bản của lý thuyết độ phức tạp
1.1.1 Máy Turing tất định và không tất định
Máy Turing là một máy tính trừu tượng mơ tả các q trình tính tốn
trên máy tính.
Máy Turing có hai loại: Máy Turing tất định (Deterministic Turing
Machine) và Máy Turing không tất định (Nondeterministic Turing
Machine) được mô tả như sau:
Máy Turing tất định
Mô tả cách làm việc của máy:
Máy Turing tất định gồm một bộ điều khiển hữu hạn trạng thái, một
đầu đọc và ghi, một băng vô hạn được chia thành từng ơ vng, mỗi ơ có
thể lưu giữ một ký hiệu thuộc tập hữu hạn các ký hiệu.

Hình 1.1. Mơ tả máy tính Turing tất định
Khởi đầu, một xâu Input được đặt trên một băng, đó là chuỗi ký hiệu
có chiều dài hữu hạn được chọn từ một bộ chữ cái. Những ơ cịn lại của
băng vơ hạn theo cả hai bên phải và trái, chứa một ký hiệu đặc biệt là ký

hiệu trống ( diễn tả trạng thái ơ khơng có ký hiệu nào).
Có một đầu đọc – ghi luôn chỉ vào một trong các ô của băng. Ta nói
rằng máy Turing đang đọc – ghi ô đó. Lúc khởi hoạt, đầu đọc – ghi nằm


4

tận bên trái của xâu Input.
Một bước hoạt động của máy Turing được quy định bởi một hàm phụ
thuộc trạng thái của bộ điều khiển và ký hiệu đang được đọc chuyển vị.
Trong một bước hoạt động, máy Turing sẽ:
- Thay đổi trạng thái. Trạng thái tiếp theo cũng chính là trạng thái hiện
tại.
- Ghi một ký hiệu băng vào ô đang được quét. Ký hiệu băng này thay
thế ký hiệu băng đang có ở ơ vng đó. Ký hiệu được ghi cũng có thể
chính là ký hiệu hiện đang ở đó.
- Di chuyển đầu đọc – ghi sang trái hoặc sang phải.
Một cách khơng hình thức, ta có thể định nghĩa như sau:
Định nghĩa 1.1 Một máy Turing M tất định là một bộ M = (Q, Σ, Γ, δ,
q0, B, F)
Trong đó các thành phần của M có ý nghĩa như sau:
Q: là tập hữu hạn các trạng thái của bộ điều khiển hữu hạn.
Σ: Tập hữu hạn các chữ cái.
Γ: Tập đầy đủ các kí hiệu băng; Σ luôn là tập con của Γ
: Hàm chuyển vị, : Γ ×Q x {1, 0, 1}.Đối của (q, X) là một trạng
thái q và một kí hiệu băng X. Giá trị của (q, X) nếu được định nghĩa sẽ
là một bộ ba (p, Y, D) trong đó:
p: trạng thái tiếp theo
Y: Một ký hiệu thuộc Γ và sẽ được ghi vào ô đang được quét,
thay thế cho ký hiệu đang ở trong ơ đó.

D: Một trong hai ký hiệu L (sang trái) hoặc R (sang phải) để chỉ
ra hướng di chuyển của đầu đọc – ghi.
q0: Trạng thái bắt đầu, một phần tử Q là trạng thái khởi đầu của bộ điều
khiển.
B: ký tự trắng (blank). B

Γ

F: Tập kiểm hợp các trạng thái kết thúc, một tập con của Q.


5

- Các chức năng và đặc trưng cơ bản của máy Turing tất định:

Ngôn ngữ xác định bởi máy Turing và ngơn ngữ đốn nhận được
Cho M = ( Q, Σ, Γ , δ, q0, B, F) là một máy tính Turing.
Một hình trạng của máy tính Turing M là một từ có dạng aqb, trong
đó a

Γ*, b

Γ*, biểu thị nội dung: trên băng có từ ab, đầu đọc - ghi nhìn

kí tự đầu b và máy ở trạng thái q. Hàm chuyển δ dho ta quy tắc chuyển đổi
các hình trạng. Nếu máy tính Turing M bắt đầu làm việc với hình trạng
q0w (trong đó w

Z*) và chuyển đổi liên tiếp sau một số hữu hạn bước đến


hình trạng kết thúc aFb ở trạng thái chấp nhận F, thì ta nói rằng máy tính
Turing M chấp nhận từ vào w.
Ta ký hiệu LM = {w\ w

Z*, M chấp nhận w).

Định nghĩa 1.2. Ngôn ngữ LM gọi là ngôn ngữ xác định bởi máy
Turing hay cịn gọi là ngơn ngữ tương ứng với của máy tính Turing M.
Định nghĩa 1.3. Cho L là một ngôn ngữ trên bảng chữ cái Σ
Ngơn ngữ L gọi là đốn nhận được bởi máy tính Turing nếu tồn tại M
sao cho LM = L (tức là tồn tại một máy tính Turing sao cho ngơn ngữ tương
ứng của nó trùng với một ngơn ngữ cho trước L).
Ta nói máy tính Turing đốn nhận ngơn ngữ L.
Máy tính Turing khơng tất định
Máy tính Turing tất định là một dạng đặc biệt của máy tính Turing
khơng tất định.

Hình 1.2. Mơ tả máy tính Turing khơng tất định


6

Nhưng máy tính Turing khơng tất định có một hàm chuyển vị

sao

cho mỗi trạng thái q và ký hiệu đọc được (q, X) là một bộ ba {(q1, Y1, D1),
(q2, Y2, D2),… (qk, Yk, Dk), trong đó k là một số ngun hữu hạn nào đó. Tại

mỗi bước máy tính Turing khơng tất định có thể chọn một trong các bộ ba

để thực hiện bước chuyển tiếp theo. Tuy nhiên nó khơng thể lấy một trạng
thái từ một trong các bộ ba này, một ký hiệu băng từ bộ ba khác và một
hướng lại từ bộ ba khác nữa.
So sánh hai định nghĩa trên ta thấy máy tính Turing khơng tất định
được định nghĩa một cách hình thức giống máy tính Turing tất định có
thêm mơđun phỏng đốn, nhằm để có thể chọn bước thực thi kế tiếp tùy ý
trong một tập cho trước các lệnh và có khả năng xử lý song song các
phỏng đoán.
1.1.2 Bài toán quyết định và ngôn ngữ tƣơng ứng
Định nghĩa 1.4 Cho một tập các dữ kiện (instance) và câu hỏi (question)
trên các dữ kiện thuộc tập đó. Bài tốn quyết định là bài tốn mà câu trả lời
của nó là ―Yes‖ hay ―No‖ (tương ứng với True/1 hay False/0)
Sau đây là vài ví dụ minh họa cho bài tốn quyết định:
Ví dụ 1.1: Bài toán kiểm tra số nguyên tố
Instance: một số nguyên n > 2
Question: n có phải số nguyên tố hay khơng?
Ví dụ 1.2: Bài tốn HC ( Hamilton Cycle)
Instance: đồ thị vô hướng G = (V, E)
Question: đồ thị vô hướng G = (V, E) có chu trình Hamilton hay khơng?
Về ngun tắc mọi bài tốn đều có thể biểu diễn lại dưới bài tốn quyết định
tương ứng.
Ngơn ngữ tƣơng ứng với bài toán quyết định:
Giả sử cho một bài toán quyết định π với tập các dữ kiện I được biểu
diễn bởi các xâu trên bảng chữ cái Σ nào đó, và với question Q trên tập


7

I. Ký hiệu L(π) là tập các xâu (thuộc Σ* ) biểu diễn các dữ kiện mà câu
hỏi Q có trả lời “đúng”. Khi đó ta nói ngơn ngữ L(π) là ngơn ngữ tương

ứng với bài tốn π.
2.3.1 Thời gian tính của một máy tính Turing
Cho trước một bài tốn quyết định π với tập các dữ kiện I được biểu
diễn bởi các xâu trên bảng chữ cái Σ nào đó, với câu hỏi Q trên tập I. Ký
hiệu L(π) là tập các xâu (thuộc Z* ) biểu diễn các dữ kiện của một instance
cụ thể của bài toán π. Ta biết rằng ngôn ngữ L(π) là một ngôn ngữ tương
ứng với bài toán π. Với mỗi instance I cụ thể, ta sẽ có một input biểu diễn
nó, mà ta ký hiệu là x(I). Bây giờ ta có thể biểu diễn thời gian tính của bài
tốn π đối với một máy tính Turing cho trước. Với một input x(I)

L(π),

máy tính sẽ chạy cho đến lúc dừng tại trạng thái ―Yes/No‖. Thời gian tính
x(I) sẽ là số bước đốn nhận xâu x(I) của máy cho tới khi máy dừng lại.
Thông thường số bước chạy máy này phụ thuộc vào I, và tất nhiên là một
hàm số của độ dài biểu diễn I, tức là độ dài của xâu x(I).
Bằng cách đó ta định nghĩa: TM(n):= max{m: tồn tại một xâu x

Z*

với |x| = n mà thời gian đoán nhận xâu là m}
Một máy tính Turing (hay một chương trình tính tốn trên cơ sở máy
tính Turing) được nói là có thời gian tính tốn đa thức (gọi tắt là thời gian
đa thức) nếu như tồn tại một đa thức p(n) sao cho mọi số tự nhiên n ta có
TM(n) ≤ p(n). Khi đó ta cũng nói rằng chương trình máy tính Turing có độ
phức tạp tính tốn khơng vượt q p(n).
1.1.4. Lớp P, NP và mối quan hệ giữa lớp P và lớp NP
Định nghĩa l.5 ( Lớp P - Polynomial time)
Ta gọi lớp P là lớp những bài toán quyết định giải được bằng máy tính
Turing tất định trong thời gian đa thức.



8

Một bài toán quyết định π là giải được trong thời gian đa thức, nếu
ngôn ngữ L(π) tương ứng với nó thuộc lớp P, tức nó đốn nhận được trong
thời gian đa thức.
Như vậy, lớp P gần như tương ứng với lớp các bài toán quyết định giải
được trong thời gian đa thức, về mặt lý thuyết, có thể xem là lớp các bài tốn
dễ.
Ví dụ 1.3: Bài tốn kiểm tra số nguyên tố
Instance: một số nguyên n > 2
Question: n có phải là số ngun tố hay khơng?
Ví dụ 1.4: Thuật tốn Kruskal tìm cây khung bé nhất của một đồ thị có
m nút và e cạnh.
Instance: một đồ thị có m nút và e cạnh
Question: tìm cây khung bé nhất?
Định nghĩa l.6 ( Lớp NP - Nondeterministic Polynomial)
Ta gọi lớp NP là lớp các bài toán quyết định có thể giải được bằng máy
tính Turing khơng tất định trong khoảng thời gian đa thức.
Một cách khơng hình thức, chúng ta nói một ngơn ngữ L thuộc lớp NP
nếu có một máy tính Turing khơng tất định và một độ phức tạp thời gian T(n)
sao cho L = LM và khi M được cho nguyên liệu có chiều dài n thì khơng có
dãy bước chuyển nào của M vượt q T(n) bước chuyển.

Ví dụ 1.5: Bài tốn chu trình Hamilton
Instance: đồ thị vô hướng G = (V, E)
Question: đồ thị vơ hướng G = (V, E) có chu trình Hamilton hay không?



9

Để nói về mối quan hệ giữa lớp P và lớp NP ta thấy do máy tính Turing
tất định là trường hợp đặc biệt của máy tính Turing khơng tất định nên các bài
toán thuộc lớp P sẽ thuộc lớp NP.
Tuy P

NP là rất hiển nhiên song ta vẫn chưa biết P = NP hay không,

nhưng hầu hết các nhà nghiên cứu đều tin rằng P

NP. Từ đó ta có mơ hình

mơ phỏng sau:

NP

P

Hình 1.3 Mối quan hệ giữa lớp P và NP
1.1.5 Phép dẫn với thời gian đa thức (Polynomial Time Reduction)
Giả sử ta muốn giải quyết bài toán π1 ( trong đó π1: I1 —> {Yes/ No})
mà ta có thuật tốn cho bài tốn π2 (trong đó π2: I2 —> {Yes/ No}, giả sử ta
có hàm f: I1 —> I2 mà dữ kiện x của π1 sinh ra dữ kiện f(x) cho π2 sao cho
câu trả lời đúng cho π1 trên x là ―Yes‖ nếu và chỉ nếu câu trả lời đúng cho π2
trên f(x) là ―Yes‖ và ngược lại, thì ta có thể sử dụng thuật tốn cho π2 để giải
quyết bài toán π1.
Định nghĩa 1.7
Cho π1 và π2 là hai bài toán quyết định, πi (Y) là lớp các Instance ứng
với YES, πi (N) là lớp các Instance ứng với No.



10

Một cách biến đối f biến mỗi Instance của π1 thành Instance của π2 được
gọi là phép dẫn thời gian đa thức nếu nó thỏa mãn:
- Phép dẫn f thực hiện được trong thời gian đa thức bởi máy tính
Turing.
- Mỗi dữ kiện π1 (Y) thành dữ kiện thuộc π2 (Y)
- Mỗi dữ kiện π1 (N) thành dữ kiện thuộc π2 (N)

Thuật tốn π1
Dữ
kiện
π1

f(x)
Thuật tốn π2

f
Dữ kiện π2

Yes/No

Hình 1.4 Một phép dẫn bài toán π1 thành π2 trong thời gian đa thức
Có thể phát biểu bằng lời như sau: nếu bài tốn π1 có thể dẫn được về
bài tốn π2 trong thời gian đa thức, và giải được bài toán π2 trong thời gian đa
thức, thì ta sẽ giải được bài toán π1 trong thời gian đa thức. Theo nghĩa thời
gian đa thức thì bài tốn π2 khó hơn hoặc bằng bài toán π1 .
Địnhnghĩa 1.8 f là phép dẫn đa thức từ π1 về π2

1. f có thể được tính trong thời gian đa thức.
2. Với dữ kiện đầu vào x cho bài toán π1 câu trả lời đúng cho bài
toán π2 trên f (x) là giống như câu trả lời đúng cho π1 trên x.
Định nghĩa 1.9 Bài toán quyết định π1 dẫn về bài toán quyết định π2


11

trong thời gian đa thức, nếu tồn tại một phép dẫn với thời gian đa thức từ π1 về
π2.
Ta viết π1 π2
Định lý 1.1 Nếu π1

π2 và π2 P thì π1 P (và tương tự nếu π2 P thì π1

P).
Ví dụ 1.4 Bài tốn chu trình Hamilton:
Instance: đồ thi vơ hướng G = (V, E)
Question: đồ thị vô hướng G = (V, E) có chu trình Hamilton hay khơng?
Ví dụ 1.5 Bài toán Traveling Salesman ( người bán hàng ):
Instance: n thành phố C ={ C1, C2, ..., Cn} với d (Ci, Cj) là khoảng cách
giữa hai thành phố Ci vàCj. Một giới hạn W

Z+ (Z+ là tập các số ngun

dương).
Question: Người bán hàng có đi một vịng khắp các thành phố và quay
về thành phố ban đầu với tổng độ dài không vuợi quá W hay không ? Tức là
có tồn tại hốn vị π trên {1, 2, .., n} sao cho:
+ d (cπ (i), cπ (i-1))


W?

Ta sẽ chỉ ra bài tốn chu trình Hamilton dẫn về bài tốn người bán hàng:
cho trước đồ thị G = (V, E) gồm m đỉnh, phép biến đổi f là phép nối thêm các
cạnh (x, y) cho hai đỉnh không kề nhau x, y trong G và gán trọng số cho các
cạnh có sẵn của đồ thị bằng 1 và trọng số các cạnh được nối thêm là 2. Đồ thị
thu được , ký hiệu là f(G). Ta chọn W = m.
Dễ dàng thấy G có chu trình Hamilton khi và chỉ khi f(G) có một chu
trình Hamilton với tổng trọng số các cạnh bằng m.
Giới hạn W đối với độ dài tuyến đường mong muốn là một bộ bằng m.
Ta thấy rằng phép dẫn f này có thể tính được bởi một thuật toán thời gian đa


12

thức. Với mỗi trọng số:

các khoảng cách d(v1, v2) mà phải cụ thể

hóa, thì cần thiết kiểm tra G để xem {(v1, v2} có phải là một cạnh của E hay
khơng?
Như vậy tính chất thứ nhất của u cầu được thỏa mãn.
Để chứng minh yêu cầu thứ hai được thỏa mãn, chúng ta phải chỉ ra rằng
G có chứa chu trình Hamilton khi và chỉ khi có tuyến đường đi qua tất cả các
thành phố trong hàm f (G) mà có tổng độ dài tuyến đường

W.

Trước tiên, giả sử (v1, v2..., vm) là một chu trình Hamilton cho G sau đó

(v1, v2..., vm) cũng là một tuyến đường trong f(G) và tuyến đường này có tổng
độ dài m = W, bởi vì mỗi khoảng cách giữa các thành phố tương đương với
một cạnh đồ thị G và như vậy có độ dài từ 1( từ đỉnh này đến đỉnh kia có cạnh
nối trực tiếp).
Ngược lại, giả sử (v1, v2..., vm) là tuyến đường trong f(G) với tổng độ
dài nhỏ hơn hoặc bằng W. Do bất kỳ hai thành phố hoặc là có đường đi trực
tiếp hoặc là gián tiếp và độ dài giữa m thành phố như vậy được cộng lại để
tính độ dài của tuyến đường. Thực tế W = m cho biết mỗi cặp các thành phố
đã đi qua là khoảng cách trực tiếp. Với định nghĩa:
f (G)  {vi, vi+1,} (trong đó i

là các cá các cạnh của đồ thị G.

Chính vì thế (v1, v2..., vm) là một chu trình Hamilton cho đồ thị G.
Như vậy, ta đã chỉ được rằng bài tốn chu trình Hamilton dẫn được về
bài toán người bán hàng. Tuy rằng chứng minh này đơn giản nhưng nó chứa
tồn bộ những yếu tố cần thiết cho phép dẫn với thời gian đa thức và từ đó ta
có thể sử dụng một dạng về cách thức cấu trúc những bằng chứng như vậy.
Ý nghĩa cho định lý l.1 cho các bài toán quyết định giờ đây có thể được
minh họa dưới dạng dưới bài tốn chu trình Hamilton và bài tốn người bán
hàng, và ta có thể kết luận rằng nếu người bán hàng có thể được giải quyết


13

bằng một thuật tốn trong thời gian đa thức thì chu trình Hamilton cũng được
giải quyết trong thời gian đa thức.
Ngược lại, nếu bài tốn chu trình Hamilton là bài tốn khơng giải quyết
được trong thời gian đa thức thì bài toán người bán hàng cũng như vậy.


1.2. Các bài toán NP-C trong lý thuyết đồ thị, trong quy hoạch
nguyên
Trong lý thuyết độ phức tạp tính tốn, lớp NP-C là một lớp các bài toán
quyết định. Lớp NP-C được quan tâm nghiên cứu bởi khả năng kiểm chứng
nhanh chóng lời giải (NP) dường như có liên hệ với khả năng tìm kiếm nhanh
chóng lời giải (P). Hiện vẫn chưa biết được nếu mọi bài tốn trong NP đều có
thể được giải quyết nhanh chóng hay khơng. Tuy nhiên, nếu bất kì một bài
tốn nào trong NP-C có thể được giải quyết nhanh chóng, thì theo định nghĩa
của NP-C, mọi bài tốn trong NP đều có thể được giải quyết nhanh chóng.
1.2.1 Lịch sử lớp các bài tốn NP - C
Khái niệm NP- C được đưa ra bởi Stephen Cook năm 1971 trong bài báo
mang tên "The complexity of theorem-proving procedures".Tuy nhiên tên gọi
NP- C không xuất hiện trong bài báo này mà được đưa ra sau này. Trong đó
Cook đã chứng minh định lý Cook-Levin (Leonid Levin cũng chứng minh
định lý này một cách độc lập cùng thời gian với Cook). Định lý này chứng
minh bài toán Circuit-SAT là NP-C. Năm 1972, Richard Karp chứng minh 21
bài toán khác cũng là NP-C. Từ sau đó đến nay, hàng nghìn bài toán đã được
chứng minh là NP-C. Nhiều bài toán quan trọng trong số đó được liệt kê trong
cuốn "Computers and Intractability: A Guide to the Theory of NPCompleteness" của Garey và Johnson.
1.2.2 Bài toán lớp NP-C (Nondeterministic Polynomial -Complete)


14

Người ta đã chứng minh được rằng trong lớp NP có những bài tốn khó
hơn bất kì bài tốn nào khác trong lớp này, tức là nếu có thuật tốn thời gian
đa thức để giải một bài tốn nào đó trong số chúng thì cũng có thuật tốn thời
gian đa thức để giải mọi bài toán trong lớp NP. Những bài toán như vậy được
gọi là NP - Complete (NP-C).
Định nghĩa 1.10 Một bài toán thuộc lớp NP mà mọi bài tốn thuộc lớp

NP khác đều dẫn được về nó với thời gian đa thức được gọi là bài tốn
NP-C.
Ví dụ 1.6: Bài tốn Satisfiability problem hay cịn được gọi là bài toán
SAT.
Bài toán SAT là các biểu thức Boole được xây dựng từ:
Các biến mang giá trị Boole; nghĩa là chúng nhận một trong hai giá trị:
giá trị 1(đúng) hoặc 0 (sai).
- Các tốn tử hai ngơi kí hiệu ^ (cho phép AND) và kí hiệu (cho phép
OR).
- Các tốn tử một ngơi ký hiệu

(đại diện cho phép Not).

- Các dấu ngoặc ( ) để nhóm các tốn tử và tốn hạng nhằm mục đích là
thay đổi độ ưu tiên của các toán tử.
- Bài toán SAT được phát biểu như sau:
Cho một biểu thức Boole, tồn tại hay không phép các biến cho giá trị
đúng / sai (T/F) để biểu thức nhận giá trị đúng (T)?
Bài toán SAT được phát biểu dưới dạng bài toán quyết định như sau:
Instance: Cho trước một tập hợp A các tục biến ( là các biến hoặc phủ
định của nó).
Trong đó, một tục biến là một tập hợp các biến hoặc phủ định của nó
chẳng hạn (v1, v4,

,v6)


15

Question: Tồn tại hay không một phép gán giá trị các biến sao cho tất cả

các tục biến của A đều có ít nhất một giá trị True
Bài tốn SAT là bài toán đầu tiên được chứng minh là thuộc bài toán
NPC
Từ định nghĩa ta thấy một bài toán

là NP-C nếu nó thoả mãn đồng thời

hai điều kiện sau:
1.

NP

2.

Với

’ thuộc NP thì ’ dẫn được về

với thời gian đa

thức.
Như vậy để chứng minh một bài toán

là NP-C ta cần chứng minh hai

điều:
1.

Bài toán


phải thuộc lớp NP

2.

Mọi hai toán thuộc lớp NP đều dẫn được về bài toàn

với

phép dẫn thời gian đa thức.
Định lý 1.2. Nếu bài toán P1 là NP-C, P2 là NP và có một phép thu thời
gian đa thức từ P1 về P2 thì P2 cũng là NP-C.
Chứng minh:
Ta cần chứng tỏ rằng mỗi ngôn ngữ L thuộc NP đều thu được P2 trong
thời gian đa thức. Khi đó theo định nghĩa P2 sẽ thuộc NP-C.
Vì P1 là NP-C nên có một phép thu đa thức L về P1. Giả sử thời gian
của phép thu này là p(n). Vì thế có một chuỗi W
biến đổi thành một chuỗi x

L có chiều dài n được

P1 có chiều dài tối đa là p(n). Biết rằng có

một phép thu thời gian đa thức từ P1 về P2 .
Giả sử thời gian của phép thu này là q(m) thì phép thu này biến đổi
chuỗi x

P1

về một chuỗi y nào đó thuộc P2 với thời gian tối đa là


q(p(n)). Vì thế phép biến đổi W

L về y

P2 mất thời gian tối đa là p(n) +


16

q(p(n)). Đây cũng là một đa thức. Vậy có thể kết luận rằng L có thể thu về
P2 trong thời gian đa thức, tức là P2 cũng là NP-C.
Định lý 1.3. Nếu có một bài tốn nào đó là NP-C mà lại thuộc lớp P thì
ta có P=NP.
Chứng minh: Giả sử có bài tốn Q

NP-C và Q

P thì mọi ngơn ngữ L

trong NP đề thu được về Q trong thời gian đa thức. Nếu Q
Như vậy NP

P. Kết hợp với điều hiển nhiên P

P thì L

P.

NP ta được P = NP.


Ví dụ 1.7: Tập độc lập (Independent Set)
Cho G là một đồ thị vơ hướng. Ta nói tập con I của các đỉnh thuộc G
là một tập độc lập nếu khơng có 2 đỉnh nào của I được nối bởi một cạnh của
G (tức là I là tập các đỉnh mà khơng có 2 đỉnh nào là liền kề nhau). Một tập
độc lập là cực đại nếu nó có nhiều nút nhất trong số các tập độc lập.
Đồ thị trong hình 1.5 có tập độc lập gồm các đỉnh {1, 4}. Đó cũng là tập độc
lập cực đại.
1

2

3

4

1

1

Hình 1.5 Ví dụ về tập độc lập

Bài toán:

Cho một đồ thị G. Tìm tập độc lập cực đại.

Giống như mọi bài tốn trong lý thuyết các bài toán nan giải, ta sẽ
phát biểu bài toán trong dạng Yes/No. Để làm việc này ta đưa thêm một
cận dưới vào phát biểu của bài toán và diễn tả lại câu hỏi là: đồ thị đã cho có
một tập độc lập tối thiểu bằng với cận đó hay khơng.
Bài tốn: Tập độc lập hay IS (Independent Set).



17

Instance: Một đồ thị G và một cận dưới k, 1 k

n, n là số đỉnh của G.

Question: Yes nếu và chỉ nếu G có một tập độc lập gồm k đỉnh.
Định lý 1.4. Bài toán tập độc lập là NP-C
Chứng minh:
Trước tiên dễ thấy rằng bài toán IS

NP.

Cho trước đồ thị G = (V, E) và một cận k. Đốn thử k nút và kiểm tra
chúng độc lập (có nhiều khả năng chọn k nút nên bài toán là NP).
Tìm cách thu bài tốn 3SAT về IS.
Gọi

E = (e1)(e2)...(em) là một biểu thức 3-CNF. Ta xây dựng từ E

đồ thị G có 3m nút mà ta sẽ đặt tên là [i, j] với 1

I

m; j = 1, 2, 3. Nút [i, j]

biểu diễn nguyên đề (literal) thứ j trong phân đề (clause) ei.
Ví dụ 1.8.


Bài tốn phủ đỉnh (vertex cover)

Phủ đỉnh của một đồ thị là tập các đỉnh sao cho mỗi cạnh liên thuộc với
ít nhất một đỉnh thuộc tập này.
Bài tốn đặt ra là tìm phủ đỉnh bé nhất.
Bài toán phủ đỉnh và bài toán tập độc lập liên quan chặt chẽ với nhau:
Bù của một tập độc lập là một phủ đỉnh và ngược lại.
Thí dụ Trong đồ thị trên bù của phủ đỉnh là tập các đỉnh
{2, 4}. Hai đỉnh này độc lập nhau.
1

2

3

6

5

4

1

1

Hình 1.6. Thí dụ về phủ đỉnh


18


Chúng ta sẽ phát biểu bài toán phủ định dưới dạng bài toán quyết định
Yes/No:
Cho một đồ thị

G và một số k : 0 < k < /v/ 1.

Hỏi: ? Phủ đỉnh với số đỉnh

k.

Định lý 1.5 . Bài toán phủ đỉnh là NP-C.
Chứng minh:
a) Rõ ràng bài toán phủ đỉnh thuộc NP: Lấy một tập k đỉnh và kiểm tra
xem đó có phải là phủ đỉnh hay khơng tức là mỗi cạnh bất kỳ của G có một
đầu nằm trong tập đó.
b) Quy dẫn bài tốn tập độc lập về bài toán phủ đỉnh. Trước hết nhận
xét rằng bù của một tập độc lập là một phủ đỉnh. Chẳng hạn trong hình 3.8
tập các nút khơng tơ màu đỏ tạo thành một phủ đỉnh. Vì các nút đỏ là tập
độc lập cực đại nên các nút còn lại tạo thành một phủ đỉnh cực tiểu.
Xây dựng phép quy dẫn: Gọi G với một cận dưới k là một thể hiện của
bài tốn tập độc lập. Nếu G có n nút, gọi G với cận trên n k là một thể hiện
của bài toán phủ đỉnh. Phép biến đổi này có thể thực hiện được trong thời
gian tuyến tính.
Ta khẳng định rằng:
G có tập độc lập kích thước k G có một phủ đỉnh kích thước n k.
Chứng minh:
• Đủ: Gọi N là tập các nút của G và C là phủ đỉnh với kích thước n k.
Ta chứng minh: N\ C là một tập độc lập. Giả sử không phải, nghĩa là tồn tại
cặp đỉnh v, w N\ C sao cho có cạnh nối chúng thuộc G. Thế thì, vì v, w C, cạnh

(v, w) G khơng được phủ bởi C. Mâu thuẫn. Như vậy N \ C là tập độc lập với k
nút.
• Cần: Giả sử I là tập độc lập có k nút. Ta sẽ chứng minh rằng
N \ I là một phủ đỉnh có n k nút. Ta cũng chứng minh bằng phản chứng. Giả


19

sử N \ I không phải là phủ đỉnh. Khi đó tồn tại một cạnh (v, w) khơng được
phủ bởi N\ I, tức là cả v, w N \ I v, w I. Mâu thuẫn vì I là tập độc lập.
1.2.3 Một số bài tốn NP-C khác
Q trình khám phá các bài tốn thuộc loại NP-C cho biết rằng có rất ít
cơ hội phát triển được một thuật tốn hiệu quả để giải nó. Và để giải các bài
tốn NP-C đó thường dùng các phương pháp tìm kiếm các heuristic, các lời
giải từng phần, các xấp xỉ và những cách khác nhằm tránh giải trực diện bài
toán.
Mọi bài toán NP-C đều đòi hỏi thời gian mũ để giải. Sau đây là một số
ví dụ về bài tốn NP-C.
Ví dụ 1.9 Bài tốn tơ màu đồ thị (Graph k-colorability, k 3)
Instance: Đồ thị

G = (V, E), số nguyên dương k.

Question: Có cách tô k màu cho các đỉnh của G hay không, tức là tồn
tại hay không một hàm f : V

{1, 2, ..., k} sao cho nếu (u, v)

E thì f (u) ≠ f (v).


Người ta đã chứng minh được rằng bài toán Graph 2- color giải được
trong thời gian đa thức, cịn tất cả các bài tốn Graph k-color với k

3 đều

là NP-C.
Ví dụ 1.10: Bài tốn Hamilton Cycle
Bài tốn chu trình Hamilton là bài tốn đi xác định xem với một đồ thị G
= (V, E) cho trước có chứa một chu trình Hamilton (chu trình đơn chứa mọi
đỉnh của G). Bài toán được phát biểu dưới dạng bài toán quyết định như sau:
Instance: Cho đồ thị G = (V, E).
Question: G có chứa một chu trình đơn đi qua mọi đỉnh hay khơng?
Ví dụ 1.11. Bài tốn ba lô (knapsack problem) nguyên


20

Giả sử có một cái ba lơ có thể chứa được trọng lượng C (nguyên
dương) và n loại đồ vật có trọng lượng s1, s2, ..., sn tương ứng và giá trị sử
dụng là p1, p2, ..., pn tương ứng. Các số si, pi đều là nguyên dương. Bài
toán được phát biểu dưới dạng bài toán quyết định như sau:
Instance: Cho số K.
Question: Tồn tại hay không tập hợp con các đồ vật chứa vào ba lô
sao cho tổng giá trị sử dụng
phân x = (x1, x2, ..., xn), xi

K, cụ thể là có tồn tại hay khơng một bộ n số nhị
{0, 1} sao cho n

n


K

xi p i
i 1
n

xi s i

W

i 1

Ví dụ 1.12 Maximum cut problem
Dữ kiện: Cho G = (V, E). Ký hiệu dij là độ dài của cạnh từ đỉnh i đến
đỉnh j (cạnh eij

E).

Câu hỏi: Tìm phân hoạch V thành A và B: A
sao cho Σ dij

B = V, A

max

i A
j B

Ví dụ 1.13. Subset-sum

Dữ kiện: Các số tự nhiên C1, C2, ..., Cn, K.
Câu hỏi: Tồn tại hay không

S {1, 2, ..., n} sao cho

Σ Ci = K
i S

Ví dụ 1.14. Bất đẳng thức tuyến tính nguyên
Dữ kiện: Ma trận nguyên A Z m x n, vector b Zm.
Câu hỏi: Tồn tại hay không x

Zn thỏa mãn Ax b.

B=∅


21

Sau đây là các định lí NP- C, nó cũng là điểm then chốt của việc quyết
định P thực tế có bằng với NP hay khơng?
Định lý 1.6 Nếu bài toán

1

là NPC, bài toán

dẫn với thời gian đa thức từ bài tốn

1


về bài tốn

2
2

là NP và có một phép
thì bài tốn

2

cũng là

bài tốn NP-C.
Định lý 1.7 Nếu có một bài toán NP-C bất kỳ giải được theo thời gian
đa thức, thì P = NP. Nếu một bài tốn trong NP bất kỳ khơng giải được theo
thời gian đa thức, thì tất cả các bài tốn NP-C đều khơng giải được theo thời
gian đa thức.
1.2.3 Mối quan hệ giữa các bài tốn lớp P, NP, và NPC
Nếu có một giải thuật trong thời gian đa thức cho một bài toán NPC, vậy
thì chứng minh được P = NP. Tuy nhiên cho đến nay chưa có một thuật tốn
thời gian đa thức nào để giải cho bài tốn NPC. Chính vì lý do này mà cuộc
nghiên cứu vào câu hỏi P ≠ NP tập trung vào các bài toán NPC. Hầu hết các
nhà khoa học máy tính lý thuyết đều tin rằng khả năng P ≠ NP rất có thể xảy
ra, do đó NPC

P = . Mối quan hệ giữa lớp P, NP và NP-C có thể biểu diễn

như hình sau:


NP

P

NP-C

Hình 1.7 Mối quan hệ giữa lớp P, NP và NP-C


22

Chƣơng 2: PHƢƠNG PHÁP THAM VÀ PHƢƠNG PHÁP NHÁNH
CẬN GIẢI MỘT SỐ BÀI TỐN NP-C

2.1. Thuật tốn xấp xỉ
2.1.1. Giới thiệu chung về thuật tốn xấp xỉ
Việc tìm nghiệm của các bài tốn NP-C với kích cỡ đầu vào n tương
đối lớn là rất khó khăn, thường là khơng khả thi vì độ phức tạp có thể nói là
hàm mũ. Đây là những bài tốn nan giải hay cịn gọi là bất trị. Vì thế thay
cho việc tìm lời giải đúng (lời giải tối ưu) người ta phải tìm nghiệm gần
đúng (lời giải gần tối ưu) mà có thể chấp nhận được.
Trong khoa học máy tính , thuật tốn xấp xỉ là các thuật tốn tìm lời giải
xấp xỉ cho các bài tốn tối ưu hóa. Thuật tốn xấp xỉ thường được sử dụng cho
các bài toán NP-C, hoặc các bài toán giải được trong thời gian đa thức nhưng
quá chậm cho dữ liệu lớn.
Nhiều bài tốn NP-C có thể được biểu diễn dưới dạng quy hoạch
nguyên và giải trong thời gian lũy thừa. Nhiều thuật toán xấp xỉ xuất phát từ
việc nới lỏng điều kiện nguyên và đưa về giải bài tốn quy hoạch tuyến tính,
quy hoạch xác định khơng âm,quy hoạch lồi tương ứng.
2.1.2 Một số thuật tốn xấp xỉ

* Bài toán phủ đỉnh bé nhất (thuộc NP-C)
Input: Đồ thị vô hướng G = (V, E).
Output: Phủ đỉnh bé nhất.
Thuật toán gần tối ưu: Procedure ApproxVertexCover
C := Ø{C là tập phủ đỉnh gần tối ưu}
E := Tập các cạnh của G
While E = Ø do


23

Chọn (u, v) là một cạnh bất kỳ
C := C  {u, v} {kết nạp 2 đỉnh u, v vào phủ đỉnh C}
Loại bỏ khỏi E cạnh uv và mọi cạnh liên thuộc với u hoặc v
End do
Return(C)
* Giải thuật tham lam giải các bài tốn tối ƣu hóa thuộc
loại NP-C
Giải thuật tham lam là một heuristic. GrA (Greedy Algorithm) khơng
phải ln ln cho lời giải tối ưu. Thường nó chỉ cho lời giải gần tối ưu.
Khi nó cho lời giải tối ưu thì việc chứng minh tính đúng đắn của thuật tốn
cũng khơng đơn giản.
Để mơ tả chính xác GrA cần mơ tả chính xác mơi trường trong đó các
bài toán tối ưu đặt ra. Trong các bài toán tối ưu trong ngữ cảnh GrA người
ta có:
- Tập (danh sách) các ứng viên, thí dụ, các nút, các cạnh trong đồ thị.
- Tập các ứng viên đã sử dụng.
- Một cách (predicate/solution) để kiểm tra liệu một tập các ứng viên đã
cho có lời giải (khơng nhất thiết là tối ưu) hay không?
- Một hàm lựa chọn (selection function) để chọn các ứng viên chưa

được sử dụng.
- Hàm mục tiêu gán giá trị cho các lời giải.
* Heuristic đối với bài toán phủ đỉnh
Bài toán: Cho đồ thị G = (V, E). Tìm tập đỉnh C nhỏ nhất phủ G theo
nghĩa nếu cạnh uv E

u

Thuật toán tham lam:
Input: Đồ thị G = (V, E).

C hoặc v C.


24

Output: Phủ C của G gần với phủ nhỏ nhất.
begin
C := Ø;
while E
Chọn trong

Ø do
V đỉnh có bậc cao nhất, loại nó ra khỏi G và bổ sung vào C.

End;
Vì mục đích của ta là phủ tất cả các cạnh của G bởi số ít đỉnh nhất nên
chiến lược chọn trên mỗi bước một đỉnh phủ được nhiều cạnh nhất là hồn
tồn chấp nhận được. Tất nhiên vì bài tốn là NP-C nên không hy vọng là
thuật giải này hiệu quả để đạt được tập phủ đỉnh bé nhất. Câu hỏi là tập đỉnh

tìm được gần với tập đỉnh tối ưu đến mức nào?

Áp dụng giải thuật trên cho đồ thị sau:

c1

c2

C1

b2

b1

a1

c4

c3

b3

a2

c5

b4

b5


a3

Hình 2.1 Đồ thị về bài tốn phủ đỉnh
Đầu tiên chọn một trong các đỉnh a1, a2 hoặc a3 có bậc bằng 5. Giả sử ta
chọn a1, a2 rồi a3. Cuối cùng là c1, c2, c3, c4 và c5. Như vậy phủ đỉnh gồm 8