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

Kiatchumpol: /* Shortest Paths */

2010-09-23T10:54:05Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-23T10:41:38Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-22T17:20:31Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-17T18:21:22Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-17T17:11:53Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-17T16:46:37Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-17T16:44:41Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-09T10:55:29Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-09T10:45:37Z

Shortest Paths

Kiatchumpol: /* Shortest Paths */

2010-09-08T17:18:04Z

Shortest Paths

@@ แถว 166: / แถว 166: @@
-'''Dijkstra's Algorithm'''
+'''Dijkstra's Algorithm''' ''ใช้กับกราฟที่ไม่มี negative cycle''
 เป็นวิธีการแบบหนึ่งที่ใช้สำหรับหา shortest path โดยใช้หลักการ <u>เลือกสแกน labeled node u ที่มี <math>D(u)</math> น้อยที่สุด</u> ซึ่งทำให้รับประกันได้ว่าเมื่อเราสแกนโหนดนี้ไปแล้วจะไม่ต้องกลับมาสแกนที่โหนดเดียวกันอีก
@@ แถว 206: / แถว 206: @@
 | Fibonacci Heap || <math>O(log n)</math> || <math>O(1)</math><br>amortized || <math>O(nlogn+m)</math>
 |}

@@ แถว 184: / แถว 184: @@
 :  <math>for</math> <math>all</math> <math>edge(u,v)</math><br>
 :<math>    if D(u) + l(u,v) < D(v)</math><br>
-::<math>       D(v) \leftarrow D(u) + l(u,v)</math> _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ขั้นตอนนี้เรียกว่าการทำ Decrease key<br>
+::<math>       D(v) \leftarrow D(u) + l(u,v)</math> _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ขั้นตอนนี้เรียกว่าการทำ Decrease Key<br>
 ::<math>       p(v) \leftarrow u</math><br>
 ::       เปลี่ยนสถานะ <math>v</math> ให้เป็น Labeled

@@ แถว 160: / แถว 160: @@
      Topological Sort
      - โหนดที่ไม่มี edge ใดๆ ชี้หาเรียกว่า "source"
