ในคณิตศาสตร์เศรษฐศาสตร์และวิทยาศาสตร์คอมพิวเตอร์โดยเฉพาะอย่างยิ่งในสาขาทฤษฎีเกมเชิงผสมและอัลกอริทึมปัญหาเพื่อนร่วมห้องที่เสถียร ( Stable -Roommate Problem หรือ SRP ) คือปัญหาการหาคู่ที่เสถียรสำหรับเซตที่มีขนาดเป็นเลขคู่ การจับคู่คือการแบ่งเซตออกเป็นคู่ที่ไม่ซ้ำกัน ("เพื่อนร่วมห้อง") การจับคู่จะเสถียรหากไม่มีองค์ประกอบสองตัวใดที่ไม่ใช่เพื่อนร่วมห้องและทั้งสองตัวต่างก็ชอบกันเองมากกว่าเพื่อนร่วมห้องของตนภายใต้การจับคู่นั้น ซึ่งแตกต่างจากปัญหาการจับคู่ที่เสถียร (ปัญหาการแต่งงานที่เสถียร) ตรงที่ปัญหาเพื่อนร่วมห้องที่เสถียรอนุญาตให้จับคู่ระหว่างองค์ประกอบสองตัวใดๆ ก็ได้ ไม่ใช่เฉพาะระหว่างกลุ่มชายและหญิงเท่านั้น

โดยทั่วไปมักกล่าวไว้ดังนี้:

ในปัญหาการหาเพื่อนร่วมห้องที่มั่นคง (Stable-Roommates Problem: SRP) ผู้เข้าร่วม 2nคนจะจัดลำดับความชอบของกันและกันอย่างเคร่งครัด การจับคู่ (Matching) คือเซตของคู่ผู้เข้าร่วมที่ไม่ซ้ำกันn คู่ การจับคู่ Mในปัญหา SRP จะมั่นคงหากไม่มีผู้เข้าร่วมxและyคู่ใดที่ต่างฝ่ายต่างชอบอีกฝ่ายมากกว่าคู่ของตนในMคู่ดังกล่าวเรียกว่าคู่ที่ขัดขวางMหรือเป็นคู่ที่ขัดขวางM

แตกต่างจากปัญหาการแต่งงานที่มั่นคงการจับคู่ที่มั่นคงอาจไม่เกิดขึ้นจริงสำหรับผู้เข้าร่วมบางกลุ่มและความชอบของพวกเขา ตัวอย่างง่ายๆ ของการจับคู่ที่มั่นคงที่ไม่มีอยู่จริง ลองพิจารณาคน 4 คน ได้แก่A , B , CและDซึ่งมีการจัดอันดับดังนี้:

A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)

ในการจัดอันดับนี้ A, B และ C แต่ละคนเป็นบุคคลที่เหมาะสมที่สุดสำหรับใครบางคน ในทุกๆ วิธีแก้ปัญหา หนึ่งใน A, B หรือ C จะต้องจับคู่กับ D และอีกสองคนจะต้องจับคู่กันเอง (ตัวอย่างเช่น AD และ BC) แต่สำหรับใครก็ตามที่จับคู่กับ D สมาชิกคนอื่นจะให้คะแนนพวกเขาไว้สูงที่สุด และคู่ของ D ก็จะชอบสมาชิกคนนั้นมากกว่า D ในตัวอย่างนี้ AC เป็นการจับคู่ที่เหมาะสมกว่า AD แต่การจับคู่ที่เหลือของ BD ก็ทำให้เกิดปัญหาเดียวกัน ซึ่งแสดงให้เห็นถึงการขาดการจับคู่ที่มั่นคงสำหรับผู้เข้าร่วมเหล่านี้และความชอบของพวกเขา

