итак, есть конкретное решение на MVC , здача коммивояжера
| Код |
/*задача коммивояжёра
Коммивояжёр (бродячий торговец) должен выйти из первого города, посетить по разу
в неизвестном порядке города и вернуться в первый город.
Расстояние между городами известны. В каком порядке следует обходить города,
чтобы замкнутый путь (тур) коммивояжёра был кротчайшим.
Иными словами, коммивояжёр должен обойти все города по кротчайшему пути и
при этом посещая каждый город только один раз.
Расстояния берутся из файла. В файле матрица с произвольными правильными
значениями (т.е. значение не отрицательны и такие, что проход коммивояжёром
всех городов возможен).
Программа ищет путь с помощью метода ветвей и границ.
*/
#include <fstream.h>
const int maxn=100; //максимум городов
int n,i,s,min,count,found; //n-количество городов
//i-счетчик
//s-текущая сумма
//min-минимальная сумма
//count-счетчик пройденных городов
//found-найден ли город
int a[maxn][maxn]; //матрица рассояний
int m[maxn],minm[maxn]; //m-текущий путь
//minm-минимальный путь
void _input() //ввод данных
{
ifstream fin("input.txt"); //открыли файл
fin >> n; //считали n
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
fin >> a[i][j]; //считали матрицу расстояний
}
void _output() //вывод данных
{
ofstream fout("output.txt"); //открыли файл
if (found) //если найден маршрут...
{
fout << "Lenght of min path = " << min << endl;
fout << "Path : ";
int c=1; //номер в порядке обхода городов
for (int i=1;i<=n;i++) //пробегаем по всем городам
{
int j=1;
while ((j<=n)&& //ищем следующий город в порядке обхода
(minm[j]!=c)) j++;
fout << j <<"->";
c++;
}
fout << minm[1] << endl; //обход завершается первым городом
}
else fout << "Path not found!";
}
void search(int x) //поиск следующего города в порядке
//обхода после города с номером Х
{
if ((count==n)&& //если просмотрели все города
(a[x][1]!=0)&& //из последнего города есть путь в первый город
(s+a[x][1]<min)) //новая сумма расстояний меньше минимальной суммы
{
found=1; //маршрут найден
min=s+a[x][1]; //изменяем: новая минимальная сумма расстояний
for (int i=1;i<=n;i++)minm[i]=m[i];//изменяем: новый минимальный путь
}
else
{
for (int i=1;i<=n;i++) //из текущего города просматриваем все города
if ((i!=x)&& //новый город не совпадает с текущим
(a[x][i]!=0)&& //есть прямой путь из x в i
(m[i]==0)&& //новый город еще не простотрен
(s+a[x][i]<min)) //текущая сумма не превышает минимальной
{
s+=a[x][i]; //наращиваем сумму
count++; //количество просмотренных городав
m[i]=count; //отмечаем у нового города новый номер в порядке обхода
search(i); //поиск нового города начиная с города i
m[i]=0; //возвращаем все назад
count--; //-"-
s-=a[x][i]; //-"-
}
}
}
void run()
{ //инициализация
s=0;
found=0;
min=32767;
for (int i=1;i<=n;i++) m[i]=0;
count=1;
m[1]=count; //считаем что поиск начинается с первого города
search(1); //считаем что поиск начинается с первого города
}
void main()
{
_input(); //ввод данных
run(); //запуск основного алгоритма
_output(); //вывод результатов
}
|
пример файла input.txt
| Код |
4
0 6 1 5
6 0 3 1
1 3 0 2
5 1 2 0
|
|