Mixed Chinese postman problem
মিক্সড চাইনিজ পোস্টম্যান প্রবলেম (এম. সি. পি. পি বা এম. সি. পি) হল একটি গ্রাফের সংক্ষিপ্ততম ট্র্যাভার্সাল অনুসন্ধান যার শীর্ষবিন্দু V, ধনাত্মক যুক্তিসঙ্গত ওজন সহ অনির্দিষ্ট প্রান্ত E-এর একটি সেট এবং ধনাত্মক যুক্তিসঙ্গত ওজন সহ নির্দেশিত চাপ A-এর একটি সেট যা প্রতিটি প্রান্ত বা চাপকে কমপক্ষে একবার ন্যূনতম ব্যয়ে আচ্ছাদন করে। পাপদিমিত্রিউ এই সমস্যাটিকে এন. পি-সম্পূর্ণ বলে প্রমাণ করেছেন। মিশ্র চীনা পোস্টম্যান সমস্যাটি প্রায়শই বরফ চাষের মতো চাপের পথের সমস্যাগুলির মধ্যে উদ্ভূত হয়, যেখানে কিছু রাস্তা উভয় দিকে অতিক্রম করার জন্য খুব সংকীর্ণ এবং অন্যান্য রাস্তাগুলি দ্বিমুখী এবং উভয় দিকেই চাষ করা যেতে পারে। গ্রাফটি দৃঢ়ভাবে সংযুক্ত কিনা তা যাচাই করে একটি মিশ্র গ্রাফের কোনও আকারের পোস্টম্যান ট্যুর আছে কিনা তা পরীক্ষা করা সহজ। সমস্যাটি হল এনপি কঠিন যদি আমরা পোস্টম্যান সফরকে প্রতিটি চাপ ঠিক একবার অতিক্রম করার জন্য সীমাবদ্ধ করি বা যদি আমরা এটিকে প্রতিটি প্রান্ত ঠিক একবার অতিক্রম করার জন্য সীমাবদ্ধ করি, যেমনটি জারাগোজা মার্টিনেজ প্রমাণ করেছেন। গাণিতিক সংজ্ঞা গাণিতিক সংজ্ঞাটি হলঃ ইনপুটঃ প্রতিটি প্রান্তের জন্য খরচ এবং সর্বোচ্চ খরচ সহ একটি দৃঢ়ভাবে সংযুক্ত, মিশ্র গ্রাফ। প্রশ্নঃ এমন কোনও (নির্দেশিত) সফর আছে কি যা প্রতিটি প্রান্ত এবং প্রতিটি চাপ অন্তত একবার অতিক্রম করে এবং যার জন্য সর্বাধিক খরচ হয়? গণনামূলক জটিলতা মিশ্র চীনা পোস্টম্যান সমস্যা সমাধানের প্রধান অসুবিধা হল (অনির্দিষ্ট) প্রান্তগুলির জন্য অভিমুখ নির্বাচন করা যখন আমাদের সফরের জন্য একটি শক্ত বাজেট দেওয়া হয় এবং প্রতিটি প্রান্ত কেবল একবার অতিক্রম করার সামর্থ্য থাকে। তারপরে আমাদের প্রান্তগুলি অভিমুখী করতে হবে এবং আরও কিছু চাপ যোগ করতে হবে যাতে একটি নির্দেশিত ইউলারিয়ান গ্রাফ পাওয়া যায়, অর্থাৎ প্রতিটি শীর্ষকে ভারসাম্যপূর্ণ করা যায়। যদি একটি শীর্ষে একাধিক প্রান্ত থাকে, তবে প্রতিটি প্রান্তের সঠিক অভিমুখ নির্ধারণ করা সহজ কাজ নয়। গণিতবিদ পাপাডিমিত্রিউ আরও বিধিনিষেধের সাথে এই সমস্যাটি বিশ্লেষণ করেছেন; "মিক্সড চাইনিজ পোস্টম্যান এনপি-সম্পূর্ণ, এমনকি ইনপুট গ্রাফটি সমতল হলেও, প্রতিটি শীর্ষে সর্বাধিক তিনটি ডিগ্রি থাকে এবং প্রতিটি প্রান্ত এবং বৃত্তের দাম এক।" একটি মিশ্র গ্রাফ ইউলারিয়ান কিনা তা পরীক্ষা করার প্রক্রিয়াটি মিশ্র চীনা পোস্টম্যান সমস্যা সমাধানের জন্য একটি অ্যালগরিদম তৈরি করার জন্য গুরুত্বপূর্ণ। একটি মিশ্র গ্রাফ জি-এর ডিগ্রি অবশ্যই ইউলারিয়ান চক্রের জন্য সমান হতে হবে, তবে এটি যথেষ্ট নয়। আনুমানিক মিশ্র চীনা পোস্টম্যান এনপি-হার্ড হওয়ার ফলে বহুপদী সময় অ্যালগরিদমগুলির অনুসন্ধান করা হয়েছে যা যুক্তিসঙ্গত সীমার সর্বোত্তম সমাধানের দিকে এগিয়ে যায়। ফ্রেডেরিকসন 3/2 গুণক সহ একটি পদ্ধতি তৈরি করেছিলেন যা প্ল্যানার গ্রাফগুলিতে প্রয়োগ করা যেতে পারে এবং রাঘবাচারী এবং বীরাসামি এমন একটি পদ্ধতি খুঁজে পেয়েছিলেন যা প্ল্যানার হতে হবে না। যাইহোক, বহুপদী সময় শিরশ্ছেদ করার খরচ খুঁজে পায় না, রাস্তায় পৌঁছানোর জন্য একটি বরফের লাঙল যে সময় নেয় তা লাঙল বা রাস্তার ঝাড়ুদার রাস্তায় পৌঁছানোর জন্য এটি ঝাড়ু দেবে। আনুষ্ঠানিক সংজ্ঞা একটি ভার্টেক্স সেট এবং এজ সেটের সাথে দৃঢ়ভাবে সংযুক্ত মিশ্র গ্রাফ, একটি আর্ক সেট এবং প্রত্যেকটির জন্য একটি অ-নেতিবাচক খরচ দেওয়া হলে, এম. সি. পি. পি প্রতিটি লিঙ্কের মধ্য দিয়ে অন্তত একবার ন্যূনতম খরচের সফর খুঁজে বের করে। প্রদত্ত,, ঠিক একটি শেষ বিন্দু সহ প্রান্তের সেটকে বোঝায়, এবং। একটি শীর্ষে, (ইন্ডেগ্রি) চাপ প্রবেশের সংখ্যা নির্দেশ করে, (আউট ডিগ্রি) হল ছেড়ে যাওয়া চাপের সংখ্যা, এবং (ডিগ্রি) হল সংযোগের সংখ্যা। এটা মনে রাখবেন। একটি মিশ্র গ্রাফকে বলা হয়, এমনকি যদি এর সমস্ত শীর্ষে জোড় ডিগ্রি থাকে, তবে প্রতিটি শীর্ষের জন্য এটিকে প্রতিসম বলা হয়, এবং এটিকে ভারসাম্যপূর্ণ বলা হয় যদি, শীর্ষগুলির কোনও উপসেট দেওয়া হয়, থেকে নির্দেশিত চাপের সংখ্যা এবং থেকে নির্দেশিত চাপের সংখ্যার মধ্যে পার্থক্য, যোগ হওয়া অনির্দিষ্ট প্রান্তের সংখ্যার চেয়ে বেশি না হয় এবং,। এটি একটি সুপরিচিত সত্য যে একটি মিশ্র গ্রাফ ইউলারিয়ান হয় যদি এবং শুধুমাত্র যদি জোড় এবং ভারসাম্যপূর্ণ হয়। লক্ষ্য করুন যে যদি জোড় এবং প্রতিসম হয়, তবে জি-ও ভারসাম্যপূর্ণ (এবং ইউলেরিয়ান)। উপরন্তু, যদি জোড় হয়, তবে বহুপদী সময়ে ঠিক সমাধান করা যেতে পারে। এমনকি এম. সি. পি. পি অ্যালগরিদম একটি জোড় এবং দৃঢ়ভাবে সংযুক্ত মিশ্র গ্রাফ দেওয়া হলে, একই খরচ সহ প্রান্তগুলিতে এলোমেলোভাবে একটি দিক নির্ধারণ করে প্রাপ্ত চাপের সেট হতে দিন। নির্দেশিত গ্রাফের প্রতিটি শীর্ষের জন্য গণনা করুন। সরবরাহ চাহিদার সাথে একটি শীর্ষকে একটি উৎস (সিঙ্ক) হিসাবে বিবেচনা করা হবে। লক্ষ্য করুন যে একটি জোড় গ্রাফের মতো, সমস্ত সরবরাহ এবং চাহিদা জোড় সংখ্যা (শূন্যকে জোড় সংখ্যা হিসাবে বিবেচনা করা হয়)। আসুন সেই সংশ্লিষ্ট প্রান্তগুলির দামের সাথে এবং তার সাথে বিপরীত দিকে চাপের সেট হতে দিন এবং শূন্য ব্যয়ে সমান্তরাল চাপের সেট হতে দিন। সমস্ত শীর্ষগুলির চাহিদা মেটানোর জন্য, গ্রাফের একটি ন্যূনতম ব্যয় প্রবাহের সমস্যা সমাধান করুন, যেখানে প্রতিটি বৃত্তের অসীম ক্ষমতা রয়েছে এবং প্রতিটি বৃত্তের ক্ষমতা 2। সর্বোত্তম প্রবাহ হতে দিন। প্রতিটি চাপের জন্যঃ যদি, তাহলে সংশ্লিষ্ট প্রান্তটি থেকে দিকে অভিমুখ করুন (ধাপ 1-এ সংশ্লিষ্ট প্রান্তে নির্ধারিত দিক, থেকে, "ভুল" ছিল); যদি, তাহলে জি-তে সংশ্লিষ্ট প্রান্তটি থেকে দিকে অভিমুখ করুন (এই ক্ষেত্রে, ধাপ 1-এর অভিমুখটি "সঠিক" ছিল)। লক্ষ্য করুন কেসটি অসম্ভব, কারণ বৃত্তের মধ্য দিয়ে সমস্ত প্রবাহের মানগুলি জোড় সংখ্যা। প্রতিটি চাপের অনুলিপি যোগ করে বৃদ্ধি করুন। ফলস্বরূপ গ্রাফটি জোড় এবং প্রতিসম। হিউরিস্টিক অ্যালগরিদম যখন মিশ্র গ্রাফটি জোড় হয় না এবং সমস্ত নোডের সমান ডিগ্রি থাকে না, তখন গ্রাফটি জোড় গ্রাফে রূপান্তরিত হতে পারে। একটি মিশ্র গ্রাফ হতে দিন যা দৃঢ়ভাবে সংযুক্ত। চাপের দিকগুলি উপেক্ষা করে বিজোড় ডিগ্রি নোডগুলি খুঁজে বের করুন এবং একটি ন্যূনতম ব্যয়ের মিল পান। একটি সমান গ্রাফ তৈরি করতে ন্যূনতম ব্যয়ের মিল থেকে প্রান্তগুলি দিয়ে গ্রাফটি বৃদ্ধি করুন। গ্রাফটি জোড় কিন্তু প্রতিসম নয় এবং একটি ইউলারিয়ান মিশ্র গ্রাফ জোড় এবং প্রতিসম। একটি ন্যূনতম ব্যয় প্রবাহের সমস্যা সমাধান করুন যাতে একটি প্রতিসম গ্রাফ পাওয়া যায় যা সমান নাও হতে পারে। চূড়ান্ত ধাপে রয়েছে প্রতিসম গ্রাফকে সমান করা। বিজোড় ডিগ্রি নোডগুলিকে লেবেল করুন। এমন চক্র খুঁজুন যা চাপ সেটের লাইন এবং প্রান্ত সেটের লাইনের মধ্যে পরিবর্তিত হয় যা পয়েন্টগুলিতে শুরু এবং শেষ হয়। খিলানগুলিকে অনির্দিষ্ট প্রান্ত হিসাবে বিবেচনা করা উচিত, নির্দেশিত খিলান হিসাবে নয়। জেনেটিক অ্যালগরিদম হুয়া জিয়াং এট দ্বারা প্রকাশিত একটি গবেষণাপত্র। আল একটি জনসংখ্যার উপর কাজ করে মিশ্র চীনা পোস্টম্যান সমস্যা সমাধানের জন্য একটি জেনেটিক অ্যালগরিদম স্থাপন করেছিলেন। এমসিপিপির জন্য অন্যান্য আনুমানিক অ্যালগরিদমের তুলনায় অ্যালগরিদমটি ভাল কাজ করেছে। আরও দেখুন ক্যাপাসিটেড আর্ক রাউটিং সমস্যা রেফারেন্স গ্রাফ তত্ত্বে গণনামূলক সমস্যা