Решение задачи методом ветвей и границ

 

Код функции:

void pusk()

{                            

summ=0;                    //обнуляем сумму растояний

ngor=0;                      //маршрут не найден

min=45654;               //сумма не минимальна

for (int i=1;i<=k;i++) M[i]=0;  //текущий путь не найден

gor=1;                        //первый город пройден

M[1]=gor;                  //считаем что поиск начинается с первого города

poisk(1);                    //считаем что поиск начинается с первого города

}

 

2.4 Описание интерфейса

 

Интерфейс программы состоит  из основного диалогового окна в  котором есть:

1. Поле для расстановки вершин(Image1).
2. Кнопка “дуга” (Speed Button1) и поле (Edit1) для ввода длины между вершинами графа.
3. Список (ListBox1) для отображения названий и выбора вершин графа.
4. Кнопка “таблица” (Button1) и таблица (StringGrid)  для отображения таблицы смежности.
5. Поле (Memo1) для вывода результатов.

 

При очередном клике мыши по полю Image1(верхняя часть окна), на месте клика будут последовательно отображаться названия вершин.

 Для обозначений расстояний  между вершинами необходимо выбрать  2 вершины, указать вес ребра  между ними и нажать кнопку  “дуга”. Данные автоматически сохранятся в матрице смежности.

Для отображения матрицы  смежности необходимо нажать на кнопку “таблица”.

Нажатие кнопки “Посчитать” запускает основной алгоритм программы и выводит результат в поле “Memo1”, но для перед этим необходимо убедиться, что граф замкнутый.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Экспериментальная часть  

                                                                             

3.1  Тестовые задания 

                                                  

Вычислить кратчайший путь для 5 городов.

Входные данные

0	3	4	0	2
3	0	5	5	0
4	5	0	6	0
0	5	6	0	3
2	0	0	3	0

 

Выходные  данные

Длина=19

Путь – A->B->C->D->E->A

 

Результаты работы программы

Вычислить кратчайший путь для 7 городов.

Входные данные

0	10	8	7	0	0	3
10	0	8	7	13	0	0
8	8	0	0	3	0	5
7	7	0	0	5	2	0
0	13	3	5	0	2	0
0	0	0	2	2	0	0
3	0	5	0	0	0	0

 

Выходные  данные

Длина=32

Путь – A->B->D->F->E->C->G->A

 

Результат работы программы

4. Список использованной литературы

 

 

1. О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
2. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. — М. : Издательский дом "Вильяме", 2000. — 384 с.

3. http://ru.wikipedia.org/wiki/Задача_коммивояжёра «Задача коммивояжера»
4. 3. В. М. Бондарев «Основы программирования» 1998 г., 368 с. изд. дом «Феникс»

 

 

 

 

 

 

 

 

 

 

        

 

 

 

 

 

 

 

 

 

5. Приложение

Листинг программы:

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "stdio.h"

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

int i=0, k=0; //счетчик количества  вершин графа

