ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ ବିଷୟରେ ଜାଣନ୍ତୁ

ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ

• ଅପ୍ଟିମାଇଜେସନ୍ ସମସ୍ୟା ସମାଧାନ ପାଇଁ ଏକ ସରଳ, ସ୍ୱଜ୍ଞାନ ଏବଂ ଦକ୍ଷ ଆଭିମୁଖ୍ୟ ହେଉଛି ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ ।
• ଏଥିରେ ପ୍ରତ୍ୟେକ ପର୍ଯ୍ୟାୟରେ ଏପରି ଏକ ପସନ୍ଦ କରାଯାଏ ଯାହା ସେହି ସମୟରେ ସର୍ବୋତ୍ତମ ମନେହୁଏ, ଭବିଷ୍ୟତର ପରିଣାମ ବିଷୟରେ ଚିନ୍ତା ନକରି ।

ସୁବିଧା ଏବଂ ଅସୁବିଧା

• ସୁବିଧା: କାର୍ଯ୍ୟକାରୀ କରିବା ସହଜ ଏବଂ ପ୍ରାୟତଃ ବହୁତ ଦକ୍ଷ ।
• ଅସୁବିଧା: ସର୍ବଦା ସର୍ବୋତ୍ତମ ସମାଧାନର ଗ୍ୟାରେଣ୍ଟି ଦିଏ ନାହିଁ ।

ସାଧାରଣ ନୀତି

• ଅପ୍ଟିମାଇଜେସନ୍ ସମସ୍ୟାକୁ ବ୍ୟାଖ୍ୟା କରନ୍ତୁ ।
• ଏକ ଚୟନ ମାପଦଣ୍ଡ (ଉଦ୍ଦେଶ୍ୟ ଫଙ୍କସନ୍) ବାଛନ୍ତୁ ଯାହା ପ୍ରତ୍ୟେକ ପର୍ଯ୍ୟାୟରେ "ସର୍ବୋତ୍ତମ" ପସନ୍ଦ ନିର୍ଣ୍ଣୟ କରିବାକୁ ଅନୁମତି ଦିଏ ।
• ସମ୍ଭାବ୍ୟ ପସନ୍ଦଗୁଡିକର ସମୂହ ଉପରେ ଚୟନ ମାପଦଣ୍ଡ ପ୍ରୟୋଗ କରନ୍ତୁ ।
• ଉଦ୍ଦେଶ୍ୟ ଫଙ୍କସନ୍ କୁ ସର୍ବାଧିକ (କିମ୍ବା ସର୍ବନିମ୍ନ) କରୁଥିବା ଚୟନକୁ ଚୟନ କରନ୍ତୁ ।
• କରାଯାଇଥିବା ଚୟନକୁ ବିଚାରକୁ ନେଇ ସମସ୍ୟାକୁ ହ୍ରାସ କରନ୍ତୁ ।
• ଏକ ସମ୍ପୂର୍ଣ୍ଣ ସମାଧାନ ନହେବା ପର୍ଯ୍ୟନ୍ତ ଷ୍ଟେପ୍ 3 ରୁ 5 କୁ ପୁନରାବୃତ୍ତି କରନ୍ତୁ ।

ପ୍ରୟୋଗ ଉଦାହରଣ

ଫ୍ରାକ୍ସନାଲ୍ ବ୍ୟାକ୍‌ପ୍ୟାକ୍ ସମସ୍ୟା

• ଜଣେ ଚୋର ପାଖରେ ସର୍ବାଧିକ କ୍ଷମତା $W$ ର ଏକ ବ୍ୟାକ୍‌ପ୍ୟାକ୍ ଅଛି ।
• ତାଙ୍କ ପାଖରେ $n$ ବସ୍ତୁ ମଧ୍ୟରୁ ବାଛିବାର ଅଛି, ପ୍ରତ୍ୟେକର ଓଜନ $w_i$ ଏବଂ ମୂଲ୍ୟ $v_i$ ଅଛି ।
• ଉଦ୍ଦେଶ୍ୟ ହେଉଛି ବ୍ୟାକ୍‌ପ୍ୟାକ୍‌ର କ୍ଷମତା ଅତିକ୍ରମ ନକରି ନିଆଯାଇଥିବା ବସ୍ତୁଗୁଡ଼ିକର ମୋଟ ମୂଲ୍ୟକୁ ସର୍ବାଧିକ କରିବା ।
• କେବଳ ଏକ ବସ୍ତୁର ଏକ ଅଂଶ ନେବା ସମ୍ଭବ ।

ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ

