ในคณิตศาสตร์เชิงการจัดเรียง (combinatorics)กรีดอยด์ (greedoid) คือ ระบบเซตชนิดหนึ่งมันเกิดขึ้นจากแนวคิดของแมทรอยด์ (matroid ) ซึ่งเดิมที วิทนีย์ (Whitney)นำเสนอในปี 1935 เพื่อศึกษาเกี่ยว กับ กราฟระนาบและต่อมาเอ็ดมอนด์ (Edmonds) นำมาใช้ เพื่อจำแนกลักษณะของปัญหาการหาค่าเหมาะสมที่สุดที่สามารถแก้ไขได้ด้วย อัลก อริทึมแบบโลภ (greedy algorithms ) ประมาณปี 1980 คอร์เต (Korte)และโลวัสซ์ (Lovász)ได้นำเสนอกรีดอยด์เพื่อขยายขอบเขตการจำแนกลักษณะของอัลกอริทึมแบบโลภนี้ให้กว้างขึ้น จึงเป็นที่มาของชื่อกรีดอยด์ นอกจากการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์แล้ว กรีดอยด์ยังเชื่อมโยงกับทฤษฎีกราฟทฤษฎีภาษาทฤษฎีลำดับและสาขาอื่นๆ ของคณิตศาสตร์ อีก ด้วย

ระบบเซต( F , E )คือกลุ่มของเซตย่อยของเซตพื้นฐานE (กล่าวคือFเป็นเซตย่อยของเซตกำลังของE ) เมื่อพิจารณาถึงกรีดอยด์ สมาชิกของFเรียกว่าเซตที่เป็นไปได้เมื่อพิจารณาถึงแมทรอยด์เซตที่เป็นไปได้ยังเรียกว่าเซตอิสระ อีก ด้วย

ระบบเซตที่เข้าถึงได้( F , E )คือระบบเซตที่เซตที่เป็นไปได้ที่ไม่ว่างทุกเซตXประกอบด้วยองค์ประกอบxที่ทำให้เป็นไปได้ ซึ่งหมายความว่าระบบเซตที่เข้าถึงได้ที่ไม่ว่างและจำกัด ใดๆ จะต้องมีเซตว่าง ∅ อยู่ด้วย ^{[ 1 ]}${\displaystyle X\setminus \{x\}}$

กรีดอยด์( F , E )คือระบบเซตที่เข้าถึงได้แบบจำกัดซึ่งสอดคล้องกับคุณสมบัติการแลกเปลี่ยน :

• สำหรับทุกสิ่งที่มีอยู่ย่อมมีบางสิ่งบางอย่างเช่นนั้น${\displaystyle X,Y\in F}$${\displaystyle |X|>|Y|,}$${\displaystyle x\in X\setminus Y}$${\displaystyle Y\cup \{x\}\in F.}$

(หมายเหตุ: บางคนสงวนคำว่า " คุณสมบัติการแลกเปลี่ยน" ไว้ สำหรับเงื่อนไขบนพื้นฐานของกรีดอยด์ และนิยมเรียกเงื่อนไขข้างต้นว่า "คุณสมบัติการเพิ่มขึ้น")

ฐานของกรีดอยด์คือเซตที่เป็นไปได้สูงสุด หมายความว่าเป็นเซตที่เป็นไปได้แต่ไม่อยู่ในเซตอื่นใด ฐานของเซตย่อยXของ Eคือเซตที่เป็นไปได้สูงสุดที่อยู่ในX

อันดับของกรีดอยด์คือขนาดของฐาน ตามคุณสมบัติการแลกเปลี่ยน ฐานทั้งหมดมีขนาดเท่ากัน ดังนั้น ฟังก์ชันอันดับจึงถูกกำหนดไว้อย่างดีอันดับของเซตย่อยXของEคือขนาดของฐานของX เช่นเดียวกับแมทรอยด์ กรีดอยด์มีคริปโตมอร์ฟิซึมในแง่ของฟังก์ชันอันดับ^{[ 2 ]} ฟังก์ชัน r เป็นฟังก์ชันอันดับของกรีดอยด์บนเซตพื้นฐานEก็ต่อเมื่อrเป็นซับคาร์ดินัลโมโนโทนิกและเซมิโมดูลาร์ เฉพาะ ที่ นั่นคือ สำหรับและ ใดๆเรามี: ${\displaystyle r:2^{E}\to \mathbb {Z} }$${\displaystyle X,Y\subseteq E}$${\displaystyle e,f\in E}$

