Cardcaptor เมื่อ 14:50, 4 ตุลาคม 2552

2009-10-04T14:50:11Z

158.108.183.136: หน้าที่ถูกสร้างด้วย 'สังเกตว่าในกราฟนี้ทุก edge มีความยาวเป็น 1 ดังนั้นเร…'

2009-10-04T14:49:22Z

หน้าที่ถูกสร้างด้วย 'สังเกตว่าในกราฟนี้ทุก edge มีความยาวเป็น 1 ดังนั้นเร…'

หน้าใหม่

สังเกตว่าในกราฟนี้ทุก edge มีความยาวเป็น 1 ดังนั้นเราจึงาสามารถหา shortest path จาก u ไป v ได้ด้วย breadth first search (BFS)

ในการแก้ปัญหาในโจทย์ เราจะพยายามแก้ปัญหาที่เป็นแนวทั่วไปมากขึ้น กล่าวคือเราจะไม่หาจำนวน shortest path ที่แตกต่างกันจาก <math>u \,</math> ไปยัง <math>v \,</math> เท่านั้น
แต่เราจะทำการหาคำนวณอะเรย์ <math>M[\cdot] \,</math> โดยที่ <math>M[w] \,</math> มีค่าเท่ากับจำนวน shortest path จาก <math>u \,</math> ไปยัง <math>w \,</math>
เมื่อ <math>w \,</math> เป็น vertex ใดๆ ในกราฟ

อันดับแรก สังเกตว่า <math>M[u] = 1 \,</math> เนื่องจาก shortest path จาก <math>u \,</math> ไปยัง <math>u \,</math> มีอยู่ path เดียวคือ path ความยาว 0 ที่เริ่มที่ <math>u \,</math> แล้วไม่เคลื่อนต่อไปไหน

ต่อไป ให้ <math>w \,</math> เป็น vertex ใดๆ ในกราฟ สมมติว่า shortest path จาก <math>u \,</math> ไปยัง <math>w \,</math> มีความยาว <math>\ell \,</math> edge
เราจะได้ว่า
: <math>M[w] = M[x_1] + M[x_2] + \dotsb + M[x_k]</math> (*)
เมื่อ <math>x_1, x_2, \ldots, x_k \,</math> คือ vertex ทั้งหมดที่
# ความยาวของ shortest path จาก <math>u \,</math> ไปยัง <math>x_i \,</math> มีค่าเท่ากับ <math>\ell-1 \,</math> และ
# มี edge <math>\{ x_i, w \} \,</math> อยู่ในกราฟ สำหรับทุกๆ <math>i \,</math>
ที่เป็นเช่นนี้เพราะว่าสำหรับ path ความยาว <math>\ell \,</math> จาก <math>u \,</math> ไปถึง <math>w \,</math> ทุก path จะมี vertex สุดท้ายก่อนจะไปถึง <math>w \,</math>
สมมติให้ vertex สุดท้ายนั้นเป็น <math>x \,</math> เราจะได้ว่า
: ความยาวของ shortest path จาก <math>u \,</math> ไปยัง <math>x \,</math> จะต้องเป็น <math>\ell-1 \,</math>
(ัอันดับแรก ความยาวของ shortest path จาก <math>u \,</math> ไปยัง <math>x \,</math> จะมีค่ามากที่สุดเท่ากับ <math>\ell - 1 \,</math> เนื่องจาก path จาก <math>u \,</math> ไปถึง <math>x \,</math> ก่อนที่จะไป <math>w \,</math> มีความยาว <math>\ell-1 \,</math> อยู่แล้ว อันดับที่สอง shortest path จาก <math>u \,</math> ไปถึง <math>x \,</math> จะสั้นกว่า <math>\ell-1 \,</math> ไม่ได้ เนื่องจากถ้ามันสั้นกว่านั้นความยาวของ shortest path จาก <math>u \,</math> ไปถึง <math>w \,</math> ก็จะสั้นลงด้วย)

ด้วยเหตุนี้ สำหรับ shortest path จาก <math>u \,</math> ไปถึง <math>x \,</math> หนึ่ง path จะทำให้เกิด shortest path จาก <math>u \,</math> ไปถึง <math>w \,</math> หนึ่ง path ด้วย (กล่าวคือเราเดินจาก <math>u \,</math> ไปถึง <math>x \,</math> แล้วเดินต่อจาก <math>x \,</math> ไปยัง <math>w \,</math> โดยผ่าน edge <math>\{x, w\} \,</math>) สมการ (*) จีงเป็นความจริง

