ขั้นตอนวิธีการผลักดัน - ติดป้ายใหม่

**ขั้นตอนวิธีการผลักดัน - ติดป้ายใหม่** () เป็นหนึ่งในกลไกที่มีประสิทธิภาพมากที่สุดเพื่อคำนวณการไหลสูงสุด

## ขั้นตอนวิธี
กำหนดให้การไหลของเครือข่าย *G(V,E)* ที่มีความจุจากปม *u* ไปยัง ปม *v* ให้เป็น *c(u,v)* , เราต้องการหาปริมาณการไหลสูงสุดจากจุดเริ่มต้นที่ปม *s* ไปยังจุดสิ้นสุดที่ปม *t* ภายในเครือข่าย
โดยใช้การดำเนินการ 2 อย่าง คือ การผลักดัน และ การติดป้ายใหม่ ดังนี้
* ***f(u,v)*** คือการไหลจากปม *u* ไปที่ปม *v* โดยให้ความจุที่ได้คือ *c(u,v) − f(u,v)*
* ***height(u)*** ถ้าเงื่อนไข *height(u) > height(v)* เราจะทำการผลักดันจากปม *u* ไปปม *v* เท่านั้น โดยที่ สำหรับทุกปม *u* จะทำให้ *height(u)* เป็นจำนวนเต็มที่ไม่ติดลบ
* ***excess(u)*** คือผลรวมการไหลทั้งเข้าและออกจาก *u*

ในแต่ละขึ้นตอนของขั้นตอนวิธีนั้น จะทำการไหลก่อนล่วงหน้า เพื่อให้ผลคำนวณเป็นไปตามที่เราต้องการ ดังนี้
* ***f(u,v) ≤ c(u,v)*** คือ การไหลจากปม *u* ไปปม *v* นั้น ต้องไม่เกินความจุจากปม *u* ไปปม *v*
* ***f(u,v) = -f(v,u)*** เราจะคงค่าการไหลไว้ คือ ไหลไปในทิศทางเดียว ถ้าไหลย้อนกลับ ค่าการไหลนั้นจะติดลบ ซึ่งก็คือ ไหลย้อนทางนั่นเอง
* ***∑ f(v,u) = excess(u) ≥ 0*** สำหรับปม *u ≠ s* ที่เป็นจุดเริ่มต้นของการไหลเท่านั้น
ขอให้สังเกตว่าเงื่อนไขที่ทำการไหลก่อนล่วงหน้านี้ เป็นการผ่อนคลายจากสภาพที่สอดคล้องกันสำหรับ กฎการไหล ในเครือข่ายของการไหลปกติ
เราสังเกตเห็นว่าเส้นทางที่ยาวมากที่สุดที่เป็นไปได้จากปม *s* ไปปม *t* คือ ขนาดของปม | *V* |
ดังนั้นเป็นไปได้ที่จะกำหนดความสูงให้กับปม ตามกฎของการไหล ดังนี้ *height(s) = | V |* และ *height(t) = 0*
และถ้าค่าการไหลจากปม *u* ไปปม *v* นั้นเป็นบวก คือ *height(u) > height(v)* เราจะปรับความสูงของปม เหมือนกับการไหลของน้ำที่ไหลลงพื้น
ความสูงของปม ( ยกเว้นปม *s* และปม *t* ) จะถูกปรับ และการไหลจะถูกส่งระหว่างปมจนกระทั่งถึงปม *t* จากนั้นเราจะทำการเพิ่มความสูงของปมที่อยู่ภายในจนกระทั่งทุกปมในเครือข่ายที่ไม่ถึงปม *t* มีการไหลย้อนกลับไปสู่ปม *s*
ปมสามารถทำให้ความสูงถึง *2| V | − 1* ก่อนที่จะเสร็จสมบูรณ์ คือ ความยาวสูงสุดที่เป็นไปได้ของเส้นทางที่กลับมาที่ปม *s* รวมปม *t* ด้วย ยาวเท่ากับ *| V | − 1* และมี *height(s) = | V |, height(t) = 0*

