algorithm
लालची एल्गोरिदम

टिप्पणियों

निरंतर knapsack समस्या

वस्तुओं (value, weight) रूप में दिए जाने पर हमें उन्हें एक क्षमता k एक नैकपैक (कंटेनर) में रखने की आवश्यकता k । ध्यान दें! हम मूल्य को अधिकतम करने के लिए आइटम तोड़ सकते हैं!

उदाहरण इनपुट:

values[] = [1, 4, 5, 2, 10]
weights[] = [3, 2, 1, 2, 4]
k = 8

अपेक्षित उत्पादन:

maximumValueOfItemsInK = 20;

कलन विधि:

1) Sort values and weights by value/weight.
   values[] = [5, 10, 4, 2, 1]
   weights[] = [1, 4, 2, 2, 3]
2) currentWeight = 0; currentValue = 0;
3) FOR i = 0; currentWeight < k && i < values.length; i++ DO:
       IF k - currentWeight < weights[i] DO
           currentValue = currentValue + values[i];
           currentWeight = currentWeight + weights[i];
       ELSE
           currentValue = currentValue + values[i]*(k - currentWeight)/weights[i]
           currentWeight = currentWeight + weights[i]*(k - currentWeight)/weights[i]
       END_IF
   END_FOR
   PRINT "maximumValueOfItemsInK = " + currentValue;

हफमैन कोडिंग

हफ़मैन कोड एक विशेष प्रकार का इष्टतम उपसर्ग कोड है जो आमतौर पर दोषरहित डेटा संपीड़न के लिए उपयोग किया जाता है। यह डेटा को संपीड़ित होने की विशेषताओं के आधार पर 20% से 90% मेमोरी में डेटा को प्रभावी ढंग से सहेजता है। हम डेटा को वर्णों का एक क्रम मानते हैं। हफ़मैन की लालची एल्गोरिथ्म एक तालिका का उपयोग करता है जो प्रत्येक वर्ण को कितनी बार (यानी, इसकी आवृत्ति) बाइनरी स्ट्रिंग के रूप में प्रत्येक वर्ण का प्रतिनिधित्व करने का एक इष्टतम तरीका बनाने के लिए उपयोग करता है। हफ़मैन कोड डेविड ए। हफ़मैन द्वारा 1951 में प्रस्तावित किया गया था।

मान लीजिए कि हमारे पास 100,000-वर्ण डेटा फ़ाइल है जिसे हम कॉम्पैक्ट रूप से संग्रहीत करना चाहते हैं। हम मानते हैं कि उस फ़ाइल में केवल 6 अलग-अलग अक्षर हैं। पात्रों की आवृत्ति निम्न द्वारा दी गई है:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
|Frequency (in thousands)|  45 |  13 |  12 |  16 |  9  |  5  |
+------------------------+-----+-----+-----+-----+-----+-----+

हमारे पास जानकारी के इस तरह की फ़ाइल का प्रतिनिधित्व करने के लिए कई विकल्प हैं। यहां, हम एक बाइनरी कैरेक्टर कोड को डिजाइन करने की समस्या पर विचार करते हैं जिसमें प्रत्येक चरित्र को एक अद्वितीय बाइनरी स्ट्रिंग द्वारा दर्शाया जाता है, जिसे हम एक कोडवर्ड कहते हैं।

निर्मित पेड़ हमें प्रदान करेगा:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
| Fixed-length Codeword  | 000 | 001 | 010 | 011 | 100 | 101 |
+------------------------+-----+-----+-----+-----+-----+-----+
|Variable-length Codeword|  0  | 101 | 100 | 111 | 1101| 1100|
+------------------------+-----+-----+-----+-----+-----+-----+

यदि हम एक निश्चित-लंबाई कोड का उपयोग करते हैं, तो हमें 6 वर्णों का प्रतिनिधित्व करने के लिए तीन बिट्स की आवश्यकता होती है। संपूर्ण फ़ाइल को कोड करने के लिए इस विधि में 300,000 बिट्स की आवश्यकता होती है। अब सवाल यह है कि क्या हम बेहतर कर सकते हैं?

