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

Chalet16: แก้ข้อความอ่านไม่ออก(ใช้ wget + KHexedit + HTML Decode) ทั้งหมด

2008-03-18T13:33:46Z

แก้ข้อความอ่านไม่ออก(ใช้ wget + KHexedit + HTML Decode) ทั้งหมด

2008-03-18T13:30:10Z

แก้ข้อความอ่านไม่ออก(ใช้ wget + KHexedit + HTML Decode) ยังแก้ได้แค่บางส่วน

2007-10-12T12:24:15Z

Single Source Shortest Path

2007-10-12T12:23:45Z

2007-10-06T06:02:03Z

Efficient Scanning Order

2007-10-06T05:10:02Z

Labelling Step

2007-10-06T05:08:36Z

Labelling Step

2007-10-05T14:08:23Z

Single Source Shortest Path

2007-10-05T13:56:25Z

2007-10-05T13:44:16Z

@@ แถว 179: / แถว 179: @@
 :Running time จาก Algorithm นี้คือ O(m+n)
 :<b><u>***Topological ของโหนด</u></b> คือ การเรียงของโหนดที่รับประกันได้ว่าไม่มี edge จากโหนดด้านหลังชี้มายังโหนดด้านหน้า<br><br>
-;<b>(II) กราฟไม่มี edge ที่ความยาวเป็นลบ [Dijkstra's Algorithm]</b><br><br> ://เว้นไว้ใส่รูป***<br><br>
+;<b>(II) กราฟไม่มี edge ที่ความยาวเป็นลบ [Dijkstra's Algorithm]</b><br><br> <br><br>
 :ในบรรดาโหนดที่มีสถานะเป็น Labelled ให้ Scan โหนด w ที่ distance(w) น้อยที่สุด <u>โดยจะไม่ Scan ซ้ำ</u><br>
 :จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่<br><br><br>

@@ แถว 111: / แถว 111: @@
 {{กล่องทฤษฎีบท|
 '''Lemma'''
-:ถ้า labelling step terminate ,parent o จะ form ตัวเป็น shortest path tree T
+:ถ้า labelling step terminate ,parent p จะ form ตัวเป็น shortest path tree T
 :และสำหรับ u ที่ <math>distance(u)\ne\infty</math> , distance(u)จะเท่ากับความยาวของ path ใน T จาก s ไป u
 }}

@@ แถว 115: / แถว 115: @@
 }}
 '''กำหนดให้'''
-*<math>p^k(n) = p(p^{k-1}(n))\,</math>
+*<math>p^k(u) = p(p^{k-1}(u))\,</math>
-*<math>p^1(n) = p(n)\,</math>
+*<math>p^1(u) = p(u)\,</math>
 {{เริ่มบทพิสูจน์}}
 '''Proof'''<br>

@@ แถว 73: / แถว 73: @@
 ::เราทราบว่า<math>length(u,v) \ge dist_T(v) - dist_T(u)</math> <br>
 ::นำมา map กับ P<br>
-::จะได้ว่า <math>length(P) \ge (dist_T(v_1)-dist_T(v_0))+(dist_T(v_2)-dist_T(v1))+...+(dist_T(v_k-1)-dist_T(v_k))</math> <br>
+::จะได้ว่า <math>length(P) \ge (dist_T(v_1)-dist_T(v_0))+(dist_T(v_2)-dist_T(v1))+...+(dist_T(v_k)-dist_T(v_k-1))</math> <br>
 ::<math>length(P) \ge dist_T(v_k)-dist_T(v_0)</math><br>
 ::<math>length(P) \ge dist_T(t)-0</math><br>

@@ แถว 4: / แถว 4: @@
 อมรเดช แจ่มสว่าง 50653963<br>
-ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ ''แก้ต่อ...''
+ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path
 ==นิยาม==

@@ แถว 93: / แถว 93: @@
 [[ภาพ:sp05.png]]
 ----
-{{กล่องนิยาม|
+{{กล่องทฤษฎีบท|
 '''Lemma'''
 :ถ้า <math>distance(u)\ne\infty</math> , จะมี path จาก s ไป u ที่มีความยาว distance(u)<br>
 }}
 '''Proof'''
 : assume ว่า lemma จริงเมื่อตอนต้นการทำงาน<br>
@@ แถว 106: / แถว 107: @@
 ::<math>distance(v)\leftarrow distance(u) + length(u,v)</math><br>
 ::ซึ่งเท่ากับความยาวของ <math>p' = p \cup \{u,v\}</math>
 ----
 '''Lemma'''
 :ถ้า labelling step terminate ,parent o จะ form ตัวเป็น shortest path tree T
 :และสำหรับ u ที่ <math>distance(u)\ne\infty</math> , distance(u)จะเท่ากับความยาวของ path ใน T จาก s ไป u
 '''กำหนดให้'''
 *<math>p^k(n) = p(p^{k-1}(n))\,</math>
 *<math>p^1(n) = p(n)\,</math>
 '''Proof'''<br>
 '''(I)'''
@@ แถว 148: / แถว 153: @@
 # parent จะ form ตัวกันเป็น tree T
 # ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree<br><br>
 == Labelling & Scanning Method ==