Stacker crane problem
কম্বিনেটোরিয়াল অপ্টিমাইজেশনে, স্ট্যাকার ক্রেন সমস্যা হল একটি অপ্টিমাইজেশান সমস্যা যা ভ্রমণকারী বিক্রেতার সমস্যার সাথে ঘনিষ্ঠভাবে সম্পর্কিত। এর ইনপুট একটি মেট্রিক স্পেসে অর্ডার করা জোড়া পয়েন্টের সংগ্রহ নিয়ে গঠিত, এবং লক্ষ্য হল এই পয়েন্টগুলিকে ন্যূনতম মোট দৈর্ঘ্যের একটি চক্রে সংযুক্ত করা যাতে সমস্ত জোড়া অন্তর্ভুক্ত থাকে, একে অপরের সাথে ধারাবাহিকভাবে ভিত্তিক। এটি একটি স্ট্যাকার ক্রেন, নির্মাণ ক্রেন বা (ড্রেয়েজে) একটি ট্রাক দ্বারা পৃথক পৃথক পণ্যসম্ভার তোলার এবং সরবরাহের সময়সূচী নির্ধারণের সমস্যাগুলির মডেল তৈরি করে, এই সরবরাহের সময়ের সীমাবদ্ধতা ছাড়াই সরলীকৃত আকারে। এটি দ্বারা প্রবর্তিত হয়েছিল, মিশ্র গ্রাফের পরিপ্রেক্ষিতে একটি সমতুল্য গঠনের সাথে নির্দেশিত প্রান্তগুলি ইনপুট জোড়া এবং অনির্দিষ্ট প্রান্তগুলি তাদের দূরত্বের মডেলিং করে। ফ্রেডেরিকসন ও অন্যান্য। এর গঠনের কৃতিত্ব ড্যানিয়েল জে রোজেনক্রান্টজের ব্যক্তিগত যোগাযোগকে দেওয়া হয়। স্ট্যাকার ক্রেন সমস্যাকে মেট্রিক স্পেসে ভ্রমণকারী বিক্রেতার সমস্যার একটি সাধারণীকরণ হিসাবে দেখা যেতে পারেঃ ভ্রমণকারী বিক্রেতার সমস্যার যে কোনও উদাহরণ স্ট্যাকার ক্রেন সমস্যার একটি উদাহরণে রূপান্তরিত হতে পারে, ভ্রমণকারী বিক্রেতার উদাহরণে প্রতিটি পয়েন্টের জন্য একটি জোড়া থাকে। অন্য দিকে, স্ট্যাকার ক্রেন সমস্যাটিকে অসমমিত ভ্রমণকারী বিক্রেতা সমস্যার একটি বিশেষ ক্ষেত্রে দেখা যেতে পারে, যেখানে অসমমিত ভ্রমণকারী বিক্রেতা সমস্যার পয়েন্টগুলি হল স্ট্যাকার ক্রেনের উদাহরণের জোড়া এবং এক জোড়া থেকে অন্য জোড়া পর্যন্ত দূরত্বকে প্রথম জুটির ডেলিভারি পয়েন্ট থেকে, তার পিকআপ পয়েন্টের মাধ্যমে, দ্বিতীয় জুটির ডেলিভারি পয়েন্ট পর্যন্ত দূরত্ব হিসাবে নেওয়া হয়। যেহেতু এটি ভ্রমণকারী বিক্রেতার সমস্যাকে সাধারণীকরণ করে, তাই এটি একই গণনামূলক জটিলতা উত্তরাধিকার সূত্রে পায়ঃ এটি এনপি-শক্ত, এবং কমপক্ষে আনুমানিক করা কঠিন। ভ্রমণকারী বিক্রেতার সমস্যার জন্য ক্রিস্টোফাইডস অ্যালগরিদমের উপর ভিত্তি করে একটি আনুমানিক অ্যালগরিদম স্ট্যাকার ক্রেন সমস্যার সমাধানকে আনুমানিক 9/5 অনুপাতের মধ্যে অনুমান করতে পারে। ব্যবহৃত সুতোর মোট পরিমাণ হ্রাস করার জন্য একটি সূচিকর্ম প্যাটার্নের পিছনের দিকটি ডিজাইন করার সমস্যাটি স্ট্যাকার ক্রেন সমস্যার সাথে ঘনিষ্ঠভাবে সম্পর্কিত, তবে এটি তার প্রতিটি জোড়া পয়েন্টকে (প্যাটার্নের সামনের দিকে দৃশ্যমান সেলাইয়ের প্রান্ত) উভয় দিকেই অতিক্রম করার অনুমতি দেয়, ট্র্যাভারসালকে সমস্ত জোড়ার মধ্য দিয়ে সামঞ্জস্যপূর্ণ দিকে যাওয়ার প্রয়োজন হয় না। ভ্রমণকারী বিক্রেতার সমস্যা থেকে একই রূপান্তর দ্বারা এটি এন. পি-হার্ড, এবং 2 এর আনুমানিক অনুপাতের মধ্যে অনুমান করা যেতে পারে। স্ট্যাকার ক্রেন সমস্যার আরেকটি বৈচিত্র্য, যাকে ডায়াল-এ-রাইড সমস্যা বলা হয়, একটি গাড়ির জন্য ন্যূনতম রুটের জন্য জিজ্ঞাসা করে যাতে এটি তার পথে যে কোনও সময়ে কিছু সংখ্যক লোড ধরে রাখতে পারে। তথ্যসূত্র ভ্রমণকারী বিক্রেতার সমস্যা