Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Описание разработанной программной системы



Программная система была реализована в интегрированном пакете C++ Builder 5.0. Внеш­ний вид окна программы представлен на рисунке 5.

 

Рис. 5 - Внешний вид программы

 

В верхней части окна пользователю необходимо ввести количество городов, которое необ­ходимо посетить коммивояжёру, а также матрицу расстояний. После того как пользова­тель ввёл все необходимые параметры задачи, ему необходимо выбрать из меню «Решить» каким методом решать задачу. Все полученные значения будут выведены в нижней части окна программы.

Если при вводе параметров будет допущено нарушение формата, программа даст соответ­ствующее сообщение и предложит пользователю заменить неподходящее значение на допустимое.

Численные эксперименты

Ручная реализация алгоритма решения задачи с помощью алгоритма Литла

На данном этапе необходимо выполнить ручной просчёт на основании данных, взя­тых из задания к курсовой работе.

Шаг 1. Приводим матрицу:

-> ->

->

Шаг2. Вычисляем нижнюю оценку

Шаг 3. По образовавшимся нулевым элементам в матрице пробуем составить цикл. Получаем < 1, 2, 3, 4, 5, 1> следовательно задача решена. Маршрут < 1, 2, 3, 4, 5, 1> является оптималь­ным, а его длина равна 13.


3.2 Ручная реализация алгоритма решения задачи с помощью метода пол­ного перебора

На данном этапе необходимо выполнить ручной просчёт на основании данных, взя­тых из задания к курсовой работе. На данном этапе необходимо выполнить ручной просчёт на основании данных, взятых из задания к курсовой работе. В качестве примера для данного алгоритма мы приведем только несколько расчетов.

Исходная матрица:

А А А А А

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

- является первым опорным планом.

 

{5, 7, 3, 6, 4}

{5, 7, 3, 6, 4} ( ) = 8+3+7+8 = 26 {3, 7, 5, 6, 4} ( ) = 3+5+2+8= 18

{5, 3, 7, 6, 4} ( ) = 3+3+3+8 = 17 {7, 3, 5, 6, 4} ( ) = 3+6+2+8 = 19

{7, 5, 3, 6, 4} ( ) = 5+3+7+8 = 23 {3, 5, 7, 6, 4} ( ) = 6+8+3+8 = 25

 

В первом случае для решении мы не изменяем предпоследние и последнее число, а по всем остальным числам будет вестись пересчет. После всех расчетов мы выбираем наименьшую оценку и ее записываем для дальнейших расчетов. В данном случае наименьшей оценкой является выражение: {5, 3, 7, 6, 4} ( ) = 3+3+3+8 = 17

 

{5, 3, 7, 6, 4}

{5, 3, 7, 6, 4} ( ) = 3+3+3+8 = 17 {5, 6, 7, 3, 4} ( ) = 2+3+3+1= 9

{5, 3, 6, 7, 4} ( ) = 3+7+3+16 = 29 {5, 7, 6, 3, 4} ( ) = 8+3+2+1 = 14

{5, 6, 3, 7, 4} ( ) = 2+2+3+16 = 23 {5, 7, 3, 6, 4} ( ) = 8+3+7+8 = 26

 

Во втором случае для решении мы не изменяем первое и последнее число, а по всем остальным числам будет вестись пересчет. В данном случае наименьшей оценкой является выражение: {5, 6, 7, 3, 4} ( ) = 2+3+3+1= 9

 

{5, 6, 7, 3, 4}

{5, 6, 7, 3, 4} ( ) = 2+3+3+1= 9 {5, 6, 4, 3, 7} ( ) = 2+8+4+3= 17

{5, 6, 7, 4, 3} ( ) = 2+3+16+4 = 25 {5, 6, 3, 4, 7} ( ) = 2+2+1+9 = 14

{5, 6, 4, 7, 3} ( ) = 2+8+9+3 = 22 {5, 6, 3, 7, 4} ( ) = 2+2+3+16 = 23

 

Случай

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

 

{3, 6, 4, 7, 5}

{3, 6, 4, 7, 5} ( ) = 7+8+9+5 = 29 {4, 6, 3, 7, 5} ( ) = 2+2+3+5= 12

{3, 4, 6, 7, 5} ( ) = 1+2+3+5 = 11 {6, 4, 3, 7, 5} ( ) = 8+4+3+5 = 20

{4, 3, 6, 7, 5} ( ) = 4+7+3+5 = 19 {6, 3, 4, 7, 5} ( ) = 2+1+9+5 = 25

 

В первом случае для решении мы не изменяем предпоследние и последнее число, а по всем остальным числам будет вестись пересчет. После всех расчетов мы выбираем наименьшую оценку и ее записываем для дальнейших расчетов. В данном случае наименьшей оценкой является выражение: {3, 4, 6, 7, 5} ( ) = 1+2+3+5 = 11

 