एक चर-लंबाई कोड एक निश्चित-लंबाई कोड की तुलना में काफी बेहतर कर सकता है, लगातार पात्रों को छोटे कोडवर्ड और बार-बार अक्षर लंबे कोडवर्ड देता है। इस कोड की आवश्यकता है: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 बिट्स फ़ाइल का प्रतिनिधित्व करने के लिए, जो लगभग 25% मेमोरी बचाता है।

एक बात याद रखें, हम यहाँ केवल उन कोडों पर विचार करते हैं जिनमें कोई कोडवर्ड भी किसी अन्य कोडवर्ड का एक उपसर्ग नहीं है। इन्हें उपसर्ग कोड कहा जाता है । चर-लंबाई कोडिंग के लिए, हम 3-वर्ण फ़ाइल abc को 0.101.100 = 0101100 के रूप में कोड करते हैं, जहां "।" संघात को दर्शाता है।

उपसर्ग कोड वांछनीय हैं क्योंकि वे डिकोडिंग को सरल बनाते हैं। चूँकि कोई कोडवर्ड किसी अन्य का उपसर्ग नहीं है, कोडकोड जो एन्कोडेड फ़ाइल शुरू करता है, वह अस्पष्ट है। हम केवल प्रारंभिक कोडवर्ड की पहचान कर सकते हैं, इसे मूल चरित्र में वापस अनुवाद कर सकते हैं, और एन्कोडेड फ़ाइल के शेष भाग पर डिकोडिंग प्रक्रिया को दोहरा सकते हैं। उदाहरण के लिए, 001011101 पार्स विशिष्ट 0.0.101.1101 के रूप में, aabe को डीकोड जो। संक्षेप में, द्विआधारी प्रतिनिधित्व के सभी संयोजन अद्वितीय हैं। उदाहरण के लिए कहें, यदि एक अक्षर को 110 से निरूपित किया जाता है, तो 1101 या 1100 तक किसी अन्य पत्र को निरूपित नहीं किया जाएगा। ऐसा इसलिए है क्योंकि आप 110 का चयन करने के लिए भ्रम का सामना कर सकते हैं या अगले बिट को जारी रखने के लिए जारी रख सकते हैं और उस का चयन कर सकते हैं।

संपीड़न तकनीक:

तकनीक नोड्स का एक बाइनरी ट्री बनाकर काम करती है। ये एक नियमित सरणी में संग्रहीत किए जा सकते हैं, जिनमें से आकार प्रतीकों की संख्या पर निर्भर करता है, एन । एक नोड या तो लीफ नोड या आंतरिक नोड हो सकता है । प्रारंभ में सभी नोड्स लीफ नोड्स होते हैं, जिसमें प्रतीक स्वयं, इसकी आवृत्ति और वैकल्पिक रूप से, इसके बच्चे नोड्स के लिए एक लिंक होता है। एक सम्मेलन के रूप में, बिट '0' बाएं बच्चे का प्रतिनिधित्व करता है और बिट '1' सही बच्चे का प्रतिनिधित्व करता है। नोड्स को संग्रहीत करने के लिए प्राथमिकता कतार का उपयोग किया जाता है, जो पॉप होने पर सबसे कम आवृत्ति के साथ नोड प्रदान करता है। प्रक्रिया नीचे वर्णित है:

1. प्रत्येक प्रतीक के लिए एक पत्ता नोड बनाएं और इसे प्राथमिकता कतार में जोड़ें।
2. जबकि कतार में एक से अधिक नोड हैं:
   1. कतार से सर्वोच्च प्राथमिकता के दो नोड निकालें।
   2. बच्चों के रूप में इन दो नोड्स के साथ और दो नोड्स की आवृत्ति के योग के बराबर आवृत्ति के साथ एक नया आंतरिक नोड बनाएं।
   3. कतार में नया नोड जोड़ें।
3. शेष नोड रूट नोड है और हफमैन पेड़ पूरा हो गया है।

हमारे उदाहरण के लिए:

छद्म कोड इस तरह दिखता है:

Procedure Huffman(C):     // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
    n = node(C[i])
    Q.push(n)
end for
while Q.size() is not equal to 1
    Z = new node()
    Z.left = x = Q.pop
    Z.right = y = Q.pop
    Z.frequency = x.frequency + y.frequency
    Q.push(Z)
end while
Return Q

