ในคณิตศาสตร์เชิงการจัดเรียง (combinatorics)ซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์แมทรอยด์แบบถ่วงน้ำหนัก (weighted matroid ) คือแมทรอยด์ที่มีฟังก์ชันกำหนดน้ำหนักให้กับแต่ละองค์ประกอบ ในทางคณิตศาสตร์ ให้เป็นแมทรอยด์ โดยที่Eคือเซตขององค์ประกอบ และIคือกลุ่มของเซตอิสระ แมทรอยด์แบบถ่วงน้ำหนักมีฟังก์ชันน้ำหนักซึ่งกำหนดน้ำหนักที่เป็นบวกอย่างเคร่งครัดให้กับแต่ละองค์ประกอบของเราขยายฟังก์ชันนี้ไปยังเซตย่อยของโดยการบวกคือผลรวมของบนเซต ใน${\displaystyle M=(E,I)}$${\displaystyle w:E\rightarrow \mathbb {R} ^{+}}$${\displaystyle E}$${\displaystyle E}$${\displaystyle w(A)}$${\displaystyle w(x)}$${\displaystyle x}$${\displaystyle A}$

ปัญหาพื้นฐานอย่างหนึ่งเกี่ยวกับเมทริกซ์ถ่วงน้ำหนักคือการหาเซตอิสระที่มีน้ำหนักรวมสูงสุด ปัญหานี้สามารถแก้ไขได้โดยใช้อัลกอริทึมแบบโลภ (greedy algorithm) ง่ายๆ ดังต่อไปนี้ :

• กำหนดให้เซตAเป็นเซตว่าง โปรดทราบว่า ตามนิยามของแมทรอยด์แล้วAเป็นเซตอิสระ
• สำหรับแต่ละองค์ประกอบxในE \ Aให้ตรวจสอบว่า Au{x} ยังคงเป็นเซตอิสระอยู่หรือไม่
  • หากไม่มีองค์ประกอบดังกล่าวแล้ว ให้หยุด เนื่องจากAไม่สามารถขยายต่อไปได้อีก
  • หากมีองค์ประกอบดังกล่าวอย่างน้อยหนึ่งรายการ ให้เลือกองค์ประกอบที่มีน้ำหนักมากที่สุด แล้วเพิ่มเข้าไปใน A

อัลกอริทึมนี้ไม่จำเป็นต้องรู้โครงสร้างแมทรอยด์ใดๆ เลย มันต้องการเพียงแค่ออราเคิลตรวจสอบความเป็นอิสระสำหรับแมทรอยด์เท่านั้น ซึ่งก็คือรูทีนย่อยสำหรับทดสอบว่าเซตนั้นเป็นอิสระหรือไม่

Jack Edmonds ^{[ 1 ]}พิสูจน์แล้วว่าอัลกอริทึมง่ายๆ นี้ค้นหาเซตอิสระที่มีน้ำหนักสูงสุดได้จริง กำหนดให้เซตที่พบโดยอัลกอริทึมเป็น e ₁ ,...,e _kโดยคุณสมบัติของเมทริกซ์ เป็นที่ชัดเจนว่า k=rank(M) มิฉะนั้นเซตอาจขยายได้ สมมติโดยการขัดแย้งว่ามีเซตอื่นที่มีน้ำหนักสูงกว่า โดยไม่เสียความเป็นทั่วไป เป็นไปได้ที่จะสมมติว่าเซตนี้มีองค์ประกอบ rank(M) เช่นกัน กำหนดให้เป็น f ₁ ,...,f _kเรียงลำดับรายการเหล่านี้โดยที่ w(f ₁ ) ≥ ... ≥ w(f _k ) ให้jเป็นดัชนีแรกที่ w(f _j ) > w(e _j ) ใช้คุณสมบัติการเพิ่มกับเซต {f ₁ ,...,f _j } และ {e ₁ ,...,e _j-1 }; เราสรุปได้ว่าต้องมีi ≤ j บางตัวที่ f _iสามารถเพิ่มเข้าไปใน {e ₁ ,...,e _j-1 } ได้ในขณะที่ยังคงความเป็นอิสระ แต่ w(f _i ) ≥ w(f _j ) > w(e _j ) ดังนั้น f _iควรจะถูกเลือกในขั้นตอน j แทนที่จะเป็น e _jซึ่งเป็นข้อขัดแย้ง^{[ 2 ]}