{3, 4, 6, 7, 5}

{3, 4, 6, 7, 5} ( ) = 1+2+3+5 = 11 {3, 6, 4, 7, 5} ( ) = 7+8+9+5= 29

{3, 4, 7, 6, 5} ( ) = 1+9+3+4 = 17 {3, 7, 6, 4, 5} ( ) = 3+3+8+4 = 18

{3, 6, 7, 4, 5} ( ) = 7+3+16+4 = 30 {3, 7, 4, 6, 5} ( ) = 3+16+2+4 = 25

 

Во втором случае для решении мы не изменяем, первое и последнее число, а по всем остальным числам будет вестись пересчет. В данном случае наименьшей оценкой является выражение: {3, 4, 6, 7, 5} ( ) = 1+2+3+5 = 11

 

{3, 4, 6, 7, 5}

{3, 4, 6, 7, 5} ( ) = 1+2+3+5 = 11 {3, 4, 5, 7, 6} ( ) = 1+4+8+3= 16

{3, 4, 6, 5, 7} ( ) = 1+2+4+8 = 15 {3, 4, 7, 6, 5} ( ) = 1+9+3+4 = 17

{3, 4, 5, 6, 7} ( ) = 1+4+2+3 = 10 {3, 4, 7, 5, 6} ( ) = 1+9+5+2 = 17

 

Для удобства расчетов составим таблицу, содержащую в первом столбце пути во втором сумму расстояний для этого пути, а в третьем длину получившегося пути.

 