• ପ୍ରତ୍ୟେକ ବସ୍ତୁ ପାଇଁ ମୂଲ୍ୟ/ଓଜନ ଅନୁପାତ $v_i/w_i$ ଗଣନା କରନ୍ତୁ ।
• ଏହି ଅନୁପାତର ଅବତରଣ କ୍ରମରେ ବସ୍ତୁଗୁଡ଼ିକୁ ସଜାନ୍ତୁ ।
• ଯେଉଁଗୁଡ଼ିକର ମୂଲ୍ୟ/ଓଜନ ଅନୁପାତ ସର୍ବାଧିକ, ସେଗୁଡ଼ିକ ସହିତ ଆରମ୍ଭ କରି ବ୍ୟାକ୍‌ପ୍ୟାକ୍‌ରେ ବସ୍ତୁଗୁଡ଼ିକୁ ଯୋଡନ୍ତୁ, ଯେପର୍ଯ୍ୟନ୍ତ ବ୍ୟାକ୍‌ପ୍ୟାକ୍ ପୂର୍ଣ୍ଣ ନହୁଏ ।
• ଯଦି କୌଣସି ବସ୍ତୁ ସମ୍ପୂର୍ଣ୍ଣ ରୂପେ ଫିଟ୍ ନହୁଏ, ତେବେ ବ୍ୟାକ୍‌ପ୍ୟାକ୍ ଭରୁଥିବା ଅଂଶକୁ ନିଅନ୍ତୁ ।

ମୁଦ୍ରା ଫେରସ୍ତ କରିବା

• ଉପଲବ୍ଧ ମୁଦ୍ରାଗୁଡିକର ଏକ ସମୂହ $v_1, v_2,..., v_n$ ଅଛି, ଏବଂ ଆମେ ସର୍ବନିମ୍ନ ମୁଦ୍ରା ବ୍ୟବହାର କରି $S$ ରାଶି ଫେରସ୍ତ କରିବାକୁ ଚାହୁଁଛୁ ।

ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ

• ମୁଦ୍ରାଗୁଡିକୁ ସେମାନଙ୍କ ମୂଲ୍ୟର ଅବତରଣ କ୍ରମରେ ସଜାନ୍ତୁ ।
• ସବୁଠାରୁ ବଡ଼ ସମ୍ଭାବ୍ୟ ମୂଲ୍ୟର ମୁଦ୍ରା ଯୋଡନ୍ତୁ ଯେପର୍ଯ୍ୟନ୍ତ ଅବଶିଷ୍ଟ ରାଶି ଏହି ମୂଲ୍ୟଠାରୁ ଅଧିକ କିମ୍ବା ସମାନ ହୋଇଥାଏ ।
• ଅବଶିଷ୍ଟ ରାଶି ଏବଂ ପରବର୍ତ୍ତୀ ନିମ୍ନ ମୂଲ୍ୟର ମୁଦ୍ରା ସହିତ ପର୍ଯ୍ୟାୟ 2 କୁ ପୁନରାବୃତ୍ତି କରନ୍ତୁ ।
• ଧ୍ୟାନ ଦିଅନ୍ତୁ, ଏହି ଆଲଗୋରିଦମ ସର୍ବଦା ସମସ୍ତ ମୁଦ୍ରା ବ୍ୟବସ୍ଥା ପାଇଁ ସର୍ବୋତ୍ତମ ସମାଧାନ ଦେଇନଥାଏ (ଉଦାହରଣ ସ୍ୱରୂପ, {1, 3, 4} ମୁଦ୍ରାଗୁଡ଼ିକ ସହିତ ଏବଂ 6 ର ରାଶି, ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ 4 + 1 + 1 ଦେବ, ଯେତେବେଳେ କି ସର୍ବୋତ୍ତମ ସମାଧାନ ହେଉଛି 3 + 3) ।

କାର୍ଯ୍ୟ ସୂଚୀ ପ୍ରସ୍ତୁତ କରିବା

