एमआईटी 6.00x पाठ्यक्रम (edx.org) पर प्राप्त ज्ञान को व्यवहार में लाना

6.002x MITx पाठ्यक्रम के बारे में मेरी पोस्ट की टिप्पणियों में , मुझे एक सवाल पूछा गया था - क्या सीखा जीवन में काम आया। और मैंने उत्तर दिया - हाँ, निश्चित रूप से, यहाँ सुबह अपने दाँत ब्रश करते समय, मैंने आरसी स्थिरांक की गणना की ... लेकिन कोई सबूत नहीं थे। तब से मैंने दो और पाठ्यक्रम पूरे कर लिए हैं - UC बर्कले CS188.1x आर्टिफिशियल इंटेलिजेंस का परिचय (18 फरवरी को पंजीकरण खुला) और MITx: 6.00x कंप्यूटर साइंस और प्रोग्रामिंग का परिचय । और अगर CS188.1x के बाद मैं सिर्फ भावनाओं से भरा था और यह नहीं जानता था कि हौसले से प्राप्त ज्ञान को कैसे रखा जाए ( घोड़े की प्रगति की समस्या को हल करने के अलावा), तो 6.00x पास करने के बाद मुझे दिखावा करने का मौका मिला।

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

चीनी चेकर्स

एक मैदान है, मैदान पर चिप्स हैं। कोशिकाओं में से एक खाली है। हम केवल एक पड़ोसी सेल पर एक चेकर खाकर, उस पर कूद कर आगे बढ़ सकते हैं। तिरछे खाने के लिए असंभव है। प्रारंभिक स्थिति:

  oooooooooooooooo।  oooooooooooooooo 

निम्न चाल संभव है, उदाहरण के लिए, यह:

  oooooooooooooo।  ।  ooooooooooooooooo 

नतीजतन, केवल एक ही होना चाहिए। यहाँ इतना आसान काम है। हेह, मैंने सोचा, एक फैसले के बारे में तीन मिनट। कुछ दिनों के बाद, मैंने अपने सिर को कसकर खरोंच दिया और किसी प्रकार की सक्रिय रणनीति को जन्म देने की कोशिश की। समस्या, ****, हल नहीं किया गया था। अजगर का उपयोग करना होगा।

पाठ्यक्रमों से मैंने जाना कि सभी खोज कार्यों में, केवल तीन उपकेंद्रों को हल करने की आवश्यकता है (भगवान, जिनके बारे में मैं आपको बताता हूं कि यह संभवतः मूल बातें हैं):

1. प्रणाली की स्थिति को एनकोड करें
2. जांचें कि क्या एक निश्चित स्थिति एक समाधान है
3. निम्नलिखित राज्य उत्पन्न करें

मैंने जो कुछ भी किया, राज्य कोडिंग से संघर्ष किया, और अंततः 49 वर्णों की एक सरल रेखा पर बस गया:

initState = ' ooo '+' ooo '+'ooooooo'+'o..oooo'+'ooooooo'+' ooo '+' ooo ' 

