কবুতর, কার্ভ, এবং ভ্রমণ বিক্রেতা সমস্যা

মো উইলেমস ‘ শিশুদের বই কবুতরকে বাস চালাতে দেবেন না!, প্রধান চরিত্র – একটি কবুতর, obvs – বইয়ের প্রতিটি কৌশল ব্যবহার করে (আক্ষরিকভাবে) পাঠককে বোঝানোর জন্য যে, একজন নিয়মিত চালককে হঠাৎ করে চলে যেতে হলে বাস চালানোর অনুমতি দেওয়া উচিত। উইলমসের বইটি 2012 সালে একটি অনিচ্ছাকৃত বৈজ্ঞানিক পরিণতি লাভ করেছিল, যখন সম্পূর্ণরূপে সম্মানিত জার্নাল হিউম্যান কগনিশন সম্পূর্ণরূপে সম্মানিত গবেষক ব্রেট গিবসন, ম্যাথিউ উইলকিনসন এবং ডেবি কেলি দ্বারা একটি সম্পূর্ণ সম্মানজনক কাগজ প্রকাশ করেছিল। তারা পরীক্ষামূলকভাবে দেখিয়েছিল যে কবুতরগুলি সমাধান খুঁজে পেতে পারে, অনুকূলের কাছাকাছি, একটি বিখ্যাত গাণিতিক কৌতূহলের সহজ ক্ষেত্রে: ভ্রমণ বিক্রয়কর্মী সমস্যা। তাদের শিরোনাম ছিল ‘কবুতরকে বাস চালাতে দিন: পায়রা একটি ঘরে ভবিষ্যতের পথ পরিকল্পনা করতে পারে।’

কেউ যেন দাবি না করে যে বিজ্ঞানীদের মধ্যে হাস্যরসের অভাব রয়েছে। অথবা যে সুন্দর শিরোনাম প্রচার করতে সাহায্য করে না।

ট্রাভেলিং সেলসম্যান সমস্যা শুধু কৌতূহল নয়। এটি একটি বিশাল ব্যবহারিক তাৎপর্যের সমস্যাগুলির একটি অত্যন্ত গুরুত্বপূর্ণ উদাহরণ, যাকে বলা হয় কম্বিনেটরিয়াল অপটিমাইজেশন। গণিতবিদদের আপাত তুচ্ছ বিষয়ে গভীর এবং তাৎপর্যপূর্ণ প্রশ্ন তুলে ধরার অভ্যাস আছে।

উল্লেখযোগ্য তুচ্ছ বিষয় যা এই প্রবন্ধকে অনুপ্রাণিত করে, তার উৎপত্তি একটি সহায়ক বইতে ছিল – আপনি এটি অনুমান করেছিলেন – ভ্রমণকারী বিক্রয়কর্মীদের জন্য। দ্বারে দ্বারে বিক্রেতারা। যেকোনো বুদ্ধিমান ব্যবসায়ী ব্যক্তির মতো, 1832 সালের জার্মান ভ্রমণ বিক্রয়কর্মী (এবং সেই দিনগুলিতে এটি সর্বদা একজন মানুষ ছিল) তার সময়কে দক্ষতার সাথে ব্যবহার করার এবং খরচ কমানোর জন্য একটি প্রিমিয়াম রেখেছিলেন। সৌভাগ্যবশত, একটি ম্যানুয়াল আকারে সাহায্য ছিল: ভ্রমণকারী বিক্রয়কর্মী he তার কেমন হওয়া উচিত এবং তাকে কী করতে হবে, অর্ডার পেতে এবং তার ব্যবসায়ের সুখী সাফল্যের বিষয়ে নিশ্চিত হতে — একজন পুরনো ভ্রমণ বিক্রয়কর্মী।

এই প্রবীণ পেরিপ্যাটেটিক বিক্রেতা নির্দেশ করেছেন যে:

ব্যবসা এখন ভ্রমণকারী বিক্রয়কর্মীকে এখানে নিয়ে আসে, তারপর সেখানে, এবং কোন ভ্রমণ রুট সঠিকভাবে নির্দেশ করা যাবে না যা ঘটছে সমস্ত ক্ষেত্রে উপযুক্ত; কিন্তু কখনও কখনও, একটি যথাযথ পছন্দ এবং সফরের ব্যবস্থা দ্বারা, এত বেশি সময় লাভ করা যেতে পারে, যে আমরা মনে করি না যে আমরা এই বিষয়ে কিছু নিয়ম দেওয়া এড়াতে পারি … একই জায়গায় দুবার স্পর্শ করতে।

ম্যানুয়াল এই সমস্যা সমাধানের জন্য কোন গণিত প্রস্তাব করেনি, কিন্তু এতে পাঁচটি কথিত অনুকূল ভ্রমণের উদাহরণ রয়েছে।

ট্র্যাভেলিং সেলসম্যান প্রবলেম, বা টিএসপি, যেমনটি জানা গিয়েছিল – পরবর্তীতে সেক্সিজম এড়ানোর জন্য ট্রাভেলিং সেলসপারসন প্রবলেমে পরিবর্তিত হয়েছে, যা সুবিধাজনকভাবে একই সংক্ষিপ্তসার – এটি গাণিতিক ক্ষেত্রের একটি প্রতিষ্ঠিত উদাহরণ যা এখন কম্বিনেটরিয়াল অপটিমাইজেশন নামে পরিচিত। যার অর্থ ‘সম্ভাবনার একটি পরিসরের মধ্যে সেরা বিকল্প খোঁজা যা এক সময়ে একটি চেক করার জন্য অনেক বড়।’