• ଆମ ପାଖରେ କରିବାକୁ କାର୍ଯ୍ୟଗୁଡିକର ଏକ ସମୂହ ଅଛି, ପ୍ରତ୍ୟେକର ଏକ ନିର୍ଦ୍ଧାରିତ ତାରିଖ $d_i$ ଏବଂ ଯଦି ଏହା ତାରିଖ ପୂର୍ବରୁ କରା ନଯାଏ ତେବେ ଏକ ଜୋରିମାନା $p_i$ ଅଛି ।
• ସମୟ ସୀମା ପୂର୍ବରୁ କାର୍ଯ୍ୟଗୁଡ଼ିକ ପାଇଁ ମୋଟ ଜୋରିମାନା କମ୍ କରିବା ଲକ୍ଷ୍ୟ ।

ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ

• ସେମାନଙ୍କ ଜୋରିମାନାର ଅବତରଣ କ୍ରମରେ କାର୍ଯ୍ୟଗୁଡ଼ିକୁ ସଜାନ୍ତୁ ।
• ଏହି କ୍ରମରେ କାର୍ଯ୍ୟଗୁଡ଼ିକୁ କରନ୍ତୁ, ସେମାନଙ୍କର ନିର୍ଦ୍ଧାରିତ ତାରିଖ ପୂର୍ବରୁ କରାଯାଇପାରିଲେ ସର୍ବାଧିକ ଜୋରିମାନା ଥିବା କାର୍ଯ୍ୟଗୁଡ଼ିକଠାରୁ ଆରମ୍ଭ କରନ୍ତୁ ।
• ଯଦି କୌଣସି କାର୍ଯ୍ୟ ସମୟାନୁସାରେ କରାଯାଇ ନପାରେ ତେବେ ଏହାକୁ ପ୍ରତ୍ୟାଖ୍ୟାନ କରନ୍ତୁ ।

ଉତ୍କୃଷ୍ଟତାର ପ୍ରମାଣ

• ଏକ ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ ସର୍ବୋତ୍ତମ ସମାଧାନ ଦେଉଛି ବୋଲି ପ୍ରମାଣ କରିବାକୁ ଆମେ ନିମ୍ନଲିଖିତ କୌଶଳ ବ୍ୟବହାର କରିପାରିବା:
• ଇଣ୍ଡକ୍ସନ୍: ଆମେ ଦର୍ଶାଉଛୁ ଯେ ପ୍ରତ୍ୟେକ ପର୍ଯ୍ୟାୟରେ କରାଯାଇଥିବା ଗ୍ଲୋଟନ୍ ପସନ୍ଦ ସର୍ବୋତ୍ତମ ସମାଧାନ ପାଇବାରେ ବାଧା ସୃଷ୍ଟି କରେ ନାହିଁ ।
• ବିନିମୟ ଯୁକ୍ତି: ଆମେ ଅନୁମାନ କରୁ ଯେ ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ ଦ୍ୱାରା ପ୍ରାପ୍ତ ସମାଧାନଠାରୁ ଭିନ୍ନ ଏକ ସର୍ବୋତ୍ତମ ସମାଧାନ ଅଛି, ଏବଂ ଆମେ ଦର୍ଶାଉଛୁ ଯେ ଆମେ ଏହାର ଗୁଣବତ୍ତାକୁ ହ୍ରାସ ନକରି ଏହାକୁ ଗ୍ଲୋଟନ୍ ସମାଧାନରେ ପରିଣତ କରିପାରିବା ।

ସିଦ୍ଧାନ୍ତ

• ଅନେକ ଅପ୍ଟିମାଇଜେସନ୍ ସମସ୍ୟା ସମାଧାନ ପାଇଁ ଗ୍ଲୋଟନ୍ ଆଲଗୋରିଦମ ଏକ ସରଳ ଏବଂ ଦକ୍ଷ ଆଭିମୁଖ୍ୟ ।
• ଅବଶ୍ୟ, ଯାଞ୍ଚ କରିବା ଜରୁରୀ ଯେ ସେମାନେ ବିଚାର କରାଯାଉଥିବା ସମସ୍ୟା ପାଇଁ ସର୍ବୋତ୍ତମ ସମାଧାନ ଦିଅନ୍ତି, କିମ୍ବା ସେମାନଙ୍କ କାର୍ଯ୍ୟଦକ୍ଷତାକୁ ସୀମିତ କରନ୍ତି।