ভ্রমণ বিক্রয়কর্মী সমস্যা

একজন বিক্রয়-ব্যক্তি একটি শহরে আছেন, তাকে তালিকাভুক্ত অন্যান্য শহরগুলি দেখতে হবে, এক শহর থেকে অন্য শহরে ভ্রমণের খরচও দেওয়া হয়৷ সেই রুটটি খুঁজুন যেখানে খরচ ন্যূনতম সব শহরে একবার ঘুরে আসুন এবং তার শুরুর শহরে ফিরে যান৷

এই ক্ষেত্রে গ্রাফটি অবশ্যই সম্পূর্ণ হতে হবে, যাতে বিক্রয়-ব্যক্তি যেকোনো শহর থেকে সরাসরি যেকোনো শহরে যেতে পারে।

এখানে আমাদের ন্যূনতম ওজনযুক্ত হ্যামিলটোনিয়ান সাইকেল খুঁজে বের করতে হবে।

ইনপুট এবং আউটপুট

ইনপুট:ম্যাট্রিক্সের খরচ ম্যাট্রিক্স। 0 20 42 25 3020 0 30 34 1542 30 0 10 1025 34 10 0 2530 15 10 25 0আউটপুট:ট্রাভেলিং সেলসম্যানের দূরত্ব 
অ্যালগরিদম
 
ভ্রমণ বিক্রয়কর্মী (মুখোশ, অবস্থান)
 

 একটি টেবিল dp আছে, এবং VISIT_ALL মান চিহ্নিত করার জন্য সমস্ত নোড পরিদর্শন করা হয়েছে
 

 ইনপুট -  কিছু শহর, অবস্থান মাস্ক করার জন্য মুখোশের মান।
 

 আউটপুট বিয়োগ; সমস্ত শহর পরিদর্শন করার জন্য সংক্ষিপ্ততম রুট খুঁজুন।
 
শুরু করুন যদি মাস্ক =VISIT_ALL, তারপর //যখন সমস্ত শহর পরিদর্শন করা হয় ফেরত খরচ[pos, 0] if dp[mask, pos] ≠ -1, তারপর dp[mask, pos] চূড়ান্ত খরচ ফেরত দিন :=∞ সব শহরের জন্য i, tempMask করুন :=(1 বার বাম দিকে স্থানান্তর করুন) যদি মাস্ক এবং tempMask =0 হয়, তাহলে tempCpst :=খরচ[pos, i] + travellingSalesman(mask বা tempMask, i) finalCost :=ন্যূনতম চূড়ান্ত খরচ এবং tempCost সম্পন্ন dp [mask, pos] =finalCost return finalCostEnd
 
উদাহরণ
 
#include#define CITY 5#define INF 9999using namespace std;int cost[CITY][CITY] ={0, 20, 42, 25, 30}, {20, 0, 30, 34, 15}, {42, 30, 0, 10, 10}, {25, 34, 10, 0, 25}, {30, 15, 10, 25, 0}}; int VISIT_ALL =(1 < 
আউটপুট
 
ভ্রমণ বিক্রয়কর্মীর দূরত্ব:80