Cardcaptor: หน้าที่ถูกสร้างด้วย 'อัลกอริทึมในการหา cycle ที่สั้นที่สุดมีดังต่อไปนี้ #…'

2009-10-04T11:51:00Z

หน้าที่ถูกสร้างด้วย 'อัลกอริทึมในการหา cycle ที่สั้นที่สุดมีดังต่อไปนี้ #…'

หน้าใหม่

อัลกอริทึมในการหา cycle ที่สั้นที่สุดมีดังต่อไปนี้
# รัน Floyd's algorithm บนกราฟ <math>G \,</math> และสมมติให้ output ของมันอยู่ในอะเรย์ <math>M[\cdot, \cdot] \,</math>
# สำหรับ edge <math>(u,v) \,</math> แต่ละ edge ใน <math>G \,</math> ให้คำนวณค่า <math>M[v,u] + \ell_{(u,v)} \,</math> โดยที่ <math>\ell_{(u,v)} \,</math> คือความยาวของ edge <math>(u,v) \,</math> แล้วจำค่า <math>M[v,u] + \ell_{(u,v)} \,</math> ที่ต่ำสุดเอาไว้
# ถ้าค่าที่ต่ำที่สุดในข้อ 2 เป็น <math>\infty \,</math> ก็ให้ตอบว่าไม่มี cycle มิเช่นนั้นให้คืนมันเป็นคำตอบ

เราสามารถแสดงว่าคำตอบของอัลกอริทึมข้างบนคืนมาเป็นความยาวของ cycle ที่สั้นสุด ได้ดังต่อไปนี้

'''กรณีที่ 1:''' ถ้ากราฟไม่มี cycle เราจะได้ว่าสำหรับทุกๆ edge <math>(u,v) \,</math> จะไม่มี path จาก <math>v \,</math> ไปยัง <math>u \,</math> ดังนั้น <math>M[v,u] = \infty \,</math> เสมอ ด้วยเหตุนี้ค่า <math>M[v,u] + \ell_{(u,v)} \,</math> ที่ต่ำที่สุดจึงมีค่าเท่ากับ <math>\infty \,</math> และอัลกอริทึมข้างบนจะตอบว่ากราฟไม่มี cycle ได้อย่างถูกต้อง

'''กรณีที่ 2''' ถ้ากราฟมี cycle เราจะได้ว่ามี edge <math>(u,v) \,</math> อย่างน้อยหนึ่ง edge ที่ทำให้ <math>M[u,v] + \ell_{(u,v)}\,</math> มีค่าน้อยกว่า <math>\infty \,</math> เราจะต้องแสดงว่าค่า <math>M[v,u] + \ell_{(u,v)} \,</math> ที่น้อยที่สุดคือความยาวของ cycle ที่สั้นที่สุด

อันดับแรก ให้พิจารณา edge <math>(u,v) \,</math> ใดๆ เราได้ว่า <math>M[v,u] \,</math> คือความยาวของ shortest path จาก <math>v \,</math> ไปยัง <math>u \,</math>
ด้วยเหตุนี้ <math>M[v,u] + \ell_{(u,v)}\,</math> จึงเป็นความยาวของ cycle ที่สั้นที่สุดที่มี edge <math>(u,v) \,</math>
(เราสามารถแสดงว่าข้อความสุดท้ายนี้เป็นจริงได้โดยการสมมติให้เกิดข้อขัดแย้งว่า <math>M[v,u] + \ell_{(u,v)} \,</math>
ไม่ใช่ความยาวของ cycle ที่สั้นที่สุดที่มี edge <math>(u,v) \,</math> แต่เราจะได้ว่า cycle นั้นจะต้องมี path จาก <math>v \,</math> ไปยัง <math>u \,</math>
และไม่มี path จาก v ไป u ที่มีความยาวน้อยกว่า <math>M[v,u] \,</math> แล้ว ทำให้เกิดข้อขัดแย้งขึ้น)

อันดับที่สอง เนื่องจาก cycle ที่สั้นที่สุดจะต้องผ่าน edge อย่างน้อย 1 edge เราจึงได้ว่าการนำความยาว cycle ที่สั้นที่สุดที่ผ่าน edge แต่ละ edge มาเปรียบเทียบกัน
เพื่อหาความยาวที่น้อยที่สุดจะทำให้เราได้ความยาวของ cycle ที่สั้นที่สุดเสมอ

ด้วยเหตุนี้เราจึงสามารถสรุปได้ว่า ถ้ากราฟมี cycle แล้ว อัลกอริทึมข้างบนจะตอบความยาวของ cycle ที่สั้นที่สุดมาเสมอ

เราเห็นได้ชัดว่าการทำงานในขั้นตอนที่ 1 ของอัลกอริทึมข้างบนใช้เวลา <math>O(|V|^3) \,</math> และการทำงานขั้นที่สองใช้เวลา <math>O(|E|) = O(|V^2|) \,</math> ดังนั้นอัลกอริทึมข้างบนจึงทำงานได้ในเวลา <math>O(|V|^3) \,</math>

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

Cardcaptor: หน้าที่ถูกสร้างด้วย 'อัลกอริทึมในการหา cycle ที่สั้นที่สุดมีดังต่อไปนี้ #…'