একজন সেলসম্যান একটি শহরে আছে, তাকে লিস্ট করা সমস্ত অন্যান্য শহর ঘুরতে হবে, একটি শহর থেকে অন্য শহর যাওয়ার খরচও দেওয়া আছে। এমন একটি রুট খুঁজে বের করতে হবে যেখানে খরচ ন্যূনতম হয় সব শহর একবার করে ঘুরে আবার তার শুরুর শহরে ফিরে আসার জন্য।
গ্রাফটি অবশ্যই কমপ্লিট হতে হবে এই কেসে, যাতে সেলসম্যান যেকোনো শহর থেকে যেকোনো শহরে সরাসরি যেতে পারে।
এখানে আমাদের ন্যূনতম ওজনযুক্ত হ্যামিল্টোনিয়ান সাইকেল বের করতে হবে।
ইনপুট এবং আউটপুট
ইনপুট: ম্যাট্রিক্সের খরচ ম্যাট্রিক্স। 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 আউটপুট: ট্রাভেলিং সেলসম্যানের দূরত্ব: ৮০
অ্যালগরিদম
travellingSalesman (mask, pos)
একটি টেবিল dp, এবং VISIT_ALL মান আছে সব নোড ভিজিট করা হয়েছে চিহ্নিত করতে
ইনপুট - কিছু শহর মাস্ক করার জন্য mask মান, পজিশন।
আউটপুট মাইনাস; সব শহর ঘুরে যাওয়ার সবচেয়ে ছোট রুট খুঁজুন।
শুরু
যদি mask = VISIT_ALL, তবে //যখন সব শহর ভিজিট হয়েছে
cost[pos, 0] ফেরত দিন
যদি dp[mask, pos] ≠ -1, তবে
dp[mask, pos] ফেরত দিন
finalCost := ∞
সব শহর i জন্য, করুন
tempMask := (1 কে i বার বামে শিফট)
যদি mask AND tempMask = 0, তবে
tempCpst := cost[pos, i] +
travellingSalesman(mask OR tempMask, i)
finalCost := finalCost এবং tempCost-এর ন্যূনতম
শেষ
dp[mask, pos] = finalCost
finalCost ফেরত দিন
শেষউদাহরণ
#include<iostream> #define CITY 5 #define INF 9999 using 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 << CITY) - 1; int dp[16][4]; //(2^n, n) আকারের অ্যারে তৈরি int travellingSalesman(int mask, int pos) { if(mask == VISIT_ALL) //যখন সব শহর ভিজিটেড হিসেবে চিহ্নিত return cost[pos][0]; //বর্তমান শহর থেকে মূল শহর if(dp[mask][pos] != -1) //যখন এটি বিবেচনা করা হয়েছে return dp[mask][pos]; int finalCost = INF; for(int i = 0; i<CITY; i++) { if((mask & (1 << i)) == 0) { //যদি রেজাল্টের i-তম বিট ০, তবে সেটি আনভিজিটেড int tempCost = cost[pos][i] + travellingSalesman(mask | (1 << i), i); //যেহেতু i-তম শহর ভিজিটেড finalCost = min(finalCost, tempCost); } } return dp[mask][pos] = finalCost; } int main() { int row = (1 << CITY), col = CITY; for(int i = 0; i<row; i++) for(int j = 0; j<col; j++) dp[i][j] = -1; //dp অ্যারে -1 দিয়ে ইনিশিয়ালাইজ করুন cout << "Distance of Travelling Salesman: "; cout <<travellingSalesman(1, 0); //প্রাথমিকভাবে mask হল 0001, কারণ ০তম শহর ইতিমধ্যে ভিজিটেড }আউটপুট
Distance of Travelling Salesman: 80
