204512-53/lecture8

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 07:00, 24 กันยายน 2553 โดย 158.108.233.60 (คุย)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

บันทึกคำบรรยายวิชา 204512-53 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

Algorithm Lecture #8 จดบันทึกคำบรรยายโดย:

นาย บดินทร์ แสงทองล้วน 5314550113

นาย วิชา มีสุขสบาย 5314550164

นาย อภิชาติ ทวีศิริเวทย์ 5314550199


Network flow problem

1. กราฟมีทิศทาง

2. ความจุ (capacity)

3. จุดเริ่มต้น source

4. จุดสิ้นสุด sink

5. flow เป็น function จาก

เงื่อนไข

1. Capacity constraints :

2. Skew symmetry :

3. conservation :

ปริมาตร flow

Maximum flow problem

Maximum flow problem: ปัญหาการหาปริมาณการไหลสูงสุด ซึ่งเป็นหนึ่งในปัญหาเน็ตเวิร์คโฟล์วที่น่าสนใจ

สัญลักษณ์ที่เกี่ยวข้อง

G คือ กราฟที่เราสนใจ

G = (V,E) คือ ฟังก์ชั่นของกราฟ G โดยที่ V คือ เซตของโหนด และ E คือเซตของเส้นเชื่อม

C: E->R+ คือ Capacity ของเส้นเชื่อม เซตจำนวนจริงบวกไม่รวมศูนย์ (0, +∞)

s-t คือ เซตของเส้นทางจาก s ไปถึง t

Maximum flow คือโจทย์หนึ่งของเน็ตเวิร์คโฟล์วโจทย์นี้ต้องการหาค่ามากที่สุดของโฟล์ว จากต้นทาง(s) ที่ส่งได้ไม่เกินความจุของเส้นเชื่อม(u) แต่ละเส้น เพื่อให้ได้ค่ารวมมากที่สุดจากต้นจนถึงปลายทาง (t)

Classic problem

Untitled1.png

Maximum flow คือเท่าไหร่ : ต้องหา path มาเรื่อยๆ จนไม่มี path

Untitled2.png หรือ Untitled3.png

ถ้าได้รูปแบบข้างต้นก็ไม่มีปัญหา แต่ถ้าเกิดได้แบบ

Untitled4.png

จะกลายเป็นปัญหา แล้วจะแก้ไขอย่างไร?

แนวคิด

Untitled5.png

Untitled6.png

Untitled7.png

Algorithm

  1. F <- 0
  2. G(f) เป็น residual graph ของ f
  3. ถ้ามี path จาก s ไป t ใน G(f)
  4. P <- path จาก s ไป t ใน G(f)
  5. C <- capacity ต่ำสุดของเส้นเชื่อมใน path P
  6. Update f ด้วย flow path P ด้วยปริมาตร C
  7. หา G(f) <- residual graph ของ flow f


st-cut

พิจารณา sub set ของ node กลุ่มหนึ่ง

St 1.png

ถ้า จะเรียก ว่า st-cut ;

cut ที่ตัด s กับ t ออกจากกัน

เราสนใจ edge ทั้งหมดที่ข้ามจาก s ไป t

1) นิยาม

          

Flow ใดๆเราพิจารณาการส่ง volumeจาก s ไป t

ถ้าเราพิจารณา volume ที่วิ่งผ่าน cut ต้องเท่ากับ volume ที่ออกจาก S

2) นิยาม

            ; flow ที่วิ่งจาก  ทั้งหมดเลย

St 2.png

flow สามารถวิ่งไปและวิ่่งกลับได้

สำหรับ st-cut ใดๆ เราได้ว่า

เราจะพิสูจน์

คือ Volume ของ f

พิสูจน์

สำหรับ st-cut S ใดๆ

พิสูจน์

St 3.png

สำหรับทุกๆ

พิสูจน์ โดย Induction ตั้งแต่ 0 ถึง k

St 4.png

เป็น base case ซึ่งจะเท่ากันตามนิยาม

เราจะพิสูจน์ว่า

St 5.png

ได้ มี flow ที่วิ่งเข้าวิ่งออกของ c กับ d สุดท้ายรวม flow เส้นปะเข้า

ไปเราได้ว่า

เนื่องจากเรารู้ว่า

Claim(1)

               

Claim(2)

               

Ford-Fullerson

สำหรับ st-cut ใดๆ

เราพิจารณา flow มีขนาดเท่ากับ cut ใดๆ แปลว่า flow นั้นมีขนาดใหญ่สุด

เราสามารถพิสูจน์ต่อได้ว่า flow ที่มีขนาดเท่ากับ เราจะได้ flow ที่มีขนาดใหญ่ที่สุด

พิสูจน์ว่า

flow f ที่ out-put โดย Ford-Fullerson เป็น maximum flow

หา s-t cut ที่

St 6.png

เราต้องการ

พิสูจน์

1) flowต้องเต็ม

2) edgeที่วิ่งกลับต้องไม่มีflowเลย

เราพิสูจน์โดย By Contradition

St 7.png

พิจารณา e=(u,v) ที่

Claim

       

ถ้าไม่เท่ากัน flow จะไม่เต็ม เท่ากับว่ามี path อีก 1 path ใน residual graph เพราะฉะนั้น เป็นจริง

สิ่งที่เราได้นอกจากจะได้ max flow เราจะได้ min cut เพราะ max flow = min cap

St 8.png

เวลาในการทำงาน

ความคืบหน้าของมันคือจำนวน |f| เพิ่มขึ้นเรื่อยๆ แต่ต้องมันใจว่าไปถึง max flow ไม่ใช่เพิ่มขึ้นน้อยลงเรื่อยก็ไม่มีทางไปถึง

m คือจำนวน edge, n คือ จำนวน node; ทำทั่วไป  ; หา path  ;

ถ้า Capacity เป็น integer จำนวนรอบที่ใช้จะเท่ากับจำนวนของ max flow

ตัวอย่างที่ Fold-Fullerson ล้มเหลว

St 9.png

Bipatite Matching

ปัญหาที่สามารถมองเป็น max flow ได้

กราฟ G จะเรียกว่าเป็น Bipatite graph ถ้า set ของ vertex V สามารถแบ่งเป็น

A,B ที่

แล้วไม่มีเส้นเชื่อม (u,v) ที่ หรือ

เซต เรียกว่าเป็น matching ถ้าไม่มีโหนดใดๆ ติดกับเส้นเชื่อม M เกิน 1 เส้น

St 10.png

ปัญหา Bipartite Matching

St 11.png

สมมุติว่า มีคน n คน ซื้อกับข้าว n ห่อ เส้นเชื่อมที่โยงไปคือ ที่สามารถกินข้าวห่อได้ ทำอย่างไรให้ทุกคนได้กินข้าวห่อ

สร้าง Supernode S กับSupernode T ใส่ทิศทางและ Capasity

หาคำตอบในกราฟนี้โดยใช้ maxflow จะ work ได้ maxflow ต้องเป็นจำนวนเต็ม