நீங்கள் நினைப்பதை விட, மேம்பாட்டுத் திட்டங்கள் பல்வேறு அல்காரிதம்களைப் பயன்படுத்துகின்றன. எடுத்துக்காட்டாக, சில தரவை சில அளவுருக்கள் (நெடுவரிசைகள்) மூலம் வரிசைப்படுத்த வேண்டும் என்று வைத்துக்கொள்வோம், எனவே அதிக முயற்சி இல்லாமல் தரவு வழியாக செல்லலாம். எனவே ஒரு வேலை நேர்காணல் செய்பவர் உங்களிடம் ஒரு குறிப்பிட்ட அடிப்படை வழிமுறையைப் பற்றி கேட்பது மற்றும் குறியீட்டைப் பயன்படுத்தி அதை செயல்படுத்தும் பணியை வழங்குவது விசித்திரமாக இருக்காது. நீங்கள் இந்த இணையதளத்தில் இருப்பதால், நீங்கள் ஜாவாவில் எழுதுகிறீர்கள் என்று எண்ணும் அளவுக்கு நான் தைரியமாக இருப்பேன். அதனால்தான் சில அடிப்படை அல்காரிதம்கள் மற்றும் ஜாவாவில் அவற்றை எவ்வாறு செயல்படுத்துவது என்பதற்கான குறிப்பிட்ட எடுத்துக்காட்டுகளுடன் உங்களைப் பழக்கப்படுத்திக்கொள்ளுமாறு இன்று நான் பரிந்துரைக்கிறேன். "சில" என்பதன் மூலம், அதாவது:
வரிசை வரிசையாக்க அல்காரிதம்களின் கண்ணோட்டம்:
குமிழி வரிசை,
தேர்வு வகை,
செருகும் வரிசை,
ஷெல் வரிசை,
விரைவான வரிசை,
ஒன்றிணைக்கும் வகை,
பேராசை நெறிமுறைகள்
பாதை கண்டறியும் அல்காரிதம்கள்
ஆழமான முதல் தேடல்
அகலம்-முதல் தேடல்
Dijkstra's Shortest Path First algorithm
சரி, மேலும் கவலைப்படாமல், வணிகத்திற்கு வருவோம்.
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 முறை செய்யப்படுகிறது. உள் வளையம் N முறையும் செயல்படுத்தப்படுகிறது. இதன் விளைவாக, நாம் N*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);
}
}
சந்தேகத்திற்கு இடமின்றி, Quicksort அல்காரிதம் மிகவும் பிரபலமானது, ஏனெனில் பெரும்பாலான சூழ்நிலைகளில் இது மற்றவர்களை விட வேகமாக இயங்கும். அதன் நேர சிக்கலானது 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;
}
}
இங்கே சிறப்பு எதுவும் இல்லை: உருப்படியின் பண்புகளை வரையறுக்கும் மூன்று புலங்கள் (பெயர், எடை, மதிப்பு). மேலும், நீங்கள் பார்க்க முடியும் என, ஒப்பிடக்கூடிய இடைமுகம் எங்கள் பொருட்களை விலையின்படி வரிசைப்படுத்த அனுமதிக்கும் வகையில் செயல்படுத்தப்படுகிறது. அடுத்து, நாம் பை வகுப்பைப் பார்ப்போம், இது எங்கள் நாப்சாக்கைக் குறிக்கிறது:
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 என்பது நமது பேக்பேக்கின் திறன் ஆகும், இது நாம் ஒரு பொருளை உருவாக்கும் போது அமைக்கப்படும்;
பொருட்கள் நமது பையிலுள்ள பொருட்களைக் குறிக்கின்றன;
தற்போதைய எடை , தற்போதைய மதிப்பு - இந்த புலங்கள் பையிலுள்ள அனைத்து பொருட்களின் தற்போதைய எடை மற்றும் மதிப்பை சேமித்து வைக்கும், இது 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
கொஞ்சம் நல்லது, இல்லையா? பேராசை கொண்ட வழிமுறையானது ஒவ்வொரு அடியிலும் உள்ளூரில் உகந்த தேர்வை செய்கிறது, இறுதித் தீர்வும் உகந்ததாக இருக்கும் என்று நம்புகிறது. இந்த அனுமானம் எப்போதும் செல்லுபடியாகாது, ஆனால் பல பணிகளுக்கு, பேராசை கொண்ட அல்காரிதம்கள் ஒரு சிறந்த இறுதி தீர்வை அளிக்கின்றன. இந்த அல்காரிதத்தின் நேர சிக்கலானது O(N) ஆகும். மிகவும் நல்லது, இல்லையா?
நீங்கள் இந்த இணையதளத்தில் இருப்பதால், நீங்கள் ஜாவாவில் எழுதுகிறீர்கள் என்று எண்ணும் அளவுக்கு நான் தைரியமாக இருப்பேன். அதனால்தான் சில அடிப்படை அல்காரிதம்கள் மற்றும் ஜாவாவில் அவற்றை எவ்வாறு செயல்படுத்துவது என்பதற்கான குறிப்பிட்ட எடுத்துக்காட்டுகளுடன் உங்களைப் பழக்கப்படுத்திக்கொள்ளுமாறு இன்று நான் பரிந்துரைக்கிறேன். "சில" என்பதன் மூலம், அதாவது:
GO TO FULL VERSION