यह पहले पैराग्राफ के समाधान की बहुत सुविधा देता है, लेकिन तीसरे की समस्याओं के साथ धमकी देता है। अच्छा, ठीक है। सामान्य तौर पर, जैसा कि हमें सिखाया गया था, हम समस्या वर्ग लिखते हैं:

 class Problem(object): def __init__(self, initState): self.initState = initState def isGoal(self, state): if state.count('o') > 1: return False else: return True def generateSuccessors(self, state): res = [] idx = 0 for c in state: if c == '.': ##we can move here res += self.getValidMoves(state, idx) idx += 1 return res def getValidMoves(self, state, idx): res = [] ## get North: if idx in [16,17,18,23,24,25,28,29,30,31,32,33,34,37,38,39,44,45]: sN = state[:] if sN[idx-7] == 'o': if sN[idx-14] =='o': sN = sN[0:idx-14]+'.'+sN[idx-13:idx-7]+'.'+sN[idx-6:idx]+'o'+sN[idx+1:] res.append(sN) ## get South: if idx in [2,3,4,9,10,11,14,15,16,17,18,19,20,23,24,25,30,31,32]: sS = state[:] if sS[idx+7] == 'o': if sS[idx+14] =='o': sS = sS[0:idx]+'o'+sS[idx+1:idx+7]+'.'+sS[idx+8:idx+14]+'.'+sS[idx+15:] res.append(sS) ## get West: if idx in [4,11,16,17,18,19,20,23,24,25,26,27,30,31,32,33,34,39,46]: sW = state[:] if sW[idx-1] == 'o': if sW[idx-2] =='o': sW = sW[0:idx-2]+'..o'+sW[idx+1:] res.append(sW) ## get East: if idx in [2,9,14,15,16,17,18,21,22,23,24,25,28,29,30,31,32,37,44]: sE = state[:] if sE[idx+1] == 'o': if sE[idx+2] =='o': sE = sE[:idx]+'o..'+sE[idx+3:] res.append(sE) return res def printState(self, state): res = '' for x in range(7): for y in range(7): res += state[x*7+y]+' ' res+='\r\n' print res 

वास्तव में, यहां हम समस्या के आरंभीकरण के दौरान सिस्टम के प्रारंभिक मूल्य को निर्धारित करते हैं और आइटम 2 और 3 को हल करने के तरीकों का निर्धारण करते हैं। सौभाग्य से, किसी भी स्थिति की जाँच करना कि क्या यह समाधान बेहद सरल है - हम गिनते हैं कि बोर्ड में कितने चिप्स बचे हैं - यदि एक से अधिक हैं, तो फिर हमें अभी भी काम करना है।
लेकिन मान्य अगली चालों की पीढ़ी के साथ, मुझे थोड़ा नुकसान हुआ, क्योंकि लाइन एक-आयामी है, और बोर्ड दो-आयामी है। और हमें किसी तरह इसे एक दूसरे के पास लाना होगा। शायद यह भी संभावना है, मैं nabydlokodil, लेकिन मेरे बचाव में मैं कहना है मुझे लगता है कि मैं KISS सिद्धांत, जिसके बारे में इतना Habré पढ़ने लागू करने में सक्षम था चाहते हैं। और इसलिए हम बोर्ड के साथ जाते हैं, प्रत्येक खाली सेल पर हम सभी दिशाओं में देखते हैं - क्या उस दिशा में दो चिप्स हैं। यदि ऐसा है, तो हम उन चिप्स को खाली स्थानों के साथ बदल देते हैं, और खाली स्थान को एक चिप के साथ। और दे, अगले कदम के रूप में।
कुछ अवलोकन:

• इस समस्या में, समाधान हमेशा ग्राफ के नीचे होता है। इसलिए चौड़ाई-पहली खोज हमेशा यथासंभव लंबी रहेगी।
• इस कार्य में पिछले राज्यों में से एक में आना असंभव है। तदनुसार, आप ग्राफ लूप की जांच करके भाप स्नान नहीं कर सकते हैं (आगे देखें, सब कुछ वास्तव में अधिक दिलचस्प है), लेकिन उन्होंने मुझे बस इस तरह से सिखाया और मैंने इसे किया
• हेयुरिस्टिक को इस कार्य के लिए नहीं सोचा जाता है। कम से कम वह अभी नहीं आया है किसी भी कदम से चिप्स की संख्या में 1. कमी आती है। इसलिए, चिप्स की सापेक्ष स्थिति से राज्य की "अच्छाई" या "खराबता" का मूल्यांकन करना संभव है। और यह nontrivial है