1 2 3 4 5 3+ 1+ 4+ 2+ 3
1 2 3 5 4 2+ 1+ 4+ 8+ 3
1 2 4 3 5 3+ 1+ 2+ 4+ 8
1 2 4 5 3 3+ 1+ 2+ 3+ 5
1 2 5 3 4 2+ 1+ 9+ 5+ 2
1 2 5 4 3 3+ 1+ 9+ 3+ 4
1 3 2 4 5 3+ 6+ 2+ 2+ 3
1 3 2 5 4 2+ 6+ 2+ 9+ 3
1 3 4 2 5 3+ 6+ 2+ 8+ 9
1 3 4 5 2 4+ 6+ 2+ 3+ 16
1 3 5 2 4 2+ 6+ 8+ 16+ 2
1 3 5 4 2 4+ 6+ 8+ 3+ 8
1 4 2 3 5 3+ 7+ 8+ 4+ 8
1 4 2 5 3 3+ 7+ 8+ 9+ 5
1 4 3 2 5 3+ 7+ 4+ 2+ 9
1 4 3 5 2 4+ 7+ 4+ 8+ 16
1 4 5 2 3 3+ 7+ 3+ 16+ 4
1 4 5 3 2 4+ 7+ 3+ 5+ 2
1 5 2 3 4 2+ 3+ 16+ 4+ 2
1 5 2 4 3 3+ 3+ 16+ 2+ 4
1 5 3 2 4 2+ 3+ 5+ 2+ 2
1 5 3 4 2 4+ 3+ 5+ 2+ 8
1 5 4 2 3 3+ 3+ 3+ 8+ 4
1 5 4 3 2 4+ 3+ 3+ 4+ 2
2 1 3 4 5 16+ 4+ 6+ 2+ 3
2 1 3 5 4 8+ 4+ 6+ 8+ 3
2 1 4 3 5 16+ 4+ 7+ 4+ 8
2 1 4 5 3 2+ 4+ 7+ 3+ 5
2 1 5 3 4 8+ 4+ 3+ 5+ 2
2 1 5 4 3 2+ 4+ 3+ 3+ 4
2 3 1 4 5 16+ 4+ 3+ 7+ 3
2 3 1 5 4 8+ 4+ 3+ 3+ 3
2 3 4 1 5 16+ 4+ 2+ 2+ 3
2 3 4 5 1 1+ 4+ 2+ 3+ 3
2 3 5 1 4 8+ 4+ 8+ 3+ 7
2 3 5 4 1 1+ 4+ 8+ 3+ 2
2 4 1 3 5 16+ 2+ 2+ 6+ 8
2 4 1 5 3 2+ 2+ 2+ 3+ 5
2 4 3 1 5 16+ 2+ 4+ 3+ 3
2 4 3 5 1 1+ 2+ 4+ 8+ 3
2 4 5 1 3 2+ 2+ 3+ 3+ 6
2 4 5 3 1 1+ 2+ 3+ 5+ 3
2 5 1 3 4 8+ 9+ 3+ 6+ 2
2 5 1 4 3 2+ 9+ 3+ 7+ 4
2 5 3 1 4 8+ 9+ 5+ 3+ 7
2 5 3 4 1 1+ 9+ 5+ 2+ 2
2 5 4 1 3 2+ 9+ 3+ 2+ 6
2 5 4 3 1 1+ 9+ 3+ 4+ 3
3 1 2 4 5 5+ 3+ 1+ 2+ 3
3 1 2 5 4 4+ 3+ 1+ 9+ 3
3 1 4 2 5 5+ 3+ 7+ 8+ 9
3 1 4 5 2 4+ 3+ 7+ 3+ 16
3 1 5 2 4 4+ 3+ 3+ 16+ 2
3 1 5 4 2 4+ 3+ 3+ 3+ 8
3 2 1 4 5 5+ 2+ 4+ 7+ 3
3 2 1 5 4 4+ 2+ 4+ 3+ 3
3 2 4 1 5 5+ 2+ 2+ 2+ 3
3 2 4 5 1 6+ 2+ 2+ 3+ 3
3 2 5 1 4 4+ 2+ 9+ 3+ 7
3 2 5 4 1 6+ 2+ 9+ 3+ 2
3 4 1 2 5 5+ 2+ 2+ 1+ 9
3 4 1 5 2 4+ 2+ 2+ 3+ 16
3 4 2 1 5 5+ 2+ 8+ 4+ 3
3 4 2 5 1 6+ 2+ 8+ 9+ 3
3 4 5 1 2 4+ 2+ 3+ 3+ 1
3 4 5 2 1 6+ 2+ 3+ 16+ 4
3 5 1 2 4 4+ 8+ 3+ 1+ 2
3 5 1 4 2 4+ 8+ 3+ 7+ 8
3 5 2 1 4 4+ 8+ 16+ 4+ 7
3 5 2 4 1 6+ 8+ 16+ 2+ 2
3 5 4 1 2 4+ 8+ 3+ 2+ 1
3 5 4 2 1 6+ 8+ 3+ 8+ 4
4 1 2 3 5 3+ 2+ 1+ 4+ 8
4 1 2 5 3 2+ 2+ 1+ 9+ 5
4 1 3 2 5 3+ 2+ 6+ 2+ 9
4 1 3 5 2 2+ 2+ 6+ 8+ 16
4 1 5 2 3 2+ 2+ 3+ 16+ 4
4 1 5 3 2 2+ 2+ 3+ 5+ 2
4 2 1 3 5 3+ 8+ 4+ 6+ 8
4 2 1 5 3 2+ 8+ 4+ 3+ 5
4 2 3 1 5 3+ 8+ 4+ 3+ 3
4 2 3 5 1 7+ 8+ 4+ 8+ 3
4 2 5 1 3 2+ 8+ 9+ 3+ 6
4 2 5 3 1 7+ 8+ 9+ 5+ 3
4 3 1 2 5 3+ 4+ 3+ 1+ 9
4 3 1 5 2 2+ 4+ 3+ 3+ 16
4 3 2 1 5 3+ 4+ 2+ 4+ 3
4 3 2 5 1 7+ 4+ 2+ 9+ 3
4 3 5 1 2 2+ 4+ 8+ 3+ 1
4 3 5 2 1 7+ 4+ 8+ 16+ 4
4 5 1 2 3 2+ 3+ 3+ 1+ 4
4 5 1 3 2 2+ 3+ 3+ 6+ 2
4 5 2 1 3 2+ 3+ 16+ 4+ 6
4 5 2 3 1 7+ 3+ 16+ 4+ 3
4 5 3 1 2 2+ 3+ 5+ 3+ 1
4 5 3 2 1 7+ 3+ 5+ 2+ 4
5 1 2 3 4 3+ 3+ 1+ 4+ 2
5 1 2 4 3 8+ 3+ 1+ 2+ 4
5 1 3 2 4 3+ 3+ 6+ 2+ 2
5 1 3 4 2 9+ 3+ 6+ 2+ 8
5 1 4 2 3 8+ 3+ 7+ 8+ 4
5 1 4 3 2 9+ 3+ 7+ 4+ 2
5 2 1 3 4 3+ 16+ 4+ 6+ 2
5 2 1 4 3 8+ 16+ 4+ 7+ 4
5 2 3 1 4 3+ 16+ 4+ 3+ 7
5 2 3 4 1 3+ 16+ 4+ 2+ 2
5 2 4 1 3 8+ 16+ 2+ 2+ 6
5 2 4 3 1 3+ 16+ 2+ 4+ 3
5 3 1 2 4 3+ 5+ 3+ 1+ 2
5 3 1 4 2 9+ 5+ 3+ 7+ 8
5 3 2 1 4 3+ 5+ 2+ 4+ 7
5 3 2 4 1 3+ 5+ 2+ 2+ 2
5 3 4 1 2 9+ 5+ 2+ 2+ 1
5 3 4 2 1 3+ 5+ 2+ 8+ 4
5 4 1 2 3 8+ 3+ 2+ 1+ 4
5 4 1 3 2 9+ 3+ 2+ 6+ 2
5 4 2 1 3 8+ 3+ 8+ 4+ 6
5 4 2 3 1 3+ 3+ 8+ 4+ 3
5 4 3 1 2 9+ 3+ 4+ 3+ 1
5 4 3 2 1 3+ 3+ 4+ 2+ 4

 

