Оптимизация переналадки автоматической линии

Одной из задач оперативного планирования и управления промышленным предприятием является задача определения оптимальной последовательности переналадки технологического оборудования, в частности, автоматических линий. Внедрение результатов решения этой задачи в практику автоматизированного планирования и управления позволяет получить существенный экономический эффект без дополнительных материальных затрат. На концептуальном и математическом уровнях такая задача обычно сводится к задаче дискретного программирования, в частности, к такой известной комбинаторной задаче как задача коммивояжера. Задача коммивояжера была поставлена более 200 лет назад. Для ее решения предложены различные точные алгоритмы, базирующиеся на методе ветвей и границ и методе динамического программирования, а также разработан ряд эвристических алгоритмов. Однако до настоящего времени не создано эффективных методов ее решения, позволяющих получать практически приемлемое решение для реальных задач большой размерности. Целью настоящей курсовой работы является количественное исследование, ориентированное на применении Intel-совместимых ЭВМ, реальной производственной ситуации, возникающей при переналадке автоматических линий с помощью методов, применяемых при решении задачи коммивояжера. Для достижения этой цели, в работе решаются следующие задачи: на основе содержательного описания исследуемой операции, предлагается ее концептуальная модель и дается математическая постановка задачи; для предложенного метода решения разрабатывается его подробный алгоритм и структурная схема; для Intel-совместимой ЭВМ составляется и отлаживается программа и выполняется количественное исследование операции с помощью ручных и машинных расчетов.

1. Постановка задачи

1.1 Качественное описание исследуемой операции

На автоматической линии обрабатывается партия из n деталей - А, А+1,… А+n-1. Время наладки линии для обработки Аi детали зависит от того, какая деталь обрабатывается перед этим. Совокупность времен переналадки представлена в виде матрицы || tij ||, где tij- время переналадки линии с обработки Аi детали на обработку Аj детали; i , j. Необходимо определить порядок обработки деталей, при котором затраты времени на переналадку автоматической линии минимальны. При этом следует учесть, что обработка деталей ведется по партиям и по окончании обработки последней детали партии автоматическая линия должна быть переналажена на выпуск первой детали партии. Поставленную задачу решить методом ветвей и границ и методом полного перебора. Задачу необходимо решить для следующих данных:

1.2 Концептуальная модель операции

Исходная задача может быть представлена как задача коммивояжера, которая формулируется следующим образом:

Задано n городов иматрица расстояний между ними. Коммивояжер должен посетить каждый из городов один и только один раз и вернуться в исходный пункт, причем его маршрут должен быть таким, чтобы минимизировать суммарную длину пройденного пути.

Математическая постановка задачи

Вводятся переменные /1/:

Хij = 1, - если коммивояжер переезжает из Аi в Аj;

Хij = 0, - в противном случае.

Тогда необходимо минимизировать функционал суммарной длины маршрута:

(4.1)

при условиях

(4.2)

(4.3)

, (4.4)

где ui , uj - произвольные целые и неотрицательные числа. Условие (4.2) означает, что коммивояжер выезжает из каждого города ровно один раз, а условие (4.3) - что он въезжает в каждый город ровно один раз. Условия (4.4) в аналитической форме отражают цикличность маршрута. Нетрудно доказать что для любого цикла можно найти ui, удовлетворяющие условию (4.3) . Пусть ui = Р, если коммивояжер посещает город Аi на p-м этапе. Тогда при xij = 0 для всех i,j выполняется условие 2, а при хij=1 условие (4.3) превращается в равенство, т.к. ui - u j + (n - 1) xij = Р - (Р + 1) + (n - 1) = n - 2.

2. Алгоритмизация решения задачи

2.1 Анализ методов решения задачи

