ผลต่างระหว่างรุ่นของ "418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II"
Aoy (คุย | มีส่วนร่วม) (→ข้อ 5) |
Aoy (คุย | มีส่วนร่วม) (→ข้อ 1) |
||
แถว 5: | แถว 5: | ||
เอาพุต: จำนวนของเส้นทางที่สั้นที่สุดที่แตกต่างกันจาก <math> u \,</math> ไปยัง <math> v \,</math> | เอาพุต: จำนวนของเส้นทางที่สั้นที่สุดที่แตกต่างกันจาก <math> u \,</math> ไปยัง <math> v \,</math> | ||
+ | |||
+ | [[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 1|เฉลย]] | ||
== ข้อ 2 == | == ข้อ 2 == |
รุ่นแก้ไขเมื่อ 14:25, 3 ตุลาคม 2552
ข้อ 1
[Dasgupta, Papadimitriou, Vazirani 4.5]โดยทั่วไปแล้วเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนดในกราฟมักจะมีมากกว่าหนึ่งเส้นทาง จงออกแบบอัลกอริทึมที่ทำงานในเวลา linear time สำหรับปัญหาต่อไปนี้
อินพุต: กราฟแบบไม่มีทิศทาง ที่มี cost ของ edge ทุก edge เท่ากันหมด และให้โหนดมาสองโหนดคือ
เอาพุต: จำนวนของเส้นทางที่สั้นที่สุดที่แตกต่างกันจาก ไปยัง
ข้อ 2
[Dasgupta, Papadimitriou, Vazirani 4.10]ให้กราฟแบบมีทิศทางพร้อมกับ cost ของแต่ละ edge (อาจมีค่าเป็นลบได้) โดยที่รับประกันว่าเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนดในกราฟมีอย่างมาก edge จงออกแบบอัลกอริทึมที่หาเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนด และ โดยอัลกอริทึมดังกล่าวทำงานได้ในเวลา
ข้อ 3
[Dasgupta, Papadimitriou, Vazirani 4.11]จงหาอัลกอริทึมที่รับอินพุตเป็นกราฟแบบมีทิศทางที่มี cost ของแต่ละ edge เป็นบวก และให้คำตอบเป็นความยาวของ cycle ที่สั้นที่สุดในกราฟ (ถ้ากราฟไม่มี cycle อัลกอริทึมนี้จะตอบ no) อัลกอริทึมของคุณควรทำงานได้ในเวลา
ข้อ 4
[Dasgupta, Papadimitriou, Vazirani 4.12]จงหาอัลกอริทึมที่ทำงานได้ในเวลา สำหรับปัญหาต่อไปนี้
อินพุต: กราฟไม่มีทิศทาง ความยาวของ edge และ edge
เอาพุต:ความยาวของ cycle ที่สั้นที่สุดที่มี edge ที่ให้มาอยู่ใน cycle นั้น
ข้อ 5
[Dasgupta, Papadimitriou, Vazirani 4.14]ให้ strongly connected directed graph ที่ cost ของแต่ละ edge มีค่าเป็นบวกและ node จงหาอัลกอริทึมที่มีเวลาทำงานเป็นพหุนานามที่ใช้หาเส้นทางที่สั้นที่สุดสำหรับทุกคู่ของ node โดยที่เส้นทางดังกล่าวจะต้องผ่าน node