• ความเป็นจำนวนย่อย :${\displaystyle r(X)\leq |X|}$
• ความสม่ำเสมอ : เมื่อใดก็ตามที่${\displaystyle r(X)\leq r(Y)}$${\displaystyle X\subseteq Y\subseteq E}$
• เซมิโมดูลาร์เฉพาะที่ : เมื่อใดก็ตามที่${\displaystyle r(X)=r(X\cup \{e,f\})}$${\displaystyle r(X)=r(X\cup \{e\})=r(X\cup \{f\})}$

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

เกรดอยด์ช่วง( F , E )คือเกรดอยด์ที่ตรงตามคุณสมบัติของช่วง :

• ถ้าเช่นนั้น สำหรับทุกคน${\displaystyle A,B,C\in F}$${\displaystyle A\subseteq B\subseteq C,}$${\displaystyle x\in E\setminus C:}$

$${\displaystyle {\begin{matrix}A\cup \{x\}\in F\\C\cup \{x\}\in F\end{matrix}}\implies B\cup \{x\}\in F.}$$

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

แอนติแมทรอยด์ ( F , E )คือกรีดอยด์ที่สอดคล้องกับคุณสมบัติช่วงโดยไม่มีขอบเขตบน :

• ถ้า⁠ ⁠${\displaystyle A,B\in F}$กับ⁠ ⁠${\displaystyle A\subseteq B,}$แล้ว สำหรับทุก⁠ ⁠ ⁠ ${\displaystyle x\in E\setminus B,}$⁠ หมายความ${\displaystyle A\cup \{x\}\in F}$ว่า⁠ ⁠${\displaystyle B\cup \{x\}\in F.}$

ในทำนองเดียวกัน แอนติแมทรอยด์คือ (i) กรีดอยด์ที่มีฐานเฉพาะตัว หรือ (ii) ระบบเซตที่เข้าถึงได้ซึ่งปิดภายใต้การรวมกัน เห็นได้ชัดว่าแอนติแมทรอยด์ยังเป็นกรีดอยด์ช่วงอีกด้วย

เมทริกซ์ ( F , E )คือเมทริกซ์เกรดอยด์ที่ไม่ว่างเปล่าซึ่งมีคุณสมบัติช่วงโดยไม่มีขอบเขตล่าง :

• ถ้า⁠ ⁠${\displaystyle B,C\in F}$กับ⁠ ⁠${\displaystyle B\subseteq C,}$แล้ว สำหรับทุก⁠ ⁠ ⁠ ${\displaystyle x\in E\setminus C,}$⁠ หมายความ${\displaystyle C\cup \{x\}\in F}$ว่า⁠ ⁠${\displaystyle B\cup \{x\}\in F.}$

เห็นได้ชัดว่า matroid ก็คือ interval greedoid เช่นกัน

