பேராசைப் படியரிப்பு ஒவ்வொரு படியிலும் உள்ளூர் உகந்த தேர்வை செய்கிறது, அது உலகளாவிய உச்ச நிலைக்கு வழிவகுக்கும் என்று நம்புகிறது. இது எளிமையானது மற்றும் வேகமானது, ஆனால் சிக்கலுக்கு பேராசைத் தேர்வு பண்பு மற்றும் உகந்த உப-கட்டமைப்பு இருக்கும்போதுதான் சரியாக இருக்கும்.
கடந்த தேர்வுகளை மறு சிந்தனை செய்ய வேண்டாம் — சிறந்த உடனடி விருப்பத்திற்கு உறுதிபடுத்தி முன்னேறுங்கள்.
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} போன்ற தொகுப்புகளுக்கு தோல்வியடைகிறது, இங்கு பேராசை 6 க்கு 4+1+1 ஐ 3+3 க்குப் பதிலாக தருகிறது.
பணிபுரியும் எடுத்துக்காட்டுகள்: Dijkstra, Kruskal/Prim (MST), Huffman குறியாக்கம், இடைவெளி திட்டமிடல்.
সাধாரணமாக வேகமான — பெரும்பாலும் O(n log n) வரிசையின் பிறகு.
பேராசை எப்போதும் சரியாக இல்லை. பேராசைத் தேர்வு பண்பை நிரூபிக்கவும் அல்லது அதை நம்பும் முன் brute-force/DP அடிப்படையுடன் சோதிக்கவும்.
பேராசை பொருந்தும்போது, இது DP அல்லது brute force ஐ விட மிகவும் எளிமையானது மற்றும் வேகமானது.
எப்போது இது சரியாக உள்ளது என்பதை அறிதல் — மற்றும் எப்போது அது மிகவும் தவறான பதில்களைக் கொடுக்கிறது — இது ஆல்கரிதம் முதிர்ச்சির ஒரு அடையாளம்.
நிறைய அடிப்படை வரைபட algorithms பேராசை மையமாக உள்ளன.