Просмотрев таблицу, находим в ней строку с минимальным значением третьего столбца. В нашем случае таких строк 5:

1 2 3 4 5 3+ 1+ 4+ 2+ 3
2 3 4 5 1 1+ 4+ 2+ 3+ 3
3 4 5 1 2 4+ 2+ 3+ 3+ 1
4 5 1 2 3 2+ 3+ 3+ 1+ 4
5 1 2 3 4 3+ 3+ 1+ 4+ 2

 

Но все они фактически являются одним и тем же путем только с разным начальным городом т.к. если их прокрутить, то они станут одинаковыми.

Значит, маршрут < 1, 2, 3, 4, 5, 1> является оптимальным, а его длина равна 13.

Машинные эксперименты с разработанной программой

В полученную программу были введены исходные данные курсовой работы. На ри­сунке 6 представлено основное окно программы с введёнными исходными параметрами за­дачи.

Рисунок 6- Исходные параметры задачи

 

Как видно из рисунка 6, полученные результаты полностью соответствуют результа­там, полученным в ходе выполнения ручного просчёта. Этот факт свидетельствует о том, что программа работает верно.

Заключение

 

В ходе выполнения курсовой работы, была разработана автоматизированная система, по­зволяющая находить оптимальный путь выпуска продукции с целью сокращения времени пере­наладки автоматизированной линии. Полученная программа имеет простой и удобный в ис­пользовании графический интерфейс, выполняющийся в среде операционной системы Windows.

Программа была протестирована на достаточно большом количестве исходных дан­ных. При этом все полученные результаты соответствуют результатам, полученным при руч­ном счёте. Таким образом, можно утверждать, что программа работает верно.

В разделе 3.1 и 3.2 данной курсовой работы имеется детальный ручной просчёт исход­ной задачи. В свою очередь, в разделе 3.3 имеется рисунок, подтверждающий правиль­ность результатов, полученных с помощью разработанной автоматизированной системы.

 

 

Список литературы

 

  1. Зайченко Ю.П. Исследование операций. -Киев: Вища шк., 1979.-392с.
  2. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний.-М.: Наука, 1975. - 359 с.
  3. Мудрой В.И. Задача о коммивояжере.-М.: Знание, 1969.-60с.
  4. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование.- М.: Наука, 1969.-368 c.
  5. Шкурба В.В. Задача трех станков. - М.: Наука, 1976. 93с.
  6. Черноморов Г.А. Теория принятия решений: Учебное пособие / Юж.-Рос. гос. техн. ун-т. Новочеркасск: Ред. Журн. «Изв. вузов. Электромеханика», 2002, 276 с.
  7. Таха, Хэдми, А. Введение в исследование операций, 6-е издание. – М.: Вильямс, 2001.-912с.

Приложение А

 

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

Листинг файла Unit1.h


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

 

#ifndef Unit1H

#define Unit1H

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

#include < Classes.hpp>

#include < Controls.hpp>

#include < StdCtrls.hpp>

#include < Forms.hpp>

#include < Grids.hpp>

#include < ExtCtrls.hpp>

#include < Dialogs.hpp>

#include < Menus.hpp>

#include < ComCtrls.hpp>

#include " CSPIN.h"

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

class TForm1: public TForm

{

__published: // IDE-managed Components

TPanel *Panel1;

TStringGrid *StringGrid1;

TLabel *Label1;

TOpenDialog *OpenDialog1;

TMainMenu *MainMenu1;

TMenuItem *N1;

TMenuItem *N2;

TMenuItem *N3;

TCSpinEdit *CSpinEdit1;

TMenuItem *N4;

TLabel *Label2;

TPanel *Panel2;

TLabel *Label3;

TLabel *Label5;

TLabel *Label6;

TMenuItem *N5;

TMenuItem *N6;

TMemo *Memo1;

void __fastcall FormCreate(TObject *Sender);

void __fastcall N2Click(TObject *Sender);

void __fastcall N3Click(TObject *Sender);

void __fastcall CSpinEdit1Change(TObject *Sender);

void __fastcall N4Click(TObject *Sender);

void __fastcall FormClose(TObject *Sender, TCloseAction & Action);

void __fastcall N6Click(TObject *Sender);

private: // User declarations

public: // User declarations

__fastcall TForm1(TComponent* Owner);

void poln(char*);

void Next(unsigned *A);

};

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

extern PACKAGE TForm1 *Form1;

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

#endif

Листинг файла Unit1.cpp

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

 

#include < vcl.h>

#pragma hdrstop

 

#include " Unit1.h"

#include " litl.h"