-     - วิธีการคือ วิ่งหา source แล้วก็ลบโหนดนั้นทิ้ง แล้วก็ไล่หา source ตัวถัดไปแล้วก็ลบโหนดนั้นทิ้งอีก ทำเช่นนี้ไปเรื่อยๆ
+     - วิธีการคือ วิ่งหา source แล้วก็ลบโหนดนั้นทิ้ง แล้วก็ไล่หา source ตัวถัดไปแล้วก็ลบโหนดนั้นทิ้งอีก ทำเช่นนี้ไปเรื่อยๆ ลำดับในการลบที่ได้คือ topological order
      พิสูจน์ว่า DAG ใดๆ มี topological order โดยใช้วิธีการ contradiction
          เนื่องจากกราฟมีโหนดจำนวนจำกัด ถ้าหากอัลกอริทึม topological sort สามารถทำงานไปได้เรื่อยๆ ไม่จบ แสดงว่ากราฟนั้นมี cycle ซึ่งไม่เป็น DAG

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 18:21, 17 กันยายน 2553
แถว 129:		แถว 129:
	เริ่มต้น		เริ่มต้น
	[[ไฟล์:lecture7_figure9.png]]		[[ไฟล์:lecture7_figure9.png]]
		+
		+	เมื่ออัลกอริทึมเริ่มทำงาน ตามรูป โหนด s มีสถานะเป็น scanned ส่วนโหนด a มีสถานะเป็น labeled
		+	[[ไฟล์:lecture7_figure10.png]]
		+
		+	ถ้ามีการ update โหนดที่เป็น scanned อยู่แล้ว โหนดนั้นก็จะกลับมาสู่สถานะ labeled อีกครั้ง
		+
		+	เมื่อทุกโหนดเปลี่ยนสถานะเป็น scanned ทั้งหมด อัลกอรึทึมนี้ก็จะถือว่าทำงานจบ
		+	[[ไฟล์:lecture7_figure11.png]]
		+
		+	จะเห็นว่า มีความเป็นไปได้ที่เราจะต้องทำการ scan โหนดบางโหนดมากกว่าหนึ่งครั้ง ดังนั้นถ้าเราสามารถจัดลำดับของการ scan ที่ทำให้แต่ละโหนดได้รับการ scan แค่ครั้งเดียวก็จะเป็นการดี
		+
		+	'''Directed Acyclic Graph (DAG)'''
		+
		+	กราฟที่มีทิศทาง G จะเป็น DAG ก็ต่อเมื่อ G ไม่มี cycle
		+
		+	ให้กราฟ <math>G</math> , ลำดับของโหนด <math>v_1, v_2, v_3, ..., v_n</math> จะเป็น topological order ถ้าไม่มีเส้นเชื่อม <math>(v_i, v_j)</math> ที่ <math>i > j</math>
		+
		+	ถ้ากราฟใดๆ มี topological order ก็สรุปได้ว่าเราสามารถไล่ scan โหนดไปในทิศทางเดียวโดยที่ไม่ต้องย้อนกลับมา scan โหนดเดิมอีกได้
		+
		+	รูปข้างล่างแสดงตัวอย่างของกราฟที่ไม่มี topological order
		+
		+	[[ไฟล์:lecture7_figure12.png]]
		+
		+	นั่นคือ ถ้ากราฟมี cycle กราฟนั้นจะไม่มี topological order
		+
		+	'''คำถาม''' ถ้ากราฟไม่มี cycle กราฟนั้นจะมี topological order รึเปล่า
		+
		+	'''ตอบ''' มีเสมอ สามารถพิสูจน์ได้โดยแสดงอัลกอริทึม topological sort
		+
		+	Topological Sort
		+	- โหนดที่ไม่มี edge ใดๆ ชี้หาเรียกว่า "source"
		+	- วิธีการคือ วิ่งหา source แล้วก็ลบโหนดนั้นทิ้ง แล้วก็ไล่หา source ตัวถัดไปแล้วก็ลบโหนดนั้นทิ้งอีก ทำเช่นนี้ไปเรื่อยๆ
		+
		+	พิสูจน์ว่า DAG ใดๆ มี topological order โดยใช้วิธีการ contradiction
		+	เนื่องจากกราฟมีโหนดจำนวนจำกัด ถ้าหากอัลกอริทึม topological sort สามารถทำงานไปได้เรื่อยๆ ไม่จบ แสดงว่ากราฟนั้นมี cycle ซึ่งไม่เป็น DAG

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:11, 17 กันยายน 2553
แถว 122:		แถว 122:
	p(v) <- u		p(v) <- u
	เปลี่ยนสถานะ v ให้เป็น LABELED		เปลี่ยนสถานะ v ให้เป็น LABELED
		+
		+	ดูตัวอย่างตามรูปข้างล่าง
		+	มีกราฟ
		+	[[ไฟล์:lecture7_figure8.png]]
		+
		+	เริ่มต้น
		+	[[ไฟล์:lecture7_figure9.png]]

@@ แถว 116: / แถว 116: @@
 เลือก labeled node u , scan u แล้วเปลี่ยนสถานะของ u ให้เป็น SCANNED
+ '''scan (u)'''
       for all edge(u,v)
           if  D(u) + l(u,v) < D(v)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:44, 17 กันยายน 2553