यद्यपि रैखिक-समय पर दिए गए सॉर्ट किए गए इनपुट, मनमाने ढंग से इनपुट के सामान्य मामलों में, इस एल्गोरिथ्म का उपयोग करने के लिए पूर्व-छँटाई की आवश्यकता होती है। इस प्रकार, चूंकि छँटाई सामान्य मामलों में O (nlogn) समय लेती है, दोनों विधियों में एक ही जटिलता है।

चूँकि यहाँ n वर्णमाला में प्रतीकों की संख्या है, जो आम तौर पर बहुत छोटी संख्या (संदेश की लंबाई की तुलना में एन्कोडेड) है, इस एल्गोरिथ्म की पसंद में समय की जटिलता बहुत महत्वपूर्ण नहीं है।

अपघटन तकनीक:

विघटन की प्रक्रिया बस उपसर्ग कोड की धारा को अलग-अलग बाइट मान में अनुवाद करने का मामला है, आमतौर पर हफ़मैन पेड़ के नोड को नोड द्वारा ट्रेस करके के रूप में प्रत्येक बिट इनपुट स्ट्रीम से पढ़ा जाता है। पत्ती नोड तक पहुंचना आवश्यक रूप से उस विशेष बाइट मान की खोज को समाप्त करता है। पत्ती मूल्य वांछित चरित्र का प्रतिनिधित्व करता है। आमतौर पर हफ़मैन ट्री का निर्माण प्रत्येक संपीड़न चक्र पर सांख्यिकीय रूप से समायोजित डेटा का उपयोग करके किया जाता है, इस प्रकार पुनर्निर्माण काफी सरल है। अन्यथा, पेड़ को फिर से संगठित करने की जानकारी अलग से भेजी जानी चाहिए। छद्म कोड:

Procedure HuffmanDecompression(root, S):   // root represents the root of Huffman Tree
n := S.length                              // S refers to bit-stream to be decompressed
for i := 1 to n
    current = root
    while current.left != NULL and current.right != NULL
        if S[i] is equal to '0'
            current := current.left
        else
            current := current.right
        endif
        i := i+1
    endwhile
    print current.symbol
endfor

लालची व्याख्या:
हफ़मैन कोडिंग प्रत्येक चरित्र की घटना को देखता है और इसे एक इष्टतम तरीके से एक बाइनरी स्ट्रिंग के रूप में संग्रहीत करता है। विचार इनपुट इनपुट पात्रों के लिए चर-लंबाई कोड आवंटित करने के लिए है, निर्दिष्ट कोड की लंबाई संबंधित वर्णों की आवृत्तियों पर आधारित होती है। हम एक बाइनरी ट्री बनाते हैं और उस पर बॉटम-अप तरीके से काम करते हैं ताकि कम से कम दो लगातार अक्षर जितना संभव हो जड़ से दूर हो। इस तरह, सबसे लगातार चरित्र को सबसे छोटा कोड मिलता है और सबसे कम चरित्र को सबसे बड़ा कोड मिलता है।

संदर्भ:

• एल्गोरिदम का परिचय - चार्ल्स ई। लिसेरसन, क्लिफोर्ड स्टीन, रोनाल्ड रिवेस्ट और थॉमस एच। कॉर्मेन
• हफ़मैन कोडिंग - विकिपीडिया
• असतत गणित और उसके अनुप्रयोग - केनेथ एच। रोसेन

परिवर्तन करने की समस्या

एक मुद्रा प्रणाली को देखते हुए, क्या इस राशि के अनुरूप सिक्कों की एक राशि देना और सिक्कों का न्यूनतम सेट खोजना संभव है।

कैनन मनी सिस्टम। कुछ पैसे की व्यवस्था के लिए, जैसे हम वास्तविक जीवन में उपयोग करते हैं, "सहज" समाधान पूरी तरह से काम करता है। उदाहरण के लिए, यदि अलग-अलग यूरो सिक्के और बिल (सेंट को छोड़कर) 1 €, 2 €, 5 €, 10 € हैं, तो उच्चतम सिक्का या बिल देने तक हम राशि तक पहुँचते हैं और इस प्रक्रिया को दोहराने से सिक्कों का न्यूनतम सेट होगा। ।

हम OCaml के साथ पुनरावृत्ति कर सकते हैं:

