สร้างคำสั่งซื้อทั้งหมดหรือบางส่วนจากความสัมพันธ์ที่ไม่สอดคล้องกัน
ลองนึกภาพว่าฉันต้องการสร้างคำสั่งซื้อทั้งหมดจากชุดขององค์ประกอบ $E$แต่ฟังก์ชันการเปรียบเทียบจะให้ผลลัพธ์ที่ไม่ได้กำหนด ฉันสร้างรายการคู่องค์ประกอบ (e, e) ผ่านการใช้ฟังก์ชันเปรียบเทียบซ้ำ ๆ เพื่อให้แต่ละองค์ประกอบในชุดแสดงอย่างน้อยหนึ่งครั้ง
ฉันจะใช้ข้อมูลที่ป้อนนี้เพื่อสร้างคำสั่งซื้อทั้งหมดได้อย่างไร คลาสของอัลกอริทึมที่สามารถนำไปใช้ที่นี่คืออะไร?
เพื่อความชัดเจนยิ่งขึ้นฉันจะยกตัวอย่างที่เป็นรูปธรรม
ท็อปปิ้งพิซซ่าที่ดีที่สุดคืออะไร?
ชุดองค์ประกอบของฉัน $E$ รวมถึงท็อปปิ้งพิซซ่ายอดนิยม ได้แก่ เป็ปเปอร์โรนีชีสเห็ดสับปะรดเบลล์เปปเปอร์มะกอก
จากนั้นสำหรับเพื่อนของฉันแต่ละคนฉันเลือกท็อปปิ้งส่วนย่อยที่มีขนาดสุ่มและขอให้เพื่อนของฉันเรียงลำดับจากดีที่สุดไปหาแย่ที่สุด เพื่อนของฉันตอบกลับตามหน้าที่และสร้างอินพุตสำหรับอัลกอริทึมของฉัน:
- ชีสเปปเปอโรนีมะกอก
- ชีสสับปะรดเห็ดมะกอก
- พริกหยวกเห็ดมะกอก
- เป็ปเปอร์โรนีชีสมะกอก
- ชีสพริกหยวก
ดูเหมือนจะมีคำสั่งที่คลุมเครือที่นี่ (ทุกคนเห็นด้วยว่ามะกอกเป็นสิ่งที่แย่ที่สุด) แต่เพื่อนของฉันยังไม่ได้รับความเห็นเป็นเอกฉันท์ว่าพิซซ่าหน้าไหนดีกว่ากัน: ชีสหรือเปปเปอโรนี เมื่อพิจารณาว่ารายการเกิดขึ้นที่ใดในปัจจัยการผลิตและความถี่ที่เกิดขึ้นฉันอาจจะสร้างคำสั่งเช่นนี้
- ชีส> เปปเปอร์โรนี> ระฆัง> สับปะรด> เห็ด> มะกอก
ฉันไม่แน่ใจว่าจะทำอย่างไรให้เป็นทางการและทำให้มันใช้งานได้กับอินพุตที่มีขนาดใหญ่กว่ามาก
ฉันคิดว่าวิธีแก้ปัญหาอาจเกี่ยวข้องกับกราฟและขอบถ่วงน้ำหนัก แต่ฉันไม่มีความคุ้นเคยกับอัลกอริทึมกราฟเพียงพอที่จะรับรู้ว่านี่เป็นพื้นที่ศึกษาที่ตั้งชื่อไว้หรือไม่ ฉันเจอ "การเรียงลำดับโทโพโลยี" แล้ว แต่ใช้ได้กับกราฟอะไซคลิกที่กำหนดทิศทางเท่านั้นและฉันสนใจเป็นพิเศษในอินพุตที่ไม่สามารถสร้าง DAG ได้
ฉันยังสังเกตเห็นว่าปัญหานี้ดูเหมือนกับการลงคะแนนเสียงให้กับผู้แทนที่มาจากการเลือกตั้ง ในความเป็นจริงปัญหาระดับเดียวกันหรือไม่?
คำตอบ
เป็นการยากที่จะพูดโดยไม่มีบริบทและการสร้างแบบจำลองเพิ่มเติม จะต้องมีสมมติฐานบางประการว่าผลลัพธ์ของฟังก์ชันการเปรียบเทียบเกี่ยวข้องกับลำดับรวมที่ต้องการ (ซ่อน) อย่างไร
มันเป็นไปได้ที่คุณอาจต้องการรุ่นแบรดลีย์เทอร์รี่-Luce ถ้าเป็นเช่นนั้นมีอัลกอริทึมมาตรฐานมากมาย ดูสิ่งนี้ด้วยhttps://cs.stackexchange.com/a/85204/755.
เป็นไปได้ว่าคุณอาจต้องการระบบการจัดอันดับเช่น Elo เป็นต้น
เป็นไปได้ว่าคุณอาจต้องการระบบการลงคะแนนแบบจัดอันดับเช่น IRV, Condorcet method, Borda count หรืออื่น ๆ อีกมากมาย พวกเขาทั้งหมดมีข้อบกพร่องและข้อเสียต่าง ๆ มีข้อพิสูจน์ว่าไม่มีระบบใดที่จะมีคุณสมบัติทั้งหมดที่เราต้องการ - ดูเช่นทฤษฎีบทของลูกศรและปัญหาการไม่เคลื่อนย้าย (แม้ว่าความชอบส่วนบุคคลของเพื่อนแต่ละคนจะเป็นสกรรมกริยากล่าวคือเป็นคำสั่งซื้อทั้งหมดแล้ว ไม่มีการรับประกันว่ามีคำสั่งซื้อรวมทั่วโลกที่สอดคล้องกับคำสั่งซื้อทั้งหมด)