204512/บรรยาย 12 - ประวัติรุ่นแก้ไข

158.108.226.51: /* Capacity scalling min cost flow */

2007-10-06T08:28:42Z

Capacity scalling min cost flow

2007-10-06T08:13:43Z

Ford Fulkerson + Capacity Scalling

2007-10-06T08:08:48Z

Successive Shortest Path

2007-10-06T08:08:03Z

Successive Shortest Path

2007-10-06T08:06:43Z

Price Function reduced cost

2007-10-06T08:06:18Z

Price Function reduced cost

2007-10-06T08:05:11Z

Ford Fulkerson + Capacity Scalling

2007-10-06T08:04:05Z

Successive Shortest Path

2007-10-06T08:03:49Z

Ford Fulkerson + Capacity Scalling

2007-10-06T08:03:21Z

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:28, 6 ตุลาคม 2550
แถว 157:		แถว 157:
	::<math>t(</math>Δ<math>)</math> เป็นเซตของ node <math>u</math> ที่ <math>b(u)<=</math> &minus Δ		::<math>t(</math>Δ<math>)</math> เป็นเซตของ node <math>u</math> ที่ <math>b(u)<=</math> &minus Δ
	::<math>G_f(</math>Δ<math>)</math> เป็น residual graph ที่ทุก edge มี cap อย่างน้อย Δ		::<math>G_f(</math>Δ<math>)</math> เป็น residual graph ที่ทุก edge มี cap อย่างน้อย Δ
		+	:รูป?
		+	:หลังจาก Δ augment flow ที่เหลือไม่เกิน Δ
		+	:<math>G_f(</math>Δ<math>)</math> ไม่มี negative cost cycle → มี feasible price function
		+	:Δ<math>/2 = G_f(</math>Δ<math>/2)</math>
		+	:อาจมี negative cost cycle นั้นคือ <math>f</math> ไม่มี min cost บน <math>edge(x,y)</math> ที่ <math>C_d < 0</math>
		+	:<math>saturate(x,y)</math> สร้างคู่ demand excess

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:13, 6 ตุลาคม 2550
แถว 150:		แถว 150:
	Δ <math>=</math> Δ <math>/2</math>		Δ <math>=</math> Δ <math>/2</math>
	until Δ <math><1</math>		until Δ <math><1</math>
		+	== Capacity scalling min cost flow ==
		+	:แต่ละ node จะมี demand <math>b(u)</math>
		+	:โดย parameter Δ จะเติม flow ครั้งละ Δ
		+	:ให้
		+	::<math>s(</math>Δ<math>)</math> เป็นเซตของ node <math>u</math> ที่ <math>b(u)>=</math> Δ
		+	::<math>t(</math>Δ<math>)</math> เป็นเซตของ node <math>u</math> ที่ <math>b(u)<=</math> &minus Δ
		+	::<math>G_f(</math>Δ<math>)</math> เป็น residual graph ที่ทุก edge มี cap อย่างน้อย Δ

@@ แถว 110: / แถว 110: @@
 Running Time
-. หา shortest path O(mn) ต่อรอบ
+<br>1. หา shortest path O(mn) ต่อรอบ
-. augment flow ทั้งหมด <= mC รอบ
+<br>2. augment flow ทั้งหมด <= mC รอบ
-. ทำงานในเวลา O(n<math> m^2 </math>C)
+<br>3. ทำงานในเวลา O(n<math> m^2 </math>C)
 Lemma2: ในแต่ละรอบที่ augment flow f ที่ได้เป็น min cost flow

@@ แถว 110: / แถว 110: @@
 Running Time
 . หา shortest path O(mn) ต่อรอบ
 . augment flow ทั้งหมด <= mC รอบ
 . ทำงานในเวลา O(n<math> m^2 </math>C)
 Lemma2: ในแต่ละรอบที่ augment flow f ที่ได้เป็น min cost flow
