กลับไปหน้าบทความ

อ่าน 1 นาที

การไหลแบบซับโมดูลาร์

ในทฤษฎี การเพิ่มประสิทธิภาพเชิงการจัดเรียง การไหลย่อยโมดูลาร์ เป็นปัญหาการเพิ่มประสิทธิภาพทั่วไปที่รวมถึงกรณีพิเศษต่างๆ เช่นปัญหา การไหลต้นทุนต่ำสุด การตัดกันของเมทริกซ์...

การไหลแบบซับโมดูลาร์

ในทฤษฎีการเพิ่มประสิทธิภาพเชิงการจัดเรียงการไหลย่อยโมดูลาร์เป็นปัญหาการเพิ่มประสิทธิภาพทั่วไปที่รวมถึงกรณีพิเศษต่างๆ เช่นปัญหาการไหลต้นทุนต่ำสุดการตัดกันของเมทริกซ์และปัญหาการคำนวณไดจอยน์ น้ำหนักต่ำสุด ในกราฟทิศทางที่ มีน้ำหนัก ปัญหา นี้ได้รับการกำหนดขึ้นครั้งแรกโดยJack Edmondsและ Rick Giles [ 1 ]และสามารถแก้ไขได้ในเวลาพหุนาม[ 2 ] [ 3 ] [ 4 ]

ในปัญหาการไหลต้นทุนต่ำสุดแบบคลาสสิก อินพุตคือเครือข่ายการไหลที่มีความจุที่กำหนด ซึ่งระบุขีดจำกัดล่างและบนของปริมาณการไหลต่อขอบ รวมถึงต้นทุนต่อหน่วยการไหลตามแต่ละขอบ เป้าหมายคือการหาสระบบของปริมาณการไหลที่สอดคล้องกับความจุบนแต่ละขอบ สอดคล้องกับกฎของ Kirchhoffที่ว่าปริมาณการไหลทั้งหมดที่เข้าสู่แต่ละจุดยอดเท่ากับปริมาณการไหลทั้งหมดออก และมีต้นทุนรวมต่ำสุด ในการไหลแบบซับโมดูลาร์เช่นกัน จะมีการกำหนดฟังก์ชันเซตซับโมดูลาร์บนเซตของจุดยอดของกราฟ แทนที่จะสอดคล้องกับกฎของ Kirchhoff ข้อกำหนดคือ สำหรับทุกเซตของจุดยอด การไหลส่วนเกิน (ฟังก์ชันที่แมปเซตไปยังความแตกต่างระหว่างการไหลเข้าและการไหลออก) จะต้องมีค่าไม่เกินค่าที่กำหนดโดยฟังก์ชันซับโมดูลาร์[ 4 ]

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Submodular_flow&oldid=1351709205 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ การไหลแบบซับโมดูลาร์

ในทฤษฎี การเพิ่มประสิทธิภาพเชิงการจัดเรียง การไหลย่อยโมดูลาร์ เป็นปัญหาการเพิ่มประสิทธิภาพทั่วไปที่รวมถึงกรณีพิเศษต่างๆ เช่นปัญหา การไหลต้นทุนต่ำสุด การตัดกันของเมทริกซ์...