Dykstra's projection algorithm
डिक्स्ट्रा का एल्गोरिथ्म एक ऐसी विधि है जो उत्तल समुच्चय के प्रतिच्छेदन में एक बिंदु की गणना करती है, और वैकल्पिक प्रक्षेपण विधि का एक प्रकार है (जिसे उत्तल समुच्चय विधि पर प्रक्षेपण भी कहा जाता है)। अपने सबसे सरल रूप में, विधि प्रत्येक उत्तल समुच्चय पर पुनरावृत्त रूप से प्रक्षेपित करके दो उत्तल समुच्चय के प्रतिच्छेदन में एक बिंदु पाती है; यह वैकल्पिक प्रक्षेपण विधि से अलग है जिसमें मध्यवर्ती चरण हैं। एल्गोरिथम का एक समानांतर संस्करण गैफके और माथर द्वारा विकसित किया गया था। इस विधि का नाम रिचर्ड एल. डिक्स्ट्रा के नाम पर रखा गया है जिन्होंने 1980 के दशक में इसका प्रस्ताव रखा था। डिक्स्ट्रा के एल्गोरिथ्म और मानक प्रत्यावर्ती प्रक्षेपण विधि के बीच एक प्रमुख अंतर तब होता है जब दो सेटों के प्रतिच्छेदन में एक से अधिक बिंदु होते हैं। इस मामले में, प्रत्यावर्ती प्रक्षेपण विधि इस प्रतिच्छेदन में कुछ मनमाना बिंदु देती है, जबकि डिक्स्ट्रा का एल्गोरिथ्म एक विशिष्ट बिंदु देता हैः प्रतिच्छेदन पर r का प्रक्षेपण, जहां r एल्गोरिथ्म में उपयोग किया जाने वाला प्रारंभिक बिंदु है, एल्गोरिथ्म डिक्स्ट्रा का एल्गोरिथ्म प्रत्येक के लिए केवल ऐसा पाता है किः जहां उत्तल सेट हैं। यह समस्या सेट पर के प्रक्षेपण को खोजने के बराबर है, जिसे हम दर्शाते हैं। डिक्स्ट्रा के एल्गोरिदम का उपयोग करने के लिए, किसी को पता होना चाहिए कि सेट पर और अलग से कैसे प्रोजेक्ट किया जाए। सबसे पहले, बुनियादी प्रत्यावर्ती प्रक्षेपण (उर्फ पी. ओ. सी. एस.) विधि पर विचार करें (पहले अध्ययन किया गया, उस मामले में जब सेट रैखिक उप-स्थान थे, जॉन वॉन न्यूमैन द्वारा), जो अनुक्रम को आरंभ करता है और फिर उत्पन्न करता है। डिक्स्ट्रा का एल्गोरिथ्म एक समान रूप का है, लेकिन अतिरिक्त सहायक चर का उपयोग करता है। शुरू करें और तब तक अद्यतन करें फिर अनुक्रम मूल समस्या के समाधान में परिवर्तित हो जाता है। अभिसरण परिणामों और साहित्य पर एक आधुनिक परिप्रेक्ष्य के लिए, संदर्भ उद्धरण कन्वेक्स ज्यामिति अनुकूलन एल्गोरिदम और विधियाँ देखें।