@@ แถว 139: / แถว 139: @@
                -Cd(y,x)>=0
   นั้นคือ <math> { f^' } </math> เป็น min cost flow
 == Ford Fulkerson + Capacity Scalling ==
    มี parameter &Delta; เป็น scale บอกว่าจะ augment flow ใน path ครั้งละ &Delta; หน่วย

@@ แถว 71: / แถว 71: @@
 Cp(W)=C(W)
 หมายเหตุ : ยังไม่ได้ใส่รูป
-                       การใช้ reduced cost ไม่มีผลต่อการมีอยู่ของ negative cost cycle
+การใช้ reduced cost ไม่มีผลต่อการมีอยู่ของ negative cost cycle
 จะกล่าวว่า Price function P เป็น feasible price function ถ้า

@@ แถว 66: / แถว 66: @@
 <math> =P(V{0})+ \sum\limits_{i = 1}^k {(V{i-1},V{1})}-P(V{k})</math>
 <math> =P(V{0})+C(P)-P(V{k})</math>
 พิจารณา cycle W
-                        Cp(W)=C(W)
+Cp(W)=C(W)
 หมายเหตุ : ยังไม่ได้ใส่รูป
                         การใช้ reduced cost ไม่มีผลต่อการมีอยู่ของ negative cost cycle
@@ แถว 86: / แถว 85: @@
 พิจารณา price function p ใดๆ พิจารณา negative cost cycle W  Cp(W)=C(W)<0 นั่นคือมีบาง edge
 :<math> {e \in W} </math>
-    ที่ Cp(e) < 0
+ที่ Cp(e) < 0
 นั่นคือ p ไม่ feasible

@@ แถว 141: / แถว 141: @@
   นั้นคือ <math> { f^' } </math> เป็น min cost flow
 == Ford Fulkerson + Capacity Scalling ==
-มี parameter &Delta; เป็น scale บอกว่าจะ augment flow ใน path ครั้งละ &Delta; หน่วย
+  มี parameter &Delta; เป็น scale บอกว่าจะ augment flow ใน path ครั้งละ &Delta; หน่วย
-ให้ &Delta; <math>= m.u</math>
+  ให้ &Delta; <math>= m.u</math>, <math>f = </math>Zero flow
-<math>f = </math>Zero flow
+  Repeat
-Repeat
+    Repeat
-Repeat
+      หา <math>Gf</math>, หา augmenting path ที่มี cap <math>>=</math> &Delta;
-หา <math>Gf</math>, หา augmenting path ที่มี cap <math>>=</math> &Delta;
+      เติม augment &Delta; หน่วย
-เติม augment &Delta; หน่วย
+    until หา augmenting path ขนาด &Delta; ไม่ได้
-until หา augmenting path ขนาด &Delta; ไม่ได้
+  &Delta; <math>=</math> &Delta; <math>/2</math>
-&Delta; <math>=</math> &Delta; <math>/2</math>
+  until &Delta; <math><1</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:04, 6 ตุลาคม 2550
แถว 140:		แถว 140:
	-Cd(y,x)>=0		-Cd(y,x)>=0
	นั้นคือ <math> { f^' } </math> เป็น min cost flow		นั้นคือ <math> { f^' } </math> เป็น min cost flow
		+	== Ford Fulkerson + Capacity Scalling ==
		+	มี parameter Δ เป็น scale บอกว่าจะ augment flow ใน path ครั้งละ Δ หน่วย
		+	ให้ Δ <math>= m.u</math>
		+	<math>f = </math>Zero flow
		+	Repeat
		+	Repeat
		+	หา <math>Gf</math>, หา augmenting path ที่มี cap <math>>=</math> Δ
		+	เติม augment Δ หน่วย
		+	until หา augmenting path ขนาด Δ ไม่ได้
		+	Δ <math>=</math> Δ <math>/2</math>
		+	until Δ <math><1</math>

@@ แถว 98: / แถว 98: @@
 ::<math>C</math><sub>D</sub><math>(u,v) = D(u) + C(u,v) - D(v)</math>
-== Ford Fulkerson + Capacity Scalling ==
 == Successive Shortest Path ==

@@ แถว 1: / แถว 1: @@
 ----
 '''จดบันทึกคำบรรยายโดย:'''
-:นาย
+:นาย ชาคริต กิตโร รหัส 50653757
 :นาย รักพงค์ แก้วพวง  รหัส 50653880
 <br />