ยกตัวอย่างง่ายๆ สมมติว่าเราต้องการหาป่าแผ่คลุมสูงสุดของกราฟ นั่นคือ กำหนดกราฟและน้ำหนักสำหรับแต่ละขอบ ให้หาป่าที่ประกอบด้วยทุกจุดยอดและมีน้ำหนักรวมของขอบในต้นไม้สูงสุด ปัญหานี้เกิดขึ้นในแอปพลิเคชันการจัดกลุ่มบางอย่าง สามารถแก้ไขได้ด้วยอัลกอริทึมของ Kruskalซึ่งสามารถมองได้ว่าเป็นกรณีพิเศษของอัลกอริทึมแบบโลภ (greedy algorithm) ข้างต้นสำหรับเมท ริกซ์กราฟิก

ถ้าเราดูที่นิยามของเมทรอยด์ป่า เราจะเห็นว่าป่าที่ครอบคลุมสูงสุดนั้นก็คือเซตอิสระที่มีน้ำหนักรวมมากที่สุด — เซตดังกล่าวจะต้องครอบคลุมกราฟ มิฉะนั้นเราจะสามารถเพิ่มขอบได้โดยไม่สร้างวงจร แต่เราจะหาเซตนั้นได้อย่างไร?

มีอัลกอริทึมง่ายๆ สำหรับการหาฐาน:

• ในตอนแรก ให้เป็นเซตว่าง${\displaystyle A}$
• สำหรับแต่ละใน${\displaystyle x}$${\displaystyle E}$
  • ถ้าเป็นอิสระ ให้ตั้งค่าเป็น.${\displaystyle A\cup \{x\}}$${\displaystyle A}$${\displaystyle A\cup \{x\}}$

ผลลัพธ์ที่ได้คือเซตอิสระอย่างชัดเจน เป็นเซตอิสระสูงสุดเพราะถ้าเซตหนึ่งไม่เป็นอิสระสำหรับเซตย่อยบางส่วนของ เซตแรก แล้วเซตที่สองก็จะไม่เป็นอิสระเช่นกัน (ข้อความแย้งเป็นผลมาจากคุณสมบัติการสืบทอด ) ดังนั้น ถ้าเราละทิ้งองค์ประกอบหนึ่งไป เราจะไม่มีโอกาสได้ใช้มันอีกในภายหลัง เราจะขยายอัลกอริทึมนี้เพื่อแก้ปัญหาที่ยากขึ้น ${\displaystyle B\cup \{x\}}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A\cup \{x\}}$

เซตอิสระที่มีน้ำหนักรวมมากที่สุดเรียกว่า เซต ที่เหมาะสมที่สุดเซตที่เหมาะสมที่สุดมักจะเป็นฐานเสมอ เพราะหากสามารถเพิ่มขอบได้ ก็ควรเพิ่มเข้าไป เพราะจะทำให้น้ำหนักรวมเพิ่มขึ้นเท่านั้น ปรากฏว่ามีอัลกอริธึมแบบโลภ (greedy algorithm) ที่ เรียบง่าย สำหรับการคำนวณเซตที่เหมาะสมที่สุดของเมทริกซ์ที่มีน้ำหนัก โดยทำงานดังนี้:

