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
này đều tăng rất nhanh theo kích thước bài toá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 toán trong NP đều có
thể được giải quyết nhanh chóng hay không (đây chính là bài toán P so với
2
NP). Tuy nhiên, nếu bất kì một bài toá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 toá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 toán
xấp xỉ, thuật toá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 toá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
toá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ề đồ
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ó ở ô vuông đó. 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, Σ,
Γ
, δ,
q
0
,
Γ
, δ, q
0
, 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
q
0
w (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 L
M
= {w\ w Z
*
, Y
1,
D
1
),
(q
2
, Y
2,
D
2
),… (q
k
, Y
k,
D
k
), trong đó k là một số nguyên 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 đoá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)
ứ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
toá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 đoá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: T
M
(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 toán trên cơ sở máy
tính Turing) được nói là có thời gian tính toá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ó
T
M
(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 toán không vượt quá 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
Để 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:
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
: I
1
—> {Yes/ No})
mà ta có thuật toán cho bài toán π
2
(trong đó π
2
: I
2
—> {Yes/ No}, giả sử ta
i
(N) là lớp các Instance ứng với No. NP
P
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)
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
Thuật toán π
1
Dữ
kiện
π
1
Dữ kiện π
2
f
f(x)
Thuật toán π
2
Yes/No
11
Ví dụ 1.5 Bài toán Traveling Salesman ( người bán hàng ):
Instance: n thành phố C ={ C
1
, C
2
, , C
n
} với d (C
i
, C
j
) là khoảng cách
giữa hai thành phố C
i
vàC
j
. Một giới hạn W Z
+
(Z
+
là tập các số nguyên
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 hoán vị π trên {1, 2, , n} sao cho:
+ d (c
π (i)
, c
π (i-1)
) W?
1
, v
2
, v
m
) là một chu trình Hamilton cho G sau đó
(v
1
, v
2
, v
m
) 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ử (v
1
, v
2
, v
m
) 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) {v
i
, v
chóng lời giải (P). Hiện vẫn chưa biết được nếu mọi bài toá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
toá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 toá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 toá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 NP-
Completeness" 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 toán khó
hơn bất kì bài toán nào khác trong lớp này, tức là nếu có thuật toán thời gian
đa thức để giải một bài toán nào đó trong số chúng thì cũng có thuật toá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 toá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 toán
NP-C.
Ví dụ 1.6: Bài toán Satisfiability problem hay còn được gọi là bài toán
SAT.
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 P
1
là
NP-C, P
2
là
NP và có một phép thu thời
gian đa thức từ P
1
về P
2
thì P
2
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 P
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ề
P
2
trong thời gian đa thức, tức là P
2
cũng
là NP-C.
Định lý 1.3. Nếu có một bài toá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 toá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 P thì L P.
Như vậy NP P. Kết hợp với điều hiển nhiên 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.
Gọi E = (e
1
)(e
2
) (e
m
) 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) e
i
.
Ví dụ 1.8. Bài toá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 toá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.
Hình 1.6. Thí dụ về phủ đỉnh
1
6
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 toán NP-C khác
Quá trình khám phá các bài toá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 toán hiệu quả để giải nó. Và để giải các bài
toá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 toán NP-C.
Ví dụ 1.9 Bài toán tô màu đồ thị (Graph k-colorability, k 3)
Instance: Đồ thị G = (V, E), số nguyên dương k.
tương ứng. Các số s
i
, p
i
đề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 K, cụ thể là có tồn tại hay không một bộ n số nhị
phân x = (x
1
, x
2
, , x
n
), x
i
{0, 1} sao cho n
i
n
i
i
px
1
K
i
n
i
= 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 Z
m
.
Câu hỏi: Tồn tại hay không x Z
n
thỏa mãn Ax 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
2
là NP và có một phép
dẫn với thời gian đa thức từ bài toán
1
về bài toán
2
thì bài toán
2
cũng là
bài toán 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 TOÁN NP-C
2.1. Thuật toán xấp xỉ
2.1.1. Giới thiệu chung về thuật toán xấp xỉ
Việc tìm nghiệm của các bài toá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 toá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 toán xấp xỉ là các thuật toán tìm lời giải
xấp xỉ cho các bài toán tối ưu hóa. Thuật toá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 toá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 toá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 toá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
Thuật toán tham lam:
Input: Đồ thị G = (V, E).
24
Output: Phủ C của G gần với phủ nhỏ nhất.
begin
C := Ø;
while E Ø do
Chọn trong 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à hoàn
toàn chấp nhận được. Tất nhiên vì bài toá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:
c
2
c
3
c
4
c
5
b
2
b
3
b
4
b
5
b
1
a
1
a
2
a
3
Hình 2.1 Đồ thị về bài toán phủ đỉnh
Copyright: Tài liệu đại học ©