କ୍ରସକାଲର ଆଲଗୋରିଦମ ମେଜ୍ ଜେନେରେଟର

କ୍ରସ୍କାଲର ଆଲଗୋରିଦମ ହେଉଛି ଏକ ସର୍ବନିମ୍ନ ସ୍ପାନିଂ ଟ୍ରି ଆଲଗୋରିଦମ ଯାହାକୁ ମେଜ୍ ଜେନେରେସନ୍ ପାଇଁ ଅନୁକୂଳିତ କରାଯାଇପାରିବ। ଏହା ସମ୍ପୂର୍ଣ୍ଣ ମେଜ୍ ସୃଷ୍ଟି କରିବା ପାଇଁ ବିଶେଷ ପ୍ରଭାବଶାଳୀ। କ୍ରସ୍କାଲର ଆଲଗୋରିଦମର ଏକ ବିକଳ୍ପ ହେଉଛି ପ୍ରିମ୍‌ର ଆଲଗୋରିଦମ, ଯାହା ଏକ ସର୍ବନିମ୍ନ ସ୍ପାନିଂ ଟ୍ରି ଆଲଗୋରିଦମ ମଧ୍ୟ, କିନ୍ତୁ ଯେହେତୁ ସେମାନେ ସମାନ ମେଜ୍ ସୃଷ୍ଟି କରନ୍ତି ଏବଂ କ୍ରସ୍କାଲ ଦ୍ରୁତ ଗତିରେ ଚାଲେ, ମୁଁ ପ୍ରିମ୍‌କୁ କାର୍ଯ୍ୟକାରୀ କରିବାକୁ କଷ୍ଟ କରିନାହିଁ।

ଏକ ସଂପୂର୍ଣ୍ଣ ଚକ୍ରବ୍ୟୁହ ହେଉଛି ଏକ ଚକ୍ରବ୍ୟୁହ ଯେଉଁଥିରେ ଚକ୍ରବ୍ୟୁହରେ ଯେକୌଣସି ବିନ୍ଦୁରୁ ଅନ୍ୟ ଯେକୌଣସି ବିନ୍ଦୁକୁ ଠିକ୍ ଗୋଟିଏ ପଥ ଥାଏ। ଏହାର ଅର୍ଥ ହେଉଛି ଆପଣ ବୃତ୍ତରେ ବୁଲିପାରିବେ ନାହିଁ, କିନ୍ତୁ ଆପଣ ପ୍ରାୟତଃ ମୃତ ସୀମାର ସମ୍ମୁଖୀନ ହେବେ, ଯାହା ଆପଣଙ୍କୁ ପଛକୁ ବୁଲି ଫେରିବାକୁ ବାଧ୍ୟ କରିବ।

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

କ୍ରସକାଲର ଆଲଗୋରିଦମ ବିଷୟରେ

କ୍ରସ୍କାଲଙ୍କ ଆଲଗୋରିଦମ ଜଣେ ଆମେରିକୀୟ ଗଣିତଜ୍ଞ, ପରିସଂଖ୍ୟାନବିଦ ଏବଂ କମ୍ପ୍ୟୁଟର ବୈଜ୍ଞାନିକ ଜୋସେଫ ବର୍ଣ୍ଣାର୍ଡ କ୍ରସ୍କାଲ ଜୁନିଅରଙ୍କ ଦ୍ୱାରା ସୃଷ୍ଟି କରାଯାଇଥିଲା। ସେ ପ୍ରଥମେ 1956 ମସିହାରେ ତାଙ୍କର "ଅନ୍ ଦି ସର୍ଟେଷ୍ଟ ସ୍ପାନିଂ ସବଟ୍ରି ଅଫ୍ ଏ ଗ୍ରାଫ୍ ଆଣ୍ଡ୍ ଦି ଟ୍ରାଭେଲିଂ ସେଲ୍ସମ୍ୟାନ୍ ପ୍ରବ୍ଲମ୍" ପତ୍ରିକାରେ ଆଲଗୋରିଦମକୁ ବର୍ଣ୍ଣନା କରିଥିଲେ।

ଆଲଗୋରିଦମଟି ଏକ ଗ୍ରାଫର ସର୍ବନିମ୍ନ ସ୍ପାନିଂ ଟ୍ରି (MST) ଖୋଜିବା ପାଇଁ ଡିଜାଇନ୍ କରାଯାଇଛି, ଏହା ନିଶ୍ଚିତ କରେ ଯେ ସମସ୍ତ ଶୀର୍ଷଗୁଡିକ ସର୍ବନିମ୍ନ ସମ୍ଭାବ୍ୟ ମୋଟ ଧାର ଓଜନ ସହିତ ସଂଯୁକ୍ତ ଏବଂ ଚକ୍ରଗୁଡ଼ିକୁ ଏଡାଇ ଯାଇଥାଏ।

କ୍ରୁସକାଲର ଆଲଗୋରିଦମ କିପରି ମେଜ୍ ଜେନେରେସନ ପାଇଁ କାମ କରେ

ପଦକ୍ଷେପ 1: ଆରମ୍ଭ କରନ୍ତୁ

