Lektsia - бесплатные рефераты, доклады, курсовые работы, контрольные и дипломы для студентов » Описание разработанной программной системы

Программная система была реализована в интегрированном пакете 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}

{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 имеется рисунок, подтверждающий правильность результатов, полученных с помощью разработанной автоматизированной системы.

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

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

}