204512/บรรยาย 12

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 08:28, 6 ตุลาคม 2550 โดย 158.108.226.51 (คุย) (→‎Capacity scalling min cost flow)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

จดบันทึกคำบรรยายโดย:

นาย ชาคริต กิตโร รหัส 50653757
นาย รักพงค์ แก้วพวง รหัส 50653880


Min-cost flow

ให้กราฟ ความจุ บนเส้นเชื่อม หา Max-flow ที่ cost ต่ำที่สุด for flow

ให้ Max flow หาว่า เป็น min-cost หรือไม่ ให้ เป็น residual graph ของ

Thm Max flow เป็น min-cost เมื่อ และต่อเมื่อไม่มี negative cost cycle
Prof พิสูจน์ว่า เป็น min-cost จะไม่มี negative cost cycle ใน
Assume เป็น min-cost และมี negative cost cycle ใน
?รูป
augment ไปตาม cycle ทำให้ cost ของ flow ต่ำลง → ไม่ใช่ min-cost flow contradiction
Prof พิสูจน์ว่า ถ้า ไม่มี min-cost flow จะมี negative cost cycle ใน
ให้ เป็น min-cost max flow
พิจารณา มองในเชิงของ flow;
พิจารณา → เป็น cyculation ลบกันแล้วหักล้างกัน
ทำให้ เป็นลบ แสดงว่าต้องมี cycle อย่างน้อย 1 อัน เป็นลบ
<-
ผลรวมของ circulation ที่แต่ละวงเป็น cycle ที่มี cost รวมเป็นลบ
ดังนั้นมีบาง cycle ที่มี cost เป็นลบ

Negative cost cycle cancelling algorithm

  1. หา max flow 
 Repeat
   หา negative cost cycle ใน 
   cancel  จาก 
 Until ไม่มี negative cost cycle ใน
Running Time
ถ้า cost เป็น integer และ cap เป็น integer
นิยาม max cost, max cap,
ในแต่ละรอบ cost ของ flow จะลดลงอย่างน้อย 1 หน่วย
bound ของ cost เป็น
แต่ละรอบใช้เวลาหา negative cost cycle ใช้ belman-ford ใช้เวลา
รวม
cancel cycle ที่ทำให้ cost ลดลงมากที่สุด
cancel cycle ที่มี minimum mean cost → ได้ algorithm ที่ run ใน strongly polynomial time
weakly polynomial time = poly(n m log u log c)
strongly polynomial time = poly(n m)

Shortest Paths

ระยะทาง D: V-> R เงื่อนไขที่ D เป็น shortest path



D(x)+l(x,y)-D(y)>=0

Price Function reduced cost

เรียก function p : V-> R ว่าเป็น price function สำหรับ price function p นิยาม reduced cost Cp(x,y) = p(x) + c(x,y)-p(y)

พิจารณา path P = ความยาวของ P บน Cp คือ

พิจารณา cycle W Cp(W)=C(W) หมายเหตุ : ยังไม่ได้ใส่รูป การใช้ reduced cost ไม่มีผลต่อการมีอยู่ของ negative cost cycle

จะกล่าวว่า Price function P เป็น feasible price function ถ้า

Lemma : ถ้ากราฟมี negative cost cycle จะไม่มี feasible price function

Proof.

หมายเหตุ : ยังไม่ได้ใส่รูป

พิจารณา price function p ใดๆ พิจารณา negative cost cycle W Cp(W)=C(W)<0 นั่นคือมีบาง edge

ที่ Cp(e) < 0 นั่นคือ p ไม่ feasible

Optimulity condition

  1. ไม่มี negative cost cycle ใน
  2. Thm flow จะเป็น min cost flow ถ้ามี price function
Assume กราฟไม่มี negative cost cycle หา shortest path จาก ใดๆ แล้วให้ ระยะทางสั้นที่สุดจาก →
Observation 1 เป็น feasible price function →
Observation 2 ถ้าพิจารณา shortest path จาก ไปยัง node ใดๆ ทุกๆ edge บน มี ::D
D


Successive Shortest Path

เป็น Algorithm ที่ใช้่ในการหา Max flow จาก s ไป t    

      f<- Zero Flow
      Repeat :
           หา min cost path บน Gf (*) จาก s ไป t 
       (ด้วย shortest path algorithm ที่ทำงานบนกราฟที่มี cost เป็นลบได้ เช่น Belman-Ford)
           augment flow ตาม path นั้น
      until f เป็น max flow

Running Time
1. หา shortest path O(mn) ต่อรอบ
2. augment flow ทั้งหมด <= mC รอบ
3. ทำงานในเวลา O(nC)

Lemma2: ในแต่ละรอบที่ augment flow f ที่ได้เป็น min cost flow

proof : ในรอบแรก f เป็น zero flow เป็น min cost 

   พิจารณาการ augment ในรอบที่ i
       - flow f ก่อนการ augment เป็น min cost flow 
         ใน Gf ไม่มี negative cost cycle
       - ให้ d(u) เป็นระยะทางสั้นที่สุดยน Gf จาก s ที่หาได้ในขึ้นตอน(*)
         จาก observation 2 จะได้ว่า Cd(e)=0 สำหรับทุกๆ edge e บน  shortest path จาก s ไป t

             *ยังไม่ได้ใส่รูป

  ให้  เป็น flow ที่ได้จากหลักการ augment 
  พิจารณา G 
       claim : d เป็น feasible price function บน G 
  พิจารณา  edge(x,y) บน G 
       case1: 
       case2:  นั่นคือ  C(y,x) shortest path และถูก augment
    
       นั่นคือ Cd(y,x)=0 
            Cd(x,y)=d(x)+c(x,y)-dy
            = -(-d(x)-c(x,y)+dy)
            = -(dx(x)+c(x,y)-dy)
            = -Cd(y,x) 
             -Cd(y,x)>=0
นั้นคือ  เป็น min cost flow

Ford Fulkerson + Capacity Scalling

 มี parameter Δ เป็น scale บอกว่าจะ augment flow ใน path ครั้งละ Δ หน่วย
 ให้ Δ , Zero flow
 Repeat
   Repeat
     หา , หา augmenting path ที่มี cap  Δ
     เติม augment Δ หน่วย
   until หา augmenting path ขนาด Δ ไม่ได้
 Δ  Δ 
 until Δ

Capacity scalling min cost flow

แต่ละ node จะมี demand
โดย parameter Δ จะเติม flow ครั้งละ Δ
ให้
Δ เป็นเซตของ node ที่ Δ
Δ เป็นเซตของ node ที่ &minus Δ
Δ เป็น residual graph ที่ทุก edge มี cap อย่างน้อย Δ
รูป?
หลังจาก Δ augment flow ที่เหลือไม่เกิน Δ
Δ ไม่มี negative cost cycle → มี feasible price function
ΔΔ
อาจมี negative cost cycle นั้นคือ ไม่มี min cost บน ที่
สร้างคู่ demand excess
ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=204512/บรรยาย_12&oldid=3377"

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