কৌতূহলবশত, টিএসপি নামটি 1984 সাল পর্যন্ত এই সমস্যা সম্পর্কিত কোনো প্রকাশনায় স্পষ্টভাবে ব্যবহার করা হয়নি বলে মনে হয়, যদিও গণিতবিদদের মধ্যে অনানুষ্ঠানিক আলোচনায় এটি অনেক আগে প্রচলিত ছিল।

ইন্টারনেটের যুগে, কোম্পানিগুলি কদাচিৎ নমুনা ভর্তি স্যুটকেস সহ শহর থেকে শহরে কাউকে পাঠিয়ে তাদের পণ্য বিক্রি করে। তারা ওয়েবে সবকিছু রাখে। যথারীতি (অযৌক্তিক কার্যকারিতা) সংস্কৃতির এই পরিবর্তনটি টিএসপিকে অপ্রচলিত করেনি। অনলাইন শপিং দ্রুত বৃদ্ধি পাওয়ায়, রুট এবং সময়সূচী নির্ধারণের দক্ষ উপায়গুলির চাহিদা পার্সেল থেকে সুপারমার্কেট অর্ডার থেকে পিজ্জা পর্যন্ত সবকিছুর জন্যই আরও গুরুত্বপূর্ণ হয়ে উঠছে।

গণিতের বহনযোগ্যতাও কার্যকর হয়। টিএসপির আবেদনগুলি শহরের মধ্যে বা শহরের রাস্তায় ভ্রমণের জন্য সীমাবদ্ধ নয়। একসময়, বিশিষ্ট জ্যোতির্বিজ্ঞানীদের নিজস্ব টেলিস্কোপ ছিল, অথবা সেগুলি কয়েকজন সহকর্মীর সাথে ভাগ করে নিয়েছিল। টেলিস্কোপগুলি সহজেই নতুন স্বর্গীয় সংস্থাগুলির দিকে নির্দেশ করতে পারে, তাই এটিকে উন্নত করা সহজ ছিল। আর এমন নয়, যখন জ্যোতির্বিজ্ঞানীদের দ্বারা ব্যবহৃত টেলিস্কোপগুলি বিশাল, ধ্বংসাত্মক ব্যয়বহুল এবং অনলাইনে অ্যাক্সেস করা হয়। টেলিস্কোপকে একটি তাজা বস্তুর দিকে নির্দেশ করতে সময় লাগে, এবং যখন টেলিস্কোপটি সরানো হচ্ছে, এটি পর্যবেক্ষণের জন্য ব্যবহার করা যাবে না। ভুল ক্রমে লক্ষ্যগুলি পরিদর্শন করুন এবং টেলিস্কোপটি অনেক দূর এগিয়ে নিয়ে অনেক সময় নষ্ট হয়, এবং তারপর আবার যেখানে এটি শুরু হয়েছিল তার কাছাকাছি কোথাও ফিরে যান।

ডিএনএ সিকোয়েন্সিং -এ, ডিএনএ ঘাঁটির খণ্ডিত সিকোয়েন্সগুলিকে সঠিকভাবে একত্রিত করতে হবে এবং কম্পিউটারের সময় নষ্ট না করার জন্য এটি যে ক্রমে করা হয়েছে তা অনুকূলিত করতে হবে। অন্যান্য অ্যাপ্লিকেশনগুলি দক্ষতার সাথে বিমানের রাউটিং থেকে শুরু করে কম্পিউটার মাইক্রোচিপস এবং প্রিন্টেড সার্কিট বোর্ডের নকশা এবং উত্পাদন পর্যন্ত। টিএসপিগুলির আনুমানিক সমাধানগুলি হুইল অন হুইলগুলির জন্য কার্যকর রুটগুলি খুঁজে পেতে এবং হাসপাতালে রক্ত ​​সরবরাহকে অনুকূল করতে ব্যবহৃত হয়েছে। টিএসপি -র একটি সংস্করণ এমনকি ‘স্টার ওয়ার্স’ -এও দেখানো হয়েছে, আরো সঠিকভাবে প্রেসিডেন্ট রোনাল্ড রিগানের অনুমানমূলক কৌশলগত প্রতিরক্ষা উদ্যোগ, যেখানে পৃথিবীকে প্রদক্ষিণকারী একটি শক্তিশালী লেজারকে আগত পরমাণু ক্ষেপণাস্ত্রের একটি সিরিজের লক্ষ্যবস্তু করা হতো।

1956 সালে অপারেশন রিসার্চের পথিকৃৎ মেরিল ফ্লাড যুক্তি দিয়েছিলেন যে টিএসপি কঠিন হতে পারে। 1979 সালে, মাইকেল গ্যারি এবং ডেভিড জনসন প্রমাণ করেছিলেন যে তিনি সঠিক ছিলেন: ‘সবচেয়ে খারাপ ক্ষেত্রে’ সমস্যার সমাধান করার জন্য কোন কার্যকর অ্যালগরিদম নেই। কিন্তু সবচেয়ে খারাপ পরিস্থিতি প্রায়ই খুব কল্পনাপ্রসূত হয়, এবং বাস্তব জগতে উদাহরণের মতো নয়। তাই অপারেশন গবেষণায় গণিতবিদরা রিয়েল-ওয়ার্ল্ড সমস্যাগুলির জন্য তারা কতগুলি শহর পরিচালনা করতে পারে তা দেখার জন্য প্রস্তুত হয়েছিল।

Be the first to comment

Leave a Reply

Your email address will not be published.


*