จากสมการ (*) เราจึงสามารถคำนวณอะเรย์ <math>M[w] \,</math> ได้ดังต่อไปนี้
# รัน breadth first search บนกราฟโดยเริ่มจาก <math>u \,</math> แล้วให้แต่ละ vertex <math>w \,</math> แต่ละ vertex จำระดับของมัน (ซึ่งมีค่าเท่ากับความยาวของ shortest path จาก <math>u \,</math> ถึง <math>w \,</math>) ไว้ในอะเรย์ <math>L[w] \,</math>
# สร้างอะเรย์ <math>M \,</math> ให้มีขนาดใหญ่เท่ากับจำนวน vertex ในกราฟ และเซตให้ <math>M[w] = 0 \,</math> สำหรับ vertex <math>w \,</math> ทุกๆ vertex
# ไล่ vertex <math>x \,</math> ทีละเวอร์เท็กซ์ โดยไล่จากค่า <math>L[x] \,</math> น้อยไปยังค่า <math>L[x] \,</math> มาก
## พิจารณา edge <math>(x,w) \,</math> ที่ออกจาก <math>x \,</math> ทุก edge
### ถ้า <math>L[w] = L[x]+1 \,</math> แล้ว เซตให้ <math>M[w] = M[w] + M[x] \,</math>

เมื่ออัลกอริทึมทำงานเสร็จ เราจึงสามารถคืน <math>M[v] \,</math> เป็นคำตอบได้

ัอัลกอริทึมข้างบนทำงานโดยใช้เวลา <math>O(|V| + |E|) \,</math> เนื่องจาก breadth first search ทำงานได้ในเวลา <math>O(|V|+|E|) \,</math> และ loop ในข้อ 3 ก็ทำงานในเวลา <math>O(|V|+|E|) \,</math> เช่นกันเนื่องจากมันเข้าถึง edge แต่ละ edge เพียงครั้งเดียวเท่านั้น

@@ แถว 24: / แถว 24: @@
 # สร้างอะเรย์ <math>M \,</math> ให้มีขนาดใหญ่เท่ากับจำนวน vertex ในกราฟ และเซตให้ <math>M[w] = 0 \,</math> สำหรับ vertex <math>w \,</math> ทุกๆ vertex
 # ไล่ vertex <math>x \,</math> ทีละเวอร์เท็กซ์ โดยไล่จากค่า <math>L[x] \,</math> น้อยไปยังค่า <math>L[x] \,</math> มาก
-## พิจารณา edge <math>(x,w) \,</math> ที่ออกจาก <math>x \,</math> ทุก edge
+#: พิจารณา edge <math>(x,w) \,</math> ที่ออกจาก <math>x \,</math> ทุก edge
-### ถ้า <math>L[w] = L[x]+1 \,</math> แล้ว เซตให้ <math>M[w] = M[w] + M[x] \,</math>
+#:: ถ้า <math>L[w] = L[x]+1 \,</math> แล้ว เซตให้ <math>M[w] = M[w] + M[x] \,</math>
 เมื่ออัลกอริทึมทำงานเสร็จ เราจึงสามารถคืน <math>M[v] \,</math> เป็นคำตอบได้
-ัอัลกอริทึมข้างบนทำงานโดยใช้เวลา <math>O(|V| + |E|) \,</math> เนื่องจาก breadth first search ทำงานได้ในเวลา <math>O(|V|+|E|) \,</math> และ loop ในข้อ 3 ก็ทำงานในเวลา <math>O(|V|+|E|) \,</math> เช่นกันเนื่องจากมันเข้าถึง  edge แต่ละ edge เพียงครั้งเดียวเท่านั้น
+อัลกอริทึมข้างบนทำงานโดยใช้เวลา <math>O(|V| + |E|) \,</math> เนื่องจาก breadth first search ทำงานได้ในเวลา <math>O(|V|+|E|) \,</math> และ loop ในข้อ 3 ก็ทำงานในเวลา <math>O(|V|+|E|) \,</math> เช่นกันเนื่องจากมันเข้าถึง  edge แต่ละ edge เพียงครั้งเดียวเท่านั้น

418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 1 - ประวัติรุ่นแก้ไข

Cardcaptor เมื่อ 14:50, 4 ตุลาคม 2552

158.108.183.136: หน้าที่ถูกสร้างด้วย 'สังเกตว่าในกราฟนี้ทุก edge มีความยาวเป็น 1 ดังนั้นเร…'