इसलिए, एल्गोरिथ्म सरल होगा:

 def dfs(p): fringe = [[p.initState]] tried = set() while fringe: cur = fringe.pop() tried.add(cur[-1]) for lm in p.generateSuccessors(cur[-1]): if p.isGoal(lm): return cur+[lm] else: if lm not in tried: fringe.append(cur+[lm]) return None 

यहाँ p क्लास प्रॉब्लम का ऑब्जेक्ट है

 p = Problem(initState) 

सब कुछ तैयार है, हम शुरू करते हैं और हम चाय पीना छोड़ देते हैं। बारह साल, क्योंकि कंप्यूटर को सबसे खराब स्थिति में 2 ^ 32 संयोजनों को छाँटना होगा। फिर मैंने धोखा दिया और तुरंत संयोजनों की संख्या को आधे से कम कर दिया, कंप्यूटर के लिए पहला कदम बनाया और पहली चाल के बाद चिप्स की प्रारंभिक स्थिति स्थापित की। इसके अलावा, मैंने देखा कि बोर्ड केंद्रीय रूप से सममित है, जिसका अर्थ है कि हमेशा चार डुप्लिकेट राज्य होंगे, बोर्ड के रोटेशन को 90, 180 और 270 डिग्री तक ध्यान में रखते हुए। आइए ग्राफ़ के विस्तारित नोड्स के लिए चेक को जटिल करें:

 def rotateField(field): res = '' for i in range(7): for j in range(7): res += field[7*j+i] return res 

...

 if lm not in tried: lmr = rotateField(lm) if lmr not in tried: if rotateField(lmr) not in tried: if rotateField(lm) not in tried: fringe.append(cur+[lm]) 

ठीक है, आखिरकार, मैंने कई शाखाओं को काट दिया, जिसमें राज्य के लिए जाँच शामिल है जब बोर्ड पर चिप्स होते हैं, लेकिन उन्हें एक दूसरे से दूर रहने की गारंटी दी जाती है और एक-दूसरे की रक्षा करने में सक्षम नहीं होंगे:

  oooooo
 ।  ।  ।  ।  ।  ।  ।  
 ।  ।  ।  ।  ।  ।  । 
 ।  ।  ।  ।  ।  ।  । 
     oooooo 

 def checkDeadCombinations(state): ''' False = dead True - combination is OK''' if '.'*21 in state: if '.' in state[:14] and '.' in state[-15:]: return False if '.'*21 in rotateField(state): if '.' in state[:14] and '.' in state[-15:]: return False 

खैर, अब एक उम्मीद है कि मैं उस क्षण तक जीवित रहूंगा जब कंप्यूटर मेरे लिए इस समस्या का हल करेगा :-)

मास्क

मैंने पिछली समस्या को हल किया, जिसने मेरी पत्नी को प्रशंसा में लाया, और तुरंत अगले में खुद को दफन कर दिया। डोमिनोज़ का एक बॉक्स दिया जाता है (28 टुकड़े, मानक)। आपको 8 पोर का चयन करने और उन्हें 4x4 वर्ग में मोड़ने की आवश्यकता है, ताकि आपको प्रत्येक में चार पोर की दो खड़ी पंक्तियाँ मिलें।

 HHHH
 HHHH 

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

 dices = [] for i in range(7): for j in range(i,7): dices.append((i,j)) 

नतीजतन, हमारे पास प्रकार (0,0), (1,0), आदि के जोड़े की एक शीट है। हर डोमिनोज़ बोन के लिए।
चूँकि प्रत्येक पंक्ति में योग छह, चार पंक्तियों का होता है, इसलिए हमें कुल 24 देने वाले चिप्स के सभी संयोजनों की आवश्यकता होती है। मैं वहीं बैठा रहा, इन सभी संयोजनों को कैसे बनाया जाए, इस पर मेरे दिमाग को चकित कर दिया, फिर याद आया कि अजगर में बैटरी शामिल होती है और बस याद आती है पावर बटन पर:

 def iterWorkingSets(dices): for cmb in itertools.combinations(dices, 8): ds = 0 for dice in cmb: ds += dice[0] ds += dice[1] if ds == 24: yield cmb 

