204512/บรรยาย 14 - ประวัติรุ่นแก้ไข

Orion else: /* Set Cover problem */

2007-10-02T05:59:15Z

Set Cover problem

2007-10-02T05:54:37Z

Set Cover problem

2007-10-02T05:53:11Z

Set Cover problem

2007-10-02T05:50:36Z

Set Cover problem

2007-10-02T05:50:14Z

Set Cover problem

2007-10-02T05:24:55Z

Metric Steiner Tree problem

2007-10-02T05:22:38Z

Metric Steiner Tree problem

2007-10-02T05:15:22Z

2007-10-02T05:13:21Z

2007-10-02T05:11:33Z

@@ แถว 112: / แถว 112: @@
 ต้องการหา I ⊆ {1,…,m} ที่ |I| น้อยที่สุด และ u Si = U ; โดยที่ I Є I
-:เทคนิค Greedy
+:'''เทคนิค Greedy'''
 ::1.เลือก Set ที่โตที่สุดและตัดออก
 ::2.เลือก Set ใหญ่สุดที่เหลือ
@@ แถว 118: / แถว 118: @@
-:Algorithm
+:'''Algorithm'''
 ::u = U     ; 1 ← ø
 ::while u ≠ ø
@@ แถว 131: / แถว 131: @@
-:Step แรก
+:'''Step แรก'''
 ::เลือก Set ที่ Cover อย่างน้อย n/K elements
 ::ให้ ni แทน |u| หลังการเลือก Set ไป i set
@@ แถว 138: / แถว 138: @@
 ::ni ≤ n(1-1/K)^i ; ก้อนนี้จะต้องยกกำลัง i กี่ครั้งจึงจะกิน n จนหมด
-:ทำกี่ครั้ง
+:'''ทำกี่ครั้ง'''
 ::ni < n(1 - 1/K)^i ; K > 0
 ::ni < n(e^-1/K)^i

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:54, 2 ตุลาคม 2550
แถว 105:		แถว 105:
	ตัวอย่าง		ตัวอย่าง

−	<center> [[ภาพ:009-SetCover.JPG\|200px\|~~วิธีการหยิบ edge~~]] </center>	+	<center> [[ภาพ:009-SetCover.JPG\|200px\|การเลือกTestCase]] </center>

@@ แถว 129: / แถว 129: @@
 สมมติให้มี Set จำนวน K sets ที่ cover U (คำตอบที่ดีที่สุดคือ K sets)<br>
 จะต้องมีอย่างน้อย 1 set ที่กินไม่น้อยกว่า 1/K ของทั้งหมด
 == Minimum Congestion Routing problem ==

@@ แถว 125: / แถว 125: @@
 :::u ← u - Si
 ::end while
 == Minimum Congestion Routing problem ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:50, 2 ตุลาคม 2550
แถว 100:		แถว 100:

	== Set Cover problem ==		== Set Cover problem ==
		+	:มี Universal U = {1,…,n}
		+	:มี Set S1, S2,…,Sm ที่ Si ⊆ U ;∀i
		+
		+	ตัวอย่าง
		+
		+	<center> [[ภาพ:009-SetCover.JPG\|200px\|วิธีการหยิบ edge]] </center>
		+
		+
		+	เลือก Subset น้อยที่สุด และเลือกไปเรื่อยๆได้ U , เช่น run test case ให้น้อยครั้งที่สุดเพื่อหา BUG ว่ามีกี่ case โดยการเลือก Set ของการ Test
		+
		+	ต้องการหา I ⊆ {1,…,m} ที่ \|I\| น้อยที่สุด และ u Si = U ; โดยที่ I Є I
		+
		+	:เทคนิค Greedy
		+	::1.เลือก Set ที่โตที่สุดและตัดออก
		+	::2.เลือก Set ใหญ่สุดที่เหลือ
		+	::จะได้ไม่เกิน ln(n) เท่า
		+
		+
		+	:Algorithm
		+	::u = U ; 1 ← ø
		+	::while u ≠ ø
		+	:::เลือก i ที่ Maximize u ∩ Si
		+	:::I ← I υ {i}
		+	:::u ← u - Si
		+	::end while
		+
	== Minimum Congestion Routing problem ==		== Minimum Congestion Routing problem ==

@@ แถว 48: / แถว 48: @@
-Depth First Search Animation:: [[http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations.html|DFSAnimation]]
+Depth First Search Animation:: [http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations.html DFS Animation]
 **การสร้าง Steiner Tree ใดๆ สามารถหาได้จาก Spanning ที่มีค่าไม่เกน2เท่าของ Optimum
 	จะสร้าง F’ ที่เป็น Spanning Tree บน F ที่มี Cost(F’) ≤ 2.Cost(F)

@@ แถว 2: / แถว 2: @@
 '''จดบันทึกคำบรรยายโดย:'''
 :นายดิเรก ยิ้มละมัย &nbsp; รหัส : 50653799
 :: Create Date :: 27 September 2007 (05.18PM)
-::Last Update :: 02 October 2007 (12.01PM)
+:: Last Update :: 02 October 2007 (12.01PM)
 :วางโครงเฉยๆ อ่ะครับ จะรีบทำให้เสร็จเร็วๆนะครับ