Dykstra's projection algorithm
ڈائیکسٹرا کا الگورتھم ایک ایسا طریقہ ہے جو کنویکس سیٹوں کے چوراہے میں ایک نقطہ کا حساب لگاتا ہے، اور یہ متبادل پروجیکشن طریقہ کار کا ایک متغیر ہے (جسے کنویکس سیٹوں پر پروجیکشن بھی کہا جاتا ہے)۔ اپنی آسان ترین شکل میں، یہ طریقہ دو کنویکس سیٹوں کے چوراہے میں ایک نقطہ تلاش کرتا ہے جو ہر کنویکس سیٹ پر بار بار پیش کیا جاتا ہے۔ یہ متبادل پروجیکشن طریقہ سے مختلف ہے جس میں درمیانی مراحل ہوتے ہیں۔ الگورتھم کا ایک متوازی ورژن گیفکے اور ماتھر نے تیار کیا تھا۔ اس طریقہ کار کا نام رچرڈ ایل ڈکسٹرا کے نام پر رکھا گیا ہے جس نے 1980 کی دہائی میں اس کی تجویز پیش کی تھی۔ ڈائیکسٹرا کے الگورتھم اور معیاری متبادل پروجیکشن کے طریقہ کار کے درمیان ایک اہم فرق اس وقت ہوتا ہے جب دونوں سیٹوں کے چوراہے میں ایک سے زیادہ پوائنٹ ہوتے ہیں۔ اس صورت میں، الٹرنیٹنگ پروجیکشن کا طریقہ اس چوراہے میں کچھ صوابدیدی نقطہ دیتا ہے، جبکہ ڈائیکسٹرا کا الگورتھم ایک مخصوص نقطہ دیتا ہے: چوراہے پر r کا پروجیکشن، جہاں r الگورتھم میں استعمال ہونے والا ابتدائی نقطہ ہے، الگورتھم ڈائیکسٹرا کا الگورتھم ہر ایک کے لیے صرف اتنا تلاش کرتا ہے کہ: جہاں کنویکس سیٹ ہیں۔ یہ مسئلہ سیٹ پر کے پروجیکشن کو تلاش کرنے کے مترادف ہے، جس کی طرف ہم اشارہ کرتے ہیں۔ ڈائیکسٹرا کے الگورتھم کو استعمال کرنے کے لیے، کسی کو سیٹ پر اور الگ سے پروجیکٹ کرنے کا طریقہ معلوم ہونا چاہیے۔ سب سے پہلے، بنیادی الٹرنیٹنگ پروجیکشن (عرف پی او سی ایس) طریقہ پر غور کریں (پہلے مطالعہ کیا گیا، اس صورت میں جب سیٹس لکیری سب اسپیس تھے، جان وان نیومن کے ذریعہ)، جو ترتیب کو شروع کرتا ہے اور پھر ترتیب پیدا کرتا ہے۔ ڈائیکسٹرا کا الگورتھم اسی طرح کی شکل کا ہے، لیکن اضافی معاون متغیرات کا استعمال کرتا ہے۔ شروع کریں اور اپ ڈیٹ کریں پھر ترتیب اصل مسئلے کے حل میں بدل جاتی ہے۔ کنورجنس کے نتائج اور ادب پر جدید نقطہ نظر کے لیے، حوالہ جات کنویکس جیومیٹری آپٹیمائزیشن الگورتھم اور طریقے دیکھیں۔