ผลต่างระหว่างรุ่นของ "01204512/weight bipartite matching"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
: ''เอกสารนี้เป็นส่วนหนึ่งของวิชา [[01204512]]'' | : ''เอกสารนี้เป็นส่วนหนึ่งของวิชา [[01204512]]'' | ||
| + | |||
| + | ==Primal และ Dual linear programs== | ||
เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math> | เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math> | ||
| แถว 5: | แถว 7: | ||
เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร <math>x(u,v)</math> มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก | เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร <math>x(u,v)</math> มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก | ||
| − | * | + | * Maximize <math>\sum_{(u,v)\in E} w(u,v)\cdot x(u,v)</math> |
* Subject to: | * Subject to: | ||
| − | ** | + | ** for all <math>u\in U</math>, <math>\sum_{(u,v)\in E} x(u,v)=1</math> |
| − | ** | + | ** for all <math>v\in V</math>, <math>\sum_{(u,v)\in E} x(u,v)=1</math> |
| − | ** | + | ** for all <math>(u,v)\in E</math>, <math>x(u,v)\in\{0,1\}</math> |
| + | |||
| + | |||
| + | เราจะ relax ปัญหาให้เป็น linear program โดยเปลี่ยนเงื่อนไขสุดท้ายเป็น | ||
| + | |||
| + | ** For all <math>(u,v)\in E</math>, <math>x(u,v)\geq 0</math> | ||
| + | |||
| + | จาก linear program ดังกล่าว เราสามารถหา dual program ได้ โดยสร้างตัวแปร <math>a(u)</math> สำหรับทุก ๆ <math>u\in U</math> (เงื่อนไขแรก) และตัวแปร <math>b(v)</math> สำหรับทุก ๆ <math>v\in V</math> (เงื่อนไขที่สอง) เนื่องจากเงื่อนไขเป็นสมการ (ไม่ใช่ อสมการ) ตัวแปร dual ทั้งสองจะเป็นแบบไม่ระบุขอบเขต | ||
| + | |||
| + | ด้านล่างเป็น dual linear program | ||
| + | |||
| + | * Minimize <math>\sum_{u\in U} a(u) + \sum_{v\in V} b(v)</math> | ||
| + | * Subject to: | ||
| + | ** for all <math>(u,v)\in E</math>, <math>a(u)+b(v)\geq w(u,v)</math> | ||
| + | |||
| + | ==Complementary slackness== | ||
| + | |||
| + | เงื่อนไข complementary slackness บอกเราว่าที่คู่ของคำตอบที่เป็น optimal solutions ของคู่ primal/dual linear programs, ถ้าตัวแปรใน primal มีค่าไม่เท่ากับศูนย์ เงื่อนไขที่สอดคล้องกับตัวแปรนั้นใน dual จะต้อง tight, นั่นคือเป็นจริงด้วยเครื่องหมายเท่ากับ | ||
| + | |||
| + | ในกรณีนี้ นั่นคือ ใน optimal solution ถ้า <math>x(u,v)\neq 0</math>, แล้วเราจะได้ว่า <math>a(u)+b(v)=w(u,v)</math> | ||
| + | |||
| + | เราจะพยายามใช้ complementary slackness นำทางเราไปสู่คำตอบ โดยเราจะเลือกเส้นเชื่อมใส่ใน matching ก็ต่อเมื่อตัวแปร dual ของเราบนเส้นเชื่อมนั้นสอดคล้องกับ complementary slackness นั่นคือ เส้นเชื่อมนั้น tight (i.e., <math>a(u)+b(v)=w(u,v)</math>) | ||
| + | |||
| + | ==Primal-dual algorithms== | ||
รุ่นแก้ไขปัจจุบันเมื่อ 04:47, 8 สิงหาคม 2555
- เอกสารนี้เป็นส่วนหนึ่งของวิชา 01204512
Primal และ Dual linear programs
เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph ที่มีน้ำหนัก บนเส้นเชื่อม
เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก
- Maximize
- Subject to:
- for all ,
- for all ,
- for all ,
เราจะ relax ปัญหาให้เป็น linear program โดยเปลี่ยนเงื่อนไขสุดท้ายเป็น
- For all ,
จาก linear program ดังกล่าว เราสามารถหา dual program ได้ โดยสร้างตัวแปร สำหรับทุก ๆ (เงื่อนไขแรก) และตัวแปร สำหรับทุก ๆ (เงื่อนไขที่สอง) เนื่องจากเงื่อนไขเป็นสมการ (ไม่ใช่ อสมการ) ตัวแปร dual ทั้งสองจะเป็นแบบไม่ระบุขอบเขต
ด้านล่างเป็น dual linear program
- Minimize
- Subject to:
- for all ,
Complementary slackness
เงื่อนไข complementary slackness บอกเราว่าที่คู่ของคำตอบที่เป็น optimal solutions ของคู่ primal/dual linear programs, ถ้าตัวแปรใน primal มีค่าไม่เท่ากับศูนย์ เงื่อนไขที่สอดคล้องกับตัวแปรนั้นใน dual จะต้อง tight, นั่นคือเป็นจริงด้วยเครื่องหมายเท่ากับ
ในกรณีนี้ นั่นคือ ใน optimal solution ถ้า , แล้วเราจะได้ว่า
เราจะพยายามใช้ complementary slackness นำทางเราไปสู่คำตอบ โดยเราจะเลือกเส้นเชื่อมใส่ใน matching ก็ต่อเมื่อตัวแปร dual ของเราบนเส้นเชื่อมนั้นสอดคล้องกับ complementary slackness นั่นคือ เส้นเชื่อมนั้น tight (i.e., )