Метод прямого перебора для задачи коммивояжера с n городами основан на генерации n перестановок, определении на каждой перестановке суммарной длины пути и выборе в качестве оптимальной - перестановки с минимальной длиной пути. Для генерации перестановок целесообразно использовать алгоритм реупорядочения перестановочного хвоста (алгоритм - 1) /9/. К положительным сторонам этого метода следует отнести его простоту, обозримость, а также принципиальную возможность получения на гипотетической ЭВМ решение для задачи любой размерности. Основным недостатком рассматриваемого метода является стремительное возрастание количества перестановок при возрастании n. Так, при n = 10, количество перестановок равно 8628800. Этот недостаток существенно ограничивает использование данного метода для решения практических задач на реальных ЭВМ.

Существенно уменьшить количество вариантов при определенных исходных данных позволяет алгоритм Литтла, являющийся развитием метода ветвей и границ применительно к задаче коммивояжера /1/. Сущность метода состоит в том, что множество всех планов разбивается на два подмножества, первое из которых, содержит планы с непосредственным переходом из n - го города в l - й, а второе подмножество содержит планы с переходом из n-го города в l - й через промежуточные города. Для каждого подмножества вводится нижняя оценка и в качестве перспективного выбирается подмножество с минимальной оценкой. Перспективное подмножество аналогично разбивается на два подмножества, и для выбора нового перспективного подмножества сравниваются нижние оценки вновь сконструированных подмножеств с нижней оценкой подмножества, отброшенного на первом этапе. Процесс ветвления продолжается до тех пор, пока не будет получена совокупность перспективных пар, образующих замкнутый цикл длиной n . Основной недостаток данного метода - зависимость количества выполняемых операций не только от размерности матрицы расстояний, но и от значений элементов этой матрицы. Следует отметить, что при некоторых значениях элементов матрицы расстояний метод ветвей и границ по количеству операций совпадает с методом прямого перебора. Кроме того, при машинной реализации этого метода необходимо хранить преобразованные матрицы расстояний для всех конкурирующих подмножеств, что значительно повышает требования к объему памяти ЭВМ. В то же время на современном этапе развития теории дискретного программирования метод ветвей и границ является наиболее приемлемым для точного решения задачи коммивояжера при небольших значениях n . Подробное описание этого метода приведено в /1/.

2.2 Описание метода ветвей и границ

Решение задачи предварительный этап и итерации.

Предварительный этап.

На предварительном этапе происходит переход от матрицы С к матрице С0 - характеризующуюся тем что в каждой строке и в каждом столбце существует нулевое значение, эти элементы являются претендентами включения в оптимальный маршрут, для получения матрицы С0 выполняют следующие шаги:

Шаг 1. В каждой i-й строке матрицы С находят минимальный элемент hi = min cij и j образуют ||c'ij||, у которой c'ij = cij - hi, таким образом, в каждой строке присутствует хотя бы один нулевой элемент.

Шаг 2. В матрице C' для каждого столбца находят минимальный элемент, и происходит переход к матрице ||C0|| => cij=c'ij-hj. Константы hi, hj называют константами приведения.

Шаг 3. Вычисляется сумма констант приведения

Hо =

Процесс перехода от матрицы С к матрице C0 называют процессом приведения.

Этап 1.

На этом этапе формируется исходное множество Gо и находиться матрица Со, нижняя оценка (Gо) и два подмножества Р и .

Шаг 1. Исходное множество Gо или множество решений задачи коммивояжера представляет собой множества всех возможных решений, перестановок из n чисел. Общее количество таких перестановок равно n!. В качестве характеристики используют матрицу C0, которая была получена на предварительном этапе при реализации процедуры приведения.

Шаг 2. Вычисляется нижняя оценка исходное множество Gо. Она равна сумме приводящих констант:

(Gо)= Hо =

Если из нулевых элементов матрицы Со можно сформировать замкнутый маршрут, то его длинна совпадает с суммой приводящих констант, а элементы, входящие в этот маршрут, образуют оптимальное решение.

Шаг 3. Исходное множество G0 делится на два непересекающихся подмножества G и G (рис.1.).

Подмножество G содержит все маршруты с переходом из r-го города в m-й, а подмножества G- все остальные переходы. Пара (r, m) называется перспективной.

