204512-53/lecture12 - ประวัติรุ่นแก้ไข

Tommycpe เมื่อ 16:21, 31 ตุลาคม 2553

2010-10-31T16:21:25Z

Tommycpe เมื่อ 15:37, 31 ตุลาคม 2553

2010-10-31T15:37:38Z

158.108.226.93 เมื่อ 11:44, 26 ตุลาคม 2553

2010-10-26T11:44:40Z

Chatchapol: /* 204512-53/lecture12 */

2010-10-05T11:26:58Z

204512-53/lecture12

Chatchapol: หน้าที่ถูกสร้างด้วย '== '''204512-53/lecture12''' == '''จดบันทึกคำบรรยายโดย:''' นายชัชพล นุโย…'

2010-10-05T11:26:01Z

หน้าที่ถูกสร้างด้วย '== '''204512-53/lecture12''' == '''จดบันทึกคำบรรยายโดย:''' นายชัชพล นุโย…'

หน้าใหม่

== '''204512-53/lecture12''' ==
'''จดบันทึกคำบรรยายโดย:'''
นายชัชพล นุโยค รหัส 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 [[ไฟล์: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|)

----

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:21, 31 ตุลาคม 2553
แถว 6:		แถว 6:

	โดยที่มีตัวแปร 2 แบบคือ		โดยที่มีตัวแปร 2 แบบคือ
		+
		+	[[ไฟล์:Lecture12.1.gif]]
		+
		+	และเงื่อนไข อยู่ในรูป General Form
		+
		+	[[ไฟล์:Lecture12.2.gif]]
		+
		+	[[ไฟล์:Lecture12.3.gif]]
		+
		+	แปลงเป็น Minimum โดยการแปลงค่า <math>\sum_i{c_ix_i}</math> โดยการคูณเครื่องหมายลบเข้าไปจะทำให้เปลี่ยนเครื่องหมายของอสมการเปลี่ยนไปในทางตรงข้าม
		+
		+	การคิดคำนวณด้วยวิธีการ Simplex ต้องเปลี่ยนระบบอสมการในโมเดลคณิตศาสตร์เชิงเส้นให้อยู่ในรูปของสมการเพื่อความง่ายต่อการคำนวณ โดยเพิ่มตัวแปรสมมติขึ้น รูปแบบของสมการจะขยายเพิ่มเติมขึ้นเราเรียกรูปแบบนี้ว่า “Slack Form”
		+
		+	[[ไฟล์:Lecture12.4.gif]]
		+
		+	[[ไฟล์:Algorhw1.gif]]
		+
		+	หลักการเพิ่มตัวแปรใน Slack Form
		+	1. ในอสมการเดิมที่อยู่ในรูปเครื่องหมายน้อยกว่าหรือเท่ากับ เราจะเปลี่ยนเป็นเครื่องหมายเท่ากับ ดังนั้น จึงต้องเพิ่มส่วนที่เหลือโดยการเพิ่มค่าเข้าไปอีก โดยตัวแปรที่เพิ่มค่าจึงมีเครื่องหมาย + นำหน้า เพื่อให้เหมือนกับว่าเพิ่มค่าให้ได้เท่ากับ
		+	2. ในกรณีของอสมการในโมเดลคณิตศาสตร์เดิมอยู่ในรูปเครื่องหมายมากกว่าหรือเท่ากับ เปรียบว่าฝั่งซ้ายมากกว่าฝั่งขวา ดังนั้นการเปลี่ยนอสมการให้เป็นสมการจึงต้องลดลง ในที่นี้ต้องเติมตัวแปร Slack โดยมีเครื่องหมายลบนำหน้า แต่จากหลักการคำนวณทางแมทริกซ์ ตัวแปรที่ให้ผลลัพธ์แต่ละครั้งที่คำนวณหา จะมีสัมประสิทธิ์เท่ากับ + 1 ซึ่งเกิดเป็นแมทริกซ์ของสัมประสิทธิ์ของตัวแปรที่เป็นตัวแปรพื้นฐาน (basic variable) ตามข้อกำหนดของวิธีซิมเพล็กซ์ กำหนดว่า ผลลัพธ์เบื้องต้นที่เป็นไปได้จะมีค่าตัวแปรที่เป็นตัวแปรพื้นฐานมากกว่าหรือเท่ากับศูนย์ ดังนั้น จึงต้องเติมตัวแปรอีกตัวหนึ่งที่มีสัมประสิทธิ์เป็นบวก
		+	3. ในกรณีที่เป็นสมการที่มีเครื่องหมาย เท่ากับ = อยู่แล้ว ให้เพิ่มตัวแปรได้เลย
		+
		+	ปัญหา เทพวิตามิน คนต้องการ
		+	<math> v_A</math> 100 มก.
		+	<math> v_B 70</math> มก.
		+	<math> v_C</math> 500 มก.
		+
		+	[[ไฟล์:Lecture12.5.gif]]
		+
		+	[[ไฟล์:Lecture12.6.gif]]
		+
		+	[[ไฟล์:Lecture12.7.gif]]
		+
		+	[[ไฟล์:Lecture12.8.gif]]
		+
		+	แปลงให้อยู่ในรูป Matrix
		+
		+	[[ไฟล์:Algorhw2.gif]]
		+
		+	ใน Case นี้ให้ <math> x_4=0</math>
		+
		+	[[ไฟล์:Algorhw3.gif]]
		+
		+	<math>x_1= 235/36 ,x_2= 96/72 , x_3= 5/42</math>
		+
		+	สังเกตุที่ <math>x_3</math> เพิ่ม<math> x_4</math> ไปแล้ว <math>x_3</math> มีค่าเพิ่มขึ้นเรื่อยๆ ซึ่งไม่มีผลอะไรเพราะมีค่ามากกว่าเท่ากับ 0 อยู่แล้ว
		+
		+	จากโจทย์ถ้าเพิ่ม <math>x_4</math> จะมีผลกับ ส<math> _2</math> (-1) และ ส<math>_3</math> (-100)
		+
		+	[[ไฟล์:Algorhw5.gif]]
		+
		+	แก้สมการเมตริกซ์จะได้
		+	<math>
		+	d_1= (-131)/72 ,d_2= (-7)/144 , d_3= 83/144</math>
		+
		+	เพิ่ม <math>x_4</math> ไป <math>235/36 × 72/131=3.588</math> ซึ่งจะทำให้ค่า <math>x_1</math> เป็น 0
		+	เพิ่ม <math>x_4</math> ไป <math>95/72 × 144/7=27.14</math> ซึ่งจะทำให้ค่า <math> x_2</math> เป็น 0
		+
		+	กำหนด x1, x2, x3 ซึ่งเรียกว่า Basic Solution ที่เป็น matrix
		+	Max C’x
		+	Subject to
		+	Ax = b
		+	x ≥ 0
		+	เลือก B = {1,2,3}
		+
		+	[[ไฟล์:Lecture12.9.gif]]
		+
		+	โดยที่ C’ = เวกเตอร์แนวนอน, X = เวกเตอร์แนวตั้ง, A = คือ matrix มี ‘ เป็นแถวเวกเตอร์ ไม่มี ‘ เป็นหลักเวกเตอร์ , <math>A_B</math> = Matrix A ที่หยิบมาเฉพาะหลักในเซต B , <math>X_B</math> = เอาเฉพาะตัวแปรใน index B
		+
		+	[[ไฟล์:Algorhw4.gif]]
		+
		+	เริ่มจาก basic feasible solution XB มี B เป็นเซตของ basis
		+	<math>A_BX_B = b</math>
		+
		+	[[ไฟล์:Algorhw6.gif]]
		+
		+	[[ไฟล์:Lecture12.10.gif]]
		+
		+
		+	ถ้า <math> C_j+ C'_B y_B^i≤0</math> แสดงว่าปรับแล้วค่าไม่ดีขึ้น หยิบ field ไหนก็ได้ < 0
		+	พิจารณา x ใดๆ ที่เป็น Basis Feasible Solution
		+
		+	Ax = b
		+	x ≥ 0
		+
		+	[[ไฟล์:Lecture12.11.gif]]
		+
		+	พิจารณา x’b ใดๆ ที่เป็น Basis Physical Solution
		+	Ax = b
		+	x ≥ 0
		+
		+	[[ไฟล์:Algorhw8.gif]]
		+
		+	เกมส์วิตามิน (ต่อ) : ในกรณีที่ต้องการกินวิตามินให้ได้ครบ
		+
		+	[[ไฟล์:Lecture12.12.gif]]
		+
		+	มองในแง่คนขาย ถ้าต้องการขายวิตามินให้ได้ราคาดีที่สุด
		+
		+	[[ไฟล์:lecture12.13.gif]]
		+
		+	เป็นการแปลงจากแถวเป็นหลักและทำให้ Objective เปลี่ยนไปซึ่งคุณสมบัตินี้เราเรียกว่า Dual Linear Programing
		+
		+	นฤดล ขจรวุฒิตระกูล 5214550154
		+	รัตนพงษ์ ชัยรักษ์วัฒนา 5214550243
		+	ศักดา เอื้อจิรกาล 5214550286
		+	สยาม ชุณห์วิจิตรา 5214550294
		+	สุเกติองค์ ภู่พัฒน์ 5214550316

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:37, 31 ตุลาคม 2553
แถว 6:		แถว 6:

	โดยที่มีตัวแปร 2 แบบคือ		โดยที่มีตัวแปร 2 แบบคือ
−
−	~~<math>~~
−	~~\[X\ge0\;\\sum{\in\}V^+\]~~
−	~~</math>~~

←รุ่นแก้ไขก่อนหน้า	รุ่นแก้ไขเมื่อ 11:44, 26 ตุลาคม 2553
แถว 1:	แถว 1:
	+	'''Linear Programming'''

	+	กำหนดการเชิงเส้น จะอยู่ในรูปแบบทางคณิตศาสตร์ของสมการเชิงเส้นและอสมการเชิงเส้น แล้วหาค่าสูงสุด ต่ำสุดของฟังก์ชันที่สอดคล้องกับสมการ (และอสมการ) ที่กำหนด ตัวแบบคณิตศาสตร์
	+
	+	การหาค่าสูงสุด : Maximize <math>\sum_i{c_ix_i}</math>
	+
	+	โดยที่มีตัวแปร 2 แบบคือ
	+
	+	<math>
	+	\[X\ge0\;\\sum{\in\}V^+\]
	+	</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 11:26, 5 ตุลาคม 2553
แถว 1:		แถว 1:
−	~~== '''204512-53/lecture12''' ==~~
−	~~'''จดบันทึกคำบรรยายโดย:'''~~
−	~~นายชัชพล นุโยค รหัส 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 [[ไฟล์: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\|)
−
−
−	~~----~~