## การผลักดัน
การผลักดันจากปม *u* ไปปม *v* ซึ่งหมายถึงการส่งส่วนหนึ่งของการไหลที่เกินจากปม *u* ไปปม *v* โดยทั้ง 3 เงื่อนไขข้างล่างนี้ต้องเป็นจริงจึงจะเกิดการผลักดัน
* ***excess(u) > 0*** คือ การไหลเข้าปม *u* มากกว่า การไหลออกปม *u*
* ***c(u,v) − f(u,v) > 0*** มีความจุที่เป็นค่าบวกจากปม *u* ไปปม *v*
* ***height(u) > height(v)*** คือ ต้องส่งผ่านไปยังปมที่ต่ำกว่าเท่านั้น
เราจะส่งปริมาณการไหลเท่ากับ *min( excess(u), c(u,v) − f(u,v) )*

## การติดป้ายใหม่
ทำการติดป้ายใหม่บนปม *u* ที่เพิ่มขึ้นจนกว่าจะมีความสูงอย่างน้อย 1 ปมที่มีความจุที่มีค่าเป็นจำนวนบวก โดยมีเงื่อนไขของการติดป้ายใหม่ดังนี้
* ***excess(u) > 0*** ต้องมีจุดที่ทำการติดป้ายใหม่ได้
* ***height(u) ≤ height(v)*** สำหรับทุกปม *v* ที่ *c(u,v) − f(u,v) > 0* เฉพาะปมที่มีความจุสูงกว่า
เมื่อทำการติดป้ายใหม่นั้น เราจะทำการกำหนดให้ *height(u)* เป็นค่าที่น้อยที่สุด ดังที่ว่า *height(u) > height(v)* สำหรับบางปม *v* ที่ *c(u,v) − f(u,v) > 0*

## ขั้นตอนวิธีการผลักดัน - ติดป้ายใหม่
โดยทั่วไปมีรูปแบบดังต่อไปนี้
# ตราบใดที่ยังมีกฎการผลักดัน หรือ การดำเนินการติดป้ายใหม่ ให้ทำดังนั้
## ทำตามกฎการผลักดัน หรือ
## กฎการติดป้ายใหม่
เวลาการทำงานสำหรับขั้นตอนวิธีนี้อยู่ในรูปทั่วไป *O(V2E)* (อาร์กิวเมนต์ละเว้น)

## การติดป้ายใหม่ทางด้านหน้า
การติดป้ายด้านหน้าบนปม *u* ทำได้ดังนี้
# ตราบเท่าที่ *excess(u) > 0*
## หากยังไม่ติดป้ายใหม่ให้กับทุกปมที่มีเส้นเชื่อมต่อกับ *u*
### ให้ลองผลักดันในปมที่ยังไม่ได้ลอง
## ถ้าลองครบทุกปมแล้ว
### ให้ทำการติดป้ายที่ปม *u* ใหม่
ต้องทราบว่าตอนติดป้ายใหม่ครั้งล่าสุดนั้นเราได้ลองปมใดไปบ้าง

## ขั้นตอนวิธีการติดป้ายใหม่ทางด้านหน้า โดยใช้การช่วยค้นหาแบบเข้ามาก่อนออกก่อน
โดยมีลำดับการผลักดัน และ ติดป้ายใหม่ ดังนี้
# ส่งค่าการไหลที่มากที่สุดที่เป็นไปได้
# สร้างรายการของทุกปม ยกเว้นปม *s* และปม *t*
# ตราบเท่าที่เรายังไม่ได้ไปทุกปมที่อยู่ในรายการ ให้ทำดังนี้
## ติดป้ายใหม่ทางด้านหน้าให้กับปมปัจจุบัน
## ถ้าความสูงของปมปัจจุบันเปลี่ยนแปลง ให้ทำดังนี้
### ย้ายปมปัจจุบันไปไว้หน้าสุดของรายการ
### ทำการเริ่มต้นใหม่ตั้งแต่ปมแรกของรายการ
เวลาในการทำงานของการติดป้ายใหม่ทางด้านหน้า เป็น *O(V<sup>3</sup>)*

## อ้างอิง
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.
* Jon Kleinberg & Eva Tardos. Algorithm Design. Pearson International Edition. Addison Wesley, 2006. ISBN 0-321-37291-3. Section 7.4: The Preflow-Push Maximum-Flow Algorithm.

หมวดหมู่:การไหลในเครือข่าย
หมวดหมู่:ขั้นตอนวิธีกราฟ