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

Aoy: /* ข้อ 3 */

2009-10-03T14:31:58Z

ข้อ 3

Aoy: /* ข้อ 1 */

2009-10-03T14:26:37Z

ข้อ 1

Aoy: /* ข้อ 5 */

2009-10-03T14:26:01Z

ข้อ 5

Aoy: /* ข้อ 4 */

2009-10-03T14:25:51Z

ข้อ 4

Aoy: /* ข้อ 3 */

2009-10-03T14:25:36Z

ข้อ 3

Aoy: /* ข้อ 2 */

2009-10-03T14:25:25Z

ข้อ 2

Aoy: /* ข้อ 1 */

2009-10-03T14:25:14Z

ข้อ 1

Aoy: /* ข้อ 5 */

2009-10-01T06:46:46Z

ข้อ 5

Aoy: /* ข้อ 4 */

2009-10-01T06:46:06Z

ข้อ 4

Aoy: /* ข้อ 3 */

2009-10-01T06:45:41Z

ข้อ 3

@@ แถว 14: / แถว 14: @@
 == ข้อ 3 ==
-[Dasgupta, Papadimitriou, Vazirani 4.11]จงหาอัลกอริทึมที่รับอินพุตเป็นกราฟแบบมีทิศทางที่มี cost ของแต่ละ edge เป็นบวก และให้คำตอบเป็นความยาวของ cycle ที่สั้นที่สุดในกราฟ (ถ้ากราฟไม่มี cycle อัลกอริทึมนี้จะตอบ no) อัลกอริทึมของคุณควรทำงานได้ในเวลา <math> O(|V|^3) \,</math>
+[Dasgupta, Papadimitriou, Vazirani 4.11]จงหาอัลกอริทึมที่รับอินพุตเป็นกราฟแบบมีทิศทางที่มี cost ของแต่ละ edge เป็นบวก และให้คำตอบเป็นความยาวของ cycle ที่สั้นที่สุดในกราฟ (ถ้ากราฟที่ให้มาเป็น DAG อัลกอริทึมนี้จะตอบไม่มี ) อัลกอริทึมของคุณควรทำงานได้ในเวลา <math> O(|V|^3) \,</math>
 [[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 3|เฉลย]]

@@ แถว 2: / แถว 2: @@
 [Dasgupta, Papadimitriou, Vazirani 4.5]โดยทั่วไปแล้วเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนดในกราฟมักจะมีมากกว่าหนึ่งเส้นทาง จงออกแบบอัลกอริทึมที่ทำงานในเวลา linear time สำหรับปัญหาต่อไปนี้
-อินพุต: กราฟแบบไม่มีทิศทาง <math> G=(V,E) \,</math> ที่มี cost ของ edge ทุก edge เท่ากันหมด และให้โหนดมาสองโหนดคือ <math> u,v \in V \,</math>
+อินพุต: กราฟแบบไม่มีทิศทาง <math> G=(V,E) \,</math> ที่มี cost ของ edge ทุก edge เป็นหนึ่ง และให้โหนดมาสองโหนดคือ <math> u,v \in V \,</math>
 เอาพุต: จำนวนของเส้นทางที่สั้นที่สุดที่แตกต่างกันจาก <math> u \,</math> ไปยัง <math> v \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:26, 3 ตุลาคม 2552
แถว 29:		แถว 29:
	== ข้อ 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>		[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\|เฉลย]]

@@ แถว 24: / แถว 24: @@
 เอาพุต:ความยาวของ cycle ที่สั้นที่สุดที่มี edge <math> e \,</math> ที่ให้มาอยู่ใน cycle นั้น
 == ข้อ 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>

@@ แถว 15: / แถว 15: @@
 == ข้อ 3 ==
 [Dasgupta, Papadimitriou, Vazirani 4.11]จงหาอัลกอริทึมที่รับอินพุตเป็นกราฟแบบมีทิศทางที่มี cost ของแต่ละ edge เป็นบวก และให้คำตอบเป็นความยาวของ cycle ที่สั้นที่สุดในกราฟ (ถ้ากราฟไม่มี cycle อัลกอริทึมนี้จะตอบ no) อัลกอริทึมของคุณควรทำงานได้ในเวลา <math> O(|V|^3) \,</math>
 == ข้อ 4 ==

@@ แถว 10: / แถว 10: @@
 == ข้อ 2 ==
 [Dasgupta, Papadimitriou, Vazirani 4.10]ให้กราฟแบบมีทิศทางพร้อมกับ cost ของแต่ละ edge (อาจมีค่าเป็นลบได้) โดยที่รับประกันว่าเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนดในกราฟมีอย่างมาก <math> k \,</math> edge จงออกแบบอัลกอริทึมที่หาเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนด <math> u \,</math> และ <math> v \,</math> โดยอัลกอริทึมดังกล่าวทำงานได้ในเวลา <math> O(k|E|) \,</math>
 == ข้อ 3 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:25, 3 ตุลาคม 2552
แถว 5:		แถว 5:

	เอาพุต: จำนวนของเส้นทางที่สั้นที่สุดที่แตกต่างกันจาก <math> u \,</math> ไปยัง <math> v \,</math>		เอาพุต: จำนวนของเส้นทางที่สั้นที่สุดที่แตกต่างกันจาก <math> u \,</math> ไปยัง <math> v \,</math>
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 1\|เฉลย]]

	== ข้อ 2 ==		== ข้อ 2 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:46, 1 ตุลาคม 2552
แถว 20:		แถว 20:

	== ข้อ 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>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:46, 1 ตุลาคม 2552
แถว 13:		แถว 13:

	== ข้อ 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 นั้น

	== ข้อ 5 ==		== ข้อ 5 ==