Dykstra's projection algorithm
ডাইকস্ট্রার অ্যালগরিদম এমন একটি পদ্ধতি যা উত্তল সেটগুলির ছেদস্থলে একটি বিন্দু গণনা করে এবং এটি বিকল্প অভিক্ষেপ পদ্ধতির একটি বৈকল্পিক (যাকে উত্তল সেটগুলির উপর অভিক্ষেপ পদ্ধতিও বলা হয়)। তার সহজতম আকারে, পদ্ধতিটি প্রতিটি উত্তল সেটের উপর পুনরাবৃত্তভাবে অভিক্ষেপ করে দুটি উত্তল সেটের ছেদস্থলে একটি বিন্দু খুঁজে পায়; এটি বিকল্প অভিক্ষেপ পদ্ধতির থেকে পৃথক কারণ সেখানে মধ্যবর্তী ধাপ রয়েছে। অ্যালগরিদমের একটি সমান্তরাল সংস্করণ গ্যাফকে এবং মাথার তৈরি করেছিলেন। এই পদ্ধতির নামকরণ করা হয়েছে রিচার্ড এল. ডাইকস্ট্রার নামে যিনি 1980-এর দশকে এটি প্রস্তাব করেছিলেন। ডাইকস্ট্রার অ্যালগরিদম এবং স্ট্যান্ডার্ড অল্টারনেটিং প্রজেকশন পদ্ধতির মধ্যে একটি মূল পার্থক্য ঘটে যখন দুটি সেটের ছেদস্থলে একাধিক বিন্দু থাকে। এই ক্ষেত্রে, বিকল্প অভিক্ষেপ পদ্ধতি এই ছেদস্থলে কিছু নির্বিচারে বিন্দু দেয়, যেখানে ডাইক্স্ট্রার অ্যালগরিদম একটি নির্দিষ্ট বিন্দু দেয়ঃ ছেদস্থলে r-এর অভিক্ষেপ, যেখানে r হল অ্যালগরিদমে ব্যবহৃত প্রাথমিক বিন্দু, অ্যালগরিদম ডাইক্স্ট্রার অ্যালগরিদম প্রত্যেকটির জন্য কেবল এমন খুঁজে পায় যেঃ যেখানে উত্তল সেট রয়েছে। এই সমস্যাটি সেটের উপর প্রজেকশন খুঁজে বের করার সমতুল্য, যা আমরা দ্বারা চিহ্নিত করি। ডাইকস্ট্রার অ্যালগরিদম ব্যবহার করার জন্য, একজনকে অবশ্যই সেটগুলিতে এবং আলাদাভাবে প্রজেক্ট করতে হবে তা জানতে হবে। প্রথমে, মৌলিক অল্টারনেটিং প্রজেকশন (ওরফে পি. ও. সি. এস) পদ্ধতিটি বিবেচনা করুন (প্রথমে অধ্যয়ন করা হয়েছিল, যখন সেটগুলি রৈখিক সাবস্পেস ছিল, জন ভন নিউম্যান দ্বারা), যা শুরু করে এবং তারপর ক্রম তৈরি করে। ডাইকস্ট্রার অ্যালগরিদম একই ধরনের, তবে অতিরিক্ত সহায়ক চলক ব্যবহার করে। দিয়ে শুরু করুন এবং আপডেট করুন তারপর ক্রমটি মূল সমস্যার সমাধানে একত্রিত হয়। সংমিশ্রণ ফলাফল এবং সাহিত্যের উপর একটি আধুনিক দৃষ্টিভঙ্গির জন্য, রেফারেন্স উদ্ধৃতি কনভেক্স জ্যামিতি অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি দেখুন।