नतीजतन, हमने सभी अंगुलियों के संयोजन को समाप्त कर दिया, जिन्हें कोई समाधान नहीं देने की गारंटी है। फिर मैंने बस सभी संयोजनों को पार किया और प्रत्येक संयोजन के लिए पोर को फिर से व्यवस्थित किया, अगर कोई समाधान था:

 def checkArr(arr): diag = 0 idx = 0 ##print arr for row in arr: diag += row[idx] idx += 1 if sum(row) != 6: #print 'row', idx, 'is not 6' return False if diag !=6: #print 'diag 1 is not 6' return False diag = 0 idx = 3 arr = arr.transpose() for row in arr: diag += row[idx] idx -= 1 if sum(row) != 6: #print 'column', idx, 'is not 6' return False if diag != 6: #print 'diag 2 is not 6' return False return True 

कोई निर्णय नहीं था। मैंने उसे फिर से दौड़ाया। फिर कोई फैसला नहीं हुआ। अगर मैं धूम्रपान करता, तो मैं धूम्रपान के लिए जाता। यहाँ कुछ गलत है, मैंने सोचा। आप आसानी से जानवर बल फारवर्डर नहीं उठा सकते हैं, एक समाधान होना चाहिए, जिसका अर्थ है कि जानवर बल में गलती। और वह गलती ढूंढने लगा। त्रुटि नहीं मिली। एक निश्चित मात्रा में कॉफी पीने के बाद, मैं यह समझने के लिए खेल खेलने गया - मैं क्या गलत कर रहा हूँ। उन्होंने खेल शुरू किया, मैदान पर पोरों को छोड़ दिया और उन्हें स्थानांतरित करना शुरू कर दिया और ... टर्न आउट! Brutforser ने अंगुली नहीं घुमाई!
ओह, और यह कैसा है, लानत है, लिखने के लिए? पुन: itertools, हम रेंज (6) के लिए सुपरसेट उत्पन्न करते हैं, फिर प्रत्येक संयोजन के लिए हम इसे सुपरसेट के माध्यम से चलाते हैं, पोर को घुमाते हैं। ओह माँ।

 ###        allsubsets = lambda n: list(itertools.chain(*[itertools.combinations(range(n), ni) for ni in range(n+1)])) 

 for wc in iterWorkingSets(dices): wc = list(wc) print 'I here loop through all set of dices that produce 24' print 'This is comb #', cmbNum, ':' print wc cmbNum += 1 for turn in allsubsets(6): tc = wc[:] for k in range(6): if k in turn: tc[k] = wc[k][::-1] else: tc[k] = wc[k] #print 'This is subcom of comb #', cmbNum, ':' #print tc for c in itertools.permutations(tc): ''' I here loop through all re-combinations of the same set''' allNum = [] for a in c: allNum+=list(a) arr = pylab.array(allNum).reshape(4,4) if checkArr(arr): print 'Solution:', arr break print 'Solution was not found' 

हम शुरू करते हैं। पहले से कोई समाधान नहीं है, क्योंकि सेट में "भारी हड्डियां" हैं:

 This is comb # 3 : [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 1), (2, 5)] Solution was not found 

लेकिन फिर, nth के संयोजन के साथ, निर्णय लेने शुरू होते हैं:

  [[० ० ६ ०]
  [१ ४ ० १]
  [१ २ ० ३]
  [४ ० ० २]] 

Brutforser ने मुझे छकाया, लेकिन काम किया।
खैर, यह सब है। अब, यदि आप मुझसे पूछें कि क्या मेरे जीवन में edx पाठ्यक्रम काम आये हैं, तो मैं गर्व से "हाँ!" का उत्तर दूंगा और इस लेख का लिंक दूंगा।