فروشنده دوره‌گرد

فرض کنید $n$ شهر و طول مسیر های بین آن‌ها به شما داده شده است، کمترین مسافتی که باید طی شود که با شروع از یک شهر همه‌ی شهر ها دقیقا یک بار دیده شوند و دو باره به همان شهر اولیه برگردیم چه قدر است؟

این $n$ شهر را با یک گراف $n$ راسی مدل می‌کنیم.

از یک لیست خالی شروع می کنیم و در هر مرحله به ته لیست یک راس از همسایه های راس انتهایی لیست اضافه می‌کنیم و مسیر را به صورت بازگشتی کامل می‌کنیم. در انتها، مسیر را می‌بندیم و در صورتی که (طول مسیر)$B > l$ جواب کمینه را به روز رسانی می‌کنیم و قرار می دهیم $B=l$.در هر مرحله اگر مسیر توانایی کامل شدن به دوری با طول کمتر از $B$ نداشته باشد،به عبارت دیگر کران پایین آن ($g(p)$) از $B$ بزرگ تر باشد آن را کنار گذاشته و به مرحله‌ی قبل باز می‌گردیم.

می توان $g(p)$ را برابر با جمع طول $p$(مسیر) یعنی $l$ و طول کوتاه‌ترین مسیر بین دو سر آن قرار داد. یا این که برابر با $l+(n-s)*x$ که $s$ اندازه‌ی $p$ و x طول کم وزن ترین یال در بین راس های باقی مانده است در نظر گرفت، زیرا برای برگشت حتما باید $n-s$ راس پیموده شود و هر پیمایش حداقل به اندازه‌ی مسافت $x$ هزینه خواهد داشت.این کران را می‌توان با متغیر در نظر گرفتن x بهبود داد یعنی $g(p)=l+\Sigma{x_i}$ که $x_i$ وزن کم‌وزن ترین یال ورودیی راس $i$ در بین راس های پیمایش نشده است.

زمان اجرای این الگوریتم $O(n!)$ است.

A.c

#include <iostream>#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <fstream>
#include <sstream>
 
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf  = 1000*1000*1000+100;
const int maxn = 200;
const double eps = 1e-7;
int n;
int rem;
double dist[maxn][maxn];
double B;
double l;
int mark[maxn];
vector<int> path;
vector<int> best;
 
double g(int v)
{
	double ret=0;
	for(int i=0; i < n ; ++i)
	{
		if(!mark[i])
		{
			double mi = inf;
			for(int j=0 ; j < n ; ++j)
				if( (!mark[j]||j==v) && j!=i)
					mi=min(mi,dist[j][i]);
			ret+=mi;
		}
	}
 
	return ret;
}
 
void BnB(int v)
{
	if(v==0 ){
		if(mark[v]){
			if(!rem){
				if(l < B){
					best=path;
					B=l;
					cerr << B << endl;
				}
			}
			return;
		}
	}
 
 
	if( g(v) > B-eps ){
		return;
	}	
 
	for(int i = 0 ; i < n ; ++i)
		if(!mark[i])
		{
			rem--;
			mark[i]=true;
			path.push_back(i);
			l+=dist[v][i];
 
			BnB(i);
 
			l-=dist[v][i];
			path.pop_back();
			mark[i]=false;
			rem++;
		}
 
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
 
	for(int i = 0 ; i < n ; ++i){
		for(int j = 0 ; j < n ; ++j){
			cin >> dist[i][j];
		}
	}
 
	rem = n;
	B=inf;
 
	BnB(0);
 
	cout << B << " " << (int)(best).size() << endl;
	for(int i = 0 ; i < (int)best.size() ; ++i)
		cout << best[i] << " ";
	cout << endl;
 
	return 0;
}

‌‌B.c

#include <iostream>
int main() {
}

مثال: صورت مسئله اینجا می‌آید.

• سوال عملی دوره‌ی تابستان ۲۴ [سطح: ساده]

• تابع اویلر - سایت ماکزیمال
• تابع اویلر - ویکی‌پدیا