Greedy Algorithms
Algorithm ను Greedy గా ఏది చేస్తుంది?
Greedy algorithm ఒక పరిష్కారాన్ని ఒక్కో అడుగు గా నిర్మిస్తుంది, ఎల్లప్పుడూ ఇప్పుడు ఉత్తమంగా కనిపించే ఎంపికను ఎంచుకుంటుంది - గత ఎంపికలను తిరిగి పరిగణించకుండా. Backtracking లేదు, ముందుకు చూడడం లేదు.
రెండు లక్షణాలు ఉన్నప్పుడు ఇది పనిచేస్తుంది:
- Greedy choice property - స్థానికంగా ఉత్తమ ఎంపిక సమగ్రంగా ఉత్తమ పరిష్కారానికి దారితీస్తుంది.
- Optimal substructure - ప్రతి ఎంపిక తర్వాత మిగిలిన సమస్య అదే సమస్య యొక్క చిన్న రూపం.
Activity Selection - క్లాసిక్ ఉదాహరణ
ప్రారంభ మరియు ముగింపు సమయాలతో కార్యకలాపాల సమూహం ఇచ్చినప్పుడు, అతిపెక్కు అతివ్యాప్తి కాని కార్యకలాపాలను ఎంచుకోండి.
Greedy వ్యూహం: ముగింపు సమయం ప్రకారం sort చేసి, ఎల్లప్పుడూ ముందుగా ముగిసే కార్యకలాపాన్ని ఎంచుకోండి.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
ఇది ఎందుకు పనిచేస్తుంది? ముందుగా ముగిసే కార్యకలాపాన్ని ఎంచుకోవడం భవిష్యత్ కార్యకలాపాలకు ఎక్కువ స్థలం ఇస్తుంది. మరే ఎంపికా దీని కంటే మెరుగ్గా చేయలేదు.
Huffman Coding - భావన
అత్యంత తక్కువ-ఫ్రీక్వెన్సీ రెండు చిహ్నాలను పదేపదే కలపడం ద్వారా ఉత్తమ prefix-free binary code నిర్మించండి. ఇది greedy: ప్రతి అడుగులో, చౌకైన జతను కలపండి. ఫలితం ఒక tree, ఇందులో తరచుగా వచ్చే చిహ్నాలకు చిన్న codes ఉంటాయి.
Jump Game
nums[i] index i నుండి గరిష్ట jump పొడవు అయిన array ఇచ్చినప్పుడు, మీరు చివరి index కి చేరుకోగలరా అని నిర్ణయించండి.
Greedy విధానం: ఇప్పటివరకు చేరుకోగల అతి దూర index ను ట్రాక్ చేయండి. ఎడమ నుండి కుడికి scan చేయండి - మీరు ఎప్పుడైనా వెనుకబడితే, false రిటర్న్ చేయండి.
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
Discussion
Sign in to join the discussion