Министерство образования и науки РФ
ГОУВПО «Комсомольский-на-Амуре государственный технический университет»
Кафедра математического обеспечения и применения ЭВМ
Лабораторная работа №2
По дисциплине «СиАОД»
Вариант №4
Исполнитель:
Зимин А.В.
Студент гр. 4ВС-1
Руководитель:
Хусаинов А.А.
Комсомольск-на-Амуре
2007
Постановка задачи
Решить задачу с помощью алгоритма перебора с возвратом.
Задание по варианту: Решить задачу коммивояжера методом перебора с возвратом. Цены билетов заданы с помощью симметричной n´n матрицы.
Алгоритм
Задача коммивояжера заключается в следующем: имеется nгородов и известны цены билетов. Коммивояжер должен посетить все nгородов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарная цена билетов будет минимальной. Схема маршрутов задана графом (см. рис. 1). Данная задача сводится к поиску гамильтонова цикла в графе с минимальной суммой стоимостей путей между узлами.
Для решения задачи необходимо перебрать все гамильтоновы циклы и найти среди них цикл наименьшей стоимости.
Путь будем представлять в виде последовательности вершин (x1,x2,…,xk). Такой путь будет простым если и только если xi ¹ xj для всех i¹j, i,jÎ{1,2,…,k}.
Определим предикаты.
Pk(x1,x2,…xk)=1 Û xi¹xj, при 1 £ i < j £ k, и {xi,xi+1} – ребра при 1 £ i < k;
Q(x1,x2,…xk)=1 Û k=n и {xn,x1} – ребро.
Для того, чтобы последовательности вершин (x1,x2,…xk) удовлетворяли условию xi¹xj, будем раскрашивать вершины этих последовательностей и учитывать раскраску при выборе очередей вершины. Гамильтонов цикл, с началом x1=n0, представим как последовательность (x1,x2,…,xn,xn+1), где xn+1=x1=n0.
Пусть Ak – множество вершин, смежных с xk, cn - раскраска вершины n. Согласно общей схеме алгоритма перебора с возвратом, получаем следующий алгоритм для перебора гамильтоновых циклов:
void Gamilton(int k)
{
for(yÎAk)
{
if((k==n+1)&&(y==v)) вывод x1,…,xk,x1)
else if(c[y]==0)
{
xk=y; c[y]=1;
Gamilton(k+1);
c[y]=0;
}
}
}
void main()
{
for(vÎV) c[v]=0; // V – множество всех вершин графа
x1=v0; c[v0]=1; Gamilton(2);
}
Рис. 1. Граф, задающий схему маршрутов
Текст программы
//--------------------------------------------------------------------------#include <vcl.h>
#pragma hdrstop
#define n 4
#include "Unit1.h"
//--------------------------------------------------------------------------#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//--------------------------------------------------------------------------__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//--------------------------------------------------------------------------int c[n] ; // номер хода, на котором посещается вершина
int path[n]; // номера посещаемых вершин
int rez_path[n];// путь с наим. стоимостью
int v0=0; // начальная вершина
int sum[n];
int min=3200; //мин. стоимость
int a[n][n] =
{
0,1,2,8,
1,0,9,4,
2,9,0,20,
8,4,20,0
};
void prnt(void)
{
int i, temp=0;
for ( i = 0 ; i<n ; i++)
{
temp+=sum[i];
}
temp+=a[path[n-1]][0];
if(temp<min)
{
min=temp;
for (i=0; i<n; i++)
{
rez_path[i]=path[i];
}
}
}
//подпрограмма нахождения гамильтонова цикла
int gamilton (int k)
{
int v,q1=0;
for(v=0; v<n; v++)
{
if(a[v][path[k-1]]||a[path[k-1]][v])
{
if (k==n && v==v0 ) prnt();
else if (c[v]==-1)
{
c[v] = k;
path[k]=v;
sum[k]=a[v][path[k-1]];
gamilton (k+1);
c[v]=-1;
} else continue;
}
} return q1;
}
void mainfunc()
{
int i;
String text = "";
for(i=0;i<n;i++) c[i]=-1;
path[0]=v0 ;
c[v0]=v0;
if(gamilton (1)) prnt();
for(i=0; i<n; i++)
{
text = text + IntToStr(rez_path[i]) + " ";
Form1->Edit1->Text = text;
}
text = text + "0";
Form1->Edit1->Text = text;
Form1->Edit2->Text = IntToStr(min);
}
void __fastcall TForm1::Button1Click(TObject *Sender)
{
mainfunc();
}
//---------------------------------------------------------------------------
Результат работы программы
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.