Рис. 1 - Деление исходного множества

Концепция выбора перспективной пары:

Шаг 1. Длина непосредственного перехода между городами, входящими в перспективную пару, должна быть минимальной, т.е. элемент с`о (r, m) = 0;

Шаг 2. Длина опосредованного пути стремится к максимуму. Опосредованный путь между r и m - путь проходящий из r в m через другие города.

Этап 2.

На втором этапе определяется характеристики подмножества G2 , а именно матрица С, и нижняя оценка подмножества G,

Шаг 1. Подмножество G содержит все перестановки, в которых отсутствует переход (r,m) очевидно, что матрица C должна отображать это свойство подмножества. C- получается путем преобразования C0, для этого элемент с координатами r, m приравнивают к бесконечности.

К этой матрице применяется процедура приведения, и значение суммы приводящих констант равно Н. В результате получается матрица С.

Шаг 2. Определяется нижняя оценка множества G,

( G) = (Go) + H = (Go) + (r, m).

Этап 3.

Определение характеристики множества G, матрица C и нижняя оценка.

Шаг 1. Для получения матрицы С необходимо:

1) В матрице Со вычеркнуть r-ю строку и m-й столбец. Вычеркивание r-й строки означает, что коммивояжер больше не должен выезжать из r-го города не в какой другой город, а вычеркивание m-го столбца указывает на то, что коммивояжер не должен выезжать в m-й город не из какого другого города;

2) Необходимо элемент с координатами (m,r) приравнять к бесконечности для исключения образования локальных циклов типа (r,m,r). В дальнейшем такие замкнутые подциклы называются короткими.

В результате этих преобразований получаем матрицу в результате преобразований получается матрица C=||c(i, j) ||, для получения окончательной матрицы необходимо выполнить процедуру приведения.

Шаг 2. Вычисляется нижняя оценка множества G,

о (G)= о (G0) + H .

Этап 4.

На этом этапе происходит сравнение нижних оценок конкурирующих между собой подмножеств G и G, в качестве перспективного выбирается подмножество, имеющее минимальную нижнюю оценку. После этого выполняется переход на первую итерацию, состоящую в том, что выбранное перспективное подмножество, например G, (рис. 1.3) делиться на два непересекающихся подмножества G и G. В качестве конкурирующих рассматривается как вновь образованные, так и ранее отброшенные на предыдущем этапе, как неперспективное подмножество G.

Все конкурирующие подмножества переобозначаются, как G, G и G.

Рис. 2

2.3 Описание метода прямого перебора

Концепция решения задач методом прямого перебора.

Этот метод предполагает генерацию множества возможных решений, вычисление целевой функции для каждого из решений и выбор решения, имеющего минимальное значение целевой функции. Элементами решения являются: перестановки, сочетания, размещения, либо иные комбинаторные упорядочения элементов. Трудоемкость генерации вариантов резко возрастает при увеличении размерности задачи, поэтому этот метод в основном используется либо в сочетании с другими методами, либо для проверки точности эвристических методов для малой размерности задачи планирования. Основная сложность при реализации этого метода состоит в генерации множества перестановок, сочетаний и размещений.

Алгоритм формирования перестановок на основе упорядоченных пар

Определение 1. Два числа ik,,ik+l называются упорядоченной парой при условии, что ik+l > ik.

Определение 2. Первое число упорядоченной пары называется обрывающим числом.

Определение 3. Хвостом перестановки п из п чисел называется последовательность чисел, начиная с последнего числа до первого обрывающего числа:п = (i1, i2, ..., ik, ik+l, ..., i„). Собственно обрывающее число в хвост перестановки не включается.

Шаг 1. Формируется первоначальная перестановка из п чисел = (l, 2, 3, ..., п) и пересылается в банк сгенерированных перестановок.

Шаг 2. В перестановке находится хвост, в нем определяется минимальное число, но большее, чем обрывающее число.

Шаг 3. Найденные минимальное и обрывающее числа переставляются местами.

Шаг 4. Полученный хвост упорядочивается в порядке возрастания чисел. После упорядочения результат направляется в банк сгенерированных перестановок. Производится проверка: все ли перестановки сгенерированы. Если не все, то переход на шаг 2. Исходными данными для шага 2 являются результаты, полученные на шаге 4.

Замечание. Минимальное число, найденное в хвосте перестановки, должно быть больше, чем обрывающее число. Если это условие не выполняется, то происходит поиск следующего по возрастанию числа.

2.4 Проектирование сценария диалога

В итоговой программной реализации необходимо предусмотреть следующие возможности: ввод и редактирование количества городов; ввод и редактирование матрицы расстояний; вывод оптимального значения пути для посещаемых городов; вывод последовательности посещения городов.

2.5 Описание структур данных

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

Таблица 1- Описание структуры Matrix

Для хранения информации о всех подмножествах была создана структура CitiesSet . Все поля структуры описаны в таблице 2.

Таблица 2 - Описание структуры CitiesSet

Для хранения информации о пройденном пути была создана структура Couple. Все поля структуры описаны в Таблице 3.

Таблица 3 - Описание структуры Couple

Размещено на http://www.allbest.ru/

[Введите текст]

Рис. 4 - Блок-схема алгоритма решения задачи

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

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

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

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

-> ->

->

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

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

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

задача решение метод перебор

В ходе выполнения курсовой работы, была разработана автоматизированная система, позволяющая находить оптимальный путь выпуска продукции с целью сокращения времени переналадки автоматизированной линии. Полученная программа имеет простой и удобный в использовании графический интерфейс, выполняющийся в среде операционной системы 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; //возвращение указателя на первый элемент

}

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

{

for(unsigned int i=0;i<num;i++) //проходим по всем переходам

for(unsigned int j=i;j<num;j++)

{

if(CC[i].cb==CC[j].ca) //и ставим их в нужном порядке

{

Couple t=CC[j];

CC[j]=CC[i+1];

CC[i+1]=t;

}

}

for(unsigned int i=0;i<num-1;i++) //проверяем получился ли список

if(CC[i].cb!=CC[i+1].ca)

{

ksi=32720;

next->ksi=32720;

return 1;

}

return 0;

}

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

unsigned char Yes=0;

void fin(FILE *in, char **T)

{

unsigned i,j;

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

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

{

int tmp;

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

T[i][j]=tmp;

}

void TForm1::Next(unsigned *A)

int i=num-1; unsigned t;

while((i>0)&&(A[i]>A[i+1]))

i--;

if(i>0)

int j=i+1;

while((j<num)&&(A[j+1]>A[i]))

j++;

t=A[i];

A[i]=A[j];

A[j]=t;

int jn= (num+i)/2;

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

{

t=A[j];

A[j]=A[num-j+i+1];

A[num-j+i+1]=t;

}

Yes=1;

}

else

Yes=0;

}

void TForm1::poln(char* fn)

{

unsigned i,j;

FILE *in;

in=fopen(fn,"r");

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

char **T= new char*[num];

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

T[i]=new char [num];

fin(in,T);

fclose(in);

unsigned *A= new unsigned [num+1];

unsigned *Amin=new unsigned [num+1];

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

A[i]=i;

unsigned long Smin=4294967295, S;

do

{

S=0;

S+=T[A[num]-1][A[1]-1];

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

{

S+=T[A[i]-1][A[i+1]-1];

}

if(Smin>S)

{

Smin=S;

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

Amin[j]=A[j];

Next(A);

while (Yes);

AnsiString s="<"+IntToStr(Amin[1]);

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

s.cat_sprintf(", %d",Amin[i+1]);

s.cat_sprintf(", %d>",Amin[1]);

Memo1->Text=s;

Label6->Caption=IntToStr(Smin);

delete[] A;

delete[] Amin;

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

delete[] T[i];

delete[] T;

}

Размещено на Allbest.ru