ผลต่างระหว่างรุ่นของ "204512/บรรยาย 6"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(แก้ข้อความอ่านไม่ออก(ใช้ wget + KHexedit + HTML Decode) ทั้งหมด)
 
(ไม่แสดง 14 รุ่นระหว่างกลางโดยผู้ใช้ 4 คน)
แถว 1: แถว 1:
 +
ertalia
 
{{หัวคำบรรยาย|204512}}
 
{{หัวคำบรรยาย|204512}}
ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ ''แก้ต่อ...''
+
'''จดบันทึกคำบรรยายโดย:'''<br>
 +
ณัฐ เรืองฤทธิ์ 50653773<br>
 +
อมรเดช แจ่มสว่าง 50653963<br>
 +
 
 +
ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path
  
 
==นิยาม==
 
==นิยาม==
แถว 22: แถว 27:
 
เส้นทางดังกล่าวคือ negative length cycle   
 
เส้นทางดังกล่าวคือ negative length cycle   
  
;นิยาม : เราจะเรียกวงรอบที่มีความยาวเป็นลบ ว่า '''negative length cycle''' หรือ '''negative cycle'''
+
{{กล่องนิยาม|;นิยาม : เราจะเรียกวงรอบที่มีความยาวเป็นลบ ว่า '''negative length cycle''' หรือ '''negative cycle'''}}
  
 
เราจะเรียก path ใด ๆ ว่าเป็น <u>simple path</u> ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง และจะเรียก path ใด ๆ ว่าเป็น
 
เราจะเรียก path ใด ๆ ว่าเป็น <u>simple path</u> ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง และจะเรียก path ใด ๆ ว่าเป็น
แถว 39: แถว 44:
 
{{จบบทพิสูจน์}}
 
{{จบบทพิสูจน์}}
  
 +
lirelrol
 
==Single Source Shortest Path==
 
==Single Source Shortest Path==
 
ในปัญหา single source shortest path เราจะได้รับ source ''s'' แล้วหา shortest path จาก ''s'' ไปยังทุกๆ โหนด
 
ในปัญหา single source shortest path เราจะได้รับ source ''s'' แล้วหา shortest path จาก ''s'' ไปยังทุกๆ โหนด
แถว 49: แถว 55:
 
