ხირითი ალგორითმი აკეთებს ლოკალურად ოპტიმალურ არჩევანს ყოველ ეტაპზე, იმედით რომ ეს მიდის გლობალური მაქსიმუმისკენ. ეს არის მარტივი და სწრაფი, მაგრამ სწორია მხოლოდ მაშინ, როდესაც პრობლემას აქვს greedy-choice property და optimal substructure.
ნიდაგ არ გაიაზრო წინა არჩევანი — ისე დაუჭირე საუკეთესო მყისიერ ვარიანტს და წინსულ.
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
ეს ოპტიმალური აშშ-ს მონეტებისთვის, მაგრამ ვერ იმუშავებს ისეთი ნაკრებებისთვის, როგორიცაა {1, 3, 4}, სადაც ხირითი იძლევა 4+1+1 6-ის ნაცვლად 3+3-ის.
მაგალითები, რომლებიც მუშაობს: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
ჩვეულებრივ სწრაფი — ხშირად O(n log n) დახარისხების შემდეგ.
ხირითი ყოველთვის სწორი არ არის. დაამტკიცე greedy-choice property ან გამოცადე brute-force/DP საფუძვლობის მიმართ სანამ ენდობა.
როდესაც ხირითი ვრცელდება, ეს ბევრად უფრო მარტივი და სწრაფია ვიდრე DP ან brute force.
ცნობა როდის ის მოქმედი — და როდის ჩუმად აძლევს არასწორ პასუხებს — ალგორითმული სიმწიფის ნიშანია.
მრავალი ძირეული გრაფიკის ალგორითმი ხირითი არის გულის სიგრძეზე.