ผลต่างระหว่างรุ่นของ "01204512/congestion2"

รุ่นแก้ไขเมื่อ 06:54, 4 กรกฎาคม 2555

ในเอกสาร 01204512/congestion1 เราวิเคราะห์กรณีกราฟพิเศษ

ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป จะวิเคราะห์ผ่านทางปัญหาทวิภาค (dual problem) สำหรับการหาปัญหาทวิภาคนี้ เราจะพิจารณาละเอียดต่อไป

สำหรับปัญหา congestion minimization ในปัญหาทวิภาคของปัญหาดังกล่าว เราต้องการหาค่า weight $w_{e}$ ให้กับทุก ๆ edge $e$ โดยที่ผลรวมของ weight มีค่าเท่ากับ 1 นอกจากนี้ ให้ $p_{i}$ เป็น shortest path ระหว่าง $s_{i}$ และ $t_{i}$ ภายใต้ weight $w_{e}$ เป้าหมายของเราคือพยายามจะ maximize ผลรวมของระยะทางสั้นที่สุดของทุก ๆ คู่ $(s_{i},t_{i})$

ปัญหาดังกล่าวนิยามได้ดังนี้

max $\sum _{i\in [k]}w(p_{i})$
subject to: $w_{e}\geq 0,\sum _{e\in E}w_{e}=1$

หมายเหตุ เราเขียน $[k]$ แทนเซต $\{1,2,3,\ldots ,k\}$

@@ แถว 3: / แถว 3: @@
 ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป จะวิเคราะห์ผ่านทางปัญหาทวิภาค (dual problem)  สำหรับการหาปัญหาทวิภาคนี้ เราจะพิจารณาละเอียดต่อไป
-สำหรับปัญหา congestion minimization
+สำหรับปัญหา congestion minimization ในปัญหาทวิภาคของปัญหาดังกล่าว เราต้องการหาค่า weight <math>w_e</math> ให้กับทุก ๆ edge <math>e</math> โดยที่ผลรวมของ weight มีค่าเท่ากับ 1 นอกจากนี้ ให้ <math>p_i</math> เป็น shortest path ระหว่าง <math>s_i</math> และ <math>t_i</math> ภายใต้ weight <math>w_e</math> เป้าหมายของเราคือพยายามจะ maximize ผลรวมของระยะทางสั้นที่สุดของทุก ๆ คู่ <math>(s_i,t_i)</math>
+ปัญหาดังกล่าวนิยามได้ดังนี้
+* max <math>\sum_{i\in[k]} w(p_i)</math>
+* subject to: <math>w_e\geq 0, \sum_{e\in E}w_e = 1</math>
+หมายเหตุ เราเขียน <math>[k]</math> แทนเซต <math>\{1,2,3,\ldots,k\}</math>

ผลต่างระหว่างรุ่นของ "01204512/congestion2"

รุ่นแก้ไขเมื่อ 06:54, 4 กรกฎาคม 2555

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