مشکل فروشنده دوره گرد (TSP):
با توجه به مجموعه ای از شهرها و فاصله بین هر جفت شهر، مشکل پیدا کردن کوتاه ترین مسیر ممکن است که دقیقاً یک بار از هر شهر بازدید می کند و به نقطه شروع باز می گردد. به تفاوت بین چرخه هامیلتونی و TSP توجه کنید. مشکل چرخه هامیلتونی این است که بفهمیم آیا توری وجود دارد که دقیقاً یک بار از هر شهر بازدید کند یا خیر. در اینجا می دانیم که تور همیلتونی وجود دارد (چون نمودار کامل است) و در واقع، بسیاری از این تورها وجود دارند، مشکل پیدا کردن یک چرخه همیلتونی حداقل وزن است.
به عنوان مثال، نمودار نشان داده شده در شکل سمت راست را در نظر بگیرید. یک تور TSP در نمودار 1-2-4-3-1 است. هزینه تور 10+25+30+15 می شود که 80 است. مشکل یک مشکل معروف NP-hard است. هیچ راه حلی برای این مسئله وجود ندارد. راه حل های زیر برای مشکل فروشنده دوره گرد ارائه شده است.
راه حل ساده لوحانه:
1) شهر 1 را به عنوان نقطه شروع و پایان در نظر بگیرید.
2) همه (n-1) را تولید کنید! جایگشتی شهرها
3) هزینه هر جایگشت را محاسبه کنید و حداقل جایگشت هزینه را پیگیری کنید.
4) جایگشت را با حداقل هزینه برگردانید.
پیچیدگی زمانی: Θ(n!)
برنامه نویسی پویا:
بگذارید مجموعه رئوس داده شده {1، 2، 3، 4،….n} باشد. اجازه دهید 1 را به عنوان نقطه شروع و پایان خروجی در نظر بگیریم. برای هر راس I دیگر (به غیر از 1)، مسیر حداقل هزینه را با 1 به عنوان نقطه شروع، I به عنوان نقطه پایان، و همه راس ها دقیقاً یک بار ظاهر می شوند، پیدا می کنیم. اجازه دهید هزینه این مسیر هزینه (i) داشته باشد، و هزینه چرخه مربوطه هزینه (i) + dist(i, 1) است که در آن dist(i، 1) فاصله I تا 1 است. در نهایت، ما مقدار را برمی گردانیم. حداقل همه مقادیر [cost(i) + dist(i, 1)]. این تا اینجا ساده به نظر می رسد.
حال سوال این است که چگونه هزینه (i) را بدست آوریم؟ برای محاسبه هزینه (i) با استفاده از برنامه نویسی پویا، باید یک رابطه بازگشتی از نظر مسائل فرعی داشته باشیم.
[pmpro_signup submit_button="ثبت نام و خرید اشتراک یک ماهه" level="1" login="0" redirect="referrer" title="برای دیدن ادامه مطلب عضو vip سایت شوید" hidelabels="true" short="true" ][membership]اجازه دهید یک عبارت C(S, i) را تعریف کنیم که هزینه مسیر حداقل هزینه بازدید از هر رأس در مجموعه S دقیقاً یک بار، از 1 شروع شده و به i ختم می شود . ما با تمام زیرمجموعه های اندازه 2 شروع می کنیم و C(S, i) را برای همه زیر مجموعه هایی که S زیر مجموعه است محاسبه می کنیم، سپس C(S, i) را برای همه زیر مجموعه های S اندازه 3 و غیره محاسبه می کنیم. توجه داشته باشید که 1 باید در هر زیر مجموعه وجود داشته باشد.
If size of S is 2, then S must be {1, i},
C(S, i) = dist(1, i)
Else if size of S is greater than 2.
C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.
در زیر راه‌حل برنامه‌نویسی پویا برای مسئله با استفاده از رویکرد بازگشتی + ذخیره‌سازی از بالا به پایین آمده است:
برای نگهداری زیر مجموعه ها می توانیم از بیت ماسک ها برای نمایش گره های باقی مانده در زیر مجموعه خود استفاده کنیم. از آنجایی که بیت‌ها سریع‌تر عمل می‌کنند و گره‌های کمی در گراف وجود دارد، بهتر است از بیت ماسک‌ها استفاده کنید.
مثلا: -
10100 نشان دهنده گره 2 است و گره 4 در مجموعه باقی مانده است تا پردازش شود
010010 نشان دهنده گره 1 است و 4 در زیر مجموعه باقی مانده اند.
توجه: - بیت 0 را نادیده بگیرید زیرا نمودار ما مبتنی بر 1 است
- C++
- جاوا
- پایتون 3
- سی شارپ
- جاوا اسکریپت
C++
|
#include <iostream>
using namespace std;
// there are four nodes in example graph (graph is 1-based)
const int n = 4;
// give appropriate maximum to avoid overflow
const int MAX = 1000000;
// dist[i][j] represents shortest distance to go from i to j
// this matrix can be calculated for any given graph using
// all-pair shortest path algorithms
int dist[n + 1][n + 1] = {
{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 },
};
// memoization for top down recursion
int memo[n + 1][1 << (n + 1)];
int fun(int i, int mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes already
if (mask == ((1 << i) | 3))
return dist[1][i];
// memoization
if (memo[i][mask] != 0)
return memo[i][mask];
int res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all nodes in
// mask except i and then travel back from node j to
// node i taking the shortest path take the minimum of
// all possible j nodes
for (int j = 1; j <= n; j++)
if ((mask & (1 << j)) && j != i && j != 1)
res = std::min(res, fun(j, mask & (~(1 << i)))
+ dist[j][i]);
return memo[i][mask] = res;
}
// Driver program to test above logic
int main()
{
int ans = MAX;
for (int i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = std::min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);
printf("The cost of most efficient tour = %d", ans);
return 0;
}
// This code is contributed by Serjeel Ranjan
|
Java
|
import java.io.*;
import java.util.*;
public class TSE {
// there are four nodes in example graph (graph is
// 1-based)
static int n = 4;
// give appropriate maximum to avoid overflow
static int MAX = 1000000;
// dist[i][j] represents shortest distance to go from i
// to j this matrix can be calculated for any given
// graph using all-pair shortest path algorithms
static int[][] dist = {
{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 },
};
// memoization for top down recursion
static int[][] memo = new int[n + 1][1 << (n + 1)];
static int fun(int i, int mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes
// already
if (mask == ((1 << i) | 3))
return dist[1][i];
// memoization
if (memo[i][mask] != 0)
return memo[i][mask];
int res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all
// nodes in mask
// except i and then travel back from node j to node
// i taking the shortest path take the minimum of
// all possible j nodes
for (int j = 1; j <= n; j++)
if ((mask & (1 << j)) != 0 && j != i && j != 1)
res = Math.min(res,
fun(j, mask & (~(1 << i)))
+ dist[j][i]);
return memo[i][mask] = res;
}
// Driver program to test above logic
public static void main(String[] args)
{
int ans = MAX;
for (int i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);
System.out.println(
"The cost of most efficient tour = " + ans);
}
}
// This code is contributed by Serjeel Ranjan
|
Python3
|
n = 4 # there are four nodes in example graph (graph is 1-based)
# dist[i][j] represents shortest distance to go from i to j
# this matrix can be calculated for any given graph using
# all-pair shortest path algorithms
dist = [[0, 0, 0, 0, 0], [0, 0, 10, 15, 20], [
0, 10, 0, 25, 25], [0, 15, 25, 0, 30], [0, 20, 25, 30, 0]]
# memoization for top down recursion
memo = [[-1]*(1 << (n+1)) for _ in range(n+1)]
def fun(i, mask):
# base case
# if only ith bit and 1st bit is set in our mask,
# it implies we have visited all other nodes already
if mask == ((1 << i) | 3):
return dist[1][i]
# memoization
if memo[i][mask] != -1:
return memo[i][mask]
res = 10**9 # result of this sub-problem
# we have to travel all nodes j in mask and end the path at ith node
# so for every node j in mask, recursively calculate cost of
# travelling all nodes in mask
# except i and then travel back from node j to node i taking
# the shortest path take the minimum of all possible j nodes
for j in range(1, n+1):
if (mask & (1 << j)) != 0 and j != i and j != 1:
res = min(res, fun(j, mask & (~(1 << i))) + dist[j][i])
memo[i][mask] = res # storing the minimum value
return res
# Driver program to test above logic
ans = 10**9
for i in range(1, n+1):
# try to go from node 1 visiting all nodes in between to i
# then return from i taking the shortest route to 1
ans = min(ans, fun(i, (1 << (n+1))-1) + dist[i][1])
print("The cost of most efficient tour = " + str(ans))
# This code is contributed by Serjeel Ranjan
|
C#
|
using System;
class TSE
{
// there are four nodes in example graph (graph is
// 1-based)
static int n = 4;
// give appropriate maximum to avoid overflow
static int MAX = 1000000;
// dist[i][j] represents shortest distance to go from i
// to j this matrix can be calculated for any given
// graph using all-pair shortest path algorithms
static int[, ] dist = { { 0, 0, 0, 0, 0 },
{ 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 },
{ 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 } };
// memoization for top down recursion
static int[, ] memo = new int[(n + 1), (1 << (n + 1))];
static int fun(int i, int mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes
// already
if (mask == ((1 << i) | 3))
return dist[1, i];
// memoization
if (memo[i, mask] != 0)
return memo[i, mask];
int res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all
// nodes in mask
// except i and then travel back from node j to node
// i taking the shortest path take the minimum of
// all possible j nodes
for (int j = 1; j <= n; j++)
if ((mask & (1 << j)) != 0 && j != i && j != 1)
res = Math.Min(res,
fun(j, mask & (~(1 << i)))
+ dist[j, i]);
return memo[i, mask] = res;
}
// Driver program to test above logic
public static void Main()
{
int ans = MAX;
for (int i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = Math.Min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i, 1]);
Console.WriteLine(
"The cost of most efficient tour = " + ans);
}
}
// This code is contributed by Tapesh(tapeshdua420)
|
Javascript
|
// JavaScript code for the above approach
// there are four nodes in example graph (graph is 1-based)
let n = 4;
// give appropriate maximum to avoid overflow
let MAX = 1000000;
// dist[i][j] represents shortest distance to go from i to j
// this matrix can be calculated for any given graph using
// all-pair shortest path algorithms
let dist = [
[0, 0, 0, 0, 0], [0, 0, 10, 15, 20],
[0, 10, 0, 25, 25], [0, 15, 25, 0, 30],
[0, 20, 25, 30, 0],
];
// memoization for top down recursion
let memo = new Array(n + 1);
for (let i = 0; i < memo.length; i++) {
memo[i] = new Array(1 << (n + 1)).fill(0)
}
function fun(i, mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes already
if (mask == ((1 << i) | 3))
return dist[1][i];
// memoization
if (memo[i][mask] != 0)
return memo[i][mask];
let res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all nodes in
// mask except i and then travel back from node j to
// node i taking the shortest path take the minimum of
// all possible j nodes
for (let j = 1; j <= n; j++)
if ((mask & (1 << j)) && j != i && j != 1)
res = Math.min(res, fun(j, mask & (~(1 << i)))
+ dist[j][i]);
return memo[i][mask] = res;
}
// Driver program to test above logic
let ans = MAX;
for (let i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);
console.log("The cost of most efficient tour " + ans);
// This code is contributed by Potta Lokesh
|
The cost of most efficient tour = 80
پیچیدگی زمانی: O(n 2 * 2 n ) که در آن O(n* 2 n) حداکثر تعداد زیرمسئله/حالت های منحصر به فرد و O(n) برای انتقال (از طریق برای حلقه مانند کد) در هر حالت است.
فضای کمکی: O(n*2 n )، که n تعداد گره ها/شهرها در اینجا است.
برای مجموعه ای از اندازه n، ما n-2 زیرمجموعه را با اندازه n-1 در نظر می گیریم به طوری که همه زیر مجموعه ها n ام را در خود ندارند. با استفاده از رابطه تکرار بالا، می توانیم یک راه حل مبتنی بر برنامه نویسی پویا بنویسیم. حداکثر O(n*2 n ) زیرمسائل وجود دارد و حل هر کدام به زمان خطی نیاز دارد. بنابراین کل زمان اجرا O(n 2 *2 n ) است. پیچیدگی زمانی بسیار کمتر از O(n!) است اما همچنان نمایی است. فضای مورد نیاز نیز نمایی است. بنابراین این رویکرد حتی برای تعداد کمی بالاتر از رئوس نیز غیرممکن است. به زودی در مورد الگوریتم های تقریبی برای مسئله فروشنده دوره گرد بحث خواهیم کرد.
مطلب بعدی: مشکل فروشنده دوره گرد | مجموعه 2
منابع:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
لطفاً در صورت مشاهده موارد نادرست، نظرات خود را بنویسید، یا می خواهید اطلاعات بیشتری در مورد موضوع مورد بحث در بالا به اشتراک بگذارید
در ادامه، متن انگلیسی این مطلب را میتوانید مشاهده نمایید:
Travelling Salesman Problem (TSP):
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.
For example, consider the graph shown in the figure on the right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a famous NP-hard problem. There is no polynomial-time know solution for this problem. The following are different solutions for the traveling salesman problem.
Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate the cost of every permutation and keep track of the minimum cost permutation.
4) Return the permutation with minimum cost.
Time Complexity: Θ(n!)
Dynamic Programming:
Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting and ending point of output. For every other vertex I (other than 1), we find the minimum cost path with 1 as the starting point, I as the ending point, and all vertices appearing exactly once. Let the cost of this path cost (i), and the cost of the corresponding Cycle would cost (i) + dist(i, 1) where dist(i, 1) is the distance from I to 1. Finally, we return the minimum of all [cost(i) + dist(i, 1)] values. This looks simple so far.
Now the question is how to get cost(i)? To calculate the cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems.
Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i. We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset.
If size of S is 2, then S must be {1, i},
C(S, i) = dist(1, i)
Else if size of S is greater than 2.
C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.
Below is the dynamic programming solution for the problem using top down recursive+memoized approach:-
For maintaining the subsets we can use the bitmasks to represent the remaining nodes in our subset. Since bits are faster to operate and there are only few nodes in graph, bitmasks is better to use.
For example: –
10100 represents node 2 and node 4 are left in set to be processed
010010 represents node 1 and 4 are left in subset.
NOTE:- ignore the 0th bit since our graph is 1-based
- C++
- Java
- Python3
- C#
- Javascript
C++
|
#include <iostream>
using namespace std;
// there are four nodes in example graph (graph is 1-based)
const int n = 4;
// give appropriate maximum to avoid overflow
const int MAX = 1000000;
// dist[i][j] represents shortest distance to go from i to j
// this matrix can be calculated for any given graph using
// all-pair shortest path algorithms
int dist[n + 1][n + 1] = {
{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 },
};
// memoization for top down recursion
int memo[n + 1][1 << (n + 1)];
int fun(int i, int mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes already
if (mask == ((1 << i) | 3))
return dist[1][i];
// memoization
if (memo[i][mask] != 0)
return memo[i][mask];
int res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all nodes in
// mask except i and then travel back from node j to
// node i taking the shortest path take the minimum of
// all possible j nodes
for (int j = 1; j <= n; j++)
if ((mask & (1 << j)) && j != i && j != 1)
res = std::min(res, fun(j, mask & (~(1 << i)))
+ dist[j][i]);
return memo[i][mask] = res;
}
// Driver program to test above logic
int main()
{
int ans = MAX;
for (int i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = std::min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);
printf("The cost of most efficient tour = %d", ans);
return 0;
}
// This code is contributed by Serjeel Ranjan
|
Java
|
import java.io.*;
import java.util.*;
public class TSE {
// there are four nodes in example graph (graph is
// 1-based)
static int n = 4;
// give appropriate maximum to avoid overflow
static int MAX = 1000000;
// dist[i][j] represents shortest distance to go from i
// to j this matrix can be calculated for any given
// graph using all-pair shortest path algorithms
static int[][] dist = {
{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 },
};
// memoization for top down recursion
static int[][] memo = new int[n + 1][1 << (n + 1)];
static int fun(int i, int mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes
// already
if (mask == ((1 << i) | 3))
return dist[1][i];
// memoization
if (memo[i][mask] != 0)
return memo[i][mask];
int res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all
// nodes in mask
// except i and then travel back from node j to node
// i taking the shortest path take the minimum of
// all possible j nodes
for (int j = 1; j <= n; j++)
if ((mask & (1 << j)) != 0 && j != i && j != 1)
res = Math.min(res,
fun(j, mask & (~(1 << i)))
+ dist[j][i]);
return memo[i][mask] = res;
}
// Driver program to test above logic
public static void main(String[] args)
{
int ans = MAX;
for (int i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);
System.out.println(
"The cost of most efficient tour = " + ans);
}
}
// This code is contributed by Serjeel Ranjan
|
Python3
|
n = 4 # there are four nodes in example graph (graph is 1-based)
# dist[i][j] represents shortest distance to go from i to j
# this matrix can be calculated for any given graph using
# all-pair shortest path algorithms
dist = [[0, 0, 0, 0, 0], [0, 0, 10, 15, 20], [
0, 10, 0, 25, 25], [0, 15, 25, 0, 30], [0, 20, 25, 30, 0]]
# memoization for top down recursion
memo = [[-1]*(1 << (n+1)) for _ in range(n+1)]
def fun(i, mask):
# base case
# if only ith bit and 1st bit is set in our mask,
# it implies we have visited all other nodes already
if mask == ((1 << i) | 3):
return dist[1][i]
# memoization
if memo[i][mask] != -1:
return memo[i][mask]
res = 10**9 # result of this sub-problem
# we have to travel all nodes j in mask and end the path at ith node
# so for every node j in mask, recursively calculate cost of
# travelling all nodes in mask
# except i and then travel back from node j to node i taking
# the shortest path take the minimum of all possible j nodes
for j in range(1, n+1):
if (mask & (1 << j)) != 0 and j != i and j != 1:
res = min(res, fun(j, mask & (~(1 << i))) + dist[j][i])
memo[i][mask] = res # storing the minimum value
return res
# Driver program to test above logic
ans = 10**9
for i in range(1, n+1):
# try to go from node 1 visiting all nodes in between to i
# then return from i taking the shortest route to 1
ans = min(ans, fun(i, (1 << (n+1))-1) + dist[i][1])
print("The cost of most efficient tour = " + str(ans))
# This code is contributed by Serjeel Ranjan
|
C#
|
using System;
class TSE
{
// there are four nodes in example graph (graph is
// 1-based)
static int n = 4;
// give appropriate maximum to avoid overflow
static int MAX = 1000000;
// dist[i][j] represents shortest distance to go from i
// to j this matrix can be calculated for any given
// graph using all-pair shortest path algorithms
static int[, ] dist = { { 0, 0, 0, 0, 0 },
{ 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 },
{ 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 } };
// memoization for top down recursion
static int[, ] memo = new int[(n + 1), (1 << (n + 1))];
static int fun(int i, int mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes
// already
if (mask == ((1 << i) | 3))
return dist[1, i];
// memoization
if (memo[i, mask] != 0)
return memo[i, mask];
int res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all
// nodes in mask
// except i and then travel back from node j to node
// i taking the shortest path take the minimum of
// all possible j nodes
for (int j = 1; j <= n; j++)
if ((mask & (1 << j)) != 0 && j != i && j != 1)
res = Math.Min(res,
fun(j, mask & (~(1 << i)))
+ dist[j, i]);
return memo[i, mask] = res;
}
// Driver program to test above logic
public static void Main()
{
int ans = MAX;
for (int i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = Math.Min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i, 1]);
Console.WriteLine(
"The cost of most efficient tour = " + ans);
}
}
// This code is contributed by Tapesh(tapeshdua420)
|