อัลกอริทึมที่มีประสิทธิภาพ ( Irving 1985 ) มีดังต่อไปนี้ อัลกอริทึมนี้จะตรวจสอบสำหรับปัญหาแต่ละกรณีว่ามีการจับคู่ที่เสถียรหรือไม่ และถ้ามี ก็จะค้นหาการจับคู่ดังกล่าว อัลกอริทึมของ Irving มีความซับซ้อนO( n² ⁾หากใช้โครงสร้างข้อมูลที่เหมาะสมในการจัดการรายการความชอบและการระบุการหมุนที่จำเป็น

อัลกอริทึมประกอบด้วยสองขั้นตอน ในขั้นตอนที่ 1 ผู้เข้าร่วมจะเสนอความสัมพันธ์ให้แก่กันและกัน ในลักษณะที่คล้ายกับอัลกอริทึม Gale–Shapleyสำหรับปัญหาการแต่งงานที่มั่นคงผู้เข้าร่วมแต่ละคนจะจัดลำดับสมาชิกคนอื่นๆ ตามลำดับความชอบ ส่งผลให้ได้รายการความชอบ ซึ่งเป็นชุดลำดับของผู้เข้าร่วมคนอื่นๆ จากนั้นผู้เข้าร่วมจะเสนอความสัมพันธ์ให้แก่แต่ละคนในรายการของตนตามลำดับ โดยจะดำเนินการต่อไปที่บุคคลถัดไปหากและเมื่อข้อเสนอปัจจุบันถูกปฏิเสธ ผู้เข้าร่วมจะปฏิเสธข้อเสนอหากพวกเขามีข้อเสนอจากคนที่พวกเขาชื่นชอบอยู่แล้ว ผู้เข้าร่วมจะปฏิเสธข้อเสนอที่เคยยอมรับแล้วหากพวกเขาได้รับข้อเสนอที่ตนเองชื่นชอบในภายหลัง ในกรณีนี้ ผู้เข้าร่วมที่ถูกปฏิเสธจะเสนอความสัมพันธ์ให้แก่บุคคลถัดไปในรายการของตนต่อไปเรื่อยๆ จนกว่าจะมีข้อเสนอใดได้รับการยอมรับอีกครั้ง หากผู้เข้าร่วมคนใดคนหนึ่งถูกปฏิเสธจากผู้เข้าร่วมคนอื่นๆ ทั้งหมดในที่สุด แสดงว่าไม่สามารถจับคู่ที่มั่นคงได้ มิเช่นนั้น ขั้นตอนที่ 1 จะสิ้นสุดลงโดยที่แต่ละคนมีข้อเสนอจากคนอื่นๆ อยู่แล้ว

พิจารณาผู้เข้าร่วมสองคน คือqและpถ้าqได้รับข้อเสนอจากpเราจะลบ ผู้เข้าร่วม xทั้งหมดหลังจากp ออกจากรายการ ของqและในทำนองเดียวกัน สำหรับผู้เข้าร่วมx ที่ถูกลบออกแต่ละคน เราจะลบq ออก จาก รายการ ของxด้วย เพื่อให้qอยู่ในลำดับแรกของ รายการ ของpและpอยู่ในลำดับสุดท้าย ของรายการ ของqเนื่องจากqและx ใดๆ ไม่สามารถเป็นคู่กันในการจับคู่ที่เสถียรได้ ชุดรายการลำดับความชอบที่ลดลงนี้เรียกว่า ตารางเฟส 1 ในตารางนี้ ถ้าในรายการที่ลดลงใดๆ ว่างเปล่า แสดงว่าไม่มีการจับคู่ที่เสถียร มิฉะนั้น ตารางเฟส 1 จะเป็นตารางที่เสถียรตามคำจำกัดความ ตารางที่เสถียรคือชุดรายการลำดับความชอบจากตารางเดิมหลังจากที่สมาชิกถูกลบออกจากรายการหนึ่งรายการหรือมากกว่า และเงื่อนไขสามข้อต่อไปนี้เป็นไปตามที่กำหนด (โดยที่รายการที่ลดลงหมายถึงรายการในตารางที่เสถียร):

(i) pจะเป็นคนแรกใน รายชื่อที่ลดรูป ของqก็ต่อเมื่อqเป็นคนสุดท้ายในรายชื่อของp (ii) pจะไม่อยู่ใน รายชื่อที่ลดรูป ของqก็ต่อเมื่อqไม่อยู่ใน รายชื่อ ของpก็ต่อเมื่อqชอบคนสุดท้ายในรายชื่อของตนมากกว่าpหรือpชอบคนสุดท้ายในรายชื่อของตนมากกว่าq (iii) ไม่มีรายชื่อใดว่างเปล่า

ตารางเสถียรมีคุณสมบัติสำคัญหลายประการ ซึ่งใช้เป็นเหตุผลในการอธิบายขั้นตอนที่เหลือ:

1. ตารางที่มีเสถียรภาพใดๆ จะต้องเป็นตารางย่อยของตารางเฟส 1 โดยที่ตารางย่อยนั้นเป็นตารางที่มีรายการลำดับความสำคัญของตารางย่อยเหมือนกับตารางหลัก แต่มีการลบชื่อบุคคลบางคนออกจากรายการของกันและกัน
2. ในตารางที่มีเสถียรภาพใดๆ หากทุกรายการที่ลดรูปแล้วมี บุคคล เพียงคนเดียว การจับคู่บุคคลแต่ละคนกับบุคคลเพียงคนเดียวในรายการของพวกเขาจะทำให้เกิดการจับคู่ที่มีเสถียรภาพ
3. หากอินสแตนซ์ปัญหาเพื่อนร่วมห้องที่มั่นคงมีการจับคู่ที่มั่นคง แสดงว่ามีการจับคู่ที่มั่นคงอยู่ในตารางที่มั่นคงตารางใดตารางหนึ่ง
4. ตารางย่อยเสถียรใดๆ ของตารางเสถียร และโดยเฉพาะอย่างยิ่งตารางย่อยเสถียรใดๆ ที่ระบุการจับคู่เสถียรดังในข้อ 2 สามารถได้มาโดยลำดับของการกำจัดการหมุนบนตารางเสถียร

การกำจัดการหมุนเหล่านี้ประกอบเป็นขั้นตอนที่ 2 ของอัลกอริทึมของเออร์วิง

ตามข้อ 2 หากแต่ละรายการที่ลดลงในตารางเฟส 1 มีบุคคลเพียงคนเดียว ก็จะถือว่าตรงกัน

มิเช่นนั้น อัลกอริทึมจะเข้าสู่เฟส 2 การหมุนในตารางเสถียรTถูกกำหนดให้เป็นลำดับ ( x ₀ , y ₀ ), ( x ₁ , y ₁ ), ..., ( x _k-1 , y _k-1 ) โดยที่x _iแตกต่างกันy _iเป็นตัวแรกในรายการที่ลดลงของx _{i (หรือ} x _iเป็นตัวสุดท้ายในรายการที่ลดลงของy _{i ) และ} y _i+1เป็นตัวที่สองใน รายการที่ลดลงของ x _iสำหรับ i = 0, ..., k-1 โดยที่ดัชนีถูกคำนวณแบบโมดูลัส k ดังนั้น ในตารางเสถียรใดๆ ที่มีรายการที่ลดลงซึ่งประกอบด้วยบุคคลอย่างน้อยสองคน การหมุนดังกล่าวจะมีอยู่เสมอ ในการค้นหา ให้เริ่มต้นที่p ₀ที่มีบุคคลอย่างน้อยสองคนในรายการที่ลดลง และกำหนดแบบเวียนซ้ำให้q _i+1เป็นบุคคลที่สองในรายการของp _{i และ} p _i+1เป็นบุคคลสุดท้ายในรายการของq _{i+1 จนกว่าลำดับนี้จะซ้ำกับ} p _j บางตัว ณ จุดนั้นจะพบการหมุน: มันคือลำดับของคู่ที่เริ่มต้นจากการปรากฏครั้งแรกของ ( p _j , q _j ) และสิ้นสุดที่คู่ก่อนการปรากฏครั้งสุดท้าย ลำดับของp _iจนถึงp _jเรียกว่าหางของการหมุน ข้อเท็จจริงที่ว่ามันเป็นตารางที่เสถียรซึ่งการค้นหานี้เกิดขึ้นรับประกันว่าแต่ละp _iมีบุคคลอย่างน้อยสองคนในรายการของพวกเขา

เพื่อกำจัดการหมุนy _iปฏิเสธx _iเพื่อให้x _iเสนอให้กับy _i+1สำหรับแต่ละiเพื่อคืนค่าคุณสมบัติของตารางที่เสถียร (i) และ (ii) สำหรับแต่ละiผู้สืบทอดทั้งหมดของx _i-1จะถูกลบออกจาก รายการของ y _iและy _iจะถูกลบออกจากรายการของพวกเขา หากรายการที่ลดลงว่างเปล่าในระหว่างการลบเหล่านี้ แสดงว่าไม่มีการจับคู่ที่เสถียร มิฉะนั้น ตารางใหม่จะเป็นตารางที่เสถียรอีกครั้ง และระบุการจับคู่ไว้แล้วเนื่องจากแต่ละรายการมีบุคคลเพียงคนเดียว หรือยังคงมีการหมุนอื่นที่ต้องค้นหาและกำจัด ดังนั้นจึงต้องทำซ้ำขั้นตอน

ขั้นตอนที่ 2 ของอัลกอริทึมสามารถสรุปได้ดังนี้:

T = ตารางเฟส1 ; ในขณะที่( จริง) { ระบุการหมุนr ในT ; กำจัดr ออก จากT ; ถ้าลิสต์ ใดลิสต์ หนึ่งในT ว่างเปล่าให้คืนค่าnull ; ( ไม่สามารถมีการจับคู่ที่เสถียรได้) มิฉะนั้นถ้า( แต่ละลิสต์ที่ลดขนาดในT มีขนาด1 ) ให้คืนค่าการจับคู่M = {{ x , y } | x และy อยู่ในลิสต์ของกันและกันในT }; ( นี่คือการจับคู่ที่เสถียร) }

เพื่อให้ได้เวลาการทำงาน O( n² ⁾จะใช้เมทริกซ์จัดอันดับที่มีค่าในแถวiและคอลัมน์jเป็นตำแหน่งของ บุคคลที่ jใน รายการของบุคคลที่ iซึ่งใช้เวลา O( n² ) ด้วยเมทริกซ์จัดอันดับ ^นี้การตรวจสอบว่าบุคคลหนึ่งชอบบุคคลอื่นมากกว่าอีกบุคคลหนึ่งหรือไม่ สามารถทำได้ในเวลาคงที่โดยการเปรียบเทียบอันดับของพวกเขาในเมทริกซ์ นอกจากนี้ แทนที่จะลบองค์ประกอบออกจากรายการความชอบอย่างชัดเจน ดัชนีของรายการแรก รายการที่สอง และรายการสุดท้ายในรายการที่ลดลงของแต่ละบุคคลจะยังคงอยู่ บุคคลแรกที่ยังไม่ตรงกัน กล่าวคือ มีอย่างน้อยสองคนในรายการที่ลดลงของพวกเขา ก็จะยังคงถูกเก็บรักษาไว้เช่นกัน จากนั้น ในขั้นตอนที่ 2 ลำดับของpᵢ _ที่ "สำรวจ" เพื่อค้นหาการหมุนจะถูกเก็บไว้ในรายการ และจะใช้อาร์เรย์เพื่อทำเครื่องหมายบุคคลที่ได้เยี่ยมชมแล้ว เช่นเดียวกับการสำรวจกราฟแบบค้นหาเชิงลึก มาตรฐาน หลังจากกำจัดลำดับการหมุนแล้ว เราจะเก็บเฉพาะส่วนท้าย (ถ้ามี) ไว้ในรายการและในอาร์เรย์ตามลำดับที่ได้เยี่ยมชมแล้ว จากนั้นจึงเริ่มค้นหาลำดับการหมุนถัดไปที่บุคคลสุดท้ายในส่วนท้าย และหากไม่มีส่วนท้าย ก็จะเริ่มค้นหาที่บุคคลที่ไม่ตรงกันถัดไป วิธีนี้จะช่วยลดการสำรวจส่วนท้ายซ้ำๆ เนื่องจากส่วนท้ายนั้นไม่ได้รับผลกระทบจากการกำจัดลำดับการหมุนมากนัก

ต่อไปนี้คือรายการลำดับความสำคัญสำหรับอินสแตนซ์ Stable Roommates ที่มีผู้เข้าร่วม 6 คน: 1, 2, 3, 4, 5, 6

1 :   3   4   2   6  5 2 :   6   5   4   1  3 3 :   2   4   5   1  6 4 :   5   2   3   6  1 5 :   3   1   2   4  6 6 :   5   1   3   4  2

ขั้นตอนการดำเนินการในระยะที่ 1 อาจประกอบด้วยลำดับของการเสนอและการปฏิเสธดังต่อไปนี้ โดยที่ → แทนการเสนอและ × แทนการปฏิเสธ

1 → 3 2 → 6 3 → 2 4 → 5 5 → 3;  3 × 1 1 → 4 6 → 5;  5 × 6 6 → 1

ดังนั้น ขั้นตอนที่ 1 จึงจบลงด้วยรายการลำดับความสำคัญที่ลดลงดังต่อไปนี้: (ตัวอย่างเช่น เราตัด 5 ออกแล้วแทนด้วย 1: เพราะ 1: ได้คะแนนอย่างน้อย 6)

1 : 3  4   2   6  5 2 :   6   5   4   1  3 3 :   2   4   5 1 6 4 :   5   2   3   6  1 5 :   3 1  2   4  6 6 : 5  1 3  4  2

ในขั้นตอนที่ 2 การหมุนr ₁ = (1,4), (3,2) จะถูกระบุเป็นอันดับแรก เนื่องจาก 2 เป็นตัวเลือกที่ชอบเป็นอันดับสองของ 1 และ 4 เป็นตัวเลือกที่ชอบเป็นอันดับสองของ 3 การกำจัดr ₁จะได้:

1 : 3 4  2   6  5 2 :   6   5   4   1  3 3 : 2  4   5 1 6 4 :   5   2   3 6 1 5 :   3 1  2   4  6 6 : 5  1 3 4 2

ถัดไป การหมุนr ₂ = (1,2), (2,6), (4,5) จะถูกระบุ และการกำจัดจะได้ผลลัพธ์ดังนี้:

1 : 3 4 2  6  5 2 : 6  5   4 1 3 3 : 2  4   5 1 6 4 : 5  2   3 6 1 5 :   3 1  2 4 6 6 : 5  1 3 4 2

ดังนั้น 1 และ 6 จึงตรงกัน ในที่สุด การหมุนr ₃ = (2,5), (3,4) จะถูกระบุ และการกำจัดจะให้ผลลัพธ์ดังนี้:

1 : 3 4 2  6  5 2 : 6 5  4 1 3 3 : 2 4  5 1 6 4 : 5  2 3 6 1 5 :   3 1 2 4 6 6 : 5  1 3 4 2

ดังนั้นการจับคู่ {1, 6}, {2,4}, {3, 5} จึงมีเสถียรภาพ

• อุปกรณ์คงที่^{[ 1 ]} - ส่วนขยายแบบหลายต่อหลายของเพื่อนร่วมห้องคงที่

• Python : การใช้งานอัลกอริทึมของ Irving นั้นมีให้ใช้งานเป็นส่วนหนึ่งของmatchingไลบรารี^{[ 2 ]}
• Java : แบบจำลองการเขียนโปรแกรมข้อจำกัดเพื่อค้นหาการจับคู่ที่เสถียรทั้งหมดในปัญหาเพื่อนร่วมห้องที่มีรายการที่ไม่สมบูรณ์มีให้ใช้งานภายใต้ใบอนุญาต CRAPL ^{[ 3 ] [ 4 ]}
• R : รูปแบบการเขียนโปรแกรมข้อจำกัดเดียวกันนี้ยังมีให้ใช้งานเป็นส่วนหนึ่งของmatchingMarketsแพ็คเกจ R ด้วย^{[ 5 ] [ 6 ]}
• API : API ของ MatchingTools มีอินเทอร์เฟซการเขียนโปรแกรมแอปพลิเคชันฟรีสำหรับอัลกอริทึม^{[ 7 ]}
• แอปพลิเคชันบนเว็บ : เว็บไซต์ "Dyad Finder" ให้บริการการใช้งานอัลกอริธึ ^มบนเว็บฟรี รวมถึงซอร์สโค้ดสำหรับเว็บไซต์และตัวแก้ปัญหาที่เขียนด้วยJavaScript [ ^{8 ]}
• MATLAB : อัลกอริทึมนี้ถูกนำไปใช้ในassignStableRoommatesฟังก์ชันซึ่งเป็นส่วนหนึ่งของไลบรารีส่วนประกอบ Trackerของห้องปฏิบัติการวิจัยกองทัพเรือสหรัฐฯซึ่งเป็นซอฟต์แวร์โอเพนซอร์สฟรี บนGitHub ^{[ 9 ]}

• Irving, Robert W. (1985). "อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหา "เพื่อนร่วมห้องที่เสถียร"". วารสารอัลกอริทึม 6 ( 4): 577– 595. doi : 10.1016/0196-6774(85)90033-1 .

• Fleiner, Tamás; Irving, Robert W.; Manlove, David F. (2007). "อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหา "เพื่อนร่วมห้องที่เสถียร" . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 381 ( 1– 3): 162– 176. doi : 10.1016/j.tcs.2007.04.029 .
• Gusfield, Daniel M.; Irving, Robert W. (1989). ปัญหาการแต่งงานที่มั่นคง: โครงสร้างและอัลกอริทึมสำนักพิมพ์ MIT
• Irving, Robert W.; Manlove, David F. (2002). "ปัญหาเพื่อนร่วมห้องที่เสถียรพร้อมค่าเสมอกัน" (PDF) . วารสารอัลกอริธึม . 43 (1): 85– 105. CiteSeerX  10.1.1.108.7366 . doi : 10.1006/jagm.2002.1219 .