ขั้นตอนวิธีฮังกาเรียน
บทความนี้ต้องการการจัดหน้า จัดหมวดหมู่ ใส่ลิงก์ภายใน หรือเก็บกวาดเนื้อหา ให้มีคุณภาพดีขึ้น คุณสามารถปรับปรุงแก้ไขบทความนี้ได้ และนำป้ายออก พิจารณาใช้ป้ายข้อความอื่นเพื่อชี้ชัดข้อบกพร่อง |
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ขั้นตอนวิธีชาวฮังกาเรียน หรือ ฮังกาเรียนอัลกอริทึม (อังกฤษ: Hungarian Algorithm ) คือ ขั้นตอนวิธีการหาค่าเหมาะสมที่สุดเชิงการจัด ซึ่งใช้ในการแก้ ปัญหาการกำหนดงาน ถูกคิดค้นและตั้งชื่อโดย แฮโรลด์ วิลเลียม คุห์น ในปี ค.ศ. 1955 ที่ตั้งชื่อนี้เพราะว่าขั้นตอนวิธีนี้มีพื้นฐานส่วนใหญ่จากการคิดของนักคณิตศาสตร์ชาวฮังกาเรียน 2 คน คือ เดแนช เคอนิก (Dénes Kőnig) และ แยเนอ แอแกร์วารี (Jenő Egerváry) ต่อมาเจมส์ มุนเครสได้นำขั้นตอนวิธีนี้มาตรวจสอบในปี ค.ศ. 1957 และได้พบว่ามีประสิทธิภาพเชิงเวลาเป็นแบบ strongly polynomial ตั้งแต่นั้นมาขั้นตอนวิธีนี้จึงเป็นที่รู้จักในชือว่า ขั้นตอนวิธีคุห์น-มุนเครส หรือ ขั้นตอนวิธีการกำหนดงานมุนเครส โดยมีประสิทธิภาพเชิงเวลาของขั้นตอนวิธีดั้งเดิมเป็น แต่อย่างไรก็ตามขั้นตอนวิธีนี้ แจ็ค เอดมันด์ และ ริชาร์ด แมนนิ่งคาร์ป ได้สามารถปรับปรุงให้มีประสิทธิภาพเชิงเวลาเป็น ได้ และในปี ค.ศ. 2006 มีการค้นพบว่า คาร์ล กุสตาฟ จาโคบี (Carl Gustav Jacobi) สามารถแก้ปัญหาการกำหนดงานได้ในคริสต์ศตวรรษที่ 19 และได้เผยแพร่ในปี ค.ศ. 1890 ในภาษาละติน
ปัญหาการกำหนดงาน[แก้]
ขั้นตอนวิธีฮังกาเรียนนี้ใช้แก้ปัญหาการกำหนดงาน ซึ่งเป็นปัญหาชนิดพิเศษของปัญหากำหนดการเชิงเส้นอีกลักษณะหนึ่ง มีรูปแบบคล้ายคลึงกับปัญหาการขนส่ง โดยปัญหาการกำหนดงานจะมีลักษณะดังนี้
- จำนวนงานและจำนวนคนงานเท่ากัน ในกรณีที่ไม่เท่าจะต้องเพิ่มงานหรือคนงานสมมติแล้วแต่ว่าส่วนใดขาดหายไปและให้ต้นทุนการกำหนดงานมากที่สุด
- คนงานจะทำงานได้เพียง 1 งาน
- งานแต่ละงานจะมีคนรับผิดชอบเพียงคนเดียว
- มีต้นทุนการกำหนดงาน ให้ ทำเป็น ซึ่งมีเป้าหมายของการกำหนดงานคือการทำให้เกิดต้นทุนน้อยที่สุด หรือเราสามารถดัดแปลงให้หาค่าต้นทุนมากที่สุดได้
ยกตัวอย่างเช่น สมมติให้มีคนงาน 3 คน คือ สมชาย สมหญิง และสมคิด แล้วมีงาน 3 งานคือ ล้างห้องน้ำ ถูพื้น และเช็ดกระจก เราจะกำหนดงานให้แต่ละคนอย่างไรจึงจะเกิดต้นทุนน้อยที่สุด โดยจะแทนต้นทุนการกำหนดต่างๆด้วยเมทริกซ์ ดังนี้
ล้างห้องน้ำ | ถูพื้น | เช็ดกระจก | |
สมชาย | 100 | 200 | 300 |
สมหญิง | 300 | 300 | 300 |
สมคิด | 300 | 300 | 200 |
เมื่อเราใช้ขั้นตอนวิธีฮังกาเรียนแล้วจะได้ผลลัพธ์การกำหนดงานให้คนงานแต่ละคน ซึ่งจะเกิดต้นทุนน้อยที่สุดดังนี้ สมชายล้างห้องน้ำ สมหญิงถูพื้น สมคิดเช็ดกระจก
อธิบายขั้นตอนวิธี[แก้]
- ขั้นตอนวิธีนี้จะต้องมีจำนวนงานและคนงานเท่ากัน หากมีอย่างใดอย่างหนึ่งน้อยกว่าแล้ว เราจำเป็นต้องเพิ่มตัวลวงเข้าไปให้มีจำนวนที่เท่ากัน โดยต้นทุนของตัวลวงนี้จะมีค่าเป็นต้นทุนที่มากที่สุดในตาราง
- หากเราไม่ต้องการหาต้นทุนน้อยสุด แต่ต้องการหาต้นทุนมากสุดเราสามารถทำได้โดย แก้ไขตารางต้นทุนในแต่ละช่องโดยสมมติให้ MAX คือค่าที่มากที่สุดในตาราง สมาชิกช่องที่ i,j จะมีค่าใหม่เป็น (MAX - สมาชิกข่องที่ i,j)
เมื่อเรามีตารางต้นทุนของการทำงานทุกงานของทุกคนงานแล้วเราจะมาทำตามลำดับขั้นตอนดังนี้
- เราจะหาค่าที่น้อยสุดในแต่ละแถวแล้วนำมาลบกับทุกๆสมาชิกในแต่ละแถวนั้นๆ ดังนั้นจะได้ตารางใหม่ที่มีสมาชิกในแต่ละแถวมีค่าเป็น 0 อย่างน้อย 1 ตัว
- ต่อจากนั้นเราจะทำแบบเดียวกับขั้นตอนที่ 1 ในทุกๆคอลัมน์ คือหาค่าที่น้อยที่สุดในแต่ละคอลัมน์แล้วนำมาลบกับสมาชิกทุกตัวในคอลัมน์นั้นๆ
- หากเรากำหนดงานให้คนงานได้โดยใช้เลข 0 เป็นตัวบอกว่าคนงานใดทำงานใดได้บ้างถึงจะต้นทุนน้อยสุด แล้วสามารถกำหนดงานให้ได้โดยไม่ซ้ำกันแล้ว แสดงว่าเราได้คำตอบอันเป็นที่ต้องการแล้ว ซึ่งอาจจะมีคำตอบได้หลายแบบ แต่ถ้าหากยังไม่สามารถกำหนดงานให้ได้โดยไม่ซ้ำกัน เราต้องขีดเส้นในแถวหรือคอลัมน์ใดๆให้ผ่าน 0 ครบทุกตัว โดยใช้จำนวนเส้นน้อยที่สุด ดังนี้
- ให้เราเลือกแถวที่สามารถกำหนดงานให้ได้โดยไม่ซ้ำกันเท่าที่เป็นไปได้
- จากนั้นเราจะดูแถวที่ไม่ได้เลือกไว้ และให้ทำสัญลักษณ์ที่แถวนั้น
- เราจะดูว่ามีค่า 0 อยู่ในคอลัมน์ใดบ้างในแถวที่เราทำสัญลักษณ์ แล้วเราจะทำสัญลักษณ์ที่คอลัมน์นั้น
- ดูที่คอลัมน์ที่ทำสัญลักษณ์ไว้ หากแถวใดมี 0 ก็ทำสัญลักษณ์ที่แถวนั้นด้วย
- วนทำจนไม่สามารถทำสัญลักษณ์ได้
- ให้เราขีดเส้นในคอลัมน์ที่สัญลักษณ์ และขีดเส้นแถวที่ไม่ได้ทำสัญลักษณ์ จะได้จำนวนเส้นน้อยสุด (หากว่าได้จำนวนเส้นเท่ากับจำนวนงานแล้วแสดงว่าเราได้คำตอบที่ต้องการแล้ว ให้ข้ามไปยังขั้นตอน 5)
- เราจะหาสมาชิกในช่องที่ไม่ได้ถูกขีดเส้นและมีค่าน้อยสุด นำไปลบกับสมาชิกทุกตัวที่ไม่ได้ถูกขีดเส้น และนำไปบวกับสมาชิกทุกตัวที่ถูกขีดทับสองเส้น และทำตามขั้นตอนที่ 3-4 ใหม่ จนสามารถกำหนดงานได้โดยไม่ซ้ำกันแล้วจึงไปยังขั้นตอนที่ 5
- เมื่อเราได้ตารางที่สามารถขีดเส้นผ่าน 0 ครบทุกตัวโดยใช้จำนวนเส้นเท่ากับจำนวนงานแล้ว หมายความว่าเราได้ตารางซึ่งเป็นคำตอบแล้วคือสามารถกำหนดงานให้คนงานโดยไม่ซ้ำกันและมีต้นทุนน้อยสุด โดยดูว่าช่องใดเป็น 0 ก็คือให้คนงานทำงานนั้นได้ ซึ่งอาจมีคำตอบได้มากกว่า 1 แบบ
ตัวอย่างการใช้ขั้นตอนวิธี[แก้]
ตัวอย่างการทำขั้นตอนวิธีฮังกาเรียน สมมติให้มีคนงาน ก ข ค ง แ และมี งาน ๑ ๒ ๓ ๔ โดยมีตารางต้นทุนดังนี้
๑ | ๒ | ๓ | ๔ | |
---|---|---|---|---|
ก | 32 | 27 | 29 | 30 |
ข | 28 | 34 | 26 | 22 |
ค | 22 | 24 | 20 | 29 |
ง | 31 | 27 | 29 | 26 |
โดยต่อไปจะขอละตัวระบุคนงานและตัวระบุงานซึ่งยังมีลำดับเหมือนตารางข้างต้น
1. หาค่าน้อยสุดในแต่ละแถวแล้วนำมาลบออกจากสมาชิกทุกๆตัวในแถว จะได้ตารางใหม่เป็น
5 | 0 | 2 | 3 | |
6 | 12 | 4 | 0 | |
2 | 4 | 0 | 9 | |
5 | 1 | 3 | 0 |
2. จากนั้นหาค่าน้อยสุดในแต่ละคอลัมน์แล้วนำมาลบออกจากสมาชิกทุกๆตัวในคอลัมน์ จะได้ตารางใหม่เป็น
3 | 0 | 2 | 3 | |
4 | 12 | 4 | 0 | |
0 | 4 | 0 | 9 | |
3 | 1 | 3 | 0 |
3. แล้วเรายังไม่สามารถจัดงานให้คนงานให้มีต้นทุนน้อยสุดโดยไม่ซ้ำกันได้ จึงต้องทำขั้นต่อไป
3 | 0 | 2 | 3 | |
4 | 12 | 4 | 0 | |
0 | 4 | 0 | 9 | |
3 | 1 | 3 | 0 |
4. เลือกแถวที่สามารถกำหนดงานโดยไม่ซ้ำกันเท่าที่เป็นไปได้ คือแถว 1 2 และ 3
→ | 3 | 0 | 2 | 3 |
→ | 4 | 12 | 4 | 0 |
→ | 0 | 4 | 0 | 9 |
3 | 1 | 3 | 0 |
5. แล้วทำสัญลักษณ์ที่แถวที่ไม่ได้เลือกไว้ คือแถวที่ 4 แล้วทำสัญลักษณ์ที่คอลัมน์ 4 ที่มีค่า 0 อยู่ จากนั้นดูที่คอลัมน์ 4 พบว่ามี 0 อยู่แถวที่ 2 จึงทำสัญลักษณ์ในแถวที่ 2 แล้วไม่มีค่า 0 ที่คอลัมน์อื่น จึงไปทำขั้นต่อไป
× | ||||
3 | 0 | 2 | 3 | |
× | 4 | 12 | 4 | 0 |
0 | 4 | 0 | 9 | |
× | 3 | 1 | 3 | 0 |
6. จากนั้นขีดเส้นให้เราขีดเส้นในคอลัมน์ที่สัญลักษณ์ และขีดเส้นแถวที่ไม่ได้ทำสัญลักษณ์
× | ||||
3 | 0 | 2 | 3 | |
× | 4 | 12 | 4 | 0 |
0 | 4 | 0 | 9 | |
× | 3 | 1 | 3 | 0 |
7. จะใช้สมาชิกในช่องที่ไม่ได้ถูกขีดเส้นและมีค่าน้อยสุด คือค่า 1 ลบออกจากสมาชิกทุกตัวที่ไม่ถูกขีดเส้นและ นำไปบวกเข้ากับสมาชิกที่ถูกขีดเส้นสองครั้ง
× | ||||
3 | 0 | 2 | 4 | |
× | 3 | 11 | 3 | 0 |
0 | 4 | 0 | 10 | |
× | 2 | 0 | 2 | 0 |
8. จากนั้นจะวนทำจนสามารถกำหนดงานได้โดยไม่ซ้ำ จึงได้ตารางดังนี้ เป็นตารางที่สามารถกำหนดงานให้คนงานได้โดยไม่ซ้ำกันและจะใช้ต้นทุนน้อยที่สุดด้วย โดยค่า 0 บอกถึงว่าคนงานต้องทำงานนั้นๆ หากมีหลายตัวคือทำสามารถได้หลายงาน ทำให้อาจจะมีคำตอบออกมาได้หลายแบบ
1 | 0 | 0 | 4 | |
1 | 11 | 1 | 0 | |
0 | 6 | 0 | 12 | |
0 | 0 | 0 | 0 |
และจากตารางจะได้คำตอบทั้งหมด 3 แบบ ดังนี้
ผลเฉลยที่ 1 | ผลเฉลยที่ 2 | ผลเฉลยที่ 3 | |||
กำหนดงาน | ต้นทุน | กำหนดงาน | ต้นทุน | กำหนดงาน | ต้นทุน |
ก → ๒ | 27 | ก → ๒ | 27 | ก → ๓ | 29 |
ข → ๔ | 22 | ข → ๔ | 22 | ข → ๔ | 22 |
ค → ๑ | 22 | ค → ๓ | 20 | ค → ๑ | 22 |
ง → ๓ | 29 | ง → ๑ | 31 | ง → ๒ | 27 |
รวม | 100 | รวม | 100 | รวม | 100 |
รหัสเทียม[แก้]
สำหรับทุกๆแถวของตาราง หาค่าที่น้อยสุดในแถวแล้วไปลบออกจากสมาชิกในแถวทุกตัว สำหรับทุกๆคอลัมน์ของตาราง หาค่าที่น้อยสุดในคอลัมน์แล้วไปลบออกจากสมาชิกในคอลัมน์ทุกตัว ตราบเท่าที่ จำนวนคนงานที่กำหนดงานให้ได้โดยไม่ซ้ำกัน < จำนวนงาน { ลากเส้นผ่าน 0 ทุกตัวโดยใช้เส้นน้อยสุด หาค่าที่น้อยที่สุดที่ไม่ถูกลากเส้นผ่านนำไปลบกับสมาชิกทุกตัวที่ไม่ถูกลากเส้นผ่าน และไปบวกกับสมาชิกทุกตัวที่ถูกลากเส้นผ่าน 2 เส้น } ฟังก์ชัน หาจำนวนคนงานที่กำหนดงานได้โดยไม่ซ้ำกัน ให้ n คือ จำนวนงาน, count คือ ตัวนับจำนวนคนงานที่สามารถกำหนดงานให้ได้โดยไม่ซ้ำ { แถวข้อมูลกำหนดงาน[n] = -1 แถวกำกับ[n] = 0 คอลัมน์กำกับ[n] = 0 สำหรับทุกๆคนงาน i = 0 to n -1 สำหรับทุกๆงาน j = 0 to n -1 ถ้า ตาราง[i][j] เท่ากับ 0 และ แถวกำกับ[i] กับ คอลัมน์กำกับ[j] ไม่เท่ากับ 1 { แถวข้อมูลกำหนดงาน[i] = j (คนงาน i ทำงาน j) แถวกำกับ[i] = แถวกำกับ[j] = 1 count++ } ถ้า count ไม่เท่ากับจำนวนงาน คืนค่า count หรือถ้า count เท่ากับจำนวนงานแล้ว คืน แถวข้อมูลกำหนดงาน } ฟังก์ชัน ลากเส้นผ่าน 0 ทุกตัวโดยใช้จำนวนเส้นน้อยสุด คืนค่าเป็นรายการของแถวและคอลัมน์ที่ลากเส้นผ่าน { เลือกแถวที่ไม่สามารถกำหนดงานให้ได้โดยไม่ซ้ำทำสัญลักษณ์ไว้ ตราบเท่าที่ ยังสามารถทำสัญลักษณ์ที่แถวหรือคอลัมน์ใดๆได้ { ทำสัญลักษณ์ที่คอลัมน์ที่มีค่า 0 ในแถวที่ทำสัญลักษณ์ไว้ ที่คอลัมน์ที่ทำสัญลักษณ์ไว้ หากแถวใดมี 0 ก็ทำสัญลักษณ์ที่แถวนั้นด้วย } ลากเส้นคอลัมน์ที่ทำสัญลักษณ์ และแถวที่ไม่ได้ทำสัญลักษณ์ คืนรายการของแถวและคอลัมน์ที่ลากเส้นผ่าน }
วิเคราะห์ประสิทธิภาพเชิงเวลา[แก้]
ขั้นตอนวิธีนี้มีขั้นตอนย่อยๆหลายขั้นตอน
- การลบสมาชิกทุกตัวด้วยสมาชิกที่มีค่าน้อยสุดในแต่ละแถวและคอลัมน์จะใช้เวลา
- แล้วฟังก์ชันหาจำนวนคนงานที่กำหนดงานได้ก็ใช้เวลา
- การลากเส้นผ่าน 0 ทุกตัวโดยใช้เส้นโดยที่สุดนั้นจะใช้เวลา โดยจะทำเป็นจำนวนอย่างมากไม่เกินจำนวนงานครั้ง ทำให้ในวงวนนี้ใช้เวลา
ดังนั้นสรุปแล้วประสิทธิภาพโดยรวมของขั้นตอนวิธีนี้เป็น
อ้างอิง[แก้]
- Beryl Castello, The Hungarian Algorithm เก็บถาวร 2011-07-19 ที่ เวย์แบ็กแมชชีน
- Hungarian Algorithm tutorial
แหล่งข้อมูลอื่น[แก้]
- Mordecai J. Golin, Bipartite Matching and the Hungarian Method, Course Notes, Hong Kong University of Science and Technology.
- R. A. Pilgrim, Munkres' Assignment Algorithm. Modified for Rectangular Matrices เก็บถาวร 2007-03-27 ที่ เวย์แบ็กแมชชีน, Course notes, Murray State University.
- Mike Dawes, The Optimal Assignment Problem เก็บถาวร 2006-08-12 ที่ เวย์แบ็กแมชชีน, Course notes, University of Western Ontario.
- On Kuhn's Hungarian Method – A tribute from Hungary เก็บถาวร 2017-08-09 ที่ เวย์แบ็กแมชชีน, András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
ตัวอย่าง ซอร์สโค้ด เพิ่มเติม[แก้]
- Java implementation
- Python implementation (ดูเพิ่มเติม ที่นี่ เก็บถาวร 2011-09-30 ที่ เวย์แบ็กแมชชีน)
- Ruby implementation with unit tests
- C# implementation
- Online interactive implementation
- Serial and parallel implementations.
- Implementation in Matlab and C เก็บถาวร 2008-05-03 ที่ เวย์แบ็กแมชชีน
- Perl implementation
- Lisp implementation เก็บถาวร 2007-03-25 ที่ เวย์แบ็กแมชชีน
- C++ implementation
- Another C++ implementation with unit tests
- Another Java implementation with JUnit tests (Apache 2.0)[ลิงก์เสีย]
- Matlab implementation เก็บถาวร 2012-08-14 ที่ เวย์แบ็กแมชชีน