判定問(wèn)題和優(yōu)化問(wèn)題
- 判定問(wèn)題：是否存在一個(gè)...(如小于k的點(diǎn)覆蓋)
- 優(yōu)化問(wèn)題：找出最大/最小的...(最小點(diǎn)覆蓋)
因?yàn)镹PC問(wèn)題的答案是簡(jiǎn)單的“是”或“否”（存在或不存在），不適合直接應(yīng)用于最優(yōu)化問(wèn)題，但適合用于判定問(wèn)題。
盡管證明一個(gè)問(wèn)題是NP完全問(wèn)題會(huì)讓我們的目光局限在判定問(wèn)題。但我們可以利用最優(yōu)化和判定問(wèn)題之間存在的關(guān)系，對(duì)優(yōu)化的值強(qiáng)加一個(gè)界，就可以將一個(gè)給定的最優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)相關(guān)的判定問(wèn)題了。這就是自身規(guī)約。
自身規(guī)約就是將求解（最優(yōu)化）問(wèn)題規(guī)約到一個(gè)判斷問(wèn)題上。
自身規(guī)約練習(xí)
Ⅰ. 如果存在一個(gè)多項(xiàng)式時(shí)間算法判斷一個(gè)圖是否存在一個(gè)長(zhǎng)度為k的路徑，則存在一個(gè)多項(xiàng)式時(shí)間算法要么找到圖中一個(gè)長(zhǎng)度為k的路徑要么證明此圖不存在長(zhǎng)度為k的路徑
pf.
假設(shè)存在判斷一個(gè)圖G是否存在一個(gè)長(zhǎng)度為k的路徑的多項(xiàng)式時(shí)間算法A。
首先用它判斷圖G是否存在一個(gè)長(zhǎng)度為k的路徑，若不存在，則結(jié)束；若存在，則在圖中刪除一條邊e，再用A判斷圖G=(V, E-e)中是否存在長(zhǎng)度為k的一條路徑。
若存在，則將該邊從圖中徹底刪除；若不存在，則保留這條邊（或者把該邊加入這個(gè)路徑的邊集合中）。
重復(fù)上述操作，直到圖中剩下的就是長(zhǎng)度為k的一條路徑。
Ⅱ.如果能在多項(xiàng)式時(shí)間內(nèi)判斷一個(gè)圖是否存在一個(gè)長(zhǎng)度至少為k的路徑，那么就可以在多項(xiàng)式時(shí)間內(nèi)找到這個(gè)圖的一條最長(zhǎng)路徑
pf.
假設(shè)判斷出圖G=(V, E)，存在一個(gè)長(zhǎng)度至少為k的路徑。然后依次加一，直到找出最長(zhǎng)路徑kmax。
則選取任一邊e，在圖G=(V, E-e)中判斷是否還存在一條長(zhǎng)度至少為kmax的路徑。
若存在，則在圖中刪除該邊；若不存在，則保留該邊（最長(zhǎng)路徑經(jīng)過(guò)的邊e）。
對(duì)所有邊進(jìn)行上述操作，最終圖中剩下的就是這條最長(zhǎng)路徑。
解題步驟
- 設(shè)該判斷算法為A，假設(shè)判斷出圖中存在...（大小為k的...）
- 刪除一條邊（或點(diǎn)，看具體是邊集還是點(diǎn)集的問(wèn)題），對(duì)刪除邊（點(diǎn)）后的圖運(yùn)行判斷算法A
- 若圖中還存在...（大小為k的...），則從圖中徹底刪除該邊（點(diǎn)）；若不存在，保留該邊（點(diǎn)）
- 對(duì)所有的邊（點(diǎn)）調(diào)用算法A執(zhí)行上述操作，最終剩下的就是...（大小為k的...）