แถว 111:		แถว 111:

	- '''''SCANNED''''' หมายถึง โหนดที่โดน update แล้ว และได้มีการพิจารณาทุกเส้นเชื่อมที่ติดกับโหนดนั้นและกระจายค่าไปให้คนอื่นแล้ว		- '''''SCANNED''''' หมายถึง โหนดที่โดน update แล้ว และได้มีการพิจารณาทุกเส้นเชื่อมที่ติดกับโหนดนั้นและกระจายค่าไปให้คนอื่นแล้ว
		+
		+
		+	'''SCANNING STEP:'''
		+	เลือก labeled node u , scan u แล้วเปลี่ยนสถานะของ u ให้เป็น SCANNED
		+
		+
		+	scan (u)
		+	for all edge(u,v)
		+	if D(u) + l(u,v) < D(v)
		+	D(v) <- D(u) + l(u,v)
		+	p(v) <- u
		+	เปลี่ยนสถานะ v ให้เป็น LABELED

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:55, 9 กันยายน 2553
แถว 103:		แถว 103:

	[[ไฟล์:Lecture7_figure7.png]]		[[ไฟล์:Lecture7_figure7.png]]
		+
		+	แต่ละโหนดจะมี 3 state
		+
		+	- '''''UNLABELED''''' หมายถึง โหนดที่ยังไม่เคยถูกกระทำใดๆ เลย
		+
		+	- '''''LABELED''''' หมายถึง โหนดที่โดน update แล้ว
		+
		+	- '''''SCANNED''''' หมายถึง โหนดที่โดน update แล้ว และได้มีการพิจารณาทุกเส้นเชื่อมที่ติดกับโหนดนั้นและกระจายค่าไปให้คนอื่นแล้ว

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:45, 9 กันยายน 2553
แถว 96:		แถว 96:

	คำถามต่อมาคือ เราจะรู้ได้ยังไงว่า algorithm จะทำงานจนจบ		คำถามต่อมาคือ เราจะรู้ได้ยังไงว่า algorithm จะทำงานจนจบ
		+
		+
		+	'''Claim 3:''' ถ้ามี Negative cycle ที่ไปถึงได้จาก <math>s</math> , algorithm จะทำงานไม่จบ
		+
		+	เนื่องจาก labeling step ของ Ford อิงกับเส้นเชื่อมเป็นหลัก ดังนั้นเพื่อให้พิสูจน์ได้ เราจะปรับโครงสร้างสักเล็กน้อย ซึ่งจะอิงกับ node เป็นหลัก พิจารณารูปข้างล่าง
		+
		+	[[ไฟล์:Lecture7_figure7.png]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:18, 8 กันยายน 2553
แถว 77:		แถว 77:

	[[ไฟล์:lecture7_figure6.png]]		[[ไฟล์:lecture7_figure6.png]]
		+
		+	'''''Proof:''''' พิจารณาโหนด <math>u</math> ใดๆ ให้ path <math>S=v_0, v_1, v_2, . . ., v_{k-1}, v_k (โดยที่ v_k = u)</math> เป็น shortest path จาก <math>s</math> ไป <math>u</math>
		+
		+	ดังนั้น <math>d(u) = \sum_{i=0}^{k-1} l(v_i, v_{i+1})</math>
		+
		+	เนื่องจาก Ford's algorithm ทำงานจบ เราจะได้ว่า <math>\forall(x,w) \in E</math> , <math>D(x) + l(x,w) \geq D(w)</math>
		+
		+	นั่นคือ <math>l(x,w) \geq D(w) - D(x)</math>
		+
		+	จะได้ว่า <math> d(u) \geq \sum_{i=0}^{k-1} [D(v_{i+1}) - D(v_i) ]</math>
		+	= <math>(D(v_1) - D(v_0)) + (D(v_2) - D(v_1)) + (D(v_3) - D(v_2)) + . . . + (D(v_k) - D(v_{k-1}))</math>
		+	= <math>-D(v_0) + D(v_k) </math>
		+	= <math>D(v_k) </math> (เนื่องจาก<math> D(v_0) = D(s) = 0</math>)
		+	= <math>D(u) </math> (เนื่องจาก <math>D(v_k) = D(u)</math> )
		+
		+
		+	เมื่อนำ Claim 1 มารวมกับ Claim 2 เราจะสรุปได้ว่า ถ้า Ford's algorithm ทำงานจบ เราจะได้ระยะทาง shortest path
		+
		+	คำถามต่อมาคือ เราจะรู้ได้ยังไงว่า algorithm จะทำงานจนจบ