(* assuming the money system is sorted in decreasing order *)
let change_make money_system amount =
  let rec loop given amount =
    if amount = 0 then given
    else 
      (* we find the first value smaller or equal to the remaining amount *)
      let coin = List.find ((>=) amount) money_system in
      loop (coin::given) (amount - coin)
  in loop [] amount

ये सिस्टम इसलिए बनाए गए हैं ताकि बदलाव करना आसान हो। समस्या तब और कठिन हो जाती है जब यह मनमाने ढंग से धन प्रणाली में आता है।

सामान्य मामला। 10 €, 7 € और 5 € के सिक्कों के साथ 99 € कैसे दें? यहाँ, 10 € के सिक्के देने तक हम 9 € के साथ छोड़ दिए जाते हैं, स्पष्ट रूप से कोई समाधान नहीं होता है। इससे भी बदतर एक समाधान मौजूद नहीं हो सकता है। यह समस्या वास्तव में np-hard है, लेकिन स्वीकार्य समाधान लालच और संस्मरण को मिलाते हैं। विचार सभी अधिभोग का पता लगाने और सिक्कों की न्यूनतम संख्या के साथ एक लेने के लिए है।

एक राशि> X> 0 देने के लिए, हम पैसे सिस्टम में एक पी पी चुनते हैं, और फिर XP के अनुरूप उप-समस्या को हल करते हैं। हम सिस्टम के सभी टुकड़ों के लिए यह कोशिश करते हैं। समाधान, यदि यह मौजूद है, तो सबसे छोटा रास्ता है जो 0 का नेतृत्व करता है।

यहाँ इस विधि के अनुरूप एक OCaml पुनरावर्ती कार्य है। यदि कोई समाधान मौजूद नहीं है, तो यह कोई भी नहीं लौटाता है।

(* option utilities *)
let optmin x y =
  match x,y with
  | None,a | a,None -> a
  | Some x, Some y-> Some (min x y)

let optsucc = function
  | Some x -> Some (x+1)
  | None -> None