#include " poln.h"

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

#pragma package(smart_init)

#pragma link " CSPIN"

#pragma resource " *.dfm"

TForm1 *Form1;

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

__fastcall TForm1:: TForm1(TComponent* Owner)

: TForm(Owner)

{

}

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

 

 

void __fastcall TForm1:: FormCreate(TObject *Sender)

{

unsigned int i, j;

FILE* in=fopen(" c0.___", " r" );

fscanf(in, " %d", & num);

StringGrid1-> ColCount=num;

StringGrid1-> RowCount=num;

for(i=0; i< num; i++)

for(j=0; j< num; j++)

{

int temp;

fscanf(in, " %d", & temp);

StringGrid1-> Cells[j][i]=IntToStr(temp);

}

fclose(in);

CSpinEdit1-> Value=num;

}

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

 

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

void __fastcall TForm1:: N2Click(TObject *Sender)

{

unsigned int i, j;

StringGrid1-> ColCount=num;

StringGrid1-> RowCount=num;

for(i=0; i< num; i++)

for(j=0; j< num; j++)

{

int temp;

if(i==j)

temp=-1;

else

temp=random(15)+1;

StringGrid1-> Cells[j][i]=IntToStr(temp);

}

}

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

void __fastcall TForm1:: N3Click(TObject *Sender)

{

if(OpenDialog1-> Execute())

{

unsigned int i, j;

FILE* in=fopen(OpenDialog1-> FileName.c_str(), " r" );

fscanf(in, " %d", & num);

StringGrid1-> ColCount=num;

StringGrid1-> RowCount=num;

CSpinEdit1-> Value=num;

for(i=0; i< num; i++)

for(j=0; j< num; j++)

{

int temp;

fscanf(in, " %d", & temp);

StringGrid1-> Cells[j][i]=IntToStr(temp);

}

fclose(in);

}

}

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

void __fastcall TForm1:: CSpinEdit1Change(TObject *Sender)

{

try

{

num=CSpinEdit1-> Text.ToInt();

}

catch(...)

{

ShowMessage(" Должно быть целое число от 0 до 70" );

}

StringGrid1-> ColCount=num;

StringGrid1-> RowCount=num;

}

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

void __fastcall TForm1:: N4Click(TObject *Sender)

{

unsigned int i, j;

char fname[13];

tmpnam(fname);

FILE* out=fopen(fname, " w" );

fprintf(out, " %d\n", num);

try

{

for(i=0; i< num; i++)

{

for(j=0; j< num; j++)

{

int temp;

temp=StringGrid1-> Cells[j][i].ToInt();

fprintf(out, " %2d", temp);

}

fprintf(out, " \n" );

}

fclose(out);

}

catch(...)

{

ShowMessage(" Данные не корректны" );

fclose(out);

remove(fname);

}

CitiesSet *tmp_ptr=ListInit(fname); //создаем список и получаем указатель на первое подмножество

CitiesSet *prom_ptr;

for(char f=0; f! =1; )

{

tmp_ptr=tmp_ptr-> first; //берем первый элемент

int minksi=tmp_ptr-> ksi;

prom_ptr=tmp_ptr;

for(i=0; i< tmp_ptr-> num_of_sets; i++)//выбираем множество с минимальным кси

{

if(tmp_ptr-> ksi< =minksi& & tmp_ptr-> cps_num> prom_ptr-> cps_num)

{

minksi=tmp_ptr-> ksi;

prom_ptr=tmp_ptr; //выбрали множество с минимальным кси и запомнили его

}

tmp_ptr=tmp_ptr-> next;

}

prom_ptr-> Delenie(); //делим подмножество на две части

prom_ptr-> RemoveItem(); //удаляем подмножество

 

tmp_ptr=tmp_ptr-> first; //устанавливаем указатель на первый элемент в списке

 

for(i=0; i< tmp_ptr-> num_of_sets; i++)//просматриваем все элементы списка

{

if((tmp_ptr-> cps_num)==num)//если в каком-то элементе число переходов равно числу городов значит найден оптимальный маршрут

{

if(tmp_ptr-> GetCycle()==0)//делаем цикл

{ //выводим его на экран

AnsiString s, s1;

s1.sprintf(" < %d", tmp_ptr-> CC[0].ca+1);

for(i=0; i< tmp_ptr-> cps_num; i++)

{

s.sprintf(", %d", tmp_ptr-> CC[i].cb+1);

s1=s1+s;

}

s1=s1+s.sprintf(" > " );

Memo1-> Text=(s1);

 

s1.sprintf(" %u", tmp_ptr-> ksi);

Label6-> Caption=s1;

unsigned int n=tmp_ptr-> num_of_sets; //запоминаем количество элементов в списке

for(i=0; i< n; i++) //удаляем список по одному элементу

tmp_ptr-> first-> RemoveItem();

f=1; //устанавливаем флаг окончания в 1

}

else

{

CitiesSet *next=tmp_ptr-> next-> next;

tmp_ptr-> next-> RemoveItem();

tmp_ptr-> RemoveItem();

tmp_ptr=next;

}

}

else

tmp_ptr=tmp_ptr-> next; //выбираем следующий элемент

}

}

remove(fname);

}

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