• ในตอนแรก ให้เป็นเซตว่าง${\displaystyle A}$
• สำหรับแต่ละค่าในที่นำมาเรียงลำดับตามน้ำหนักจากมากไปน้อย (แบบโมโนโทนิก) ${\displaystyle x}$${\displaystyle E}$
  • ถ้าเป็นอิสระ ให้ตั้งค่าเป็น.${\displaystyle A\cup \{x\}}$${\displaystyle A}$${\displaystyle A\cup \{x\}}$

อัลกอริทึมนี้ค้นหาฐาน เนื่องจากเป็นกรณีพิเศษของอัลกอริทึมข้างต้น มันจะเลือกองค์ประกอบที่มีน้ำหนักมากที่สุดเท่าที่จะทำได้เสมอ ในขณะที่ยังคงรักษาความเป็นอิสระ (จึงเป็นที่มาของคำว่า "โลภ") วิธีนี้จะสร้างเซตที่เหมาะสมที่สุดเสมอ สมมติว่ามันสร้างและตอนนี้สำหรับใดๆที่พิจารณาเซตเปิดและเนื่องจากมีค่าน้อยกว่าจึงมีองค์ประกอบบางอย่างของที่สามารถใส่เข้าไปใน ได้โดยที่ผลลัพธ์ยังคงเป็นอิสระ อย่างไรก็ตามเป็นองค์ประกอบที่มีน้ำหนักสูงสุดที่สามารถเพิ่มเข้าไปในเพื่อรักษาความเป็นอิสระ ดังนั้น จึงมีน้ำหนักไม่น้อยกว่าองค์ประกอบบางอย่างของและด้วยเหตุนี้จึงมีน้ำหนักอย่างน้อยเท่ากับเนื่องจากเป็นจริงสำหรับทุกจึงมีน้ำหนักมากกว่า ${\displaystyle A=\{e_{1},e_{2},\ldots ,e_{r}\}}$${\displaystyle B=\{f_{1},f_{2},\ldots ,f_{r}\}}$${\displaystyle k}$${\displaystyle 1\leq k\leq r}$${\displaystyle O_{1}=\{e_{1},\ldots ,e_{k-1}\}}$${\displaystyle O_{2}=\{f_{1},\ldots ,f_{k}\}}$${\displaystyle O_{1}}$${\displaystyle O_{2}}$${\displaystyle O_{2}}$${\displaystyle O_{1}}$${\displaystyle e_{k}}$${\displaystyle O_{1}}$${\displaystyle e_{k}}$${\displaystyle O_{2}}$${\displaystyle e_{k}}$${\displaystyle f_{k}}$${\displaystyle k}$${\displaystyle A}$${\displaystyle B}$

วิธีที่ง่ายที่สุดในการเรียงลำดับสมาชิกตามลำดับที่ต้องการคือการจัดเรียงสมาชิกเหล่านั้น ซึ่งต้องใช้เวลาโดยใช้อัลกอริธึมการจัดเรียง แบบเปรียบเทียบ นอกจากนี้ เรายังต้องทดสอบว่าแต่ละสมาชิกเป็นอิสระต่อกันหรือไม่ โดยสมมติว่าการทดสอบความเป็นอิสระต้องใช้เวลา ดังนั้นเวลาทั้งหมดสำหรับอัลกอริธึมนี้คือ ${\displaystyle E}$${\displaystyle O(|E|\log |E|)}$${\displaystyle x}$${\displaystyle A\cup \{x\}}$${\displaystyle O(f(|E|))}$${\displaystyle O(|E|\log |E|+|E|f(|E|))}$