{{กล่องทฤษฎีบท|
 
{{กล่องทฤษฎีบท|
 
'''Theorem:'''
 
'''Theorem:'''
ถ้าสำหรับทุก ๆ เส้นเชื่อม (u,v) ในกราฟ  
+
ถ้าสำหรับทุก ๆ เส้นเชื่อม (''u'',''v'') ในกราฟ  
 
<center><math>dist_T(v)\le dist_T(u) + length(u,v)</math></center>
 
<center><math>dist_T(v)\le dist_T(u) + length(u,v)</math></center>
 
แล้ว T จะเป็น shortest path tree
 
แล้ว T จะเป็น shortest path tree
แถว 69: แถว 75:
 
::เราทราบว่า<math>length(u,v) \ge dist_T(v) - dist_T(u)</math> <br>
 
::เราทราบว่า<math>length(u,v) \ge dist_T(v) - dist_T(u)</math> <br>
 
::นำมา map กับ P<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(v_k)-dist_T(v_0)</math><br>
 
::<math>length(P) \ge dist_T(t)-0</math><br>
 
::<math>length(P) \ge dist_T(t)-0</math><br>
แถว 89: แถว 95:
 
[[ภาพ:sp05.png]]
 
[[ภาพ:sp05.png]]
 
----
 
----
 +
{{กล่องทฤษฎีบท|
 
'''Lemma'''
 
'''Lemma'''
 
:ถ้า <math>distance(u)\ne\infty</math> , จะมี path จาก s ไป u ที่มีความยาว distance(u)<br>
 
:ถ้า <math>distance(u)\ne\infty</math> , จะมี path จาก s ไป u ที่มีความยาว distance(u)<br>
 +
}}
 +
{{เริ่มบทพิสูจน์}}
 
'''Proof'''
 
'''Proof'''
 
: assume ว่า lemma จริงเมื่อตอนต้นการทำงาน<br>
 
: assume ว่า lemma จริงเมื่อตอนต้นการทำงาน<br>
แถว 100: แถว 109:
 
::<math>distance(v)\leftarrow distance(u) + length(u,v)</math><br>
 
::<math>distance(v)\leftarrow distance(u) + length(u,v)</math><br>
 
::ซึ่งเท่ากับความยาวของ <math>p' = p \cup \{u,v\}</math>
 
::ซึ่งเท่ากับความยาวของ <math>p' = p \cup \{u,v\}</math>
 +
{{จบบทพิสูจน์}}
 
----
 
----
 +
{{กล่องทฤษฎีบท|
 
'''Lemma'''
 
'''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
 
:และสำหรับ 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^k(u) = p(p^{k-1}(u))\,</math>
*<math>p^1(n) = p(n)\,</math>
+
*<math>p^1(u) = p(u)\,</math>
 +
{{เริ่มบทพิสูจน์}}
 
'''Proof'''<br>
 
'''Proof'''<br>
 
'''(I)'''
 
'''(I)'''
แถว 142: แถว 155:
 
# parent จะ form ตัวกันเป็น tree T
 
# parent จะ form ตัวกันเป็น tree T
 
# ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree<br><br>
 
# ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree<br><br>
 +
{{จบบทพิสูจน์}}
  
 
== Labelling & Scanning Method ==
 
== Labelling & Scanning Method ==
แถว 167: แถว 181:
 
:Running time จาก Algorithm นี้คือ O(m+n)
 
:Running time จาก Algorithm นี้คือ O(m+n)
 
:<b><u>***Topological ของโหนด</u></b> คือ การเรียงของโหนดที่รับประกันได้ว่าไม่มี edge จากโหนดด้านหลังชี้มายังโหนดด้านหน้า<br><br>
 
:<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>
 
:ในบรรดาโหนดที่มีสถานะเป็น Labelled ให้ Scan โหนด w ที่ distance(w) น้อยที่สุด <u>โดยจะไม่ Scan ซ้ำ</u><br>
 
:จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่<br><br><br>
 
:จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่<br><br><br>

รุ่นแก้ไขปัจจุบันเมื่อ 13:33, 18 มีนาคม 2551

ertalia

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย:
ณัฐ เรืองฤทธิ์ 50653773
อมรเดช แจ่มสว่าง 50653963

ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path

นิยาม

เราจะเริ่มต้นด้วยนิยามของเส้นทางสั้นที่สุด

ให้ directed graph G = (V,E) และฟังก์ชัน ที่ระบุความยาวบนเส้นเชื่อม กล่าวคือความยาวของเส้นเชื่อม (u,v) คือ length(u,v)

สำหรับเส้นทาง P ใด ๆ เราจะนิยามความยาว length(P) เป็น

เส้นทางที่สั้นที่สุด (shotest path) จาก s ไป t คือเส้นทาง P ที่เริ่มที่ s สิ้นสุดที่ t ที่มีความยาวน้อยที่สุด

วงรอบที่เป็นลบกับเส้นทางที่สั้นที่สุด

ปัญหาแรกที่เราสนใจก็คือ: เส้นทางที่สั้นที่สุดจะมีในทุก ๆ กราฟหรือไม่?

พิจารณากราฟต่อไปนี้
Sp01.png
จากรูปจะเห็นได้ว่าถ้ามีการเลือกเส้นทางวนตรงกลางกราฟ จะสามารถวนซ้ำให้ค่าความยาวติดลบเท่าไหร่ก็ได้

เส้นทางดังกล่าวคือ negative length cycle

นิยาม 
เราจะเรียกวงรอบที่มีความยาวเป็นลบ ว่า negative length cycle หรือ negative cycle

เราจะเรียก path ใด ๆ ว่าเป็น simple path ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง และจะเรียก path ใด ๆ ว่าเป็น s-t path ถ้า path นั้นเริ่มที่ s และสิ้นสุดที่ t

ทฤษฎีบทด้านล่างแสดงว่าถ้ากราฟจะมีเส้นทางที่สั้นที่สุด เมื่อและต่อเมื่อ กราฟไม่มีวงรอบที่เป็นลบ

Theorem: ถ้าไม่มี negative cycle C ที่ไปถึงได้จาก s และบางใหนดใน C สามารถไปถึง t ได้, จะมี shortest path จาก s ไป t


Proof: สังเกตว่าสำหรับ s-t path P ใดๆ จะมี simple s-t path P' ที่มีความยาวไม่มากกว่า P ทั้งนี้เนื่องจากถ้าเส้นทางนั้นมี cycle เราสามารถตัด cycle นั้นออกได้โดยไม่ทำให้ความยาวของเส้นทางที่ได้ยาวขึ้น (ดูรูปด้านล่าง)

Sp02.png

เนื่องจากจำนวน simple s-t path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ ดังนั้นจะมี path ที่มีความยาวสั้นที่สุด

Littlebox.png

lirelrol

Single Source Shortest Path

ในปัญหา single source shortest path เราจะได้รับ source s แล้วหา shortest path จาก s ไปยังทุกๆ โหนด

นิยาม 
ต้นไม้ T ที่มี s เป็น root เป็น shortest path tree ถ้าทุกๆ path ใน T เป็น shortest path

ให้ต้นไม้ T, เราให้ distT แทนความยาวของ path ใน T จาก s ไป u ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า T เป็น shortest path tree

Theorem: ถ้าสำหรับทุก ๆ เส้นเชื่อม (u,v) ในกราฟ

แล้ว T จะเป็น shortest path tree


Proof

ถ้า T เป็น shortest path tree แล้ว length(u,v) <= 10
พิจารณา s-t path ใดๆ

Sp04.png

P ยาว length(p)
path on tree ยาว dist T(t)
P ต้องมีความยาวไม่น้อยกว่า path on tree ซึ่งเป็น shortest path ทำให้ T จะเป็น shortest path tree

Proof ด้วยวิธี induction บน P
ให้
ซึ่ง =s , =t
ดังนั้น
จาก
เราทราบว่า
นำมา map กับ P
จะได้ว่า


P มีความยาวไมน้อยกว่า path on tree ถ้าเงื่อนไขนี้เป็นตริง T จะเป็น shortest path tree
Littlebox.png


Algorithm

เริ่มต้น
  • for all

  • parent(u)= null for all u
จากนั้นจึงทำ labelling step

Labelling Step

เลือก edge(u,v) ที่ มา
แล้วปรับค่า
และ

Sp05.png


Lemma

ถ้า , จะมี path จาก s ไป u ที่มีความยาว distance(u)

Proof

assume ว่า lemma จริงเมื่อตอนต้นการทำงาน
Proof by induction บนจำนวนของการทำ labelling step
assume ว่า lemma จริงก่อนการทำงานของ step ใดๆ

Sp06.png

เนื่องจาก มี path p จาก s ไป u ที่มีความยาว distance(u) (by induction step)
หลังการทำงานตาม labelling step

ซึ่งเท่ากับความยาวของ
Littlebox.png


Lemma

ถ้า labelling step terminate ,parent p จะ form ตัวเป็น shortest path tree T
และสำหรับ u ที่ , distance(u)จะเท่ากับความยาวของ path ใน T จาก s ไป u

กำหนดให้


Proof
(I)

ถ้า G มี negative cycle ที่ไปถึงได้จาก s, labelling step จะไม่หยุดการทำงาน

ไม่ว่า distance fucntion บนโหนดจะเป็น อย่างไร
จะมีบาง edge ที่ทำ labelling step ได้

Sp08.png

พิจารณา

แสดงว่าจะมีการทำ labelling step เมื่อ
จากรูป มีโหนดจำนวน k โหนด เขียนออกมาได้ว่า






ซึ่งจะสามารถทำ labelling step ได้ถ้าบางแถวยังมีค่าน้อยกว่า 0
เมื่อลองจับทุกแถวบวกกัน
Sp09.png

จะพบว่าเหลือแต่ค่า length รวมกันซึ่งก็คือ ความยาวของ path ใน cycle
ซึ่งถ้าเป็น negative cycle แสดงว่าต้องมีตัวใดตัวหนึ่งมีค่าติดลบ
ทำให้สามารถทำ labelling step ได้เสมอ

(II)

ไม่มี v ที่ สำหรับบางค่าของ k

Sp07.png

แต่เราปรับค่า d(u) นั่นคือ


นั่นคือ

*จากเบอร์ 1 กราฟไม่มี negative cycle

(III)

ถ้ามี path จาก s ไป v
และ
เพราะถ้ามี path ถึง v แสดงว่าต้องมีการ update มาถึง v เลยทำให้ และ ด้วย

จาก (I),(II),(III) จะสามารถ proof ได้กว่า

  1. parent จะ form ตัวกันเป็น tree T
  2. ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree

Littlebox.png

Labelling & Scanning Method

แต่ละโหนดจะมีสถานะได้ดังนี้

  • Unlabelled
  • Labelled
  • Scanned
Sp10.png


เริ่มต้นโหนดทุกโหนดยกเว้น s จะมีสถานะเป็น Unlabelled และ s มีสถานะเป็น Labelled
และทุกครั้งที่ distance(u) เปลี่ยน u จะมีสถานะเป็น Labelled

Pre-Condition u มีสถานะเป็น Labelled

SCAN(u):

if distance(v) > distance(u) + length(u,v)

เปลี่ยนสถานะของ v เป็น Labelled


Sp11.png



แสดงขั้นตอนการทำ Labelling & Spanning Method



Claim : ถ้าทำตามวิธี Labelling & Scanning Method แล้วไม่แหลือโหนดที่มีสถานะเป็น Labelled เลย เราจะไม่สามารถทำ Labelling Step ได้อีก

Efficient Scanning Order

(I) กราฟที่ไม่มี cycle [Directed Acyclic Graph - DAG]
คือกราฟที่ไม่มีการเรียงแบบ Topological ของโหนด
Sp12.png


Running time จาก Algorithm นี้คือ O(m+n)
***Topological ของโหนด คือ การเรียงของโหนดที่รับประกันได้ว่าไม่มี edge จากโหนดด้านหลังชี้มายังโหนดด้านหน้า

(II) กราฟไม่มี edge ที่ความยาวเป็นลบ [Dijkstra's Algorithm]



ในบรรดาโหนดที่มีสถานะเป็น Labelled ให้ Scan โหนด w ที่ distance(w) น้อยที่สุด โดยจะไม่ Scan ซ้ำ
จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่


Enqueue(k,v) เพิ่ม (k,v) ลงใน Set
FindMin ที่มีค่า k น้อยที่สุด
ExtractMin ที่มีค่า k น้อยที่สุดและลบ (k,v) ออกจาก S
Update((k,v),k') Update k ด้วย k'



Dijkstra's Algorithm













Running Time จะแบ่งเป็น 2 ช่วงได้แก่ช่วงของการ ExtractMin (O(n)) และช่วงของการ UpdateQueue (O(m)) ซึ่งจะแตกต่างกันไป
ตามการจัดวางของ Graph แบบต่างๆ โดยสามารถเทียบเป็นตารางได้ดังนี้


ExtractMin UpdateQueue Total
Array ของโหนด
(Dijkstra)
O(n) O(1) O(n^2)
Binary Heap O(logn) O(logn) O((m+n)logn)
Fibonacci Heap O(logn) decrease key
O(1)
amortized
O(nlogn+m)
ตารางแสดง Running Time เทียบกับ form ของ graph แบบต่างๆ



(III) กราฟทั่วไป [Bellman - Ford - Moore] 
เป็นการ Scan ทุกๆ โหนดเป็นจำนวน n-1 รอบ เพราะฉะนั้น Running Time จะเป็น O(nm)