void __fastcall TForm1:: FormClose(TObject *Sender, TCloseAction & Action)

{

Action=caFree;

}

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

 

void __fastcall TForm1:: N6Click(TObject *Sender)

{

unsigned int i, j;

char fname[13];

tmpnam(fname);

FILE* out=fopen(fname, " w" );

fprintf(out, " %d\n", num);

for(i=0; i< num; i++)

{

for(j=0; j< num; j++)

{

int temp;

temp=StringGrid1-> Cells[j][i].ToInt();

fprintf(out, " %2d", temp);

}

fprintf(out, " \n" );

}

fclose(out);

poln(fname);

remove(fname);

}

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

Листинг файла litl.h

#include< stdio.h>

#include< conio.h>

#include< stdlib.h>

#include< string.h>

#include < exception>

 

 

unsigned int num=0;

 

class Matrix //матрица переходов

{

public:

char **C; //указатель на матрицу переходов

char fn[13]; //имя файла с матрицей расстояний

char s; //флаг сохранения в файл

Matrix(); //конструктор матрицы

int New(); //выделение памяти под матрицу

void Load(); //Загрузка из файла если есть необходимость

void Save(); //Выгрузка из памяти если есть необходимость

void LoadFromFile(char*); //функция загрузки матрицы из файла

void SaveToFile(); //функция выгрузки матрицы в файл

void Delete(); //функция удаления матрицы

};

 

int Matrix:: New() //выделение памяти под матрицы

{

unsigned int i;

if(C==NULL) //если массив не выделен то выделяем массив под матрицу

{

try

{

C=new char*[num+1];

for(i=0; i< num+1; i++)

C[i]=new char[num];

}

catch(Exception & e) //если произошла ошибка то выводим сообщение

{

ShowMessage(" Нехватает памяти" );

Application-> ShowException(& e);

}

return 1;

}

return 0;

}

Matrix:: Matrix()//при создании матрицы

{

C=NULL; //устанавливаем указатель на массив в NULL

tmpnam(fn); //формируем имя файла для матрицы

s=0; //ставим s равным нулю

}

 

void Matrix:: LoadFromFile(char *in=NULL)//загрузка матрицы из файла in

{

FILE *inf;

if(in==NULL)

in=fn;

inf=fopen(in, " r" ); //открываем файл

if(inf==NULL) //открылся ли файл

{ //если нет то выводим сообщение и завершаем программу

perror(" Unable to open file to read matrix." );

exit(0);

}

fscanf(inf, " %d", & num); //считываем число элементов в матрице

unsigned i, j;

 

New(); //выделяем память под матрицу

int tmp;

for(i=0; i< num; i++) //считываем матрицу из файла

for(j=0; j< num; j++)

{

fscanf(inf, " %d", & tmp);

this-> C[i][j]=tmp;

}

fclose(inf); //закрываем файл

}

 

void Matrix:: SaveToFile() //выгрузка матрицы в файл

{

unsigned int i, j;

 

if(C! =NULL)

{

FILE *outf;

outf=fopen(fn, " w" ); //открываем файл

if(outf==NULL) //открылся ли файл

{ //если файл не открылся, то выводим сообщение об ошибке и завершаем программу

perror(" Unable to open file to write matrix." );

exit(0);

}

 

fprintf(outf, " %d\n", num); //записываем количество городов

 

for(i=0; i< num; i++) //записываем элементы матрицы в файл

{

for(j=0; j< num; j++)

{

fprintf(outf, " %2d", C[i][j]);

}

fprintf(outf, " \n" );

}

Delete(); //удаляем массив из памяти

fclose(outf); //закрываем файл

}

}

 

void Matrix:: Load() //загрузка матрицы по необходимости

{

if(num> 32) //Если размер матрицы больше 32 то надо загружать из файла

{

LoadFromFile();

}

}

 

void Matrix:: Save() //сохранение матрицы по необходимости

{

if(num> 32) //если размер матрицы больше 32 то надо сохранять в файл

{

SaveToFile();

s=1;

}

}

 

void Matrix:: Delete() //удаление матрицы из памяти

{

if(C! =NULL) //находится ли матрица в памяти

{

unsigned int i;

try

{

for(i=0; i< num+1; i++) //удаление матрицы из памяти

delete[] C[i];

delete[] C;

C=NULL; //присваивание указателю на массив значения NULL

}

catch(Exception & e) //Если произошла ошибка то выводим сообщение

{

ShowMessage(" Can not delete Matrix" );

Application-> ShowException(& e);

}

}

}

 

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