หากเราต้องการหาต้นไม้แผ่คลุมขั้นต่ำแทน เราเพียงแค่ "กลับด้าน" ฟังก์ชันน้ำหนักโดยการลบออกจากค่าคงที่ขนาดใหญ่ โดยเฉพาะอย่างยิ่ง ให้โดยที่มากกว่าน้ำหนักรวมของขอบกราฟทั้งหมด ปัญหาการหาค่าเหมาะสมที่สุดอีกมากมายเกี่ยวกับเมทริกซ์และฟังก์ชันน้ำหนักทุกประเภทสามารถแก้ไขได้ด้วยวิธีง่ายๆ นี้ แม้ว่าในหลายกรณีอาจพบอัลกอริทึมที่มีประสิทธิภาพมากกว่าซึ่งใช้ประโยชน์จากคุณสมบัติเฉพาะทางมากกว่าก็ตาม ${\displaystyle w_{\text{min}}(x)=Ww(x)}$${\displaystyle W}$

โปรดทราบด้วยว่า หากเราเลือกเซตของเซต "อิสระ" ซึ่งเป็นดาวน์เซตแต่ไม่ใช่แมทรอยด์ อัลกอริทึมแบบโลภจะไม่ทำงานเสมอไป เพราะจะมีเซตอิสระและที่มีแต่ ที่ไม่มีเซตอิสระ สำหรับ${\displaystyle I}$${\displaystyle I_{1}}$${\displaystyle I_{2}}$${\displaystyle |I_{1}|<|I_{2}|}$${\displaystyle e\in I_{2}\setminus I_{1}}$${\displaystyle I_{1}\cup e}$

เลือกเซตและที่มีคุณสมบัติว่ากำหนดน้ำหนักให้กับองค์ประกอบของในช่วงให้เป็น, องค์ประกอบของในช่วงให้เป็น, องค์ประกอบของในช่วงให้เป็น, และส่วนที่เหลือในช่วงให้เป็นอัลกอริทึมแบบโลภ (greedy algorithm) จะเลือกองค์ประกอบของและจากนั้นจะไม่สามารถเลือกองค์ประกอบของ ได้อีกต่อไปดังนั้น เซตอิสระที่สร้างขึ้นจะมีน้ำหนักอย่างมากที่สุดซึ่งน้อยกว่าน้ำหนักของ ${\displaystyle \epsilon >0}$${\displaystyle \tau >0}$${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|<|I_{2}|}$${\displaystyle I_{1}\cup I_{2}}$${\displaystyle 2}$${\displaystyle 2+2\epsilon }$${\displaystyle I_{1}\setminus I_{2}}$${\displaystyle 1+\epsilon }$${\displaystyle 1+2\epsilon }$${\displaystyle I_{2}\setminus I_{1}}$${\displaystyle 1}$${\displaystyle 1+\epsilon }$${\displaystyle 0}$${\displaystyle \tau }$${\displaystyle I_{1}}$${\displaystyle I_{2}\setminus I_{1}}$${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|+|I_{1}\cup I_{2}|}$${\displaystyle I_{2}}$

อัลกอริทึมการเพิ่มประสิทธิภาพนี้อาจใช้เพื่อกำหนดลักษณะของแมทรอยด์: หากตระกูลFของเซตที่ปิดภายใต้การเลือกเซตย่อยมีคุณสมบัติที่ว่าไม่ว่าเซตจะมีน้ำหนักอย่างไร อัลกอริทึมโลภจะพบเซตที่มีน้ำหนักสูงสุดในตระกูล ดังนั้นFจะต้องเป็นตระกูลของเซตอิสระของแมทรอยด์^{[ 3 ]}

แนวคิดของ matroid ได้ถูกขยายให้ครอบคลุมถึงเซตประเภทอื่นๆ ที่อัลกอริทึมแบบโลภ (greedy algorithm) ให้คำตอบที่ดีที่สุด ดู ข้อมูลเพิ่มเติมได้ ที่ greedoidและmatroid embedding Korte และ Lovász ได้ขยายแนวคิดเหล่านี้ไปสู่วัตถุที่เรียกว่าgreedoidซึ่งช่วยให้สามารถแก้ปัญหาในกลุ่มที่ใหญ่ขึ้นได้ด้วยอัลกอริทึมแบบโลภ