किस तरह की प्रोग्रामिंग समस्याएं राज्य मशीनें सबसे उपयुक्त हैं?राज्य मशीनों के लिए किस प्रकार की समस्याएं अच्छी हैं?
मैंने राज्य मशीनों का उपयोग करके पार्सर्स को कार्यान्वित करने के बारे में पढ़ा है, लेकिन राज्य मशीन के रूप में लागू होने वाली समस्याओं के बारे में जानना चाहते हैं।
सबसे आसान जवाब शायद यह है कि वे व्यावहारिक रूप से किसी भी समस्या के लिए उपयुक्त हैं। यह न भूलें कि एक कंप्यूटर स्वयं भी एक राज्य मशीन है।
इसके बावजूद, राज्य मशीनों को आमतौर पर उन समस्याओं के लिए उपयोग किया जाता है जहां इनपुट की कुछ धारा होती है और किसी भी क्षण में गतिविधि की आवश्यकता होती है, उस बिंदु पर उस धारा में दिखाई देने वाले अंतिम तत्वों पर निर्भर करता है।
इनपुट के इस धारा के उदाहरण: पार्स के मामले में कुछ पाठ फ़ाइल, नियमित अभिव्यक्ति के लिए एक स्ट्रिंग, इस तरह के खेल ऐ के लिए player entered room, आदि के रूप घटनाओं
गतिविधियों के उदाहरण: एक नंबर को पढ़ने के लिए तैयार हो (+ के बाद एक और संख्या के बाद एक कैलकुलेटर के लिए एक पार्सर में इनपुट में दिखाई दिया है), चारों ओर मुड़ें (खिलाड़ी के संपर्क में और फिर छींकने के बाद), कूदते किक (खिलाड़ी बाएं, बाएं, दाएं, ऊपर, ऊपर दबाए जाने के बाद) करें।
टीसीपी जैसे राज्यिक प्रोटोकॉल अक्सर राज्य मशीनों के रूप में प्रदर्शित होते हैं। हालांकि यह दुर्लभ है कि आपको किसी भी राज्य मशीन के रूप में उचित रूप से कुछ भी लागू करना चाहिए। आम तौर पर आप एक के भ्रष्टाचार का उपयोग करेंगे, यानी एक राज्य में बैठे हुए, एक संक्रमण में डेटा लॉगिंग करते समय, या एक राज्य में रहते हुए डेटा का आदान-प्रदान करते समय बार-बार कार्रवाई की जाती है।
कार्यप्रवाह (.net 3.0 में WF देखें)
वे कई उपयोग हैं, पारसर्स एक उल्लेखनीय एक होने। मैंने व्यक्तिगत रूप से अनुप्रयोगों में जटिल बहु-चरण कार्य संवाद लागू करने के लिए सरलीकृत राज्य मशीनों का उपयोग किया है।
एक पार्सर उदाहरण। मैंने हाल ही में एक पार्सर लिखा है जो किसी अन्य कार्यक्रम से बाइनरी स्ट्रीम लेता है। पार्स किए गए वर्तमान तत्व का अर्थ अगले तत्वों के आकार/अर्थ को इंगित करता है। तत्वों की एक छोटी (छोटी) सीमित संख्या संभव है। इसलिए एक राज्य मशीन।
वे उन चीजों को मॉडलिंग के लिए बहुत अच्छे हैं जो स्थिति बदलते हैं, और तर्क है जो प्रत्येक संक्रमण पर ट्रिगर करता है।
मैं मेल द्वारा संकुल को ट्रैक करने के लिए परिमित राज्य मशीनों का उपयोग करता हूं, या पंजीकरण प्रक्रिया के दौरान किसी उपयोगकर्ता के विभिन्न स्तर का ट्रैक रखने के लिए उपयोग करता हूं।
संभावित स्थिति मानों की संख्या बढ़ जाती है, संक्रमण की संख्या विस्फोट हो जाती है। राज्य मशीनें उस मामले में बहुत मदद करती हैं।
चीजें जो मन में आता है:
- रोबोट/मशीन में गड़बड़ी ... कारखानों में उन रोबोट हथियारों
- सिम्युलेशनगेम, (SimCity, रेसिंग गेम आदि ..)
सामान्यीकरण: आप आदानों कि जब उनमें से किसी के साथ बातचीत के एक स्ट्रिंग है, तो, जब में किसी एक के प्रसंस्करण पिछले आदानों की या दूसरे शब्दों में ज्ञान की आवश्यकता है रखो पिछले इनपुट के ज्ञान की आवश्यकता है।
ज्यादा मुझे पता है कि की है कि हालांकि एक पार्स समस्या को कम करने योग्य नहीं है (कि यह "राज्यों" की जरूरत है,)। खेलों में
ऐ बहुत बार राज्य मशीनों का उपयोग कर कार्यान्वित किया जाता है। असतत तर्क बनाने में मदद करता है जो निर्माण और परीक्षण के लिए बहुत आसान है। खेलों में
वस्तुओं अक्सर राज्य मशीनों के रूप में प्रतिनिधित्व कर रहे हैं। एक ऐ चरित्र हो सकता है:
तो आप देख सकते इन कुछ सरल लेकिन प्रभावी राज्यों मॉडल हो सकता है
एक और उदाहरण Google Checkout पर खरीदारी करने जैसी प्रक्रिया होगी। Google वित्तीय और आदेश के लिए कई राज्यों को देता है, और फिर आपको क्रेडिट कार्ड समाशोधन या अस्वीकार करने जैसे ट्रांजिस्टियन की जानकारी देता है, और आपको यह सूचित करने की अनुमति देता है कि आदेश भेज दिया गया है।
एक जटिल प्रणाली में नियमित अभिव्यक्ति मिलान, पार्सिंग, प्रवाह नियंत्रण।
नियमित अभिव्यक्तियां राज्य मशीन का एक साधारण रूप है, विशेष रूप से परिमित ऑटोमाटा। उनके पास एक प्राकृतिक पुनर्जीवन है, हालांकि पारस्परिक रूप से पुनरावर्ती कार्यों का उपयोग करके उन्हें लागू करना संभव है।
अच्छी तरह से लागू होने पर राज्य मशीनें बहुत ही कुशल होंगी।
यदि आप एक पठनीय राज्य मशीन बनाना चाहते हैं, तो कई लक्षित भाषाओं के लिए एक उत्कृष्ट राज्य मशीन कंपाइलर है।
http://research.cs.queensu.ca/~thurston/ragel/
यह भी आप खतरनाक 'गोटो' से बचने के लिए अनुमति देता है।
बस एक साइड नोट के रूप में, आप tail recursion प्रश्न में समझाए गए उचित पूंछ कॉल के साथ राज्य मशीनों को कार्यान्वित कर सकते हैं।
उस उदाहरण में गेम में प्रत्येक कमरे को एक राज्य माना जाता है।
इसके अलावा, वीएचडीएल (और अन्य तर्क संश्लेषण भाषाओं) के साथ हार्डवेयर डिज़ाइन हार्डवेयर का वर्णन करने के लिए हर जगह राज्य मशीनों का उपयोग करता है।
यह एक अच्छा संसाधन है यह निःशुल्क State Machine EBook है। मेरा अपना त्वरित उत्तर नीचे है।
जब आपके तर्क में आखिरी बार चलने वाले बारे में जानकारी होनी चाहिए, तो इसमें राज्य होना चाहिए।
तो एक राज्य मशीन बस कोई भी कोड है जो सूचना को याद करता है (या कार्य करता है) जो केवल पहले जो हुआ उससे समझकर प्राप्त किया जा सकता है।
उदाहरण के लिए, मेरे पास एक सेलुलर मॉडेम है जो मेरे प्रोग्राम का उपयोग करना चाहिए।
अब मैं मुख्य कार्यक्रम को अवरुद्ध कर सकता हूं और प्रत्येक चरण को चलाने के लिए बस इन सभी चरणों को पार कर सकता हूं, लेकिन मैं अपने उपयोगकर्ता प्रतिक्रिया देना चाहता हूं और एक ही समय में अन्य परिचालन करना चाहता हूं। तो मैं इसे एक समारोह के अंदर एक राज्य मशीन के रूप में लागू करता हूं, और इस समारोह को एक सेकंड में 100 बार चलाता हूं।
enum states{reset,initsend, initresponse, waitonsignal,dial,ppp,...}
modemfunction()
{
static currentstate
switch(currentstate)
{
case reset:
Do reset
if reset was successful, nextstate=init else nextstate = reset
break
case initsend
send "ATD"
nextstate = initresponse
break
...
}
currentstate=nextstate
}
अधिक जटिल राज्य मशीनों प्रोटोकॉल को लागू। उदाहरण के लिए मैंने उपयोग किया गया एक ईसीयू डायग्नोस्टिक्स प्रोटोकॉल केवल 8 बाइट पैकेट भेज सकता है, लेकिन कभी-कभी मुझे बड़े पैकेट भेजने की आवश्यकता होती है। ईसीयू धीमा है, इसलिए मुझे प्रतिक्रिया के लिए इंतजार करना होगा।आदर्श रूप में जब मैं एक संदेश भेजता हूं तो मैं एक समारोह का उपयोग करता हूं और फिर मुझे कोई परवाह नहीं है कि क्या होता है, लेकिन कहीं मेरे कार्यक्रम को लाइन की निगरानी करनी चाहिए और इन संदेशों को भेजना और जवाब देना चाहिए, उन्हें छोटे टुकड़ों में तोड़ना और प्राप्त संदेशों के टुकड़ों को फिर से इकट्ठा करना अंतिम संदेश
यदि आपको एक साधारण स्टोकास्टिक प्रक्रिया की आवश्यकता है, तो आप मार्कोव चेन का उपयोग कर सकते हैं, जिसे राज्य मशीन के रूप में प्रदर्शित किया जा सकता है (वर्तमान स्थिति को देखते हुए, अगले चरण में चेन एक निश्चित संभावना के साथ राज्य एक्स में होगा)।
कोई वर्कफ़्लो एप्लिकेशन, विशेष रूप से असीमित गतिविधियों के साथ। आपके पास एक निश्चित स्थिति में वर्कफ़्लो में एक आइटम है, और राज्य मशीन जानता है कि आइटम को किसी भिन्न स्थिति में रखकर बाहरी घटनाओं पर प्रतिक्रिया कैसे करें, जिस बिंदु पर कुछ अन्य गतिविधि होती है।
राज्य की अवधारणा अनुप्रयोगों के लिए आपके सिस्टम के वर्तमान संदर्भ को "याद" करने के लिए बहुत उपयोगी है और जानकारी का एक नया टुकड़ा आने पर ठीक से प्रतिक्रिया करता है। किसी भी गैर तुच्छ अनुप्रयोग में वैरिएबल और सशर्त के माध्यम से कोड में एम्बेडेड धारणा है।
इसलिए यदि आपके आवेदन में संदर्भ के कारण हर बार अलग-अलग प्रतिक्रिया प्राप्त होती है, तो आप अपने सिस्टम को राज्य मशीनों के साथ मॉडल कर सकते हैं। एक उदाहरण कैलकुलेटर पर चाबियों की व्याख्या करने का तरीका होगा, जो इस समय उस समय पर प्रसंस्करण पर निर्भर करता है।
इसके विपरीत, यदि आपकी गणना संदर्भ से निर्भर नहीं करता है, लेकिन पूरी तरह से इनपुट (एक समारोह दो नंबर को जोड़ना) पर, आप एक राज्य मशीन की जरूरत नहीं होगी (या बेहतर कहा, आप के साथ एक राज्य मशीन होगा शून्य राज्य)
कुछ लोग पूरे मशीन को राज्य मशीनों के मामले में डिजाइन करते हैं क्योंकि वे आपके प्रोजेक्ट में ध्यान रखने के लिए आवश्यक चीजों को पकड़ते हैं और फिर निष्पादन योग्य बनाने के लिए कुछ प्रक्रिया या ऑटोकोडर्स का उपयोग करते हैं। इस तरह से कार्यक्रम के लिए कुछ प्रतिमान अवसर लगता है, लेकिन मुझे यह बहुत प्रभावी लगता है।
एक अच्छी स्पष्टीकरण के लिए वाम 4Dead के एआई में http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf देखें। –