หน้านี้เป็นเอกสารประกอบวิชา 01204512 เนื้อหาจาก http://www.cs.berkeley.edu/~satishr/cs270/sp12/ lecture 1

เนื้อหา

1 ปัญหา congestion minimization

ปัญหา congestion minimization

ให้กราฟ และเซตของคู่ของจุดยอด จำนวน คู่ เราต้องการหาเซตของเส้นทาง (path) ที่เชื่อมจุดยอดแต่ละคู่ โดยต้องการทำให้จำนวน path ที่ผ่านเส้นเชื่อมใด ๆ มีค่าน้อยที่สุด (เราจะเรียกจำนวนผ่านที่ผ่านเส้นเชื่อมใด ๆ ว่าเป็น congestion ของเส้นเชื่อมนั้น)

คำตอบใด ๆ ของปัญหานี้ คือเซตของ path จำนวน $k$ เส้น แต่เราต้องการให้ path เหล่านี้ กระจายกันไป path เหล่านี้ทำให้เกิด congestion บนเส้นเชื่อม เป้าหมายที่เราต้องการจะทำให้มีค่าต่ำสุดของปัญหานี้คือ congestion ที่มากที่สุดบนเส้นเชื่อมใด ๆ

ถ้าเขียนให้ชัดเจนก็คือ เราต้องการจะ:

หา path:

ที่ เชื่อมระหว่าง กับ $t_{i}$ สำหรับ $1\leq i\leq k$

เพื่อจะ minimize $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

\max _{e\in E}c(e)

เมื่อ คือจำนวน path ที่ผ่านเส้นเชื่อม $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

e

ปัญหานี้อาจจะยากสักหน่อย เราจะพิจารณาปัญหาที่ง่ายลง แทนที่เราจะ minimize ค่า congestion ที่สูงที่สุด เราจะ minimize ค่าเฉลี่ยของ congestion กล่าวคือ เราจะ:

minimize , เมื่อ แทนจำนวนเส้นเชื่อม

สังเกตว่าผลรวมของ congestion บนทุก ๆ เส้นเชื่อมนั้น เท่ากับผลรวมของความยาวของทุก ๆ path ดังนั้นเป้าหมายที่เราต้องการจะ minimize คือ

ซึ่งปัญหานี้ เราสามารถแก้ได้โดยง่าย โดยใช้อัลกอริทึมสำหรับ shortest path

สังเกตเพิ่มเติมว่า ค่าคำตอบของปัญหา average congestion minimization นี้ เป็น lower bound ของค่าของคำตอบของปัญหา congestion minimization (เพราะอะไร?) ดังนั้น ถ้าเราจะแก้ปัญหา congestion minimization โดยการใช้วิธีของปัญหาแรกเลยจะได้หรือไม่?

ถ้าเราพิจารณาให้ดี เราจะพบว่า มีตัวอย่างง่าย ๆ ที่ผลลัพธ์ที่ได้ มี congestion เท่ากับ $k$ ในขณะที่คำตอบที่ดีที่สุดให้ congestion แค่ 1 เท่านั้น

สังเกตว่าทุก ๆ path จะพยายามไปใช้เส้นทางที่สั้นที่สุดพร้อม ๆ กันหมด เราจะพยายามแก้ปัญหานี้โดยการทำให้เส้นทางที่สั้นที่สุดมีความ "น่าใช้" ลดลงเรื่อย ๆ เราจะทดลองหลาย ๆ แบบ

การปรับระยะทางแบบเชิงเส้น

เราจะปรับความยาวของ edge ตาม congestion ของ edge นั้น กล่าวคือ ในแต่ละรอบที่เราหาเส้นทางที่สั้นที่สุดเราจะให้ สำหรับทุก ๆ เส้นเชื่อม เราจะทยอยเพิ่ม path เข้าไปในระบบจนกว่าระบบจะ "นิ่ง"

เมื่อใดที่เราจะเรียกว่าระบบ "นิ่ง"? ถ้าเราเลือกเส้นทางใด เราจะเพิ่มค่า congestion ให้กับ edge บน เส้นทางนั้น ทำให้ในรอบต่อไปเวลาเราจะเลือกเส้นทางที่สั้นที่สุด เราจะเลือกได้เส้นทางอื่น ในที่นี้เราจะพิจารณาแบบง่ายไปก่อนว่า เราจะเรียกว่าระบบนิ่ง เมื่อความยาวของ path ใด ๆ เท่ากัน

สังเกตว่าในกรณีนี้ ความยาวของ edge ใน path ที่มี edge เดียว (เส้นล่างสุด) จะต้องยาวเท่ากับเส้นอื่น ๆ ทั้ง $k$ เส้น นั่นคือเราจะได้ว่า

