ผลต่างระหว่างรุ่นของ "ผู้ใช้:Chatchapol"
Chatchapol (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== '''204512-53/lecture13''' == '''จดบันทึกคำบรรยายโดย:''' นายชัชพล นุโย…') |
Chatchapol (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 2: | แถว 2: | ||
'''จดบันทึกคำบรรยายโดย:''' | '''จดบันทึกคำบรรยายโดย:''' | ||
นายชัชพล นุโยค รหัส 5214550049 | นายชัชพล นุโยค รหัส 5214550049 | ||
| − | นายสุรเดช วัฒนอุดมโรจน์ รหัส | + | นายสุรเดช วัฒนอุดมโรจน์ รหัส 5214550324 |
---- | ---- | ||
| − | ''' | + | ''' NP Completeness ''' |
---- | ---- | ||
| − | + | NP: Non-deterministic Polynomial time คือ เซตของ Algorithm ที่ไม่สามารถแก้ไขปัญหาได้ในเวลาที่เป็น polynomial โดยการนิยามเซตของปัญหาเพื่อประโยชน์ในการเปรียบเทียบระดับความยาก-ง่ายของ Algorithm ซึ่งเซตของปัญหาสามารถแบ่งเป็นเซต P, NP, NP-hard และ NP-complete | |
| − | + | ในการเปรียบเทียบ Algorithm ใดๆ เราจะทำการพิจารณา Algorithm ว่าจัดอยู่ในเซตของปัญหาใด โดยใช้เทคนิคการลดรูปของปัญหา (Reduction) ว่าเป็นกลุ่มเดียวกับปัญหาที่อยู่ในเซตหรือไม่ ถ้าอยู่ในกลุ่มเดียวกันจะกล่าวว่า Algorithm มีความยากเท่ากัน ความยาก คือ มี Algorithm ที่มีประสิทธิภาพแก้ไขปัญหาหรือไม่ | |
| − | '''Lemma''' : พิจารณาเซต | + | ปัญหา A สัมพันธ์ ปัญหา B |
| + | |||
| + | ปัญหา A ไม่ยากไปกว่า ปัญหา B | ||
| + | |||
| + | ปัญหา A [[ไฟล์:NPComplete7.gif]] ปัญหา B | ||
| + | |||
| + | โดยมีความหมายว่า ถ้ามี Algorithm ที่สามารถแก้ปัญหา B ได้ ปัญหา A ก็จะสามารถแก้ได้เช่นกัน | ||
| + | |||
| + | ---- | ||
| + | |||
| + | '''ปัญหาที่ 1''' : Independent Set เป็นปัญหากลุ่ม Decision Problem | ||
| + | |||
| + | '''นิยาม''' : ให้ Undirected graph G = (V, E) จะกล่าวว่า I [[ไฟล์:NPComplete1.gif]] V เป็น Independent Set ก็ต่อเมื่อ สำหรับทุกๆโหนด | ||
| + | U,V [[ไฟล์:NPComplete1.gif]] I, U [[ไฟล์:NPComplete5.gif]] V ไม่มีเส้นเชื่อมระหว่าง U และ V | ||
| + | |||
| + | '''ปัญหา''' : ให้กราฟ G = (V, E) และ integer k, มี Independent set ขนาด ≥ k หรือไม่ | ||
| + | |||
| + | [[ไฟล์:NPComplete8.gif]] | ||
| + | |||
| + | ในภาพทำการเลือกโหนด (k) เท่ากับ 1 จะกล่าวว่ามี Independent set ขนาด 1 | ||
| + | |||
| + | สามารถนำไปใช้แก้ปัญหา หาคนที่ไม่รู้จักกันในห้อง หรือ การเปิด-ปิดไฟแดงที่แยก | ||
| + | |||
| + | ---- | ||
| + | |||
| + | '''ปัญหาที่ 2''' : Vertex Cover | ||
| + | |||
| + | '''นิยาม''' : C [[ไฟล์:NPComplete1.gif]] V เป็น Vertex Cover ก็ต่อเมื่อ [[ไฟล์:NPComplete4.gif]](U,V)[[ไฟล์:NPComplete6.gif]] E,U [[ไฟล์:NPComplete6.gif]] C หรือ V [[ไฟล์:NPComplete6.gif]] C | ||
| + | |||
| + | '''ปัญหา''' : ให้กราฟ G = (V, E) และ จำนวนเต็ม k ถามว่ามี vertex cover ขนาด ≤ k หรือไม่ | ||
| + | |||
| + | [[ไฟล์:NPComplete9.gif]] | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ถ้าสมมติให้ Independent Set [[ไฟล์:NPComplete7.gif]] Vertex Cover | ||
| + | |||
| + | '''Lemma''' : พิจารณาเซต [[ไฟล์:NPComplete1.gif]] ใดๆ ให้ A เป็น imdenpendent set โดย V-A เป็น Vertec Cover | ||
| + | |||
| + | '''Proof''' : Indenpendent set [[ไฟล์:NPComplete2.gif]]Vertex Cover | ||
| + | |||
| + | '''นิยาม''' : ปัญหา A เป็น Polynomial time เพื่อลดปัญหา B ถ้ามี Algorithm T ที่ทำงานใน Polynomial time สำหรับทุกๆ instance X ของ A จะได้ T(x) เป็น instance ของ B | ||
| + | |||
| + | [[ไฟล์:NPComplete3.gif]] | ||
| + | |||
| + | X' = T(x) เป็น instance ของ B และ |X'| = Poly (|X|) | ||
| + | ถ้า x เป็น instance ตอบ "Yes" ใน A | ||
| + | => x' เป็น instance ตอบ "Yes" ใน B | ||
| + | |||
| + | ถ้า x เป็น instance ตอบ "No" ใน A | ||
| + | => x' เป็น instance ตอบ "No" ใน B | ||
| + | |||
| + | '''Lemma''' : ถ้า A [[ไฟล์:NPComplete2.gif]]B และมี Algorithm ที่แก้ปัญหา B ได้ใน Polynomial time จะมี Algorithm ที่แก้ปัญหา A ใน Polynomial time ได้ด้วย | ||
| + | |||
| + | '''Proof''' : ให้ M เป็น Polynomial time Algorithm ที่แก้ปัญหา B | ||
| + | จะได้ว่า A [[ไฟล์:NPComplete2.gif]] B | ||
| + | นั้นคือ มี Polynomial time Algorithm T ที่ [[ไฟล์:NPComplete4.gif]]instance x ของ A | ||
| + | x' = T(x) มีขนาด poly(|x|) และคำตอบของ x ในปัญหา A ตรงกับของ x' ในปัญหา B | ||
| + | |||
| + | สำหรับ Algorithm M' ดังนี้ | ||
| + | |||
| + | M'(x) : | ||
| + | x' = T(x) | ||
| + | return M(x') | ||
| + | |||
| + | |||
| + | แต่เนื่องจาก |x'| = poly(|x|) | ||
| + | ดังนั้น เวลาในการคำนวณ M(x')คือ poly(|x'|) = poly(poly(|x|)) = poly(|x|) | ||
| + | |||
| + | จากนิยาม M'(x) เป็นคำตอบของ x ใน A เหลือแต่ต้องตรวจสอบว่า M' ทำงานใน Polynomial time หรือ poly(|x|) | ||
| + | |||
| + | |||
| + | ---- | ||
รุ่นแก้ไขปัจจุบันเมื่อ 19:14, 4 ตุลาคม 2553
204512-53/lecture13
จดบันทึกคำบรรยายโดย:
นายชัชพล นุโยค รหัส 5214550049 นายสุรเดช วัฒนอุดมโรจน์ รหัส 5214550324
NP Completeness
NP: Non-deterministic Polynomial time คือ เซตของ Algorithm ที่ไม่สามารถแก้ไขปัญหาได้ในเวลาที่เป็น polynomial โดยการนิยามเซตของปัญหาเพื่อประโยชน์ในการเปรียบเทียบระดับความยาก-ง่ายของ Algorithm ซึ่งเซตของปัญหาสามารถแบ่งเป็นเซต P, NP, NP-hard และ NP-complete
ในการเปรียบเทียบ Algorithm ใดๆ เราจะทำการพิจารณา Algorithm ว่าจัดอยู่ในเซตของปัญหาใด โดยใช้เทคนิคการลดรูปของปัญหา (Reduction) ว่าเป็นกลุ่มเดียวกับปัญหาที่อยู่ในเซตหรือไม่ ถ้าอยู่ในกลุ่มเดียวกันจะกล่าวว่า Algorithm มีความยากเท่ากัน ความยาก คือ มี Algorithm ที่มีประสิทธิภาพแก้ไขปัญหาหรือไม่
ปัญหา A สัมพันธ์ ปัญหา B
ปัญหา A ไม่ยากไปกว่า ปัญหา B
ปัญหา A 
ปัญหา B
โดยมีความหมายว่า ถ้ามี Algorithm ที่สามารถแก้ปัญหา B ได้ ปัญหา A ก็จะสามารถแก้ได้เช่นกัน
ปัญหาที่ 1 : Independent Set เป็นปัญหากลุ่ม Decision Problem
นิยาม : ให้ Undirected graph G = (V, E) จะกล่าวว่า I 
V เป็น Independent Set ก็ต่อเมื่อ สำหรับทุกๆโหนด
U,V I, U 
V ไม่มีเส้นเชื่อมระหว่าง U และ V
ปัญหา : ให้กราฟ G = (V, E) และ integer k, มี Independent set ขนาด ≥ k หรือไม่
ในภาพทำการเลือกโหนด (k) เท่ากับ 1 จะกล่าวว่ามี Independent set ขนาด 1
สามารถนำไปใช้แก้ปัญหา หาคนที่ไม่รู้จักกันในห้อง หรือ การเปิด-ปิดไฟแดงที่แยก
ปัญหาที่ 2 : Vertex Cover
นิยาม : C V เป็น Vertex Cover ก็ต่อเมื่อ 
(U,V)
E,U C หรือ V C
ปัญหา : ให้กราฟ G = (V, E) และ จำนวนเต็ม k ถามว่ามี vertex cover ขนาด ≤ k หรือไม่
ถ้าสมมติให้ Independent Set Vertex Cover
Lemma : พิจารณาเซต ใดๆ ให้ A เป็น imdenpendent set โดย V-A เป็น Vertec Cover
Proof : Indenpendent set 
Vertex Cover
นิยาม : ปัญหา A เป็น Polynomial time เพื่อลดปัญหา B ถ้ามี Algorithm T ที่ทำงานใน Polynomial time สำหรับทุกๆ instance X ของ A จะได้ T(x) เป็น instance ของ B
X' = T(x) เป็น instance ของ B และ |X'| = Poly (|X|)
ถ้า x เป็น instance ตอบ "Yes" ใน A => x' เป็น instance ตอบ "Yes" ใน B
ถ้า x เป็น instance ตอบ "No" ใน A => x' เป็น instance ตอบ "No" ใน B
Lemma : ถ้า A B และมี Algorithm ที่แก้ปัญหา B ได้ใน Polynomial time จะมี Algorithm ที่แก้ปัญหา A ใน Polynomial time ได้ด้วย
Proof : ให้ M เป็น Polynomial time Algorithm ที่แก้ปัญหา B
จะได้ว่า A B
นั้นคือ มี Polynomial time Algorithm T ที่ instance x ของ A
x' = T(x) มีขนาด poly(|x|) และคำตอบของ x ในปัญหา A ตรงกับของ x' ในปัญหา B
สำหรับ Algorithm M' ดังนี้
M'(x) : x' = T(x) return M(x')
แต่เนื่องจาก |x'| = poly(|x|)
ดังนั้น เวลาในการคำนวณ M(x')คือ poly(|x'|) = poly(poly(|x|)) = poly(|x|)
จากนิยาม M'(x) เป็นคำตอบของ x ใน A เหลือแต่ต้องตรวจสอบว่า M' ทำงานใน Polynomial time หรือ poly(|x|)
