👩🏾‍⚖️ 👩🏾‍🔬 🐖 हंगेरियन एल्गोरिथ्म, या गणित असाइनमेंट्स को कैसे लागू करने में मदद करता है 👨🏼‍🍳 🕛 ☺️

नमस्कार दोस्तों! इस लेख में मैं हंगेरियन विधि के बारे में अनुशासन "ऑपरेशनल रिसर्च" से एक दिलचस्प एल्गोरिदम के बारे में बात करना चाहूंगा और इसकी मदद से असाइनमेंट की समस्याओं को हल कर सकता हूं। मैं इस मामले में इस सिद्धांत के बारे में बताऊंगा कि यह एल्गोरिथ्म किन मामलों में और किन कार्यों के लिए लागू होता है, मैं इसका चरणबद्ध तरीके से अपने आविष्कार किए गए उदाहरण का उपयोग करके विश्लेषण करूंगा, और R. भाषा में इसके कार्यान्वयन के लिए कोड की अपनी मामूली रूपरेखा साझा करूँगा। चलिए शुरू करते हैं!

विधि के बारे में कुछ शब्द

गणितीय नियमों और परिभाषाओं के साथ बहुत सारे सिद्धांत को चित्रित नहीं करने के लिए, मैं असाइनमेंट समस्या के निर्माण के लिए कुछ विकल्पों पर विचार करने का प्रस्ताव करता हूं, और मुझे लगता है कि आप तुरंत समझ पाएंगे कि हम किन मामलों में हंगेरियन पद्धति का उपयोग करेंगे:

कर्मचारियों को पदों पर नियुक्त करने का कार्य। श्रमिकों को पदों पर वितरित करना आवश्यक है ताकि अधिकतम दक्षता हासिल हो, या काम की न्यूनतम लागत हो।
उत्पादन अनुभागों को मशीनें सौंपना। मशीनों का वितरण ताकि उनके संचालन के दौरान उत्पादन जितना संभव हो उतना लाभदायक हो, या उन्हें बनाए रखने की लागत न्यूनतम हो।
विभिन्न रिक्तियों के लिए उम्मीदवारों का चयन अनुमानित है। हम नीचे इस उदाहरण का विश्लेषण करेंगे।

जैसा कि आप देख सकते हैं, कई विकल्प हैं जिनके लिए हंगेरियन पद्धति लागू है, और गतिविधि के कई क्षेत्रों में समान कार्य उत्पन्न होते हैं।

नतीजतन, कार्य को हल किया जाना चाहिए ताकि एक कलाकार (व्यक्ति, मशीन, उपकरण, ...) केवल एक ही कार्य कर सके, और प्रत्येक कार्य केवल एक कलाकार द्वारा किया गया था।

किसी समस्या को हल करने के लिए एक आवश्यक और पर्याप्त स्थिति इसका बंद प्रकार है। यानी जब कलाकारों की संख्या = कार्यों की संख्या (एन = एम)। यदि यह स्थिति पूरी नहीं होती है, तो आप काल्पनिक कलाकार, या काल्पनिक कार्य जोड़ सकते हैं, जिसके लिए मैट्रिक्स में मान शून्य होगा। यह समस्या के समाधान को प्रभावित नहीं करेगा, यह केवल इसे आवश्यक बंद प्रकार देगा।

उदाहरण के लिए चरण-दर-चरण एल्गोरिथ्म

समस्या कथन: एक महत्वपूर्ण वैज्ञानिक सम्मेलन की योजना बनाएं। इसे संचालित करने के लिए, आपको ध्वनि, प्रकाश, चित्र, मेहमानों को पंजीकृत करने और प्रदर्शनों के बीच विराम के लिए तैयार करने की आवश्यकता है। इस कार्य के लिए 5 आयोजक हैं। उनमें से प्रत्येक के पास किसी विशेष कार्य के प्रदर्शन के कुछ अनुमान हैं (मान लें कि ये अनुमान उनके कर्मचारियों की समीक्षाओं के अंकगणितीय औसत के रूप में निर्धारित हैं)। आयोजकों को वितरित करना आवश्यक है ताकि उनका कुल स्कोर अधिकतम हो। कार्य के निम्नलिखित रूप हैं:

यदि समस्या को अधिकतम (हमारे मामले में) हल किया जाता है, तो मैट्रिक्स की प्रत्येक पंक्ति में अधिकतम तत्व को खोजने के लिए आवश्यक है, इसे संबंधित पंक्ति के प्रत्येक तत्व से घटाएं और पूरे मैट्रिक्स को -1 से गुणा करें। यदि समस्या कम से कम हल हो जाती है, तो इस कदम को छोड़ देना चाहिए।

प्रत्येक पंक्ति में और प्रत्येक कॉलम में केवल एक चयनित शून्य होना चाहिए। (यानी, जब शून्य को चुना गया था, तो इस पंक्ति में या इस कॉलम में शेष शून्य अब संज्ञान में नहीं हैं)। इस मामले में, यह नहीं किया जा सकता है:

( यदि समस्या न्यूनतम पर हल हो गई है, तो आपको इस चरण से शुरू करने की आवश्यकता है )। हम आगे भी समाधान जारी रखते हैं। पंक्तियों द्वारा मैट्रिक्स में कमी (प्रत्येक पंक्ति में न्यूनतम तत्व देखें और इसे क्रमशः प्रत्येक तत्व से घटाएं):

क्योंकि चूंकि सभी न्यूनतम तत्व शून्य हैं, इसलिए मैट्रिक्स नहीं बदला गया है। हम स्तंभों में कमी को पूरा करते हैं:

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