เมื่อ คือ edge แรกใน path ที่มีจำนวน edge เท่ากับ edges (สังเกตว่าทุก ๆ edge ใน path เดี่ยวกัน จะต้องมี congestion เท่ากัน)

สังเกตว่า ผลลัพธ์ที่เราได้ จะต้องเป็น flow ที่มีขนาด k หน่วย จากจุดสมดุลย์ข้างต้น เราส่ง flow ไปแล้วทั้งสิ้นเท่ากับ

$c(e_{1})+c(e_{2})+\cdots +c(e_{k})$ หน่วย ดังนั้นเราจะ scale flow ดังกล่าวลง เพื่อให้ได้ผลรวมเท่ากับ $k$ เราจะต้องหาตัวคูณ ที่สอดคล้องกับ

$\alpha \cdot (c(e_{1})+c(e_{2})+\cdots +c(e_{k}))=k$ นั่นคือ

จัดนิพจน์ใหม่ ตามสมการด้านบน โดยแทนค่า $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

c(e_{i})=c(e_{1})/i

เราจะได้ว่า

$Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

\alpha ={\frac {k}{c(e_{1})+{\frac {c(e_{1})}{2}}+{\frac {c(e_{1})}{3}}+\cdots +{\frac {c(e_{1})}{k}}}}={\frac {k}{c(e_{1})\left(1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{k}}\right)}}

สังเกตว่าจำนวน flow ทั้งหมดที่ผ่านเส้นเชื่อม $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

e_{1}

หลังจากการ scale ด้วย

\alpha

แล้ว จะมีค่าเท่ากับ

$\alpha \cdot c(e_{1})={\frac {k}{1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{k}}}}\approx k/{\ln k}$

ซึ่งดีกว่าค่า congestion ในตอนแรก

การปรับระยะทางเป็นกำลังสอง

แทนที่เราจะปรับแบบเชิงเส้น เราจะปรับความยาวให้มากขึ้น โดยเราจะให้ สำหรับทุก ๆ เส้นเชื่อม

ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ

$Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

c(e_{1})^{2}=2\cdot c(e_{2})^{2}=3\cdot c(e_{3})^{2}=\cdots =k\cdot c(e_{k})^{2}

หรือ $c(e_{i})={\sqrt {c(e_{1})^{2}/i}}=c(e_{1})/{\sqrt {i}}$

เราแทนค่านี้ลงไปใหม่ ในการวิเคราะห์เดิมในกรณีที่ปรับค่าความยาวเป็นเชิงเสิ้น เราจะได้ว่า

$Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

\alpha ={\frac {k}{c(e_{1})+{\frac {c(e_{1})}{\sqrt {2}}}+{\frac {c(e_{1})}{\sqrt {3}}}+\cdots +{\frac {c(e_{1})}{\sqrt {k}}}}}={\frac {k}{c(e_{1})\left(1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+\cdots +{\frac {1}{\sqrt {k}}}\right)}}

ดังนั้นจำนวน flow ทั้งหมดผ่านเส้นเชื่อม หลังจากการ scale ด้วย $\alpha$ แล้ว จะมีค่าเท่ากับ

$Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

c(e_{1})\cdot {\frac {k}{c(e_{1})\left(1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+\cdots +{\frac {1}{\sqrt {k}}}\right)}}={\frac {k}{1+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+\cdots +{\frac {1}{\sqrt {k}}}}}

สังเกตว่า $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

{\frac {1}{\sqrt {i}}}\geq {\frac {1}{\sqrt {k}}}

เมื่อ

1\leq i\leq k

ดังนั้น

ดังนั้น ค่า congestion บน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

e_{1}

หลักการ scale จะมีค่าไม่เกิน

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 933957720 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Mon, 15 Jun 2026 12:23:42 GMT Sensitive client information IP address: 158.108.32.49

การปรับระยะทางแบบยกกำลัง

ถ้าเราจะปรับความยาวให้มากขึ้น โดยให้ สำหรับทุก ๆ เส้นเชื่อม

ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ

$2^{c(e_{1})}=2\cdot 2^{c(e_{2})}=3\cdot 2^{c(e_{3})}=\cdots =k\cdot 2^{c(e_{k})}$

หรือ เมื่อนำสมการนี้เข้าไปแทนในการวิเคราะห์เราสามารถแสดงได้ไม่ยากว่า congestion ที่มากที่สุด จะมีค่าไม่เกิน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

O(\log k)

01204512/congestion1

เนื้อหา

ปัญหา congestion minimization

Error

Error

การปรับระยะทางแบบเชิงเส้น

Error

Error

Error

การปรับระยะทางเป็นกำลังสอง

Error

Error

Error

Error

Error

การปรับระยะทางแบบยกกำลัง

Error

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