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


===== تعریف =====

فرض کنید $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!)$ است.


===== پیاده‌سازی اولیه =====

<code c 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;
}


</code>

===== پیاده‌سازی سریع‌تر =====

<code c ‌‌B.c>
#include <iostream>
int main() {
}
</code>


===== کابردها =====


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

<پاسخ>

پاسخ مسئله اینجا می‌آید

</پاسخ>


===== مسائل نمونه =====


  * [[سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۲۴:عملی_مقدماتی_اول:سوال_۱|سوال عملی دوره‌ی تابستان ۲۴]] [سطح: ساده]
===== مراجع =====

  * [[http://e-maxx.ru/algo/euler_function|تابع اویلر - سایت ماکزیمال]]
  * [[http://en.wikipedia.org/wiki/Euler%27s_totient_function|تابع اویلر - ویکی‌پدیا]]