हम आगे भी फैसला जारी रखेंगे। उन पंक्तियों और स्तंभों को पार करें जिनमें शून्य तत्व होते हैं ( महत्वपूर्ण! क्रॉसिंग की संख्या न्यूनतम होनी चाहिए )। शेष तत्वों में से, हम न्यूनतम की तलाश करते हैं, इसे शेष तत्वों (जो पार नहीं किया जाता है) से घटाते हैं और पार किए गए पंक्तियों और स्तंभों के चौराहे पर स्थित तत्वों में जोड़ते हैं (जो हरे रंग में चिह्नित होता है, उसे वहां घटाया जाता है; सुनहरे रंग में चिह्नित किया गया है; क्या चित्रित नहीं है - स्पर्श न करें):

जैसा कि आप अभी देख सकते हैं, प्रत्येक कॉलम और पंक्ति में केवल एक चयनित शून्य है। हम समस्या का समाधान पूरा करते हैं!

प्रारंभिक तालिका में स्थानापन्न चयनित शून्य का स्थान। इस प्रकार, हम इष्टतम या इष्टतम योजना प्राप्त करते हैं, जिसमें आयोजकों को काम के बीच वितरित किया जाता है और अनुमानों का योग इसके विपरीत हो जाता है:

यदि आप समस्या को हल करते हैं और आपके लिए शून्य का चयन करना अभी भी असंभव है, ताकि प्रत्येक स्तंभ और पंक्ति में एक ही हो, तो हम एल्गोरिथ्म को उस स्थान से दोहराते हैं जहां पंक्तियों द्वारा कटौती की गई थी (प्रत्येक पंक्ति में न्यूनतम तत्व)।

प्रोग्रामिंग भाषा कार्यान्वयन आर

हंगेरियन एल्गोरिथ्म को पुनरावर्ती का उपयोग करके कार्यान्वित किया जाता है। मुझे उम्मीद है कि मेरे कोड में कठिनाइयों का कारण नहीं होगा। पहले आपको तीन कार्यों को संकलित करने की आवश्यकता है, और फिर गणना शुरू करें।

समस्या को हल करने का डेटा example.csv फ़ाइल से लिया गया है, जिसमें फ़ॉर्म है:

कोड को स्पॉइलर में जोड़ा गया क्योंकि लेख इसकी वजह से बहुत बड़ा होगा

#     library(dplyr) # csv  (  -  ;   -  ) table <- read.csv("example.csv",header=TRUE,row.names=1,sep=";") #  unique_index <- hungarian_algorithm(table,T) # cat(paste(row.names(table[as.vector(unique_index$row),])," - ",names(table[as.vector(unique_index$col)])),sep = "\n") #   cat("  -",sum(mapply(function(i, j) table[i, j], unique_index$row, unique_index$col, SIMPLIFY = TRUE))) #____________________  __________________________________ hungarian_algorithm <- function(data,optim=F){ # optim = T,       if(optim==T) { data <- data %>% apply(1,function(x) (x-max(x))*(-1)) %>% t() %>% as.data.frame() optim <- F } #    data <- data %>% apply(1,function(x) x-min(x)) %>% t() %>% as.data.frame() #    zero_index <- which(data==0, arr.ind = T) #  ""  - unique_index <- from_the_beginning(zero_index) #  ""        , .. if(nrow(unique_index)!=nrow(data)) #.. ""  - unique_index <- from_the_end(zero_index) #    ,     if(nrow(unique_index)!=nrow(data)) { #    data <- data %>% apply(2,function(x) x-min(x)) %>% as.data.frame() zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) if(nrow(unique_index)!=nrow(data)) { #""        (!     ) index <- which(apply(data,1,function(x) length(x[x==0])>1)) index2 <- which(apply(data[-index,],2,function(x) length(x[x==0])>0)) #     min_from_table <- min(data[-index,-index2]) #     data[-index,-index2] <- data[-index,-index2]-min_from_table #  ,        data[index,index2] <- data[index,index2]+min_from_table zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) #    ""        , .. if(nrow(unique_index)!=nrow(data)) #..    hungarian_algorithm(data,optim) else #  ""  unique_index } else #  ""  unique_index } else #  ""  unique_index } #_________________________________________________________________________________ #__________   ""  -___________ from_the_beginning <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ #  ,      i,   j find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ #     i <- c(i,as.vector(find_zero[1,1])) #     j <- c(j,as.vector(find_zero[1,2])) #   data frame (     ) index <- rbind(index,setNames(as.list(find_zero[1,]), names(index))) #         from_the_beginning(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________ #__________   ""  -___________ from_the_end <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ i <- c(i,as.vector(find_zero[nrow(find_zero),1])) j <- c(j,as.vector(find_zero[nrow(find_zero),2])) index <- rbind(index,setNames(as.list(find_zero[nrow(find_zero),]), names(index))) from_the_end(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________

कार्यक्रम का परिणाम:

निष्कर्ष में

मेरे लेख को पढ़ने के लिए समय निकालने के लिए बहुत-बहुत धन्यवाद। मैं नीचे दिए गए सभी लिंक प्रदान करूंगा। मुझे आशा है कि आपने अपने लिए कुछ नया सीखा है या अपने पुराने ज्ञान को अपडेट किया है। सभी सफलता, शुभकामनाएं और शुभकामनाएं!

संसाधनों का उपयोग किया

1. विकिपीडिया पर धावा बोला
2. और अन्य अच्छी साइटें
3. इस लेख से कुछ जानकारी खुद के लिए तनावपूर्ण।

हंगेरियन एल्गोरिथ्म, या गणित असाइनमेंट्स को कैसे लागू करने में मदद करता है

विधि के बारे में कुछ शब्द

उदाहरण के लिए चरण-दर-चरण एल्गोरिथ्म

प्रोग्रामिंग भाषा कार्यान्वयन आर

निष्कर्ष में

संसाधनों का उपयोग किया

More articles: