Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Мельникова, Елена Анатольевна

• Мельникова, Елена Анатольевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Мельникова, Елена Анатольевна

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

1.1. Постановка задан дискретной оптимизации

1.2. О возможных подходах к решению

1.3. Задачи дискретной оптимизации - более подробное описание

1.4. Жадные эвристики и метод ветвей и границ

1.5. Возможный мультиэвристический подход

Глава 2.

Описание оригинального алгоритма кластеризации и некоторые предметные области его применения

2.1. Введение

2.2. Описание алгоритма кластеризации

2.3. Некоторые другие предметные области применения

2.4. Пример метрики для задачи вершинной минимизации недетерминированных конечных автоматов

Введение диссертации (часть автореферата) на тему «Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации»

3.2. Об одном подходе к организации незавершённого метода ветвей и границ

38

3.3. Описание общего алгоритма 41

3.4. Предлагаемый подход к сравнительной оценке качества эвристических алгоритмов 43

3.5. Заключение главы 45

Глава 4.

Применение кластеризации ситуаций в задачах дискретной оптимизации 45

4.1. Введение 45

4.2. Задача вершинной минимизации НКА - некоторые результаты счёта 48

4.3. Задача минимизации ДНФ: «матричная метрика» и некоторые результаты счёта 51

4.4. Задача коммивояжёра — «матричная метрика» и результаты счёта 55 4.6. Заключение главы 57

Глава 5.

Кластеризация ситуаций и сопутствующие алгоритмы в недетерминированных играх 59

5.1. Введение 59

5.2. Предварительные сведения 61

5.3. Общие эвристики в недетерминированных играх 65

5.4. Некоторые вспомогательные эвристики 68

5.5. Подход к построению статической оценки с использованием нейросети 69

5.6. Пример использования алгоритма обработки вершин 71

5.7. Заключение главы 76

Глава 6.

Возможный подход к реализации алгоритмов с помощью объектноориентированного программирования 78

6.1. Введение 78

6.2. Программная реализация одной несложной «олимпиадной» проблемы 78

6.3. Подход к программной реализации задачи вершинной минимизации недетерминированных конечных автоматов 86

6.4. Заключение главы 92

Заключение 92

Приложения 93 Приложение А.

Текст программы минимизации недетерминированных конечных автоматов

95

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

Часть текста программы решения задачи коммивояжёра 123

Литература 146

Введение

Большинство задач дискретной оптимизации являются труднорешаемыми, т.е. на сегодняшний день для них нет алгоритмов, решающих такие задачи за время, ограниченное некоторым полиномом относительно размера входных данных, и возможно, таких алгоритмов не существует вообще. Трудными также считаются задачи, для которых полиномиальная разрешимость доказана — однако (пока) неизвестны полиномиальные алгоритмы небольших степеней. В то же время оптимизационные задачи выступают в качестве моделей для огромного количества практических задач, возникающих в самых разных сферах практической деятельности. Для эффективного решения задач реальных размерностей применение точных алгоритмов на практике невозможно, поскольку требуют слишком больших затрат машинного времени и памяти. К настоящему времени разработано значительное количество методов для решения задач дискретной оптимизации. Однако решение практических задач требует поиска новых, более эффективных моделей и алгоритмов поиска точных и приближенных решений. Таким образом; исследования в области алгоритмизации труднорешаемых задач остаются по-прежнему актуальными, а их результаты имеют большое практическое значение.

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

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

Основные задачи исследования:

• модификация модели вычислений, представляющей собой незавершенный метод ветвей и границ,

• разработка подхода к формированию метрик на множестве подзадач в различных задачах дискретной оптимизации,

• разработка оригинального алгоритма кластеризации ситуаций в задачах дискретной оптимизации,

• разработка и реализация эвристических алгоритмов для решения задач дискретной оптимизации с применением кластеризации ситуаций,

• разработка подхода для создания соответствующих компьютерных программ.

Объектом исследования являются несколько конкретных задач дискретной оптимизации(3 Д О):

• вершинная минимизация недетерминированных конечных автоматов(НКА),

• минимизация дизъюнктивных нормальных форм (ДНФ),

• псевдогеометрическая версия задачи коммивояжёра(ЗКВ),

• игровые программы для недетерминированных игр (версии бэкгеммона). Научная новизна

Разработанный алгоритм кластеризации 'является новой модификацией алгоритма из группы "Hierarchical Clustering Algorithms". Новизна мультиэвристического метода решения задач дискретной оптимизации состоит в применении комплекса эвристик, в том числе кластеризации подзадач на основе разработанных автором метрик. Предложен также подход к разработке компьютерных программ на основе этого метода. Также новыми являются эвристики, предназначенные для работы с деревом перебора в недетерминированных антагонистических играх

Практическая значимость исследования

Разработанные подходы позволяют повысить эффективность работы эвристических алгоритмов для решения задач дискретной оптимизации. Полученные результаты могут быть применены практически для любой оптимизационной задачи.

Краткое содержание

Диссертация состоит из введения, 6 глав, 2 приложений. В первой главе диссертации содержится описание задач дискретной оп-тимизации и применяемых методов их решения - как классических, так и раз-работанных автором диссертации. Вторая глава посвящена предлагаемому алгоритму кластеризации. Здесь приведены данные о самом алгоритме; в частности, даны ссылки на схожие алгоритмы, разрабатываемые другими авторами. Кратко рассмотрены некоторые возможные прикладные области практического применения подобных алгоритмов. Также приведены априорные эвристические обоснования применения авторского алгоритма для работы «по аналогии» с подзадачами (ситуациями), получаемыми,в процессе решения.различных задач дискретной оптимизации.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Мельникова, Елена Анатольевна

ввода

CMatrix (int mD) : CMatr(mD) { InitMemoryMatrix(); } обычный конструктор CMatrix (CMatrix* copy); практически - конструктор копии virtual -CMatrix (); деструктор void SetLin (int ml, int mValue); void SetCol (int mJ, int mValue); int GetLin (int ml); int GetCol (int mJ); bool SetByNumbers (int ml, int mJ, int nValue);• friend istream& operator» (istreamS is, CMatrix& matrix) ; ввод матрицы из файла friend istreamS operator»= (istreamS is, CMatrixS matrix) ; // другой вариант ввода матрицы из файла; см. текст методов friend ostreams operator« (ostreamS os, CMatrixS matrix); вывод матрицы в файл int GetNumLinByNumber (int numLin); * int GetNumColByNumber (int numCol); private: void InitMemoryMatrix (); void InitFirstLinCol (); bool operator== (CMatrixS first, CMatrixS second); проверяет только равенство №№ всех строк и столбцов double operatorss (CMatrixS first, CMatrixS second); // "матричная" метрика

Работа с матрицей для ЗКВ, срр-файл ///////

CMatrix::CMatrix (CMatrix* copy) : CMatr(copy) {

InitMemoryMatrix(); for (int i=l; i<=mDim; i++) { SetLin(i,copy->GetLin(i)); SetCol(i,copy->GetCol(i) ) ;

CMatrix::-CMatrix () { delete arrNumLin; delete arrNumCol; void CMatrix::SetLin (int ml, int mValue) { ASSERT(mDim>=2 && ml>=l && mI<=mDim); arrNumLin->SetAt(Makelndex(ml),mValue); void CMatrix::SetCol (int mJ, int mValue) { ASSERT(mDim>=2 && mJ>=l && mJ<=mDim); arrNumCol->SetAt(Makelndex(mJ),mValue); int CMatrix::GetLin (int ml) {

ASSERT(mDim>=2 && ml>=l && mI<=mDim); return arrNumLin->GetAt(Makelndex(ml)); int CMatrix::GetCol (int mJ) {

ASSERT(mDim>=2 && mJ>=l && mJ<=mDim); return arrNumCol->GetAt(Makelndex(mJ)); bool CMatrix::SetByNumbers (int ml, int mJ, int nValue) int i = GetNumLinByNumber(ml); if (i<=0 || i>mDim) return false; строки с таким № может просто уже не быть int j = GetNumColByNumber(mJ); if (j<=0 || j>mDim) return false; // аналогично ' Set(i,j,nValue); return true; istreams operator» (istream& is, CMatrix& matrix) { is » matrix.mDim; is.ignore(1); matrix.InitMemoryMatr(); matrix.InitMemoryMatrix(); for (int j=l; j<=matrix.mDim; j++) { int n; is » n; matrix.SetCol(j,n); for (int i=l; i<=matrix.mDim; i++) { int n; is » n; matrix.SetLin (i,n); for (j=l; j<=matrix.mDim; j++) { IgnoreSpaces (is); if (is .peek ()=='*') { is.ignore(3); n = Getlnfty(); else is » n; matrix.Set(i,j,n); return is; double Delta (double XI,double Yl,double X2,double Y2) { return sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); istreamS operdtor»= (istream& is, CMatrixs matrix) { is » matrix.mDim; matrix.InitMemoryMatr(); matrix.InitMemoryMatrix(); for (int i=l; i<=matrix.mDim; i++) { matrix.SetLin(i,i); matrix.SetCol (i,i); for (i=l; i<=matrix.mDim; i++) { int n; is » n; if (i!=n) { cout « "bad input"; exit(l); } is » matrix.rXX[i-1] >> matrix.rYY[i-1]; double rMax = 0.0; for (i=l; i<=matrix.mDim-l; i++) for (int j=i+l; j<=matrix.mDim; j++) rMax = max( rMax, Delta( matrix.rXX[i-l],matrix.rYY[i-l], matrix.rXX[j-1],matrix.rYY[j-l])); for (i=l; i<=matrix.mDim; i++) { matrix.Set(i,i,Getlnfty()); for (int j=i+l; j<=matrix.mDim; j++) { double r = Delta( matrix.rXX[i-1],matrix.rYY[i-l], matrix.rXX[j-1],matrix.rYY[j-1]) / rMax ; int n = Boundslnt(int(r*999999),0,999999); matrix.Set(i,j,n); matrix.Set(j,i,n); return is; ostreams operator« (ostreams os, CMatrix& matr) { os « setw(3) « matr.mDim « ":"; for (int j=l; j<=matr.mDim; j++) os « setw(7) « matr.GetCol(j); os « endl; for (int i=l; i<=matr.mDim; i++) { os « setw(3) « matr.GetLin(i) « " "; for (j=l; j<=matr.mDim; j++) { int n = matr.Get(i,j) ; if (ISlnfty(n)) OS « " ******"; else os « setw(7) « n; os « endl; return os; bool operator== (CMatrix& first, CMatrixs second) { int nDim = first.GetDim(); if (nDim!=second.GetDim ()) return false; for (int i=l; i<=nDim; i++) { if (first.GetLin(i)!=second.GetLin(i)) return false; if (first.GetCol(i)!=second.GetCol(i)) return false; return true; const double rMax = 1000000.0; для перевода целых в вещественные; (по смыслу 1000000 - это "единица", длина стороны квадрата double operator&& (CMatrixs first, CMatrixs second) { int nDim = first.GetDim(); // if (nDim!=second.GetDim ()) MyError(1); double rBadness = 0.0; for (int j=l; j<=nDim; j++) if first.GetNumColByNumber(j)*second.GetNumColByNumber(j)<0) // столбец присутствует ровно в одной матрице rBadness += double(nDim); for (int i=l; i<=nDim; i++) { int ml = first.GetNumLinByNumber(i), m2 = second.GetNumLinByNumber (i); if (ml*m2<0) { // строка присутствует ровно в одной матрице rBadness += 2.0*double(nDim); continue; for (int j=l; j<=nDim; j++) { int nl = first.GetNumColByNumber(j), n2 = second.GetNumColByNumber(j); if (nl<0 I I n2<0) continue; double rl = first.Get(ml,nl)/rMax; ведь сами значения - double double r2 = second.Get(m2,n2)/rMax; rBadness += min (abs (rl-r2) , 1". 414) ; не имеет смысла считать, что ухудшение больше // диагонали квадрата - даже в пседогеометр. случае return rBadness; void CMatrix::InitMemoryMatrix () {

ASSERT(mDim>=2); arrNumLin = new CUIntArray; arrNumLin->SetSize(mDim); arrNumCol = new CUIntArray; arrNumCol->SetSize (mDim) ; int CMatrix::GetNumLinByNumber (int numLin) { for (int i=l; i<=mDim; i++) if (arrNumLin->GetAt(Makelndex(i) ) ==numLin) return i; return -1; int CMatrix::GetNumColByNumber (int numCol) { for (int j=l; j<=mDim; j++) if (arrNumCol->GetAt(Makelndex(j))==numCol) return j; return -1; void CMatrix::InitFirstLinCol () { ASSERT(mDim>=2); for (int i=l; i<=mDim; i++) { SetLin(i,i); SetCol(i,i);

Работа с подзадачей для ЗКВ, h-файл //////////////// CTask - задача с методами переборного решения class CTask { protected: int mDim; CMatrix* matr; CPairArray* parr; int nOtvet; public:

CTask (); // применяется только для последующего ввода CTask (int mD) ; генерация «пустой» задачи заданной размерности CTask (CMatrix* matrlnit); аналог конструктора копии CTask (int mD, CMatrix* matrlnit, CPairArray* parrlnit); полная инициализация virtual -CTask () ; деструктор int GetDim () { return mDim; }

CMatrix* GetMatr () { return matr; } CPairArray* GetParr () { return parr; } void Random () { matr->Random(); } случайная генерация void RandomMetric2 () { matr->RandomMetric2(); } случайная генерация 2-мерного геометрического варианта void RandomQuasiMetric2 () matr->RandomQuasiMetric2(); } // случайная генерация 2-мерного псевдогеометрического варианта virtual void IncLimit (int nine){ } // nothing to do virtual int GetOtvetForPrint () { return nOtvet; } friend istreamS operator» (istreams is, CTaskS task) ; friend ostreams operator« (ostreams os, CTask& task) ; void AddPair (int mF, int ml) { parr->Add(mF,mI); } // virtual незачем void PrintWell (ostreams os) { parr->PrintWell (os); } переборный метод(упрощённый), void RunSearch (); переборный метод с элементами выбора 0 из МВГ void RunStek (); protected: int Minus (); void RunStek (int mDeep, int nCostTmp, CPairArray* parrTmp); private: int MakeCost (CPermutation* P) ; ;

Работа с подзадачей для ЗКВ, ерр-файл extern int nBest; // стоимость текущего псевдооптимального решения ////////////// CTask - задача с методами переборного решения

CTask::CTask () { matr = new CMatrix; parr = new CPairArray;

CTask::CTask (int mD) { mDim = mD; matr = new CMatrix(mDim); parr = new CPairArray; nOtvet = Getlnfty();

CTask::CTask (CMatrix* matrlnit) { mDim = matrInit->GetDim(); matr = new CMatrix(matrlnit) ; parr = new CPairArray; nOtvet = GetlnftyO;

CTask::CTask (int mD, CMatrix* matrlnit, CPairArray* parrlnit) { mDim = mD; matr = new CMatrix(matrlnit); parr = new CPairArray; parr->Copy(parrlnit);

CTask::~CTaski() { if (matr ! =NULL) delete matr; if (parr!=NULL) delete parr; istreamS operator» (istreams is, CTasks task) { is » *(task.matr); task.mDim = task.matr->GetDim(); is » *(task.parr); is.ignore(10,1\n'); IgnoreSpaces(is); if (is.peek()!=•+') is » task.nOtvet; else task.nOtvet = Getlnfty();

IgnoreSpaces(is); is.ignore(1000,'\n'); return is; ostream& operator<< (ostream& os, CTask& task) { os « *(task.matr) « * (task.parr) « endl; if (!Islnfty(task.nOtvet)) os « task.nOtvet; os « " +-F+" « endl; task.PrintWell(os); os « " +++" « endl; return os; void CTask::RunSearch () { parr->DeleteAll();

CPermutation* perm = new CPermutation(mDim-1); nOtvet = Getlnfty(); for (;;) { int newCost = MakeCost(perm); if (newCostCnOtvet) { nOtvet = newCost; parr->DeleteAll(); parr->Add(perm->GetPerm(mDim-1),mDim); parr->Add(mDim,perm->GetPerm(1)); for (int i=l; i<=mDim-2; i++) parr->Add(perm->GetPerm(i),perm->GetPerm(i+1)) if (!perm->MakeNext()) break; delete perm; void CTask:-.RunStek' () { nOtvet = Getlnfty(); parr->DeleteAll();

CPairArray* parrTmp = new CPairArray; RunStek(0,0,parrTmp); delete parrTmp; int CTask::Minus () { int nRet = matr->Minus(); if (!Islnfty(nRet)) IncLimit(nRet); return nRet; void CTask::RunStek (int mDeep, int nCostTmp, CPairArray* parrTmp) { if (nCostTmp>=nOtvet) return; if (mDeep>=mDim) { nOtvet = nCostTmp; parr-^-NewCopy (parrTmp) ; return;

CMatr* matrDoublel = new CMatr(matr); // matrDoublel -исходная

CPredictor* pred = new CPredictor(mDim); int n = Minus(); // *matr меняется if ( !Islnfty(n)) nCostTmp += n;

CMatr* matrDouble2 = new CMatr(matr); // matrDouble2 - после Minus() int k,iMax,jMax,iMaxLin,jMaxCol; if (nCostTmp>=nOtvet) Return; pred->SetGoodman(*matr); for (;;) { if (!pred->GetMax(iMax,jMax)) goto Return; if (matr->Get(iMax,jMax)!=0) goto Return; iMaxLin = matr->GetLin(iMax); jMaxCol = matr->GetCol(jMax); bool bl = mDeep>=m.Dim-l; bool b2 - parrTmp->IsPath(jMaxCol,iMaxLin); if (bl==b2) break; pred->Set(iMax,jMax,-1); теперь идём в глубину по рекурсии; сначала - правая задача for (k=l; k<=mDim; k++) { matr->Set(iMax,k,Getlnfty()); matr->Set(k,jMax,Getlnfty()); parrTmp->Add(iMaxLin,jMaxCol); RunStek(mDeep+1,nCostTmp,parrTmp); теперь возвращаемся в состояние до вызова правой задачи parrTmp->DeleteLast() ; matr->Copy(matrDouble2) ; теперь правая задача matr->Set(iMax,jMax,Getlnfty());

RunStek(mDeep,nCostTmp,parrTmp); matr->Set(iMax,jMax,0);

Return: delete pred; delete matrDouble2; matr->Copy(matrDoublel); delete matrDoublel; int CTask::MakeCost (CPermutation* P) { int nCost = matr->Get(P->GetPerm(mDim-l),mDim) matr->Get(mDim,P->GetPerm(1)); for (int i=l; i<=mDim-2; i++) nCost += matr->Get(P->GetPerm(i),P->GetPerm(i+1)); return nCost; class CTaskMVG : public CTask { такая организация данных позволяет выполнять парал. обработку, вызывая любой из методов (прежде всего - Run()) // из любой получающейся дочерней подзадачи private: int nLimit; // граница bool bMade; // признак полностью обработанной матрицы

CPairArray* ways; public:

CTaskMVG (); // применяется только для последующего ввода CTaskMVG (int mD) : CTask(mD) { InitMVGO; }

CTaskMVG (CMatrix* matrlnit) : CTask (matrlnit) { InitMVGO; } CTaskMVG (int mD, CMatrix* matrlnit, CPairArray* parrlnit, int nL, CPairArray* wayslnit); // полная инициализация void InitMVG () { nLimit = 0; bMade = false; ways = new

CPairArray; } virtual -CTaskMVG () { delete ways; } friend istreamS operator» (istreamS is, CTaskMVGs tmvg) ; friend ostreams operator« (ostreamS os, CTaskMVGs tmvg); void AddPair (int mF, int ml); // virtual незачем friend bool operator< (CTaskMVGs first, CTaskMVGs second); void SetLimit (int nL) { nLimit = nL; } virtual void IncLimit (int nine){ nLimit += nine; } int GetLimit () { return nLimit; } bool ExistsOtvet () { return bMade; } virtual int GetOtvetForPrint () { return nLimit; } ПЕРЕБОРНЫЙ МЕТОД void RunStek (); применение родительского RunStek() и настройка своих полей // Классический метод ветвей и границ в двух следующих функциях считаем, что матрица приведна // такими же оставляем и получившиеся матрицы. CTaskMVG* MakeGoodmanRight (bool bSimmetric); // классический выбор нуля private: bool GoodmanForRight (ints iMax, ints jMax); CTaskMVG* MakeRight (int ml, int mJ, bool bSimmetric); public: bool RunDim2 (); bool RunMemo (bool bMain, bool bMetric); bool RunMemoDisk ();

Работа с подзадачей для ЗКВ с использованием МВГ, ерр-файл ////////////// CTask - задача с методами переборного решения

CTaskMVG::CTaskMVG () : CTask () { ways = new CPairArray;

CTaskMVG::CTaskMVG (int mD, CMatrix* matrlnit, CPairArray* parrlnit, int nL, CPairArray* wayslnit) : CTask(mD,matrlnit,parrlnit) { InitMVG(); nLimit = nL; ways->Copy(wayslnit); istreamS operator» (istreamS is, CTaskMVG& tmvg) { CTasks task = tmvg; is » task; is » tmvg.nLimit; int n; is » n; tmvg.bMade = n==l; is » *(tmvg.ways); return is; ostreams operator« (ostreams os, CTaskMVGS tmvg) { CTasks task = tmvg; os « task; os « tmvg.nLimit « " " « tmvg.bMade « endl; os « *tmvg.ways « endl; return os; void CTaskMVG: :AddPair (int mF, int ml) '{ parr->Add(mF,mI); ways->Add(mF,mI); //int n = ways->CombineLast(); int mFW,mIW; if ( !ways->CombineLast (mFW,mIW)) return; matr->SetByNumbers(mIW,mFW,Getlnfty()); matr->SetByNumbers(mIW,mF, Getlnfty()); matr->SetByNumbers(ml, mFW,Getlnfty() ) ; matr->SetByNumbers(ml, mF, Getlnfty()); /* ниже - более подробный вариант for (;;) { matr->SetByNumbers(ml,mFromWay, Getlnfty()); if (mFromWay==mF) break; mFromWay = parr->GetIntoByFrom(mFromWay); if (mFromWay<=0) break; // in case for (;;) { matr->SetByNumbers(mIntoWay,mF,Getlnfty ()) ; if (mIntoWay==mI) break; mlntoWay = parr->GetFromByInto(mlntoWay); if (mIntoWay<=0) break; // in case */ bool operator< (CTaskMVG& first, CTaskMVG& second) { int nl = first.GetLimit(), n2 = second.GetLimit(); int ml = first.GetDim(), m2 = second.GetDim(); return (nl/10000+ml/300) < (n2/10000+m2/300);

CTaskMVG* CTaskMVG::MakeGoodmanRight (bool bSimmetric) { // считаем, что размерность достаточно велика int ml, mJ; if ( !GoodmanForRight(ml,mJ)) return NULL; return MakeRight(ml,mJ,bSimmetric); bool CTaskMVG::GoodmanForRight (int& iMax, int& jMax) { // считаем, что размерность достаточно велика Minus (); CTask::RunStek())

CPredictor pred(mDim); // ВНИМАНИЕ! Далее 2 варианта но SetGoodmanPlus можно выбирать только в случае установленных координат! pred.SetGoodman(*matr); //pred.SetGoodmanPlus(*matr,*parr); int iMaxL^n,jMaxCol; for (;;) { if (!pred.GetMax(iMax,jMax)) return false; if (matr->Get(iMax,jMax)!=0) return false; // in case iMaxLin = matr->GetLin(iMax); jMaxCol = matr->GetCol(jMax); if ( !parr->IsPath(jMaxCol,iMaxLin)) break; if (!ways->IsPathSimple(jMaxCol,iMaxLin)) return true; pred.Set(iMax,jMax,-1);

CTaskMVG* CTaskMVG::MakeRight (int ml, int mJ, bool bSimmetric) { if (this->matr->Get(mI,mJ)!=0) return NULL; // формирование матрицы для левой подзадачи CTaskMVG* taskRet = new CTaskMVG(mDim-1); for (int i=l; i<=mDim; i++) if (i!=ml) { int il = i<ml ? i : i-1; taskRet->matr->SetLin(il,this->matr->GetLin(i)); for (int j=l; j<=mDim; j++) if (j!=mj) { int jl = j<mJ ? j : j-1; if (il==l) taskRet->matr->SetCol(jl,this->matr

GetCol(j)); taskRet->matr->Set(il,j1,this->matr->Get(i,j)); taskRet->parr->Copy(this->parr); taskRet->ways->Copy(this->ways); taskRet->AddPair(this->matr->GetLin(ml),this->matr->GetCol(mJ)); taskRet->SetLimit(nLimit); taskRet->Minus(); формирование матрицы для правой подзадачи this->matr->Set(ml,mJ,Getlnfty()); if (bSimmetric) this->matr->Set(mJ,mI,Getlnfty()); this->Minus(); return taskRet; void CTaskMVG::RunStek () { CTask: : Rur^Stek () ; в полной версии - надо вызывать её же с параметрами! bool CTaskMVG::RunDim2 () { int mil = matr->GetLin(1), mJl = matr->GetCol(1), ml2 = matr->GetLin(2), mJ2 = matr->GetCol(2); int nl = !Islnfty(matr->Get(1,1)) && !Islnfty(matr->Get(2,2)) && !parr->IsPath(mJl,mIl) && !parr->IsPath(mJ2,mI2) ? matr->Get(1,1)+matr->Get(2,2) : Getlnfty(); int n2 = !Islnfty(matr->Get(1,2)) && !Islnfty(matr->Get (2,1)) && !parr->IsPath(mJ2,mIl) && !parr->IsPath(mJl,ml2) ? matr->Get(1,2)+matr->Get(2,1) : Getlnfty(); if (Islnfty(nl) && Islnfty(n2)) return false; if (nl<n2)' { AddPair (mil, mJl) ; AddPair (ml2,mJ2) ; IncLimit (nl); else { AddPair(mil,mJ2); AddPair(ml2,mJl); IncLimit(n2) bMade = true; // признак полностью обработанной матрицы return true; bool CTaskMVG::RunMemo (bool bMain, bool. bMetric) {

CTaskMVG* taskThis; if (bMainf { nLimit = 0; taskThis = new CTaskMVG(this->matr); else taskThis = new CTaskMVG(this->GetDim(),this->matr, this->parr,this->GetLimit (),thisways); taskThis->Minus();

CTaskArray array (this->matr, bMain) ; if (!bMetric) array.Add(taskThis) ; else for (int i=0;;i++) {

CTaskMVG* taskRight = taskThis->MakeGoodmanRight(true); array.AddTask(taskRight); // sic! годится и для след.строки if (taskRight==NULL) { delete taskThis; break; } if (!array.Run()) return false; this->nLimit = array.GetOtvet(); // это - для дочерних вызовов this->nOtvet = this->nLimit; this->parr->NewCopy(array.GetPairs() ) ; this->bMade = true; return true;

Кластеризация, h-файл //////////////// ClusterRef - класс с параметризуемым предком // используется для присвоения каждому кластеризуемому элементу // номера кластера, к которому он принадежит template Ctypename type> class ClusterRef : public type { наследование от класса кластеризуемого элемента public: int clnumref; // номер кластера, содержащего элемент ClusterRef () {}

ClusterRef (const type &value):type(value) { clnumref = -1; номер кластера = -1 обозначает, что элемент не принадлежит никакому кластеру.

ClusterRefS operator= (double value) { type::operator = (value); (предполагается, что все элементы вектора-предка // после этого присваивания будут равны value) return *this; ; ///////////// FrogClusterizator - класс, выполняющий кластеризацию template ctypename type> class FrogClusterizator{ public: typedef ClusterRef<type> ClusterElement; protected:

CVariableArray <int> clusters; массив целых чисел, в котором хранятся кластеры, double dist; public:

FrogClusterizator(double adist) { dist = adist; int addCluster () { // добавляем новый кластер в массив clusters int result = clusters.getCount(); clusters.add(result); return result; int normalizeClusters () { нормализация" кластеров - удаляем лишние номера кластеров, оставшиеся после объединения близких кластеров, и перенумеровываем оставшиеся; int maxClNum = clusters.getCount(); int current = -1; if (maxClNum>0) { int *map = new int[maxClNum]; for (int k=0; kCmaxClNum; k++) map[k]=-1; int clCount =clusters.getCount(); for (int k=0; kCclCount; k++) { int civ = clusters[k]; if (map[civ]<0) map[civ] = ++current; clusters[k] = map[civ]; delete [] map; return current+1; forceinline void distrib (ClusterElement &pl, ClusterElement p2) { записываем элементы pi и p2 в свой кластер ClusterElement* pntl = &pl; ClusterElement* pnt2 = &p2; if (pntl->clnumref<0 && pnt2->clnumref<0) { если оба элементы не входят ни в один кластер. int newCluster = addCluster О; pntl->clnumref = pnt2->clnumref = newCluster; .то они образуют новый кластер printf("New Cluster %d added \n",newCluster); return; if (pntl->clnumref>pnt2->clnumref) { swap(pntl,pnt2); if (pntl->clnumref < 0 && pnt2->clnumref>=0) { // если только один из элементов входит в какой-то кластер. pntl->clnumref = pnt2->clnumref; // .то и второй элемент включаем в тот кластер //printf("Cluster %d grow \n",clusters[pntl->clnumref]); return; if (clusters[pntl->clnumref] != clusters[pnt2->clnumref])

7 если оба элемента уже в своих кластерах. int from = clusters[pnt2->clnumref]; int to = clusters[pntl->clnumref]; if (from<to) swap(from, to); printf("Cluster %d with cluster %d \n",from,to); int count = clusters.getCount(); for (int k=0;k<count;k++) // .то объединяем оба кластера в один if (clusters[k]==from) clusters[k]=to; ; //////////////// FrogClusterizatorRTree - класс, выполняющий кластеризацию с помощью R-дерева [101]

Для работы кластеризатора предполагается известной на этапе компиляции арность структуры R-tree. Кластеризатор реализует:

- метод добавления нового элемента, размещающий элемент в R-tree и определяющий кластер, к которому элемент будет принадлежать.

- метод перенумерации кластеров, обеспечивающий нумерацию кластеров без пропусков и сообщающий элементам номера кластеров, к которым они принадлежат.

Класс, описывающий элемент кластера, является наследником класса кластеризуемых элементов template ctypename type, int degree> class FrogClusterizatorRTree: public FrogClusterizator<type>{ public: typedef typename type Element; protected: class RTree:public rtree::RTreeCClusterElement,degree, true>{ public:

FrogClusterizatorRTree *fcrt; // Ссылка на класс-кластеризатор Нужна, чтобы дерево через нее "рассказывало"о близких элементах

RTree () { } void Callback(ClusterElement &vl, ClusterElement &v2){ // Перекрытый метод предка, который вызывается предком, если найдены два // близких элемента fcrt->distrib(vl,v2); Распределяем близкие элементы по кластерам } void perform(ClusterElement &cl){ // Изменяет номер кластера-владельца для элемента. // Исползуется после перенумерации кластеров int clno = cl.clnumref; if (clno>=0) cl.setClusterNo(fcrt->clusters[clno]); else cl.setClusterNo(-1); ;

RTree rt; public:

FrogClusterizatorRTree(double adist):FrogClusterizator(adist) { rt.fcrt = this; void add(const type &value){ // Добавляем и кластеризуем новый элемент. Для этого:

ClusterElement v(value); // Создаем на его основе элемент кластера rt.searchNear(v,dist); // Ищем ближайшие к нему элементы и кластеризуем их //(из searchNear вызывается для этого метод Callback) rt.add(v); // Затем добавляем в R-дерево int build () { Перенумеровываем кластеры и их номера в соответствующих элементах. ' int result = normalizeClusters(); rt.doPerform(); printf("Clusters: %d\n", result); return result;

Класс-кластеризатор в приведенном листинге параметризуется классом кластеризуемых элементов «type» и степенью ветвления (арностью) структуры R-Tree «degree». Обычно её значения достаточно брать из диапазона от 4 до 32. Внутри FrogClusterizatorRTree объявлен класс-потомок RTree, в котором конкретизирован* способ реакции на обнаруженные близкие элементы (метод Callback). А также добавлен метод «perform», отвечающий за актуализацию номеров кластеров в ранее распределенных по кластерам элементах после перенумерации кластеров (используется в методе кластеризатора «build»).

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Мельникова, Елена Анатольевна, 2009 год

1. Адельсон-Вельский Г., Арлазаров В., Битман А., Донской М. Машина играет в шахматы. - М. Наука, 1983.

2. Адельсон-Вельский Г., Арлазаров В., Донской М. Программирование игр. М., Наука, 1978.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов — М., Мир, 1979.

4. Белозёрова А., Мельников Б. Применение комплекса эвристик в задаче составления схемы нуклидных превращений. — Труды II Всеросс. научной конф. «Методы и средства обработки информации», М., Изд-во МГУ, 2005, с.208-212.

5. Беллман Р. Динамическое программирование. — М.: ИЛ, 1960.

6. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.

7. Биркгоф Г., Барти Т. Современная прикладная алгебра. СПб.: Лань, 2005.

8. Брауэр Э. Введение в теорию конечных автоматов. М.: Радио и связь, 1987.

9. Васильев Ф. Численные методы решения экстремальных задач. — М.: Наука, 1988.

10. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.

11. Гермейер Ю. Введение в теорию исследования операций. — М.: Наука, 1971.

12. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

14. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.

15. Дюк В., Самойленко A. Data Mining. СПб.: Питер, 2001.

16. Карлин С. Математические методы в теории игр, программировании и экономике. М., 1964.

17. Карманов В. Математическое программирование. — М.: Наука, 1975.

18. Карпов Ю. Теория автоматов. СПб.: Питер, 2002.

19. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь 1981г.

20. Классификация и кластер. / Под ред. Дж. Вэн Райзина. М.: Мир, 1980.

21. Ковалев М. Дискретная оптимизация (целочисленное программирование). — М.: УРСС, 2003.

22. Колмогоров А. Теория информации и теория алгоритмов. — М.: Наука, 1987.

23. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / Хачатуров В. и др. М.: Наука, 2000.

24. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы — построение и анализ. — М.: МЦНМО, 2004.

25. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

26. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. -М.: Энергоатомиздат, 1988.

27. Липпман С. Весь С++. От азов до совершенства. — СПб.: Невский диалект, 2007.

28. Липский В. Комбинаторика для,программистов. М.: Мир, 1988.

29. Люгер Д. Искусственный интеллект стратегии и методы решения сложных проблем. - М.-СПб-Киев: Вильяме, 2003.

30. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

31. Мандель И. Кластерный анализ. М.: Финансы и статистика, 1988.

32. Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации. «Кибернетика и системный анализ» (НАН Украины), 2006, №3, с.32^12.

33. Мельников Б. Эвристики в программировании недетерминированных игр. — «Программирование» (Известия РАН), 2001, №5, с.63-80.

34. Мельников Б., Мельникова Е. Кластеризация ситуаций в алгоритмах реального времени для задач дискретной оптимизации. — «Системы управления и информационные технологии», 2007, №2, с. 16-19.

35. Мельников Б., Радионов А. О выборе стратегии в недетерминированных антагонистических играх. — «Программирование» (Известия РАН), 1998, №5, с.55-62.

36. Мельникова Е. Применение алгоритмов кластеризации в задаче минимизации дизъюнктивных нормальных форм. «Известия Самарского центра РАН», 2008, выпуск 10, с. 242-247.

37. Минский М. Вычисления и автоматы. М.: Мир, 1971

38. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

39. Моисеев Н. Элементы теории оптимальных систем. М.: Наука, 1975.

40. Оре О. Графы и их применение. - М.: URSS, 2006.

41. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985.

42. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. — М.: Высшая школа, 1998.

43. Пойа Дж. Математика и правдоподобные рассуждения. М., 1975.

44. Полак Э. Численные методы. Единый подход. М.: Мир, 1974.

45. Поляк Б. Введение в оптимизацию. М.: Наука, 1988.

46. Рассел С., Норвиг П. Искусственный интеллект: современный подход. — М.-СПб-Киев: Вильяме, 2006.

47. Рейнгольд Э. Комбинаторные алгоритмы-М.: Мир, 1980.

48. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике М.: Мир, 1986.

49. Самарский А., Михайлов А. Математическое моделирование. М.: ФИЗМАТЛИТ, 2001.

50. Сачков В. Введение в комбинаторные методы дискретной математики. — М.: Наука, 1982.

51. Сигал И., Иванова А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмыю. М.: ФИЗМАТ ЛИТ, 2003.

52. Современное состояние теории исследования операций / Под ред. Моисеева Н. — М.: Наука, 1979.

53. Схрейвер А. Теория линейного и целочисленного программирования. — М.: Мир, 1991.

54. Таха X. Введение в исследование операций. — М.: Мир, 1988.

55. Успенский В., Семенов А. Теория алгоритмов: основные открытия и приложения -М.: Наука, 1987.

56. Хаггарти Р. Дискретная математика для программистов М.: Техносфера, 2003.

57. Харари Ф. Теория графов. М.: Мир, 1973.

58. Ху Т., Шинг М. Комбинаторные алгоритмы Нижний Новгород: Изд-во Нижегородского госуниверситета им. Н.И.Лобачевского, 2004.

59. Шень А. Программирование: теоремы и задачи. М.: Изд-во МЦНМО, 2004.

60. Шимко П. Оптимальное управление экономическими системами. — СПб.: Бизнесс-пресса, 2004.

61. Эделстейн Г. Интеллектуальные средства анализа, интерпретации и представления данных в информационных хранилищах ComputerWeek-Москва. 1996. №16. с. 32-33.

62. Яблонский С. Введение в дискретную математику М.: Высшая школа, 2006.

63. Adleman, L. Two theorems on random polynomial time In: Proc. 19th IEEE 1978, pp. 75-83.

64. Aida K., Osumi T. A Case Study in Running a Parallel Branch and Bound Application on the Grid Proc. IEEE/IPS J, SAINT2005.

65. Applegate D., Bixby R., Chvatal V., Cook W. Finding cuts in the TSP (A preliminaryreport), DIMACS Technical Report 95-105, March, t

66. Arora S., Lund C.: Hardness of approximation. In: Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 1997.

67. Arora, S. Polynomial time approximation shemes for Euclidean TSP and other geometric problems. In: Proc. 37th IEEE FOCS, IEEE, 1996, pp.2-11.

68. Ausiello G., D'Atri A., Protasi M. On the structure of Combinatorial problems and structure preserving reductions. In: Proc. 4th ICALP

69. Ausiello G., D'Atri A., Protasi M. Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences 21 (1980), 136— 153.

70. Bellare M., Sudan M. The complexity of decision versus search. In: Proc. 26th ACM STOC, ACM, 1994, pp. 184-193.

71. Bellmore M., Nemhauser G. The traveling salesperson problem: A survey. -Operations Research 16 (1968), pp. 538-558.

72. Bentley J. Experiments on traveling salesman heuristics. In: Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, ACM, New York 1990, and SI AM, Philadelphia, 1990, pp. 91-99.

73. Billings D. Algorithms and assessment in computer poker. — University of Alberta (USA), Ph.D. thesis, 2006.

74. Carbonell J. Derivational Analogy and Its Role in Problem Solving, AAAI (1983), pp. 64-69.

75. Champarnaud J., Hansel G., Paranthoen Т., Ziadi D. Random generation models for NFA'S // Journal of Automata, Languages and Combinatorics, 9,2004, pp. 203-216.

76. Chen Q., Ferris M. FATCOP: A fault tolerant Condor-PVM mixed integer program solver. Mathematical Programming Technical Report 99-05, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1999.

77. Cook S. The complexity of theorem proving procedures. In: Proc. 3rd ACM STOC, ACM, 1971, pp. 151-158.

78. Dorigo M., Gambardella L. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. — IEEE Transactions on Evolutionary Computation, Vo.l,No.l (1997), pp. 53-66.

79. Hauk D., Buro M., Schaeffer J.: Rediscovering *-minimax search. Computers and Games, 2004, pp. 35-50.

80. Held M., Karp R. The traveling-salesman problem and minimum spanning trees. -Operation Research, 18 (1970), pp. 1138-1162.

81. Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, 2003.

82. Hromkovic J. An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization,Communication and Cryptography. Springer, 2003.

83. Pohi I. Bi-directional search. In: B.Meltzer and D.Michie (Eds.) Machine Intelligence, 6, Edinburg University Press, Edinburg, Scotland (1971), pp. 127—140.

84. Lifschitz Y. Frames in the Space of Situations. In: Artificial Intelligence 46 (1990), pp. 365-376.

85. Melnikov В., Gumayunov V., Radionov A. Some special heuristics for discrete optimization problems. — 8th International Conference on Enterprise Information Systems, Paphos (Cyprus) (ICEIS-2006), pp. 360-364.

86. Melnikov B. On an expansion of nondeterministic finite automata. The Korean Journal of Computational and Applied Mathematics, Vo.14, No. 1-2 (2007), pp. 155— 166.

87. Melnikov B. Once more about the state-minimization of the nondeterministic finite automata The Korean Journal of Computational and Applied Mathematics, Vo.7, No.3 (2000), pp. 655-662.

88. Melnikov В., Melnikova E., Moseev A. Some heuristics for working with search tree in non-deterministic games. 9th International Workshop on Computer Science and Information Technologies (CSIT'2007), Ufa, 2007.

89. Melnikov В., Melnikova E., Moseev A., Radionov A. Some specific heuristics for situation clustering problems. 1st International Conference on Software and Data Technologies, Setubal (Portugal) (ICSOFT-2006), Vol.2, pp.272-279.

90. Melnikov B. Discrete optimization problems some new heuristic approaches. - 8th International Conference on High Performance Computing and Grid in Asia Pacific Region, IEEE Computer Society Press Ed., Beijing~(China) (HPC-Asia-2005), pp.7380.

91. Melnikov В., Melnikova E. Some programming olympiad problems with detailed solutions. International Conference on Informatics in Secondary Schools, Evolution and Perspectives (ISSEP-2006, Lithuania), pp.573-584.

92. Michie D. Game-playing and game-learning automata. Advanced in Programming . and Non-Numerical Computation, Pergamon Ed. (Oxford), 1966, pp. 183-200.

93. Samuel: Some studies in machine learning using the game of checkers. — IBM Journal, 11 (1967) 601—617.

94. Tesauro G. Neurogammon wins computer olympiad. — Neural Computation, Vo.l, No.3 (1989), pp.321-323.

95. Tesauro G. Temporal difference learning and TD-Gammon. — Commun. ACM, Vo.38, No.3 (1995), p.58-68.

96. Гончаров M. Кластеризация на основе нечётких отношений. -www.spellabs.ru/FuzzyRelationClastering.htm

97. Норенков И. Оптимизация выбора эвристик при решении сложных задач проектирования и логистики http://technomag.edu.ru/doc/44140.html100. 2007WorldFinalProblemSet.pdf- http://icpc.baylor.edu/icpc/Finals/

98. R-Trees: A Dynamic Index Structure for Spatial Searching. http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf

99. Hierarchical cluster analysis http://www.clustan.com/1.