struct Couple //переход между городами

{

unsigned char ca; //город а

unsigned char cb; //город б

};

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

class CitiesSet //подмножество решений

{

public:

int ksi; //нижняя оценка

unsigned int cps_num; //количество пройденных городов

unsigned int r, m; //перспективная пара для текущего подмножества

Matrix CM; //матрица переходов для текущего подмножества

Couple *CC; //указатель на матрицу с переходами

 

static unsigned int num_of_sets; //число перспективных вершин

static CitiesSet *first; //указатель на первый элемент из двухсвязного списка перспективных вершин

static CitiesSet *last; //указатель на последний элемент из двухсвязного списка перспективных вершин

 

CitiesSet *prev; //указатель на предъидущий элемент списка

CitiesSet *next; //указатель на следующий элемент списка

 

CitiesSet(); //конструктор подмножества

unsigned Reduction(); //приведение матрицы С и нахождение Н

void Delenie(); //деление подмножества на две части

void NewCC(); //выделение памяти под маршрут

void DeleteCC(); //удаление памяти из под маршрута

CitiesSet* GetLeftChild(); //получение левого подмножества

CitiesSet* GetRightChild(); //получение правого подмножества

void AddNewCouple(); //добавление новой пары в путь

void RemoveItem(void); //удаление подмножества

int GetCycle(); //получение цикла из набора переходов

};

 

 

//задание начальных значений для списка

unsigned int CitiesSet:: num_of_sets=0;

CitiesSet *CitiesSet:: first=NULL;

CitiesSet *CitiesSet:: last=NULL;

 

void CitiesSet:: DeleteCC() //удаление памяти из под маршрута

{

try

{

if(CC! =NULL)

delete[] CC;

CC=NULL;

} //если произошла ошибка то выводим сообщение

catch(...)

{

ShowMessage(" Can not delete CC" );

}

}

//выделение памяти под маршрут

void CitiesSet:: NewCC()

{

if(CC! =NULL) //если под массив уже выделялась память то освобождаем её

delete[] CC;

CC=new Couple[cps_num]; //выделяем память под текущий путь

if(CC==NULL)

ShowMessage(" No ram to put" );

}

CitiesSet:: CitiesSet() //конструктор по умолчанию

{

if(num_of_sets==0) //если это первый элемент списка

{

first=this; //устанавливаем на этот элемент указатель первый

this-> prev=NULL; //устанавливаем у текущего указатель на предъидущий в NULL

}

else

{

this-> prev=last; //если это не первый то устанавливаем указатель на предъидущий на последний

last-> next=this; //у последнего устанавливаем указатель на следующий на текущий

}

last=this; //делаем текущий элемент последним

this-> next=NULL; //устанавливаем у текущего указатель на следующий в NULL

ksi=0; //нижняя оценка равна нулю

CC=NULL; //ставим указатель на массив с текущим путем в NULL

num_of_sets++; //добавляем текущий элемент в число перспективных

}

 

unsigned CitiesSet:: Reduction()//приведение матрицы С и нахождение Н

{

if(CM.C==NULL) //если матрица отсутствует в памяти то выходим из процедуры

{

CM.Load();

}

unsigned int i, j, kf, k=0;

unsigned char min;

 

for(i=0; i< num; i++, kf=0)//приводим строки и находим Hi

{

min=255;

for(j=0; j< num; j++) //проходим по элементам строки и находим минимальный

{

if(CM.C[i][j]< min& & CM.C[i][j]> =0)

{

min=CM.C[i][j];

kf=1;

}

}

if(kf==1) //если минимальный был найден то отнимаем его от всех элементов этой строки

{

k+=min; //суммируем Нi

for(j=0; j< num; j++)

{

if(CM.C[i][j]> 0)

CM.C[i][j]-=min;

}

}

}

for(j=0; j< num; j++, kf=0) //приводим столбцы и находим Hj

{

min=255;

for(i=0; i< num; i++) //проходим по элементам столбца и ищем минимальный

{

if(CM.C[i][j]< min& & CM.C[i][j]> =0)

{

min=CM.C[i][j];

kf=1;

}

}

if(kf==1) //если минимальный был найден то отнимаем его от всех элементов этого столбца

{

k+=min; //прибавляем к k Нj

for(i=0; i< num; i++)

{

if(CM.C[i][j]> 0)

CM.C[i][j]-=min;

}

}

}

 

return k; //возвращаем Н

}

 

 

CitiesSet* CitiesSet:: GetLeftChild()//получение левого подмножества

