Lớp P
Thuật toán có độ phức tạp O(f(n)) nếu với mọi bộ số liệu có độ dài n, số
phép tính phải thực hiện không quá C*f(n), với C >0.
Thuật toán có độ phức tạp O(p(n)), với p(n) là một đa thức, gọi là có độ
phức tạp đa thức.
Định nghĩa:
P là lớp các bài toán được giải với thời gian đa thức.
Chú ý:
Không phải mọi bài toán thuộc lớp P đã có thuật toán hiệu quả.
Nếu bài toán không thuộc lớp P thì đều phải trả giá rất đắt về thời gian
hoặc thậm chí không giải được nó trong thực tế.
28 trang |
Chia sẻ: thanhle95 | Lượt xem: 744 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng NP - Complete, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
NP - Complete
2013-11-25 2
Một số bài toán tối ưu rời rạc
Bài toán người du lịch:
Cho n điểm trên mặt phẳng (thành phố), giữa hai thành phố bất kỳ
được xác định một thông số là chi phí đi lại. Một hành trình là một
cách đi xuất phát từ một thành phố nào đó, qua n thành phố và quay
về nơi xuất phát.
OP (Optimization Problem): Tìm hành trình * có tổng chi phí bé nhất.
DP (Decision Problem): Có tồn tại một hành trình với chi phí D?
2013-11-25 3
Một số bài toán tối ưu rời rạc
Bài toán tô màu đồ thị:
Cho đồ thị G ={V,E}.
OP: Số màu ít nhất để tô đồ thị G?
DP: Cho số nguyên K. Có tồn tại hay không cách tô màu đồ thị
G với số màu không quá K?
Một cách tô màu đồ thị là một phương án gán cho mỗi đỉnh một màu, sao
cho hai đỉnh liền kề có hai màu khác nhau.
2013-11-25 4
Một số bài toán tối ưu rời rạc
Bài toán cái túi:
Cho n đồ vật với kích thước là các số nguyên s1, s2, ..., sn và các túi
với kích thức là số nguyên T.
OP: Tìm số túi ít nhất để xếp các đồ vật.
DP: Cho số nguyên K. Có tồn tại cách xếp các đồ vật vào không quá K
túi với sức chứa T?
2013-11-25 5
Một số bài toán tối ưu rời rạc
Bài toán tập con:
Cho số nguyên dương T và tập X gồm n số nguyên dương a1, a2, ..., an.
OP: Xác định tập con của X sao cho tổng của chúng gần nhất và không
quá T.
DP: Có tồn tại tập con sao cho tổng kích thước đúng bằng T.
2013-11-25 6
Một số bài toán tối ưu rời rạc
Bài toán phân công công việc:
Giả thiết có n công việc:
Mỗi thời điểm chỉ thực hiện một công việc,
Thời gian thực hiện t1, t2, ..., tn,
Thời hạn hoàn thành d1, d2, ..., dn (tính từ khi bắt đầu công việc đầu tiên),
Mức phạt đối với mỗi công việc bị chậm là p1, p2, ..., pn.
Phân công công việc là một hoán vị của tập J={1, 2,..., n}: J(1), J(2), ..., J(n).
Tổng giá trị phạt của phân công :
OP: Tìm lịch sắp xếp công việc có giá trị hàm phạt thấp nhất P() min.
DP: Cho trước k, xác định lịch có mức phạt không quá k: P() k.
n
j
jjj pdttP
1
)()()()1( 0elsethen...if
2013-11-25 7
Lớp P
Thuật toán có độ phức tạp O(f(n)) nếu với mọi bộ số liệu có độ dài n, số
phép tính phải thực hiện không quá C*f(n), với C >0.
Thuật toán có độ phức tạp O(p(n)), với p(n) là một đa thức, gọi là có độ
phức tạp đa thức.
Định nghĩa:
P là lớp các bài toán được giải với thời gian đa thức.
Chú ý:
Không phải mọi bài toán thuộc lớp P đã có thuật toán hiệu quả.
Nếu bài toán không thuộc lớp P thì đều phải trả giá rất đắt về thời gian
hoặc thậm chí không giải được nó trong thực tế.
2013-11-25 8
Lớp NP (Nondeterministic Polynomial)
NP là lớp các bài toán quyết định mà việc kiểm tra lời giải đối
với dữ liệu vào được thực hiện với thời gian đa thức.
2013-11-25 9
Lớp NP (Nondeterministic Polynomial)
Thuật toán bất định (nondeterministic algorithm):
Pha bất định:
Một xâu kí tự S bất kỳ được sinh ra trong bộ nhớ, có thể coi như
lời giải đề nghị.
Pha tiền định:
Đọc dữ liệu vào (S có thể bị bỏ qua). Thuật toán có thể kết thúc với
khẳng định “Yes”, “No”, hoặc rơi vào vòng lặp không dừng.
Có thể coi là pha kiểm tra lời giải đề nghị S.
NP là lớp bài toán giải được bằng thuật toán bất định với
thời gian đa thức (nondeterministic polynomial bouded).
Thuật toán bất định là đa thức nếu tồn tại đa thức p sao cho với mỗi dữ liệu vào có kích
thước n và có trả lời “yes” với tính toán của thuật toán là đa thức.
2013-11-25 10
Lớp NP
Ví dụ:
đồ thị có 5 đinh, 8 cạnh và k =4:
V ={1, 2, 3, 4, 5},
E={(1,2), (1,4), (2,4), (2,3), (3,5), (2,5), (3,4), (4,5)}
Kí hiệu: R (Red), B (Blue), G (Green), O (Orange),
Y (Yellow).
1
2
4
3
5
Dùng 4 màu, các cặp đỉnh kề khác màuYesRGRBY
Dùng tới 5 màuNoRBYGO
Đỉnh 5 không được tô màuNoRGRB
Đỉnh 2 và 5 cùng màuNoRGRBG
ReasonOutputS
2013-11-25 11
Lớp P vs. NP
Hiển nhiên: P NP
NP \ P = ?
(NP P?)
P
Sắp xếp
Cây khung bé nhất
Nhân ma trận
Tìm kiếm tuần tự
Đường đi ngắn nhất
...
NP
Bài toán cái túi
Bài toán ba lô
Bài toán người du lịch
2013-11-25 12
NP-đầy đủ (NP-complete)
Hiển nhiên: P NP.
Nhưng: NP \ P = ?
Chứng minh được:
Trong NP có những bài toán khó không
kém bất cứ bài toán nào khác trong NP.
A NP: nếu có một thuật toán đa thức
nào giải được A thì với mọi bài toán B
NP đều có thuật toán đa thức để giải B.
Bài toán A được gọi là NP-đầy đủ.
Nói cách khác, A NP được gọi là NP-
đầy đủ nếu A P thì suy ra P=NP.
P
Sắp xếp
Cây khung bé nhất
Nhân ma trận
Tìm kiếm tuần tự
Đường đi ngắn nhất
...
NP
Bài toán cái túi
Bài toán ba lô
Bài toán người
du lịch
2013-11-25 13
NP-đầy đủ (NP-complete)
Hiển nhiên: P NP.
Nhưng: NP \ P = ?
Chứng minh được:
1. Nếu NP ≠ P thì có bài
toán thuộc NP nhưng
không thuộc P và cũng
không phải NP-đầy đủ.
2. Nhiều bài toán là NP-đầy
đủ.
P
Sắp xếp
Cây khung bé nhất
Nhân ma trận
Tìm kiếm tuần tự
Đường đi ngắn nhất
...
NP-
đầy
đủ
NP
2013-11-25 14
NP-đầy đủ (NP-complete)
Như vậy, để chỉ ra một bài toán nào đó là NP-đầy đủ cần chỉ ra
rằng:
Tồn tại một thuật toán đa thức bất định để giải nó (tức là chỉ ra nó
thuộc lớp NP);
Có một bài toán NP-đầy đủ dẫn về nó.
P
Sắp xếp
Cây khung bé
nhất
Nhân ma trận
Tìm kiếm tuần tự
Đường đi ngắn
nhất
...
NP-
đầy
đủ
NP
2013-11-25 15
NP-đầy đủ (NP-complete)
Giả thiết cần giải bài toán A và có thuật toán giải bài toán B.
Giả sử có ánh xạ T chuyển mỗi dữ liệu vào x của bài toán A thành dữ liệu
vào T(x) của bài toán B
T: x T(x)
sao cho:
Lời giải y của bài toán A với dữ liệu vào x
tương ứng với
Lời giải z của bài toán B với dữ liệu vào T(x)
(nếu y là ”yes” thì z cũng là ”yes”).
Thuật toán giải bài toán A = {Ánh xạ T + Thuật toán giải B}
2013-11-25 16
Bài toán CNF-SAT
Mô tả:
1) Biến logic nhận một trong hai giá trị: true hoặc false. Kí hiệu a là biến
logic, là phủ định của a. Nếu a nhận giá trị true thì nhận giá trị false và
ngược lại, nếu a nhạn giá trị false thì nhận giá trị true. Một tên biến là
một biến logic hoặc phủ định của biến logic (cũng là một biến logic).
2) Một mệnh đề là một dãy các tên biến được xen kẽ bới phép toán logic
OR ().
3) Một biểu thức logic trong dạng liên kết chuẩn (conjunction nomal form -
CNF) là một dãy các mệnh đề được kết nối bới phép toán AND ().
Bài toán quyết định:
Khi các biến nhận giá trị true hoặc false, biểu thức có nhận giá trị true hay
không?
2013-11-25 17
Bài toán CNF-SAT
Định lý Cook:
Bài toán CNF-SAT là NP-đầy đủ
Cần chỉ ra rằng bất kỳ bài toán NP nào (A) cũng dẫn chuyển
về CNF-SAT:
Cần xây dựng ánh xạ T dẫn chuyển input x của bài
toán A về một biểu thức logic.
Lời giải của bài toán quyết định A trùng với giá trị
true hoặc false của CNF-SAT.
2013-11-25 18
Bài toán CNF-SAT
Định lý Cook:
Bài toán CNF-SAT là NP-đầy đủ
x
dữ liệu
vào
của A
“yes”
hoặc
“no”
T(x)
T
CNF-SAT
Algorithm for A
2013-11-25 19
Bài toán CNF-SAT
Ví dụ: Xét bài toán 3-CG:
Đồ thị G ={V,E} như hình vẽ
có tô được bằng 3 màu?
a
db
c
Chuyển dẫn bài toán 3-CG về bài toán CNF-SAT?
2013-11-25 20
Bài toán CNF-SAT
u1
u4u3
u2
Ký hiệu: xkj – đỉnh k tô bởi màu j
Xét 32 mệnh đề:
C(k) = {xk1, xk2, xk3}, đỉnh k được tô bởi ít nhất 1 màu
A(k) = {xk1, xk2,}, đỉnh k không cùng được tô màu 1 và 2
B(k) = {xk2, xk3}, đỉnh k không cùng được tô màu 2 và 3
C(k) = {xk1, xk3}, đỉnh k không cùng được tô màu 1 và 3
k = a, b, c, d
M = C(a) & ..&C(d)&A(a)&..&A(d)&B(a)&..&B(d)&C(a)&..&C(d)
M = true nếu mỗi đỉnh được tô bởi đúng 1 trong ba màu {1, 2, 3}
2013-11-25 21
Bài toán CNF-SAT
u1
u4u3
u2
Ký hiệu: e=(u,v) E, u,v V
D(e,j) ={ xuj, xvj } - đỉnh u và v không cùng tô bởi màu j
N = D((u1,u2),1)&D((u1,u3),1)&D((u1,u4),1)& D((u2,u3),1)&D((u2,u4),1)&D((u3,u4),1)
&...&
D((u1,u2),3)&D((u1,u3),3)&D((u1,u4),3)& D((u2,u3),3)&D((u2,u4),3)&D((u3,u4),3)
N = true nếu hai đỉnh không được tô bởi cùng 1 trong ba màu {1, 2, 3}
G là đồ thị 3 màu chỉ
khi M&N có giá trị
true.
2013-11-25 22
NP-đầy đủ
Ví dụ 2: Bài toán tổng tập con
chuyển dẫn được về bài toán
lập lịch
Cho số nguyên dương T và tập n số nguyên dương
X={ a1, a2, ..., an}
Tìm tập con của X sao cho tổng của chúng gần nhất với T.
n công việc: J1, J2, ..., Jn;
thời gian thực hiện: t1, t2, ..., tn;
thời hạn hoàn thành (từ khi bắt đầu dự án): d1, d2, ..., dn
mức phạt chậm quá thời hạn: p1, p2, ..., pn.
Mỗi thời điểm chỉ thực hiện một công việc.
Phân công công việc : {1, 2,..., n} {(1), (2),..., (n)}
Thứ tự thực hiện: J(1), J(2),...,J(n).
Tổng giá trị phạt của phân công trên là
n
j
jjj pdttP
1
)()()()1( 0elsethen...if
2013-11-25 23
NP-đầy đủ
Ví dụ 2: Bài toán tổng tập con
chuyển dẫn được về bài toán
lập lịch
Nếu
i=1,..,nsi < T
bài toán tập con không có lời giải.
Có thể chuyển dẫn phương án thành bất kỳ dữ liệu vào cho
bài toán phân công công việc mà không có lời giải.
Ví dụ:
ti= 2, di = pi = 1, với i = 1, 2, ..., n.
and k=0.
(Bài toán quyết định:
Có tồn tại một tập con sao cho tổng đúng bằng T?
Có tồn tại một lịch công tác mà tổng giá trị phạt P k ?.)
2013-11-25 24
NP-đầy đủ
Ví dụ 2: Bài toán tổng tập con
chuyển dẫn được về bài toán
lập lịch
Xét trường hợp i=1,..,nsi T
Đặt ti = si,
di = T,
pi = si, với i = 1, ..., n và
k = i=1,..,nsi T.
Giả sử J NS = {1, 2,...,n}
iJsi = T
Đặt:
: J { 1, 2, ..., |J|},
: NS\J { |J|+1,...,n},
Ttss
J
i
i
J
i
i
Ji
i
||
1
)(
||
1
)( ||...,,2,1,
1
)( JjTt
j
i
i
Các công việc từ |J|+1 cho đến n đều quá hạn, giá trị phạt:
kTssssp
n
i
i
Ji
i
n
i
i
n
Ji
i
n
Ji
i
111||
)(
1||
)(
2013-11-25 25
NP-đầy đủ
Ví dụ 2: Bài toán tổng tập con
chuyển dẫn được về bài toán
lập lịch
Ngược lại: giả sử là một phân công công việc với mức phạt
không quá k. Kí hiệu m là số nguyên lớn nhất thoả mãn:
Tt
m
i
i
1
)(
Tskp
n
mi
n
i
ii
1 1
)(Giá trị phạt:
TssTss
n
mi
i
m
i
i
n
i
i
n
mi
i
1
)(
1
)(
11
)(
m
i
isT
1
)(
Ts
m
i
i
1
)(
Vậy
s(1), s(2), ..., s(m)
là lời giải bài toán tổng
tập con.
2013-11-25 26
NP-đầy đủ
Sơ đồ chứng minh A là bài toán NP-đầy đủ:
Chỉ ra rằng A thuộc lớp NP;
Chọn bài toán NP-đầy đủ nào đó, ví dụ là B và chuyển dẫn B về A
Thật vậy:
A là NP-đầy đủ nếu
A thuộc lớp NP và
mọi bài toán X thuộc lớp NP có XA.
B là NP-đầy đủ nên mọi bài toán C trong
NP:
CB
Do BA,
suy ra CA.
Nghĩa là mọi bài toán C trong NP đều
chuyển dẫn về A được.
2013-11-25 27
NP-đầy đủ
1) Thông thường, việc chỉ ra rằng một bài toán A nào
đó thuộc lớp NP là khó (phải chỉ ra được thuật
toán bất định giải nó trong thời gian đa thức).
2) Việc tìm được bài toán NP-đầy đủ để chuyển dẫn
về A xem ra có thể đơn giản hơn.
Việc chuyển dẫn được chứng tỏ nó có độ khó tương
đương với bài toán NP-đầy đủ. Những bài toán
như vậy gọi là NP-khó.
2013-11-25 28
Remark
Bài toán tìm đường đường đi ngắn nhất nối hai đỉnh của đồ thị liên
thông có trọng số có thuật toán hiệu quả để giải. Tuy nhiên, bài
toán tìm đường đi dài nhất nối hai đỉnh là bài toán NP-đầy đủ.
Bài toán xác định đồ thị G-2 màu khá đơn giản. Tuy nhiên, bài toán
kiểm tra G-3 màu lại là NP-đầy đủ.
Cho đồ thị có hướng G={V,E}, số nguyên k, tập con E’ E thoả mãn
|E’|k. E’ có chứa cạnh của các chu trình trong G? Bài toán này
được chứng mình là NP-đầy đủ, tuy nhiên nếu xét bài toán này với
đồ thị vô hướng, nó lại thuộc lớp P.