(* Change-making problem*)
let change_make money_system amount =
  let rec loop n =
    let onepiece acc piece =
      match n - piece with
      | 0 -> (*problem solved with one coin*) 
             Some 1
      | x -> if x < 0 then 
               (*we don't reach 0, we discard this solution*)
               None
             else
               (*we search the smallest path different to None with the remaining pieces*) 
               optmin (optsucc (loop x)) acc
    in
    (*we call onepiece forall the pieces*)
    List.fold_left onepiece None money_system
  in loop amount

नोट : हम टिप्पणी कर सकते हैं कि यह प्रक्रिया एक ही मूल्य के लिए निर्धारित परिवर्तन की कई बार गणना कर सकती है। व्यवहार में, इन पुनरावृत्ति से बचने के लिए संस्मरण का उपयोग करने से परिणाम तेजी से (तेजी से) होता है।

गतिविधि चयन समस्या

समस्या

आपके पास करने के लिए (गतिविधियों) चीजों का एक सेट है। प्रत्येक गतिविधि का प्रारंभ समय और अंत समय होता है। आपको एक बार में एक से अधिक गतिविधि करने की अनुमति नहीं है। आपका कार्य अधिकतम गतिविधियों को करने का एक तरीका खोजना है।

उदाहरण के लिए, मान लें कि आपके पास चुनने के लिए कक्षाओं का चयन है।

याद रखें, आप एक ही समय में दो कक्षाएं नहीं ले सकते। इसका मतलब है कि आप कक्षा 1 और 2 नहीं ले सकते क्योंकि वे 10.30 AM से 11.00 AM तक साझा करते हैं। हालांकि, आप कक्षा 1 और 3 ले सकते हैं क्योंकि वे एक सामान्य समय साझा नहीं करते हैं। इसलिए आपका काम बिना किसी ओवरलैप के अधिकतम संभव कक्षाएं लेना है। आप ऐसा कैसे कर सकते हैं?

विश्लेषण

लालची दृष्टिकोण से समाधान के लिए सोचते हैं। हम सभी में से कुछ ने बेतरतीब ढंग से कुछ दृष्टिकोण चुना और जांच करें कि काम करेगा या नहीं।

• गतिविधि को प्रारंभ समय के अनुसार क्रमबद्ध करें जिसका अर्थ है कि कौन सी गतिविधि पहले शुरू होती है हम उन्हें पहले लेंगे। फिर पहले छांटी गई सूची से अंतिम तक ले जाएं और जांच लें कि यह पिछली ली गई गतिविधि से होगी या नहीं। यदि वर्तमान गतिविधि पहले से ली गई गतिविधि के साथ प्रतिच्छेद नहीं करती है, तो हम गतिविधि का प्रदर्शन करेंगे अन्यथा हम प्रदर्शन नहीं करेंगे। यह दृष्टिकोण कुछ मामलों की तरह काम करेगा

सॉर्टिंग ऑर्डर 4 होगा -> 1 -> 2 -> 3। गतिविधि 4 -> 1 -> 3 का प्रदर्शन किया जाएगा और गतिविधि 2 को छोड़ दिया जाएगा। अधिकतम 3 गतिविधि की जाएगी। यह इस प्रकार के मामलों के लिए काम करता है। लेकिन यह कुछ मामलों के लिए विफल हो जाएगा। मामले के लिए इस दृष्टिकोण को लागू करने देता है

सॉर्ट क्रम 4 होगा -> 1 -> 2 -> 3 और केवल गतिविधि 4 का प्रदर्शन किया जाएगा, लेकिन उत्तर गतिविधि 1 -> 3 या 2 -> 3 हो सकता है। इसलिए उपरोक्त मामले के लिए हमारा दृष्टिकोण काम नहीं करेगा। चलो एक और दृष्टिकोण की कोशिश करो

• समय की अवधि के अनुसार गतिविधि को छाँटें, जिसका अर्थ है कि सबसे छोटी गतिविधि पहले करें। जो पिछली समस्या को हल कर सकता है। हालांकि समस्या पूरी तरह से हल नहीं हुई है। अभी भी कुछ मामले हैं जो समाधान को विफल कर सकते हैं। इस दृष्टिकोण को केस बोले पर लागू करें।

यदि हम समय की अवधि के अनुसार गतिविधि को क्रमबद्ध करते हैं, तो क्रम 2 -> 3 ---> 1 होगा। और यदि हम गतिविधि नंबर 2 पहले करते हैं तो कोई अन्य गतिविधि नहीं की जा सकती है। लेकिन जवाब गतिविधि 1 होगा तो 3 प्रदर्शन करेंगे। इसलिए हम अधिकतम 2 गतिविधि कर सकते हैं। इस समस्या का समाधान नहीं हो सकता है। हमें एक अलग दृष्टिकोण की कोशिश करनी चाहिए।

समाधान

• समय को समाप्त करके गतिविधि को क्रमबद्ध करें अर्थात गतिविधि पहले खत्म हो जाए। एल्गोरिथ्म नीचे दिया गया है

1. गतिविधियों को इसके अंतिम समय तक क्रमबद्ध करें।
2. यदि प्रदर्शन की जाने वाली गतिविधि सामान्य गतिविधियों को साझा नहीं करती है जो पहले की गई गतिविधियों के साथ होती है, तो गतिविधि करें।

पहले उदाहरण का विश्लेषण करें

गतिविधि को उसके अंतिम समय तक क्रमबद्ध करें, इसलिए क्रमबद्ध क्रमांक 1 -> 5 -> 2 -> 4 -> 3 .. उत्तर 1 -> 3 ये दो गतिविधियाँ की जाएंगी। जवाब है कि ans। यहाँ sudo कोड है।

1. क्रमबद्ध: गतिविधियों
2. गतिविधियों की क्रमबद्ध सूची से पहली गतिविधि करें।
3. सेट करें: करंट_एक्टिविटी: = पहली गतिविधि
4. सेट: एंड_टाइम: = एंड_टाइम वर्तमान गतिविधि
5. समाप्त होने पर मौजूद नहीं होने पर अगली गतिविधि पर जाएं।
6. यदि वर्तमान गतिविधि का start_time <= end_time: गतिविधि निष्पादित करें और 4 पर जाएं
7. और: 5 को मिला।

कोडिंग सहायता के लिए यहाँ देखें http://www.geeksforgeeks.org/greedy-al एल्गोरिदम-set-1-activity-selection-problem /