• ଚକ୍ରବ୍ୟୁହରେ ଥିବା ପ୍ରତ୍ୟେକ କୋଷକୁ ଏକ ପୃଥକ ସେଟ୍ (ଏକ ଅନନ୍ୟ ଉପାଦାନ) ଭାବରେ ବ୍ୟବହାର କରନ୍ତୁ।
• ସଂଲଗ୍ନ କୋଷଗୁଡ଼ିକ ମଧ୍ୟରେ ଥିବା ସମସ୍ତ କାନ୍ଥକୁ ସମ୍ଭାବ୍ୟ ଧାର ଭାବରେ ତାଲିକାଭୁକ୍ତ କରନ୍ତୁ।

ପଦକ୍ଷେପ 2: କାନ୍ଥଗୁଡ଼ିକୁ ସଜାନ୍ତୁ

• କାନ୍ଥଗୁଡ଼ିକୁ ଅଦଳବଦଳ କରନ୍ତୁ କିମ୍ବା ଅନିୟମିତ ଭାବରେ କ୍ରମବଦ୍ଧ କରନ୍ତୁ। ଯଦି ଏହାକୁ ପ୍ରକୃତ କ୍ରସ୍କାଲର ଆଲଗୋରିଦମ ଭାବରେ କାର୍ଯ୍ୟକାରୀ କରୁଛନ୍ତି, ତେବେ ଏକ ଅନିୟମିତ କ୍ରମରେ କାନ୍ଥଗୁଡ଼ିକୁ ସଜାନ୍ତୁ (ଯେହେତୁ ମେଜ୍ ଜେନେରେସନ୍ ପାଇଁ ଓଜନ ଆବଶ୍ୟକ ହୁଏ ନାହିଁ)।

ପଦକ୍ଷେପ 3: କାନ୍ଥ ପ୍ରକ୍ରିୟାକରଣ କରନ୍ତୁ

• ଅଦଳବଦଳ କାନ୍ଥ ଦେଇ ପୁନରାବୃତ୍ତି କର।
• ଯଦି କାନ୍ଥ ଦ୍ୱାରା ବିଭକ୍ତ ଦୁଇଟି କୋଷ ଭିନ୍ନ ସେଟର ହୋଇଥାଏ (ଅର୍ଥାତ୍, ସେମାନେ ଏପର୍ଯ୍ୟନ୍ତ ଚକ୍ରରେ ସଂଯୁକ୍ତ ହୋଇନାହାଁନ୍ତି), ତେବେ କାନ୍ଥକୁ ବାହାର କରି ସେଟଗୁଡ଼ିକୁ ମିଶ୍ରଣ କରନ୍ତୁ।
• ଯଦି ସେମାନେ ପୂର୍ବରୁ ସମାନ ସେଟରେ ଅଛନ୍ତି, ତେବେ କାନ୍ଥକୁ ଏଡ଼ାଇ ଯାଆନ୍ତୁ (ଚକ୍ରକୁ ଏଡାଇବା ପାଇଁ)।

ପଦକ୍ଷେପ 4: ସମାପ୍ତ ହେବା ପର୍ଯ୍ୟନ୍ତ ଜାରି ରଖନ୍ତୁ

• ସମସ୍ତ କୋଷଗୁଡ଼ିକ ସଂଯୋଗ ହେବା ପର୍ଯ୍ୟନ୍ତ ଏହି ପ୍ରକ୍ରିୟାକୁ ପୁନରାବୃତ୍ତି କରନ୍ତୁ, ଏକକ ସ୍ପାନିଂ ଗଛ ଗଠନ କରନ୍ତୁ।
• ଶେଷରେ, ପ୍ରତ୍ୟେକ କୋଷ ଲୁପ୍ କିମ୍ବା ପୃଥକ ବିଭାଗ ବିନା ଅନ୍ୟମାନଙ୍କ ସହିତ ସଂଯୁକ୍ତ ହୋଇଥାଏ।

ଯେହେତୁ Kruskal ର ଆଲଗୋରିଦମ ସେଟଗୁଡ଼ିକୁ ମିଶ୍ରଣ କରିବା ଉପରେ ନିର୍ଭର କରେ, ଏହାକୁ Union-Find ଆଲଗୋରିଦମ ବ୍ୟବହାର କରି ଅପ୍ଟିମାଇଜ୍ କରାଯାଇପାରିବ, ଯାହା ମେଜ୍ ଜେନେରେସନ୍ ସମୟରେ ସଂଯୁକ୍ତ ସେଲ୍ସକୁ ଟ୍ରାକ୍ କରିବାର ଏକ ଦକ୍ଷ ଉପାୟ ପ୍ରଦାନ କରେ। ଆପଣ ଏଠାରେ Union-Find ଆଲଗୋରିଦମର ମୋର PHP କାର୍ଯ୍ୟାନ୍ୱୟନ ଦେଖିପାରିବେ: ଲିଙ୍କ୍

ଅଧିକ ପଠନ

ଯଦି ଆପଣ ଏହି ପୋଷ୍ଟକୁ ଉପଭୋଗ କରିଛନ୍ତି, ତେବେ ଆପଣଙ୍କୁ ଏହି ପରାମର୍ଶଗୁଡ଼ିକ ମଧ୍ୟ ପସନ୍ଦ ଆସିପାରେ:

• ବଢୁଥିବା ଗଛ ଆଲଗୋରିଦମ୍ ମେଜ୍ ଜେନେରେଟର
• ମାଜ୍ ଜେନେରେଟରକୁ ଶିକାର ଏବଂ ହତ୍ୟା କରନ୍ତୁ
• ଏଲର୍ ଅଲଗୋରିଥମ୍ ମେଜ୍ ଜେନେରେଟର୍