• พิจารณากราฟ แบบไม่มีทิศทาง Gให้เซตพื้นฐานเป็นขอบของGและเซตที่เป็นไปได้เป็นเซตขอบของแต่ละป่า (กล่าวคือ กราฟย่อยที่ไม่มีวงจร) ของGระบบเซตนี้เรียกว่า ไซเคิลแมทรอยด์ระบบเซตจะเรียกว่า ไซเคิลแมทรอยด์ถ้ามันเป็นไซเคิลแมทรอยด์ของกราฟบางกราฟ (เดิมที ไซเคิลแมทรอยด์ถูกนิยามบนวงจรหรือเซตที่ขึ้นอยู่กัน น้อยที่สุด ดังนั้นจึงได้ชื่อว่า ไซเคิล)
• พิจารณากราฟG ที่ไม่มีทิศทางและมีจำนวนจำกัด โดย มีจุดยอดr เป็นราก ให้เซตพื้นฐานเป็นจุดยอดของGและเซตที่เป็นไปได้คือเซตย่อยของจุดยอดที่ประกอบด้วยrซึ่งทำให้เกิดกราฟย่อยที่เชื่อมต่อกันของGนี่เรียกว่าgreedoid การค้นหาจุดยอดและเป็น antimatroid ชนิดหนึ่ง
• พิจารณากราฟแบบมีทิศทาง จำกัด Dที่มีรากอยู่ที่rให้เซตพื้นฐานเป็นขอบ (แบบมีทิศทาง) ของ D และเซตที่เป็นไปได้เป็นเซตขอบของแต่ละต้นไม้ย่อยแบบมีทิศทางที่มีรากอยู่ที่rโดยที่ขอบทั้งหมดชี้ออกจากrนี่เรียกว่ากรีดอยด์แบบค้นหาเส้นหรือกรีดอยด์แบบแตกแขนงที่มีทิศทาง มันเป็นกรีดอยด์แบบช่วง แต่ไม่ใช่ทั้งแอนติแมทรอยด์หรือแมทรอยด์
• พิจารณาเมทริกซ์M ขนาด m × n ให้เซตพื้นฐานEเป็นดัชนีของคอลัมน์ตั้งแต่ 1 ถึงnและเซตที่เป็นไปได้คือนี่คือโครงสร้างที่เรียกว่าgreedoid ของการกำจัดแบบเกาส์เซียน (Gaussian elimination greedoid ) เพราะโครงสร้างนี้เป็นพื้นฐานของ อัลกอริธึม การกำจัดแบบเกาส์เซียนมันเป็น greedoid แต่ไม่ใช่ interval greedoid$${\displaystyle F=\{X\subseteq E:{\text{ submatrix }}M_{\{1,\ldots ,|X|\},X}{\text{ เป็นเมทริกซ์ผกผันได้}}\}.}$$

โดยทั่วไปอัลกอริทึมแบบโลภ (greedy algorithm)เป็นเพียงกระบวนการวนซ้ำที่เลือกตัวเลือกที่ดีที่สุดในระดับท้องถิ่นซึ่งโดยปกติจะเป็นอินพุตที่มีน้ำหนักสูงสุด ในแต่ละรอบจนกว่าจะได้ใช้ตัวเลือกที่มีอยู่ทั้งหมด ในการอธิบายเงื่อนไขตามทฤษฎี greedoid ที่ทำให้อัลกอริทึมแบบโลภมีประสิทธิภาพสูงสุด (กล่าวคือ ได้ฐานที่มีค่าสูงสุด) เราจำเป็นต้องใช้คำศัพท์ทั่วไปเพิ่มเติมในทฤษฎี greedoid โดยไม่เสียความเป็นทั่วไปเราจะพิจารณา greedoid G = ( F , E )โดยที่Eเป็นจำนวนจำกัด

A subset X of E is rank feasible if the largest intersection of X with any feasible set has size equal to the rank of X. In a matroid, every subset of E is rank feasible. But the equality does not hold for greedoids in general.

A function ${\displaystyle w:E\to \mathbb {R} }$ is R-compatible if ${\displaystyle \{x\in E:w(x)\geq c\}}$ is rank feasible for all real numbersc.

An objective function ${\displaystyle f:2^{S}\to \mathbb {R} }$ is linear over a set ${\displaystyle S}$ if, for all ${\displaystyle X\subseteq S,}$ we have ${\displaystyle f(X)=\sum _{x\in X}w(x)}$ for some weight function${\displaystyle w:S\to \Re .}$

Proposition. A greedy algorithm is optimal for every R-compatible linear objective function over a greedoid.

The intuition behind this proposition is that, during the iterative process, each optimal exchange of minimum weight is made possible by the exchange property, and optimal results are obtainable from the feasible sets in the underlying greedoid. This result guarantees the optimality of many well-known algorithms. For example, a minimum spanning tree of a weighted graph may be obtained using Kruskal's algorithm, which is a greedy algorithm for the cycle matroid. Prim's algorithm can be explained by taking the line search greedoid instead.

• Matroid
• Polymatroid

• บทนำสู่ Greedoids
• ทฤษฎีของอัลกอริทึมแบบโลภ (Theory of Greedy Algorithms) ถูกเก็บถาวรเมื่อวันที่ 4 มีนาคม 2016 ที่Wayback Machine
• ฟังก์ชันย่อยและการเพิ่มประสิทธิภาพ
• การจับคู่, แมทรอยด์ และฟังก์ชันซับโมดูลาร์