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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 1: แถว 1:
 +
: ''เอกสารนี้สำหรับรายวิชา [[01204512]] อ้างอิงจาก [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ http://www.cs.berkeley.edu/~satishr/cs270/sp12/] lecture 1
 +
 
ในเอกสาร [[01204512/congestion1]] เราวิเคราะห์กรณีกราฟพิเศษ ที่มี paths ความยาว <math>1,2,\ldots,k</math> เชื่อมระหว่างจุดปลาย
 
ในเอกสาร [[01204512/congestion1]] เราวิเคราะห์กรณีกราฟพิเศษ ที่มี paths ความยาว <math>1,2,\ldots,k</math> เชื่อมระหว่างจุดปลาย
  

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

เอกสารนี้สำหรับรายวิชา 01204512 อ้างอิงจาก http://www.cs.berkeley.edu/~satishr/cs270/sp12/ lecture 1

ในเอกสาร 01204512/congestion1 เราวิเคราะห์กรณีกราฟพิเศษ ที่มี paths ความยาว เชื่อมระหว่างจุดปลาย

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

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

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

  • max
  • subject to:

หมายเหตุ เราเขียน แทนเซต