---
title: Homework XVI
---
# P1
[CLRS 3rd] Exercise 34.2-6
- [ ] [name=民]
## Topic
A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Show that the language HAM-PATH={⟨G,u,v⟩:there is a hamiltonian path from u to v in graph G} belongs to NP.
## Solution
為了證明找到DAG上的HAM-PATH屬於$\text{NP}$, 要找到一個polynomial-time的驗證演算法
符合以下條件者為hamiltonian path:
1. 路徑為n個相異點 O(n)
2. 路徑中相鄰點在DAG裡有邊連結 O(n+m)
3. 路徑頭尾為u, v O(1)

在O(n+m)時間內可以驗證一條路徑是否為hamiltonian path, 因此找到DAG上的HAM-PATH屬於$\text{NP}$

# P2
[CLRS 3rd] Exercise 34.5-1
- [ ] [name=文]
## Topic
The subgraph-isomorphism problem takes two undirected graphs $G_1$ and $G_2$, and it asks whether $G_1$ is isomorphic to a subgraph of $G_2$. Show that the subgraphisomorphism problem is NP-complete.
## Solution
**首先需要先證明subgraph-isomorphism problem為NP問題 :**
利用$G_1$單射$G_2$的方式來檢查$G_1$與$G_2$是否為同構，因此是符合多項式時間(符合NP)
**證明subgraph-isomorphism problem為NP-complete :**
藉由證明CLIQUE $\le_\text{P}$ Subgraph-isomorphism problem來得證
為了檢查$G_2$是否包含了大小為k的clique，先假設$G_1$是有k個vertex的compelete graph，再檢查$G_1$ 和 subgraph of $G_2$是否為同構。
因為clique problem為NP-complete，故subgraph-isomorphism problem亦為NP-complete

# P3
[CLRS 3rd] Exercise 34.5-2
- [ ] [name=Joe_Wang]
## Topic
Given an integer m×n matrix A and an integer m-vector b, the 0-1 integerprogramming problem asks whether there exists an integer n-vector x with elements in the set {0,1} such that $Ax≤b$. Prove that 0-1 integer programming is NP-complete. (Hint: Reduce from 3-CNF-SAT.)
## Solution
證明3-CNF-SAT$\le_p$此問題，即可證明為NPC
Proof:
For each i，$0\le x_i\le1$，這樣可以確保x值為0-1，
然後將$(x_1 \lor x_2 \lor -x_3)$表示成$x_1+x_2+(1-x_3)\ge1$，
就可以證明$3-CNF-SAT \le_p 0-1\ integer\ programming$。

# P4
- [ ] [name=天]
## Topic
根據slide Unit12 P.19，畫出此頁TSP問題的三個版本（BFS、DFS、Best First Search）。
## Solution
### BFS

共74個node
### DFS

共50個node
### Best First Search

共27個node
# P5
- [ ] [name=昱]
## Topic
根據slide Unit12 P.13，請設計演算法，只使用一維陣列解出SOS(Sum of subset) 問題(Combining DP & Backtracking)，得到一組解即可。
## Solution
用DP解SOS若只需要最後結果, 可以只使用一維陣列紀錄答案
用Backtracking可以避免每次迭代K次
理想是如下圖只需要填少部份的表

SOS(S, K) // S is a array of integers in descending order, K is the target number
    a[K+1] = {0}
    a[0] = 1
    n = S.length()
    for i = 0 to n
        for j = K to 0 //O(min(K,2^n))
            if j < S[i] // 數字大於上限
                break
            if a[j] == 1 or a[j-S[i]] == 1
                a[j] = 1
            
    if a[K] != 0
        i = n - 1
        while K>0 // O(K+n)
            if S[i] <= K and a[K-S[i]] == 1
                print(S[i])
                K = K-S[i]
            i -= 1
    else
        print "Nope"

時間複雜度: O(n min(K,$2^n$))