विकास परियोजनाएं आपके विचार से अधिक बार विभिन्न एल्गोरिदम का उपयोग करती हैं। उदाहरण के लिए, मान लीजिए कि हमें कुछ डेटा को कुछ पैरामीटर (कॉलम) द्वारा सॉर्ट करने की आवश्यकता है ताकि हम बिना अधिक प्रयास किए डेटा के माध्यम से नेविगेट कर सकें। तो नौकरी साक्षात्कारकर्ता के लिए यह बिल्कुल अजीब नहीं होगा कि वह आपको एक विशिष्ट बुनियादी एल्गोरिदम के बारे में पूछे और शायद कोड का उपयोग करके इसे लागू करने का कार्य दें। और जब से आप इस वेबसाइट पर हैं, मैं इतना बोल्ड हो जाऊंगा कि मान लूं कि आप जावा में लिख रहे हैं। इसीलिए आज मैं सुझाव देता हूं कि आप खुद को कुछ बुनियादी एल्गोरिदम और जावा में उन्हें लागू करने के विशिष्ट उदाहरणों से परिचित कराएं। "कुछ" से मेरा मतलब है:
सरणी छँटाई एल्गोरिदम का अवलोकन:
बुलबुले की तरह,
चयन छांटना,
सम्मिलन सॉर्ट,
शैल छँटाई,
जल्दी से सुलझाएं,
मर्ज़ सॉर्ट,
लालची एल्गोरिदम
पाथफाइंडिंग एल्गोरिदम
गहराई-पहली खोज
पहले चौड़ाई खोजो
दिज्क्स्ट्रा का सबसे छोटा रास्ता सबसे पहले एल्गोरिथ्म
खैर, आगे की हलचल के बिना, व्यापार के लिए नीचे उतरें।
1. छँटाई एल्गोरिदम का अवलोकन
बुलबुले की तरह
यह छँटाई एल्गोरिथ्म मुख्य रूप से इसकी सादगी के लिए जाना जाता है, लेकिन यह सबसे धीमी गति से भी एक है। एक उदाहरण के रूप में, आरोही क्रम में संख्याओं के लिए बबल सॉर्ट पर विचार करें। आइए संख्याओं के एक यादृच्छिक क्रम की कल्पना करें। हम अनुक्रम की शुरुआत से शुरू करते हुए, इन नंबरों पर निम्नलिखित कदम उठाएंगे:
दो संख्याओं की तुलना करें;
यदि बाईं ओर की संख्या बड़ी है, तो उन्हें अदला-बदली करें;
एक स्थिति को दाईं ओर ले जाएं।
इन चरणों को पूरे अनुक्रम पर करने के बाद, हम पाएंगे कि सबसे बड़ी संख्या हमारी संख्याओं की श्रृंखला के अंत में है। फिर हम ऊपर के समान चरणों को निष्पादित करते हुए अनुक्रम पर एक और पास बनाते हैं। लेकिन इस बार हम सूची के अंतिम तत्व को शामिल नहीं करेंगे, क्योंकि यह सबसे बड़ी संख्या है और पहले से ही संख्याओं को क्रमबद्ध करते समय यह ठीक उसी स्थान पर होना चाहिए। एक बार फिर, हम अगली सबसे बड़ी संख्या को हमारे अनुक्रम के अंत तक ले जाएंगे। बेशक, इसका मतलब है कि दो सबसे बड़ी संख्याएं अपने उचित स्थान पर खड़ी हैं। फिर से, हम अनुक्रम में पास करते हैं, उन तत्वों को छोड़कर जो पहले से ही अपने स्थान पर हैं, जब तक कि सभी तत्व आवश्यक क्रम में न हों। आइए एक नजर डालते हैं कि जावा कोड में बबल सॉर्ट कैसे लागू किया जाता है:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
जैसा कि आप देख सकते हैं, यहां कुछ भी जटिल नहीं है। सब कुछ बहुत अच्छा लगता है और यह एक कमी के लिए नहीं तो होगा - बबल सॉर्ट बहुत, बहुत धीमा है। इसकी समय जटिलता O(N²) है, क्योंकि हमारे पास नेस्टेड लूप हैं। तत्वों पर बाहरी पाश एन बार किया जाता है। आंतरिक लूप को भी N बार निष्पादित किया जाता है। नतीजतन, हमें एन * एन, या एन², पुनरावृत्तियां मिलती हैं।
चयन छांटना
यह एल्गोरिथम बबल सॉर्ट के समान है, लेकिन यह थोड़ी तेजी से काम करता है। दोबारा, एक उदाहरण के रूप में, संख्याओं का एक क्रम लेते हैं जिन्हें हम आरोही क्रम में व्यवस्थित करना चाहते हैं। इस एल्गोरिथ्म का सार सभी संख्याओं के माध्यम से क्रमिक रूप से पुनरावृति करना है और सबसे छोटे तत्व का चयन करना है, जिसे हम सबसे बाएं तत्व (0 तत्व) के साथ लेते हैं और स्वैप करते हैं। यहां हमारे पास बबल सॉर्ट जैसी स्थिति है, लेकिन इस मामले में हमारा सॉर्ट किया गया तत्व सबसे छोटा होगा। इसलिए, तत्वों से अगला पास इंडेक्स 1 वाले तत्व से शुरू होगा। हम इन पासों को तब तक दोहराएंगे जब तक कि सभी तत्वों को सॉर्ट नहीं किया जाता। जावा में कार्यान्वयन:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
यह एल्गोरिथम बबल सॉर्ट से बेहतर है, क्योंकि यहां आवश्यक पारियों की संख्या O(N²) से O(N) तक कम हो जाती है। हम पूरी सूची में एक तत्व नहीं चला रहे हैं, लेकिन तुलना की संख्या अभी भी O(N²) है।
सम्मिलन सॉर्ट
हम एक और संख्या क्रम पर विचार करते हैं जिसे हम आरोही क्रम में व्यवस्थित करना चाहते हैं। इस एल्गोरिथ्म में एक मार्कर रखा जाता है, जहां मार्कर के बाईं ओर के सभी तत्व पहले से ही आंशिक रूप से आपस में क्रमबद्ध होते हैं। एल्गोरिथ्म के प्रत्येक चरण में, तत्वों में से एक का चयन किया जाएगा और आंशिक रूप से क्रमबद्ध अनुक्रम में वांछित स्थान पर रखा जाएगा। इस प्रकार, जब तक सभी तत्वों की जांच नहीं हो जाती, तब तक क्रमबद्ध भाग बढ़ेगा। क्या आप सोच रहे हैं कि आप उन तत्वों का सबसेट कैसे प्राप्त करते हैं जो पहले से ही क्रमबद्ध हैं और हम कैसे निर्धारित करते हैं कि मार्कर को कहाँ रखा जाए? लेकिन पहले तत्व से युक्त सरणी पहले से ही क्रमबद्ध है, है ना? आइए जावा में कार्यान्वयन पर एक नज़र डालें:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
इस प्रकार का प्रकार ऊपर वर्णित लोगों से बेहतर है, क्योंकि इस तथ्य के बावजूद कि इसका O(N²) चलने का समय समान है, यह एल्गोरिथम बबल सॉर्ट से दोगुना तेज़ है और चयन सॉर्ट की तुलना में थोड़ा तेज़ है।
शैल छँटाई
यह सॉर्ट अनिवार्य रूप से एक संशोधित इंसर्शन सॉर्ट है। मैं किस बारे में बात कर रहा हूं? आइए पहले चीजों को पहले रखें। हमें पहले एक अंतराल चुनना होगा। इस चुनाव को करने के कई तरीके हैं। हम इस बारे में ज्यादा डिटेल में नहीं जाएंगे। आइए हमारी सरणी को आधे में विभाजित करें और कुछ संख्या प्राप्त करें - यह हमारा अंतराल होगा। इसलिए, यदि हमारी सरणी में 9 तत्व हैं, तो हमारा अंतराल 9/2 = 4.5 होगा। हम आंशिक भाग को छोड़ देते हैं और 4 प्राप्त करते हैं, क्योंकि सरणी सूचकांक केवल पूर्णांक हो सकते हैं। हम इस अंतराल का उपयोग अपने समूह बनाने के लिए करेंगे। यदि किसी तत्व का सूचकांक 0 है, तो उसके समूह में अगले तत्व का सूचकांक 0 + 4 है, अर्थात 4. तीसरे तत्व का सूचकांक 4 + 4, चौथा - 8 + 4, और इसी तरह होगा। दूसरे समूह में, पहला तत्व होगा 1,5,9... तीसरे और चौथे समूह में स्थिति समान होगी। नतीजतन, संख्या सरणी से {6,3,8,8,6,9,4,11,1} हमें चार समूह मिलते हैं: I - {6,6,1} II - {3,9} III - {8,4 } IV - {8,11} वे सामान्य सरणी में अपना स्थान बनाए रखते हैं, लेकिन हमने एक ही समूह के सदस्यों के रूप में चिह्नित किया है: {6,3,8,8,6,9,4,11,1} अगला, सम्मिलन इन समूहों पर सॉर्ट लागू किया जाता है, और फिर वे इस तरह दिखते हैं: I - {1,6,6} II - {3,9} III - {4,8} IV - {8,11} सामान्य सरणी में, समूहों द्वारा अधिग्रहित कोशिकाएं समान रहेंगी, लेकिन उनका आंतरिक क्रम उपरोक्त समूहों के क्रम के अनुसार बदल जाएगा: {1,3,4,8,6,9,8,11,6} सरणी एक बन गई है थोड़ा और आदेश दिया, है ना? अगले अंतराल को 2 से विभाजित किया जाएगा: 4/2 = 2 हमारे पास दो समूह हैं: I - {1,4,6,8,6} II - {3,8,9,11} सामान्य सरणी में, हमारे पास है : {1,3,4,8,6,9,8,11,6} हम दोनों समूहों पर सम्मिलन सॉर्ट एल्गोरिदम चलाते हैं, और यह सरणी प्राप्त करते हैं: {1,3,4,8,6,9,6, 11, 8} अब हमारी सरणी लगभग क्रमबद्ध हो गई है। हमें एल्गोरिदम का अंतिम पुनरावृत्ति करने की आवश्यकता है: हम अंतराल को 2: 2/2 = 1 से विभाजित करते हैं। हमें एक समूह मिलता है जिसमें संपूर्ण सरणी शामिल होती है: {1,3,4,8,6,9,6,11 ,8} उस पर इंसर्शन सॉर्ट एल्गोरिथम चलाने पर, हमें मिलता है: {1,3,4,6,6,8,8,9,11} आइए देखें कि हम जावा कोड में इस सॉर्ट को कैसे जीवंत कर सकते हैं:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
इस समय, शेलसॉर्ट के प्रदर्शन को चित्रित करना आसान नहीं है, क्योंकि परिणाम अलग-अलग स्थितियों में भिन्न होते हैं। प्रायोगिक अनुमान O(N 3/2 ) से O(N 7/6 ) तक है।
जल्दी से सुलझाएं
यह सबसे लोकप्रिय एल्गोरिदम में से एक है, इसलिए यह विशेष ध्यान देने योग्य है। इस एल्गोरिथम का सार यह है कि तत्वों की सूची में एक धुरी तत्व का चयन किया जाता है। हम धुरी तत्व के सापेक्ष अन्य सभी तत्वों को क्रमबद्ध करते हैं। धुरी तत्व से कम मान बाईं ओर हैं। इससे बड़े मान दाईं ओर हैं। अगला, धुरी तत्वों को दाएं और बाएं भागों में भी चुना जाता है, और वही होता है: इन तत्वों के सापेक्ष मूल्यों को क्रमबद्ध किया जाता है। फिर नवगठित भागों में धुरी तत्वों का चयन किया जाता है, और इसी तरह जब तक हमें एक क्रमबद्ध क्रम नहीं मिल जाता। इस एल्गोरिथम का निम्नलिखित जावा कार्यान्वयन पुनरावर्तन का उपयोग करता है:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
बिना किसी संदेह के, क्विकसॉर्ट एल्गोरिथम सबसे लोकप्रिय है, क्योंकि ज्यादातर स्थितियों में यह दूसरों की तुलना में तेजी से चलता है। इसकी समय जटिलता O(N*logN) है।
मर्ज़ सॉर्ट
यह किस्म भी लोकप्रिय है। यह कई एल्गोरिदम में से एक है जो "फूट डालो और जीतो" के सिद्धांत पर निर्भर करता है। इस तरह के एल्गोरिदम पहले समस्या को प्रबंधनीय भागों में विभाजित करते हैं (क्विक सॉर्ट ऐसे एल्गोरिथम का एक और उदाहरण है)। तो इस एल्गोरिथम का सार क्या है?
विभाजित करना:
सरणी लगभग एक ही आकार के दो भागों में विभाजित है। इन दो भागों में से प्रत्येक को दो और भागों में विभाजित किया जाता है, और तब तक जब तक कि सबसे छोटा संभव अविभाज्य भाग न रह जाए। हमारे पास सबसे छोटे अविभाज्य भाग होते हैं जब प्रत्येक सरणी में एक तत्व होता है, अर्थात एक सरणी जो पहले से ही क्रमबद्ध होती है।
जीत:
यहीं से हम उस प्रक्रिया की शुरुआत करते हैं जिसने एल्गोरिथम को अपना नाम दिया: मर्ज। ऐसा करने के लिए, हम दो परिणामी क्रमबद्ध सरणियाँ लेते हैं और उन्हें एक में मिला देते हैं। इस स्थिति में, दो सरणियों के पहले तत्वों में से सबसे छोटा परिणामी सरणी में लिखा जाता है। यह ऑपरेशन तब तक दोहराया जाता है जब तक कि इन दो सरणियों के सभी तत्वों को कॉपी नहीं कर लिया जाता। यही है, अगर हमारे पास दो न्यूनतम सरणियाँ {6} और {4} हैं, तो हम उनके मूल्यों की तुलना करते हैं और इस मर्ज किए गए परिणाम को उत्पन्न करते हैं: {4,6}। यदि हमने सरणी {4,6} और {2,8} को क्रमबद्ध किया है, तो हम पहले 4 और 2 मानों की तुलना करते हैं, और फिर हम परिणामी सरणी में 2 लिखते हैं। उसके बाद, 4 और 8 की तुलना की जाएगी, और हम 4 लिखेंगे। अंत में, 6 और 8 की तुलना की जाएगी। तदनुसार, हम 6 लिखेंगे, और उसके बाद ही हम 8 लिखेंगे। परिणामस्वरूप, हमें निम्नलिखित विलयित सरणी मिलती है: {2,4,6,8}। यह जावा कोड में कैसा दिखेगा? इस एल्गोरिथ्म को चलाने के लिए, हमारे लिए पुनरावर्तन का उपयोग करना सुविधाजनक होगा:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
त्वरित छँटाई के रूप में, हम पुनरावर्ती विधि को एक मध्यवर्ती विधि में स्थानांतरित करते हैं ताकि उपयोगकर्ता को केवल क्रमबद्ध करने के लिए सरणी की आपूर्ति करने की आवश्यकता हो और कोई अतिरिक्त डिफ़ॉल्ट तर्क प्रदान करने के बारे में चिंता करने की आवश्यकता न हो। इस एल्गोरिथ्म में क्विकॉर्ट के साथ समानताएं हैं, और आश्चर्यजनक रूप से इसकी निष्पादन गति समान है: O(N*logN)।
2. लालची एल्गोरिदम
एक लालची एल्गोरिथ्म एक दृष्टिकोण है जहां प्रत्येक चरण में स्थानीय रूप से इष्टतम निर्णय किए जाते हैं, इस धारणा के साथ कि अंतिम समाधान भी इष्टतम होगा। "इष्टतम" समाधान वह होगा जो किसी विशेष कदम/चरण पर सबसे स्पष्ट और तत्काल लाभ प्रदान करता है। इस एल्गोरिथम का पता लगाने के लिए, आइए एक काफी सामान्य समस्या लें - नैकपैक समस्या। एक पल के लिए मान लीजिए कि आप चोर हैं। आप रात में एक झोला (बैकपैक) लेकर दुकान में घुसे हैं। आपके सामने कई सामान हैं जिन्हें आप चुरा सकते हैं। लेकिन साथ ही, आपके थैले की क्षमता सीमित होती है। यह 30 यूनिट से अधिक वजन नहीं उठा सकता है। आप सामान का सबसे मूल्यवान सेट भी ले जाना चाहते हैं जो बैकपैक में फिट होगा। आप कैसे निर्धारित करते हैं कि आपके बैग में क्या रखा जाए? इसलिए,
सबसे महंगी वस्तु चुनें जो अभी तक नहीं ली गई है।
यदि यह थैले में फिट बैठता है, तो इसे डालें। यदि नहीं, तो इसे छोड़ दें।
क्या हमने पहले ही सब कुछ चुरा लिया है? यदि नहीं, तो हम चरण 1 पर वापस लौटते हैं। यदि हाँ, तो हम स्टोर से तुरंत निकल जाते हैं, क्योंकि हम वह कर चुके हैं जो हम करने आए थे।
आइए इसे देखें, लेकिन जावा में। आइटम क्लास इस तरह दिखेगी:
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
यहां कुछ खास नहीं है: तीन क्षेत्र (नाम, वजन, मूल्य) जो आइटम की विशेषताओं को परिभाषित करते हैं। इसके अलावा, जैसा कि आप देख सकते हैं, तुलनीय इंटरफ़ेस लागू किया गया है ताकि हम अपने आइटम को कीमत के अनुसार क्रमबद्ध कर सकें। अगला, हम Bag क्लास को देखेंगे, जो हमारे नैकपैक को दर्शाता है:
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
maxWeight हमारे बैकपैक की क्षमता है, जो तब सेट होती है जब हम कोई वस्तु बनाते हैं;
आइटम हमारे बैकपैक में वस्तुओं का प्रतिनिधित्व करते हैं;
currentWeight , currentValue - ये फ़ील्ड बैकपैक में सभी वस्तुओं के वर्तमान वजन और मूल्य को संग्रहीत करते हैं, जिसे हम तब बढ़ाते हैं जब हम addItem विधि में एक नया आइटम जोड़ते हैं।
वैसे भी, अब उस कक्षा में चलते हैं जहाँ सारी कार्रवाई होती है:
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
सबसे पहले, हम वस्तुओं की एक सूची बनाते हैं और उसे क्रमबद्ध करते हैं। हम 30-यूनिट की क्षमता वाला एक बैग ऑब्जेक्ट बनाते हैं। अगला, हम आइटम और बैग ऑब्जेक्ट को फिलबैकपैक विधि में पास करते हैं, जो हमारे लालची एल्गोरिथ्म के अनुसार नैकपैक को भरता है:
यह बहुत सरल है: हम लागत के अनुसार क्रमबद्ध वस्तुओं की एक सूची के माध्यम से जाना शुरू करते हैं और यदि इसकी क्षमता अनुमति देती है तो उन्हें बैग में डाल दिया जाता है। यदि पर्याप्त जगह नहीं है, तो आइटम को छोड़ दिया जाएगा और जब तक हम सूची के अंत तक नहीं पहुंच जाते, तब तक हम बाकी आइटमों पर ट्रैवर्स करना जारी रखेंगे। एक बार जब हम मुख्य चलाते हैं, तो यहां कंसोल आउटपुट हमें मिलेगा:
झोले का वजन 29 है। झोले में कुल सामान की कीमत 3700 है
यह लालची एल्गोरिथ्म का एक उदाहरण है: प्रत्येक चरण में, एक स्थानीय इष्टतम समाधान का चयन किया जाता है, और अंत में, आपको विश्व स्तर पर इष्टतम समाधान मिलता है। हमारे मामले में, सबसे अच्छा विकल्प सबसे महंगी वस्तु है। लेकिन क्या यह सबसे अच्छा उपाय है? क्या आपको नहीं लगता कि हमारे बैकपैक को उन वस्तुओं से भरने के लिए हमारे समाधान में थोड़ा सुधार करना संभव है जिनका कुल मूल्य और भी अधिक है? आइए देखें कि यह कैसे किया जा सकता है।
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
यहां हम पहले प्रत्येक आइटम के लिए मूल्य-से-भार अनुपात की गणना करते हैं। यह हमें दी गई वस्तु की प्रत्येक इकाई का मूल्य बताता है। और फिर हम इन अनुपातों का उपयोग अपनी वस्तुओं को छाँटने और उन्हें अपने बैग में जोड़ने के लिए करते हैं। चलो निम्नलिखित चलाते हैं:
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
हमें यह कंसोल आउटपुट मिलता है:
थैले का वजन 29 है। थैले में सामान की कुल कीमत 4150 है
थोड़ा बेहतर है, है ना? लालची एल्गोरिथ्म हर कदम पर स्थानीय रूप से इष्टतम विकल्प बनाता है, उम्मीद करता है कि अंतिम समाधान भी इष्टतम होगा। यह धारणा हमेशा मान्य नहीं होती है, लेकिन कई कार्यों के लिए लालची एल्गोरिदम एक इष्टतम अंतिम समाधान देते हैं। इस एल्गोरिथ्म की समय जटिलता हे (एन) है। बहुत अच्छा, हुह?
और जब से आप इस वेबसाइट पर हैं, मैं इतना बोल्ड हो जाऊंगा कि मान लूं कि आप जावा में लिख रहे हैं। इसीलिए आज मैं सुझाव देता हूं कि आप खुद को कुछ बुनियादी एल्गोरिदम और जावा में उन्हें लागू करने के विशिष्ट उदाहरणों से परिचित कराएं। "कुछ" से मेरा मतलब है:
GO TO FULL VERSION