फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
==समस्या कथन== | ==समस्या कथन== | ||
समस्या का नाम वास्तविक दुनिया के फायरिंग दस्तों के साथ सादृश्य से आता | समस्या का नाम वास्तविक दुनिया के फायरिंग दस्तों के साथ सादृश्य से आता है। लक्ष्य नियमों की प्रणाली प्रस्तुत करना है जिसके अनुसार अधिकारी निष्पादन विवरण को फायर करने का आदेश दे सकता है, जिससे उसके सदस्य अपनी राइफलों को साथ में फायर कर सकें। | ||
अधिक औपचारिक रूप से, समस्या [[सेल्यूलर आटोमेटा]] से संबंधित है, परिमित राज्य मशीनों की सारणी जिन्हें | अधिक औपचारिक रूप से, समस्या [[सेल्यूलर आटोमेटा]] से संबंधित है, परिमित राज्य मशीनों की सारणी जिन्हें "कोशिकाएं" कहा जाता है, पंक्ति में व्यवस्थित होती हैं, जैसे कि प्रत्येक समय चरण पर प्रत्येक मशीन अपने पूर्व राज्य और अपने दो प्रतिवेशीयों के राज्यों के कार्य के रूप में नए राज्य में परिवर्तित हो जाती है। [[ अग्निशमक दल |फायरिंग स्क्वाड]] समस्या के लिए, लाइन में कोशिकाओं की सीमित संख्या होती है, और नियम जिसके अनुसार प्रत्येक मशीन आगामी राज्य में संक्रमण करती है, लाइन के आंतरिक सभी कोशिकाओं के लिए समान होनी चाहिए, किन्तु दो के संक्रमण कार्य रेखा के अंतिम बिंदुओं को भिन्न-भिन्न होने की अनुमति है, क्योंकि इन दोनों कोशिकाओं में से प्रत्येक के दोनों किनारों पर एक प्रतिवेशी विलुप्त है। | ||
प्रत्येक कोशिका की अवस्थाओं में तीन | प्रत्येक कोशिका की अवस्थाओं में तीन भिन्न-भिन्न अवस्थाएँ शामिल होती हैं: सक्रिय, शांत और सक्रिय, और संक्रमण कार्य ऐसा होना चाहिए कि कोशिका जो शांत है और जिसके पड़ोसी शांत हैं वह शांत बनी रहे। प्रारंभ में, समय पर {{math|1=''t'' = 0}}, सबसे बाईं ओर (सामान्य) सेल को छोड़कर, जो सक्रिय है, सभी अवस्थाएँ शांत हैं। लक्ष्य राज्यों का सेट और संक्रमण फ़ंक्शन को इस तरह डिज़ाइन करना है कि, कोशिकाओं की रेखा कितनी भी लंबी क्यों न हो, समय मौजूद हो {{mvar|t}} ऐसा कि प्रत्येक कोशिका समय पर फायरिंग अवस्था में परिवर्तित हो जाती है {{mvar|t}}, और ऐसा कि कोई भी सेल समय से पहले फायरिंग स्थिति से संबंधित नहीं है {{mvar|t}}. | ||
==समाधान== | ==समाधान== | ||
एफएसएसपी का पहला समाधान जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिन्स्की द्वारा पाया गया था और एडवर्ड एफ मूर द्वारा अनुक्रमिक मशीनों में प्रकाशित किया गया था। उनके समाधान में सैनिकों की पंक्ति के नीचे दो तरंगों का प्रसार शामिल है: तेज़ लहर और धीमी लहर जो तीन गुना धीमी गति से चलती है। तेज़ लहर रेखा के दूसरे छोर से उछलती है और केंद्र में धीमी लहर से मिलती है। फिर दोनों तरंगें चार तरंगों में विभाजित हो गईं, तेज़ और धीमी तरंग केंद्र से किसी भी दिशा में चलती हुई, प्रभावी रूप से रेखा को दो बराबर भागों में विभाजित कर देती है। यह प्रक्रिया तब तक जारी रहती है, जब तक कि प्रत्येक विभाजन की लंबाई 1 न हो जाए। इस समय, प्रत्येक सैनिक गोली चलाता है। इस समाधान के लिए n सैनिकों के लिए 3n इकाई समय की आवश्यकता होती है। | एफएसएसपी का पहला समाधान जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिन्स्की द्वारा पाया गया था और एडवर्ड एफ मूर द्वारा अनुक्रमिक मशीनों में प्रकाशित किया गया था। उनके समाधान में सैनिकों की पंक्ति के नीचे दो तरंगों का प्रसार शामिल है: तेज़ लहर और धीमी लहर जो तीन गुना धीमी गति से चलती है। तेज़ लहर रेखा के दूसरे छोर से उछलती है और केंद्र में धीमी लहर से मिलती है। फिर दोनों तरंगें चार तरंगों में विभाजित हो गईं, तेज़ और धीमी तरंग केंद्र से किसी भी दिशा में चलती हुई, प्रभावी रूप से रेखा को दो बराबर भागों में विभाजित कर देती है। यह प्रक्रिया तब तक जारी रहती है, जब तक कि प्रत्येक विभाजन की लंबाई 1 न हो जाए। इस समय, प्रत्येक सैनिक गोली चलाता है। इस समाधान के लिए n सैनिकों के लिए 3n इकाई समय की आवश्यकता होती है। | ||
न्यूनतम समय (जो है) का उपयोग करके समाधान {{math|2''n'' − 2}}समय की इकाइयों के लिए {{mvar|n}} सैनिक), सबसे पहले किसके द्वारा पाया गया था {{harvs|first=Eiichi|last=Goto|authorlink=Eiichi Goto|year=1962|txt}}, | न्यूनतम समय (जो है) का उपयोग करके समाधान {{math|2''n'' − 2}}समय की इकाइयों के लिए {{mvar|n}} सैनिक), सबसे पहले किसके द्वारा पाया गया था {{harvs|first=Eiichi|last=Goto|authorlink=Eiichi Goto|year=1962|txt}}, किन्तु उसके समाधान में हजारों राज्यों का उपयोग किया गया। {{harvtxt|Waksman|1966}}इसे 16 राज्यों तक सुधारा, और {{harvtxt|Balzer|1967}} ने इसे आठ राज्यों तक और सुधार दिया, जबकि यह साबित करने का दावा किया कि कोई चार-राज्य समाधान मौजूद नहीं है। [[पीटर सैंडर्स (कंप्यूटर वैज्ञानिक)]] ने बाद में पाया कि बाल्ज़र की खोज प्रक्रिया अधूरी थी, किन्तु सही खोज प्रक्रिया के माध्यम से चार-राज्य गैर-अस्तित्व परिणाम की फिर से पुष्टि करने में कामयाब रहे। वर्तमान में सबसे अच्छा ज्ञात समाधान, छह राज्यों का उपयोग करते हुए, द्वारा पेश किया गया था {{harvs|first=Jacques|last=Mazoyer|year=1987|txt}}. यह अभी भी अज्ञात है कि क्या पाँच-राज्य समाधान मौजूद है। | ||
न्यूनतम समय वाले समाधानों में, सामान्य सही संकेत भेजता है {{math|''S''<sub>1</sub>, ''S''<sub>2</sub>, ''S''<sub>3</sub>, ..., ''S''<sub>''i''</sub>}} गति से {{math|1, 1/3, 1/7, ..., 1/(2<sup> ''i''−1</sup> − 1)}}. सिग्नल {{math|''S''<sub>1</sub>}} लाइन के दाहिने छोर पर प्रतिबिंबित होता है, और सिग्नल से मिलता है {{math|''S''<sub>''i''</sub>}} (के लिए {{math|''i'' ≥ 2}}) सेल पर {{math|''n''/2<sup> ''i''−1</sup>}}. कब {{math|''S''<sub>1</sub>}} प्रतिबिंबित करता है, यह सही छोर पर नया जनरल भी बनाता है। सिग्नल {{math|''S''<sub>''i''</sub>}} का निर्माण सहायक संकेतों का उपयोग करके किया जाता है, जो बाईं ओर फैलता है। हर दूसरी बार जब कोई सिग्नल (दाईं ओर) चलता है, तो यह बाईं ओर सहायक सिग्नल भेजता है। {{math|''S''<sub>1</sub>}} गति 1 से अपने आप चलता है जबकि प्रत्येक धीमा सिग्नल केवल तभी चलता है जब उसे कोई सहायक सिग्नल मिलता है। | न्यूनतम समय वाले समाधानों में, सामान्य सही संकेत भेजता है {{math|''S''<sub>1</sub>, ''S''<sub>2</sub>, ''S''<sub>3</sub>, ..., ''S''<sub>''i''</sub>}} गति से {{math|1, 1/3, 1/7, ..., 1/(2<sup> ''i''−1</sup> − 1)}}. सिग्नल {{math|''S''<sub>1</sub>}} लाइन के दाहिने छोर पर प्रतिबिंबित होता है, और सिग्नल से मिलता है {{math|''S''<sub>''i''</sub>}} (के लिए {{math|''i'' ≥ 2}}) सेल पर {{math|''n''/2<sup> ''i''−1</sup>}}. कब {{math|''S''<sub>1</sub>}} प्रतिबिंबित करता है, यह सही छोर पर नया जनरल भी बनाता है। सिग्नल {{math|''S''<sub>''i''</sub>}} का निर्माण सहायक संकेतों का उपयोग करके किया जाता है, जो बाईं ओर फैलता है। हर दूसरी बार जब कोई सिग्नल (दाईं ओर) चलता है, तो यह बाईं ओर सहायक सिग्नल भेजता है। {{math|''S''<sub>1</sub>}} गति 1 से अपने आप चलता है जबकि प्रत्येक धीमा सिग्नल केवल तभी चलता है जब उसे कोई सहायक सिग्नल मिलता है। | ||
Revision as of 18:10, 10 August 2023
फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या कंप्यूटर विज्ञान और सेलुलर ऑटोमेटन में समस्या है, जिसमें लक्ष्य सेलुलर ऑटोमेटन को डिजाइन करना है, जो सक्रिय सेल से प्रारम्भ होकर अंततः ऐसी स्थिति तक पहुंचता है, जिसमें सभी कोशिकाएं एक साथ सक्रिय होती हैं। इसे प्रथम बार 1957 में जॉन माइहिल द्वारा प्रस्तावित किया गया था और 1962 में एडवर्ड एफ. मूर द्वारा (जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिंस्की द्वारा समाधान के साथ) प्रकाशित किया गया था।
समस्या कथन
समस्या का नाम वास्तविक दुनिया के फायरिंग दस्तों के साथ सादृश्य से आता है। लक्ष्य नियमों की प्रणाली प्रस्तुत करना है जिसके अनुसार अधिकारी निष्पादन विवरण को फायर करने का आदेश दे सकता है, जिससे उसके सदस्य अपनी राइफलों को साथ में फायर कर सकें।
अधिक औपचारिक रूप से, समस्या सेल्यूलर आटोमेटा से संबंधित है, परिमित राज्य मशीनों की सारणी जिन्हें "कोशिकाएं" कहा जाता है, पंक्ति में व्यवस्थित होती हैं, जैसे कि प्रत्येक समय चरण पर प्रत्येक मशीन अपने पूर्व राज्य और अपने दो प्रतिवेशीयों के राज्यों के कार्य के रूप में नए राज्य में परिवर्तित हो जाती है। फायरिंग स्क्वाड समस्या के लिए, लाइन में कोशिकाओं की सीमित संख्या होती है, और नियम जिसके अनुसार प्रत्येक मशीन आगामी राज्य में संक्रमण करती है, लाइन के आंतरिक सभी कोशिकाओं के लिए समान होनी चाहिए, किन्तु दो के संक्रमण कार्य रेखा के अंतिम बिंदुओं को भिन्न-भिन्न होने की अनुमति है, क्योंकि इन दोनों कोशिकाओं में से प्रत्येक के दोनों किनारों पर एक प्रतिवेशी विलुप्त है।
प्रत्येक कोशिका की अवस्थाओं में तीन भिन्न-भिन्न अवस्थाएँ शामिल होती हैं: सक्रिय, शांत और सक्रिय, और संक्रमण कार्य ऐसा होना चाहिए कि कोशिका जो शांत है और जिसके पड़ोसी शांत हैं वह शांत बनी रहे। प्रारंभ में, समय पर t = 0, सबसे बाईं ओर (सामान्य) सेल को छोड़कर, जो सक्रिय है, सभी अवस्थाएँ शांत हैं। लक्ष्य राज्यों का सेट और संक्रमण फ़ंक्शन को इस तरह डिज़ाइन करना है कि, कोशिकाओं की रेखा कितनी भी लंबी क्यों न हो, समय मौजूद हो t ऐसा कि प्रत्येक कोशिका समय पर फायरिंग अवस्था में परिवर्तित हो जाती है t, और ऐसा कि कोई भी सेल समय से पहले फायरिंग स्थिति से संबंधित नहीं है t.
समाधान
एफएसएसपी का पहला समाधान जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिन्स्की द्वारा पाया गया था और एडवर्ड एफ मूर द्वारा अनुक्रमिक मशीनों में प्रकाशित किया गया था। उनके समाधान में सैनिकों की पंक्ति के नीचे दो तरंगों का प्रसार शामिल है: तेज़ लहर और धीमी लहर जो तीन गुना धीमी गति से चलती है। तेज़ लहर रेखा के दूसरे छोर से उछलती है और केंद्र में धीमी लहर से मिलती है। फिर दोनों तरंगें चार तरंगों में विभाजित हो गईं, तेज़ और धीमी तरंग केंद्र से किसी भी दिशा में चलती हुई, प्रभावी रूप से रेखा को दो बराबर भागों में विभाजित कर देती है। यह प्रक्रिया तब तक जारी रहती है, जब तक कि प्रत्येक विभाजन की लंबाई 1 न हो जाए। इस समय, प्रत्येक सैनिक गोली चलाता है। इस समाधान के लिए n सैनिकों के लिए 3n इकाई समय की आवश्यकता होती है।
न्यूनतम समय (जो है) का उपयोग करके समाधान 2n − 2समय की इकाइयों के लिए n सैनिक), सबसे पहले किसके द्वारा पाया गया था Eiichi Goto (1962), किन्तु उसके समाधान में हजारों राज्यों का उपयोग किया गया। Waksman (1966)इसे 16 राज्यों तक सुधारा, और Balzer (1967) ने इसे आठ राज्यों तक और सुधार दिया, जबकि यह साबित करने का दावा किया कि कोई चार-राज्य समाधान मौजूद नहीं है। पीटर सैंडर्स (कंप्यूटर वैज्ञानिक) ने बाद में पाया कि बाल्ज़र की खोज प्रक्रिया अधूरी थी, किन्तु सही खोज प्रक्रिया के माध्यम से चार-राज्य गैर-अस्तित्व परिणाम की फिर से पुष्टि करने में कामयाब रहे। वर्तमान में सबसे अच्छा ज्ञात समाधान, छह राज्यों का उपयोग करते हुए, द्वारा पेश किया गया था Jacques Mazoyer (1987). यह अभी भी अज्ञात है कि क्या पाँच-राज्य समाधान मौजूद है।
न्यूनतम समय वाले समाधानों में, सामान्य सही संकेत भेजता है S1, S2, S3, ..., Si गति से 1, 1/3, 1/7, ..., 1/(2 i−1 − 1). सिग्नल S1 लाइन के दाहिने छोर पर प्रतिबिंबित होता है, और सिग्नल से मिलता है Si (के लिए i ≥ 2) सेल पर n/2 i−1. कब S1 प्रतिबिंबित करता है, यह सही छोर पर नया जनरल भी बनाता है। सिग्नल Si का निर्माण सहायक संकेतों का उपयोग करके किया जाता है, जो बाईं ओर फैलता है। हर दूसरी बार जब कोई सिग्नल (दाईं ओर) चलता है, तो यह बाईं ओर सहायक सिग्नल भेजता है। S1 गति 1 से अपने आप चलता है जबकि प्रत्येक धीमा सिग्नल केवल तभी चलता है जब उसे कोई सहायक सिग्नल मिलता है।
सामान्यीकरण
फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या को कई अन्य प्रकार के सेलुलर ऑटोमेटन के लिए सामान्यीकृत किया गया है, जिसमें कोशिकाओं के उच्च-आयामी सरणी भी शामिल हैं (Shinahr 1974). विभिन्न प्रारंभिक स्थितियों वाली समस्या के विभिन्न प्रकारों पर भी विचार किया गया है (Kobayashi & Goldstein 2005).
फायरिंग स्क्वाड समस्या के समाधान को अन्य समस्याओं के लिए भी अपनाया जा सकता है। उदाहरण के लिए, Patrick Fischer (1965) ने फायरिंग स्क्वाड सिंक्रोनाइज़ेशन समस्या के पहले समाधान के आधार पर अभाज्य संख्याएँ उत्पन्न करने के लिए सेलुलर ऑटोमेटन एल्गोरिदम डिज़ाइन किया।
संदर्भ
- Balzer, Robert (1967), "An 8-state minimal time solution to the firing squad synchronization problem", Information and Control, 10 (1): 22–42, doi:10.1016/S0019-9958(67)90032-0.
- Fischer, Patrick C. (1965), "Generation of primes by a one-dimensional real-time iterative array", Journal of the ACM, 12 (3): 388–394, doi:10.1145/321281.321290.
- Goto, Eiichi (1962), A minimal time solution of the firing squad problem, Dittoed course notes for Applied Mathematics 298, Cambridge, MA: Harvard University, pp. 52–59. As cited by Waksman (1966).
- Kobayashi, Kojiro; Goldstein, Darin (2005), "On formulations of firing squad synchronization problems", Unconventional Computation (PDF), Lecture Notes in Computer Science, vol. 3699, Springer-Verlag, pp. 157–168, doi:10.1007/11560319_15.
- Mazoyer, Jacques (1987), "A six-state minimal time solution to the firing squad synchronization problem", Theoretical Computer Science, 50 (2): 183–238, doi:10.1016/0304-3975(87)90124-1.
- Moore, F. R.; Langdon, G. G. (1968), "A generalized firing squad problem", Information and Control, 12 (3): 212–220, doi:10.1016/S0019-9958(68)90309-4.
- Shinahr, Ilka (1974), "Two- and three-dimensional firing-squad synchronization problem", Information and Control, 24 (2): 163–180, doi:10.1016/S0019-9958(74)80055-0.
- Waksman, Abraham (1966), "An optimum solution to the firing squad synchronization problem", Information and Control, 9 (1): 66–78, doi:10.1016/S0019-9958(66)90110-0.
