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