{

last=new CitiesSet; //создание нового элемента

last-> CM.New(); //выделение памяти под матрицу

unsigned int i, j;

 

for(i=0; i< num; i++) //копирование и изменение матрицы

for(j=0; j< num; j++)

{

if(i==r||j==m)

last-> CM.C[i][j]=-1;

else

last-> CM.C[i][j]=CM.C[i][j];

}

last-> CM.C[m][r]=-1;

last-> ksi=ksi+last-> Reduction(); //подсчет нижней оценки

last-> CM.Save(); //сохранение матрицы расстояний в файле и освобождение из под неё памяти

AddNewCouple(); //добавление новой пары в текущий путь

 

return last; //возвращение указателя на последний(левый)элемент

}

 

void CitiesSet:: AddNewCouple() //добавление текущей пары в путь

{

last-> cps_num=cps_num+1; //увеличение числа переходов на один

last-> NewCC(); //выделяем память для текущего пути

for(unsigned int i=0; i< cps_num; i++) //переносим все переходы из одного пути в другой

last-> CC[i]=CC[i];

last-> CC[last-> cps_num-1].ca=r; //добавляем перспективную пару в путь

last-> CC[last-> cps_num-1].cb=m;

}

 

CitiesSet* CitiesSet:: GetRightChild() //получение правого подмножества

{

new CitiesSet; //создание нового элемента

last-> CM.New(); //выделение памяти под матрицу

unsigned int i, j;

 

for(i=0; i< num; i++) //копирование и изменение матрицы

for(j=0; j< num; j++)

last-> CM.C[i][j]=CM.C[i][j];

last-> CM.C[r][m]=-1;

 

last-> ksi=ksi+last-> Reduction(); //вычисление нижней оценки

last-> CM.Save(); //выгрузка матрицы переходов в файл

last-> CC=CC;

CC=NULL;

last-> cps_num=cps_num; //также присваиваем количество пройденных городов

return last; //возвращаем указатель на последний(теперь правый)элемент

}

 

void CitiesSet:: RemoveItem(void) //удаление элемента

{

if(CM.s==1) //если матрица сохранялась в файл то

remove(CM.fn); //удаляем файл с матрицей переходов

 

if(first==this) //если это первый элемент

{

first=next; //устанавливаем следующий элемент первым

if(next! =NULL) //если это не последний элемент

first-> prev=NULL; //у первого элемента устанавливаем предыдущий в NULL

else

last=first; //иначе если это последний элемент то ставим последний равен первому

}

else //если это не первый элемент

{

prev-> next=next; //устанавливаем указатель предыдущего следующий на следующий текущего

if(next! =NULL) //если это не последний элемент

next-> prev=prev; //устанавливаем указатель следующего предыдущий на предыдущий текущего

else

last=prev; //иначе если это последний элемент то ставим последний равен предыдущему

}

num_of_sets--; //удаляем один элемент из числа конкурирующих

CM.Delete(); //удаляем матрицу переходов

DeleteCC();

delete this; //удаляем текущий элемент

}

 

void CitiesSet:: Delenie() //деление текущего подмножества

{

unsigned int i, j, teta, maxteta=0, f=0;

if(CM.C==NULL)

CM.Load();

for(i=0; i< num; i++) //проходим по всей матрице переходов и ищем перспективную пару

for(j=0; j< num; j++)

{

if(CM.C[i][j]==0) //если текущий элемент является претендентом в перспективные

{

unsigned ii, jj;

int mincpj=32767, mincpi=32767;

 

for(jj=0; jj< num; jj++) //находим минимальный не отрицательный

и не текущий элемент в данной строке

{

if((CM.C[i][jj]< mincpj)

& & (CM.C[i][jj]> =0)

& & (j! =jj))

mincpj=CM.C[i][jj];

}

 

for(ii=0; ii< num; ii++) //находим минимальный не отрицательный и не текущий элемент в данном столбце

{

if((CM.C[ii][j]< mincpi)

& & (CM.C[ii][j]> =0)

& & (i! =ii))

mincpi=CM.C[ii][j];

}

teta=mincpj+mincpi; //вычисляем тетту

if(teta> =maxteta) //выбираем максимальную тетту и перспективную пару

{

maxteta=teta;

r=i;

m=j;

f=1;

}

}

}

if(f==1)

{

GetLeftChild(); //создаем левое подмножемтво

GetRightChild(); //создаем правое подмножество

}

else

ksi=32700;

CM.Save();

 

}

CitiesSet* ListInit(char* fname)//функция инициализации списка

{

CitiesSet *SetsList=new CitiesSet; //создание первого элемента списка

SetsList-> CM.LoadFromFile(fname); //загрузка матрицы переходов из файла

SetsList-> ksi=SetsList-> Reduction(); //вычисление нижней оценки

SetsList-> cps_num=0; //установка числа переходов в ноль

SetsList-> Delenie(); //деление множества на две части

CitiesSet *retptr=SetsList-> next; //указатель на следующий элемент

SetsList-> RemoveItem(); //удаление элемента

return retptr;


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-06-05; Просмотров: 545; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.622 с.)
Главная | Случайная страница | Обратная связь