char Al[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; //названия вершин графа

int coord [50][2];//массив для  координат вершин

int mat[50][50];//матрица смежности

int M[50]; //M-текущий путь

int minp[50];//minp-минимальный путь

int in1,in2;//индексы вершин  графа

int min; //минимальная сумма

int summ;//текущая сумма

int gor=0;//счетчик пройденных  городов

int ngor=0;//найден ли город

//---------------------------------------------------------------------------

void poisk(int x)    //поиск  следующего города в порядке обхода после города с номером Х

{

if ((gor==k)&&                //если просмотрели все города

    (mat[x][1]!=0)&&                //из последнего города есть  путь в первый город

    (summ+mat[x][1]<min))            //новая сумма расстояний меньше  минимальной суммы

     {

     ngor=1;                    //маршрут найден

     min=summ+mat[x][1];                //изменяем: новая минимальная сумма  расстояний

     for (int i=1;i<=k;i++)minp[i]=M[i];//изменяем: новый минимальный путь

     }

     else

     {

     for (int i=1;i<=k;i++)     //из текущего города просматриваем  все города

     if ((i!=x)&&                //новый город не совпадает  с текущим

        (mat[x][i]!=0)&&            //есть прямой путь из x в i

            (M[i]==0)&&            //новый город еще не просмотрен

            (summ+mat[x][i]<min))    //текущая сумма  не превышает минимальной

        {

        summ+=mat[x][i];                //наращиваем сумму

        gor++;                //количество просмотренных городав

        M[i]=gor;                //отмечаем у нового города  новый номер в порядке обхода

        poisk(i);                //поиск нового города начиная  с города i

        M[i]=0;                    //возвращаем все назад

        gor--;               

        summ-=mat[x][i];              

        }

     }

}

//---------------------------------------------------------------------------

void pusk()

{                            

summ=0;

ngor=0;

min=45654;

for (int i=1;i<=k;i++) M[i]=0;

gor=1;

M[1]=gor;                  //считаем что поиск начинается  с первого города

poisk(1);                    //

}

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

{

Memo1->Clear();

StringGrid1->Cells[0][0] = "#";

StringGrid1->Cells[1][0] = "A";

StringGrid1->Cells[2][0] = "B";

StringGrid1->Cells[3][0] = "C";

StringGrid1->Cells[4][0] = "D";

StringGrid1->Cells[5][0] = "E";

StringGrid1->Cells[6][0] = "F";

StringGrid1->Cells[7][0] = "G";

StringGrid1->Cells[8][0] = "H";

StringGrid1->Cells[9][0] = "I";

//////////////////////////////////

StringGrid1->Cells[0][1] = "A";

StringGrid1->Cells[0][2] = "B";

StringGrid1->Cells[0][3] = "C";

StringGrid1->Cells[0][4] = "D";

StringGrid1->Cells[0][5] = "E";

StringGrid1->Cells[0][6] = "F";

StringGrid1->Cells[0][7] = "G";

StringGrid1->Cells[0][8] = "H";

StringGrid1->Cells[0][9] = "I";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FormShow(TObject *Sender)

{

Image1->Canvas->Pen->Color=(TColor)RGB(255,255,255);

Image1->Canvas->MoveTo(3,3);

Image1->Canvas->LineTo(4,8);

Image1->Canvas->Pen->Color=(TColor)RGB(0,0,0);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Image1Click(TObject *Sender)

{

int x,y,l;

if(i<50)

{

ListBox1->Items->Strings[i]=Al[i];

x=Mouse->CursorPos.x - Form1->Left - Image1->Left - 2;

y=Mouse->CursorPos.y - Form1->Top - Image1->Top - 25;

coord[i][0]=x;

coord[i][1]=y;

Image1->Canvas->Pen->Color=(TColor)RGB(0,0,0);

Image1->Canvas->Font->Size=14;

Image1->Canvas->Font->Color=(TColor)RGB(180,180,180);

Image1->Canvas->TextOutA(x-7,y-24,Al[i]);        //Пишем букву узла

Image1->Canvas->Font->Color=(TColor)RGB(0,0,0);

i++;

}

else ShowMessage("Превышено количество  вершин");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ListBox1Click(TObject *Sender)

{

int j;

j=ListBox1->ItemIndex;

if ((Edit1->Text!="") && (Edit2->Text!="")) {Edit1->Text=""; Edit2->Text="";}

if(Edit1->Text=="") {Edit1->Text=Al[j]; in1=j;}

else {Edit2->Text=Al[j]; in2=j;}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::SpeedButton1Click(TObject *Sender)

{

int x,y;

x=in1;

y=in2;

mat[x+1][y+1]=UpDown1->Position;

mat[y+1][x+1]=UpDown1->Position;

Image1->Canvas->Pen->Width=2;

Image1->Canvas->Pen->Color=(TColor)RGB(234,140,0);

Image1->Canvas->MoveTo(coord[x][0],coord[x][1]);

Image1->Canvas->LineTo(coord[y][0],coord[y][1]);

Image1->Canvas->Pen->Color=(TColor)RGB(0,0,0);

Image1->Canvas->TextOutA((coord[y][0]-coord[x][0])/2+coord[x][0]-5,(coord[y][1]-coord[x][1])/2+coord[x][1]-10,Edit3->Text);

//-------------------------------------

Image1->Canvas->Pen->Width=2;

Image1->Canvas->Pen->Color=(TColor)RGB(220,0,120);

Image1->Canvas->Rectangle(coord[x][0]-1,coord[x][1]-3,coord[x][0]+1,coord[x][1]+3);

Image1->Canvas->Pen->Color=(TColor)RGB(199,0,0);

Image1->Canvas->Font->Size=14;

Image1->Canvas->Font->Color=(TColor)RGB(0,0,0);

Image1->Canvas->TextOutA(coord[x][0]-7,coord[x][1]-20,Al[x]);

Image1->Canvas->TextOutA(coord[y][0]-7,coord[y][1]-20,Al[y]);

Image1->Canvas->Pen->Color=(TColor)RGB(0,0,0);

Edit3->Text="";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

int l,j;

for(l=1;l<i+1;l++)

{

  for(j=1;j<i+1;j++)

  {

   StringGrid1->Cells[l][j]=mat[l][j];

  }

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{

char ch[50];

k=i;

pusk();                            //запуск основного алгоритма

if (ngor)                        //если найден маршрут...

    { AnsiString cha;

      AnsiString x=min;

      Memo1->Lines->Add("Длина минимального пути="+x);

      Memo1->Lines->Add("Путь:");

      int l=1;                    //номер в порядке обхода городов

      for (int i=1;i<=k;i++)      //пробегаем по всем городам

        {

         int j=1;

         while ((j<=k)&&(minp[j]!=l)) j++;//ищем следующий  город в порядке обхода

         cha+=Al[j-1];

         cha+="->";

         ch[j-1]=Al[j];//[minp[j-1]];

         l++;

        }

        x=Al[minp[0]];

     Memo1->Lines->Add(cha+x);

    }

else  Memo1->Lines->Add("Путь не найден");

}

//---------------------------------------------------------------------------