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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(แก้ข้อความอ่านไม่ออก(ใช้ wget + KHexedit + HTML Decode) ทั้งหมด)
 
(ไม่แสดง 20 รุ่นระหว่างกลางโดยผู้ใช้ 4 คน)
แถว 1: แถว 1:
 +
ertalia
 
{{หัวคำบรรยาย|204512}}
 
{{หัวคำบรรยาย|204512}}
 +
'''จดบันทึกคำบรรยายโดย:'''<br>
 +
ณัฐ เรืองฤทธิ์ 50653773<br>
 +
อมรเดช แจ่มสว่าง 50653963<br>
 +
 +
ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path
  
 
==นิยาม==
 
==นิยาม==
แถว 21: แถว 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 ใด ๆ ว่าเป็น
 +
<u>''s''-''t'' path</u> ถ้า path นั้นเริ่มที่ ''s'' และสิ้นสุดที่ ''t''
  
 
ทฤษฎีบทด้านล่างแสดงว่าถ้ากราฟจะมีเส้นทางที่สั้นที่สุด เมื่อและต่อเมื่อ กราฟไม่มีวงรอบที่เป็นลบ
 
ทฤษฎีบทด้านล่างแสดงว่าถ้ากราฟจะมีเส้นทางที่สั้นที่สุด เมื่อและต่อเมื่อ กราฟไม่มีวงรอบที่เป็นลบ
  
{{กล่องฟ้า|'''Theorem:''' ถ้าไม่มี negative cycle ''C'' ที่ไปถึงได้จาก ''s'' และบางใหนดใน ''C'' สามารถไปถึง ''t'' ได้,
+
{{กล่องทฤษฎีบท|'''Theorem:''' ถ้าไม่มี negative cycle ''C'' ที่ไปถึงได้จาก ''s'' และบางใหนดใน ''C'' สามารถไปถึง ''t'' ได้,
 
จะมี shortest path จาก ''s'' ไป ''t''}}
 
จะมี shortest path จาก ''s'' ไป ''t''}}
 
{{เริ่มบทพิสูจน์}}
 
{{เริ่มบทพิสูจน์}}
'''Proof'''<br>
+
'''Proof:'''  
:กำหนดให้<br>
+
สังเกตว่าสำหรับ ''s-t'' path ''P'' ใดๆ จะมี simple ''s''-''t'' path ''P''' ที่มีความยาวไม่มากกว่า ''P'' ทั้งนี้เนื่องจากถ้าเส้นทางนั้นมี cycle เราสามารถตัด cycle นั้นออกได้โดยไม่ทำให้ความยาวของเส้นทางที่ได้ยาวขึ้น  (ดูรูปด้านล่าง)
:# path p เป็น <u>simple path</u> ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง<br>
+
<center>[[ภาพ:sp02.png]]</center>
:# <u>s-t path</u> คือ path ที่เริ่มที่ s และสิ้นสุดที่ t<br><br>
+
 
:สำหรับ path p ใดๆ จะมี simple s-t path p' ที่มีความยาวไม่มากกว่า p<br><br>
+
เนื่องจากจำนวน simple ''s-t'' path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ ดังนั้นจะมี path ที่มีความยาวสั้นที่สุด
[[ภาพ:sp02.png]]<br><br>
 
:สังเกตว่าจำนวน simple s-t path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ<br>
 
 
{{จบบทพิสูจน์}}
 
{{จบบทพิสูจน์}}
  
 +
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'' ไปยังทุกๆ โหนด
  
{{กล่องเทา|
+
{{กล่องนิยาม|
 
;นิยาม : ต้นไม้ ''T''  ที่มี ''s'' เป็น root เป็น '''shortest path tree''' ถ้าทุกๆ path ใน ''T'' เป็น shortest path}}
 
;นิยาม : ต้นไม้ ''T''  ที่มี ''s'' เป็น root เป็น '''shortest path tree''' ถ้าทุกๆ path ใน ''T'' เป็น shortest path}}
  
 
ให้ต้นไม้ ''T'', เราให้ ''dist<sub>T</sub>'' แทนความยาวของ path ใน ''T'' จาก ''s'' ไป ''u''  ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า ''T'' เป็น shortest path tree
 
ให้ต้นไม้ ''T'', เราให้ ''dist<sub>T</sub>'' แทนความยาวของ path ใน ''T'' จาก ''s'' ไป ''u''  ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า ''T'' เป็น shortest path tree
  
{{กล่องฟ้า|
+
{{กล่องทฤษฎีบท|
 
'''Theorem:'''
 
'''Theorem:'''
ถ้าทุก edge(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
แถว 67: แถว 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>
แถว 87: แถว 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>
แถว 98: แถว 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)'''
แถว 140: แถว 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>
[[ผู้ใช้:Dejzy|Dejzy]] 18:53, 15 กรกฎาคม 2007 (ICT)
+
{{จบบทพิสูจน์}}
----
 
  
== Labelling & Spanning Method ==
+
== Labelling & Scanning Method ==
 
แต่ละโหนดจะมีสถานะได้ดังนี้
 
แต่ละโหนดจะมีสถานะได้ดังนี้
 
:* Unlabelled
 
:* Unlabelled
แถว 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)