లోభ ఆల్గరిథమ్ ప్రతి దశలో స్థానికంగా సరైన ఎంపికను చేస్తుంది, ఇది ప్రపంచ వ్యాప్త సరైనదానికి దారితీస్తుందని ఆశిస్తుంది. ఇది సరళమైనది మరియు వేగవంతమైనది, కానీ సమస్యకు లోభ-ఎంపిక లక్షణం మరియు సరైన ఉప-నిర్మాణం ఉన్నప్పుడు మాత్రమే సరిగ్గా ఉంటుంది.
పూర్వ ఎంపికలను కొన్ని సార్లు పరిశీలించవద్దు — సెరుకైన తక్షణ ఎంపికకు నిబద్ధత చేసుకోండి మరియు ముందుకు సాగండి.
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 కోసం 3+3 కంటే 4+1+1 ఇస్తుంది.
పని చేసే ఉదాహరణలు: Dijkstra, Kruskal/Prim (MST), Huffman coding, విరామం షెడ్యూలింగ్.
సాధారణంగా వేగవంతమైనది — తరచుగా సార్టింग్ తర్వాత O(n log n).
లోభ ఎల్లప్పుడూ సరిగ్గా ఉండదు. లోభ-ఎంపిక లక్షణాన్ని నిరూపించండి లేదా దానిపై నమ్మకం చేసే ముందు brute-force/DP బేస్లైన్కు వ్యతిరేకంగా పరీక్ష చేయండి.
లోభ వర్తించినప్పుడు, ఇది DP లేదా brute force కంటే చాలా సరళమైనది మరియు వేగవంతమైనది.
ఎప్పుడు ఇది చెల్లుబాటు అయ్యేది — మరియు ఎప్పుడు విసుగుగా తప్పుడు సమాధానాలను ఇస్తుందో తెలుసుకోవడం — ఇది ఆల్గోరిథమిక్ పరిణతి యొక్క చిహ్నం.
నిజ గ్రాఫ్ ఆల్గరిథమ్లు కోర్లో లోభ.