Решение задачи о коммивояжере
Аннотация
Задача о коммивояжере состоит в том, чтобы объехать заданные города по одному разу в таком порядке, чтобы пройденное расстояние было минимальным.
Такая задача актуальна во многих областях, таких как автомобильные, судовые и железнодорожные перевозки, расчет авиационных линий, конвейерное производство.
Оглавление
Введение3
Постановка задачи4
Метод решения5
Язык программирования7
Описание алгоритма8
Описание основных структур данных12
Описание интерфейса с пользователем14
Заключение16
Литература17
Текст программы18
Введение
Задача состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы его путь был наименьшим.
Эта задача заинтересовала меня потому, что её решение интересно с точки зрения программирования и составления алгоритма. Важно нахождение такого алгоритма, который позволит наиболее оптимально решить задачу.
Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.
Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.
Постановка задачи
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице диагональ заполнена нулями). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Метод решения
Для начала
следует сказать, что в основе любого
метода решения данной задачи лежит
полный перебор всевозможных вариантов
путей. [2]
Мы проходимся по каждому
маршруту: одни отбрасываем, другие
сравниваем с минимальным путем. В конце
перебора мы получаем кратчайший путь.
Особенностью этой задачи является то, что с увеличением количества городов растет общее число различных комбинаций прохождения пути. А вместе с тем растет и время расчета результата. Поэтому главным решением оптимизации алгоритма можно свести к тому, чтобы во время вычислений отбрасывать заведомо не минимальные пути. Необходимо задать такой критерий, который отсекал бы лишние ветви в дереве поиска кратчайшего пути.
Для пояснения моего варианта решения задачи следует ввести несколько понятий. Промежуточную длину пути можно определить следующим образом: представим, что торговец выбрал какой-либо путь; он вышел из первого города и сейчас находится в каком-то городе i. Тогда все пройденное расстояние из начала в город i будем называть промежуточная длина пути. Если исходить из того, что торговец в каждый момент времени будет находиться в каком-то i-ом городе, то всегда можно подсчитать какое расстояние он прошел из начала до этого города, то есть промежуточную длину пути.
Минимальным путем будем называть маршрут, проходящий по всем городам и имеющий минимальную длину.
Мой критерий строится на одном простом утверждении: если промежуточная длина пути больше минимального пути, тогда очевидно следующее:
промежуточная длина будет расти, когда торговец будет двигаться к конечному городу,
а значит длина всего пути будет больше длины минимального маршрута.
следовательно такой маршрут можно отбросить.
П
ояснения
показаны на рисунке 1.
В данной программе используется следующий критерий: при переходе от одного города к другому рассчитывается промежуточная длина пути, и если она больше текущего минимального пути, то вычисления по данной ветви прекращаются. Таким образом, отсекаются лишние ветви.
Решение данной задачи приводит к перебору возможных вариантов пути, но критерии такого рода могут значительно сократить вычисление и уменьшить время работы программы.
Язык программирования
Для написания программы был выбран язык Си++ по следующим причинам:
Среда программирования Windows-приложений Microsoft Visual C++ 6.0 позволяет в моей задаче наглядно отобразить карту городов и схему их соединения.
Это один из языков, в котором я неплохо разбираюсь. Поэтому мне удобнее писать программу с помощью Visual C++.
Описание алгоритма
В программе содержится рекурсивная функция, которая обеспечивает перебор возможных путей для поиска самого короткого. Именно здесь заключен алгоритм решения задачи «коммивояжера». Рассмотрим его подробнее:
Для каждого города (i = от 1 до n), где мы еще не были.
Допустим, что мы пришли в какой-то город i. Помечаем его, что мы здесь уже были.
Подсчитываем длину пройденного пути.
Если она больше чем длина минимального пути,
Тогда нет смысла идти по этому пути дальше.
помечаем город как не посещенный, выходим из города.
Иначе,
если мы в конце пути
тогда, сравниваем с минимальным путем, если он меньше кратчайшего пути, тогда минимальный путь = кратчайший путь.
иначе переходим к пункту 1.
Переходим к следующему городу, где мы не были.
Следует рассмотреть один из основных моментов алгоритма, связанных с перебором маршрутов. Из рисунка №2 можно проследить порядок формирования путей и рассмотреть на конкретном примере, как работает алгоритм. Здесь приведен пример для 4 городов. Остановимся на рисунке по подробнее.
Мы начинаем путь из пункта 1. В нашем маршруте записан первый город. Рассматриваем те города, где мы не были: это 2, 3 и 4. Сначала переходим во второй.
Добавляем к маршруту 2 город. Смотрим, можно ли куда-то перейти из второго города. Можно посетить третий и четвертый. Мы выбираем третий город.
Ставим на третье место в нашем маршруте город 3. Далее мы смотрим, куда можно отправиться – в пункт 4.
На четвертое место в маршруте ставим город 4. Здесь мы видим, что в нашем маршруте заполнены все четыре места и значит наш путь закончен. Сравниваем длину нашего пути с минимальным. Затем мы выходим назад из пункта 4 в пункт 3 и в маршруте перемещаемся на третье место. Смотрим, что в городе 3 мы были, тогда берем следующий не посещенный город – четвертый.
Ставим на третье место маршрута четвертый город. Из четвертого пункта можно посетить только третий.
Пришли в третий пункт. Ставим на четвертое место маршрута город 3. Видим, что все четыре места в нашем пути заполнены и значит путь закончен. Сравниваем длину нашего пути с минимальным. Выходим назад – из пункта 3 в пункт 4 и в маршруте перемещаемся на третье место. Видим что здесь тоже нет не посещенных городов. Опять переходим на уровень вверх: из пункта 4 в пункт2 и в маршруте перемещаемся на второе место. В пункте 2 мы были, но остались не посещенными города 3 и 4. Переходим в третий. На второе место в маршруте записываем третий город.
Отсюда можно попасть во второй и четвертый. Переходим во второй. На третье место в маршруте ставим второй город. И так далее.
Из приведенного примера уже можно выделить, как алгоритм перебирает пути. Он действует по следующей схеме:
Начальное значение j = 1 (первое место в маршруте).
Мы находимся в городе k.
Для каждого города (i = от 1 до n)
Рассматриваем город i.
Если этот город еще не посещен,
тогда переходим в город i; j увеличиваем на единицу. Добавляем номер города в маршрут на место j. Помечаем город как посещенный. Переходим к пункту 1 (k = i).
иначе идти некуда, т.е. все города мы посетили.
если j = количеству городов (n), т.е мы добрались до последнего пункта в маршруте и наш путь сформирован, тогда сравниваем длину пути с длиной минимального маршрута.
Помечаем город как не посещенный и выходим из него. Уменьшаем j на единицу.
Берем следующий город (i=i+1).
Описание основных структур данных
Теперь рассмотрим структуру приложения, опишем классы и процедуры, которые были изменены и наполнены кодом.
Программа состоит из 4 классов:
CAboutDlg связан со встроенным диалоговым окном «О программе».
CKurs_LipinApp управляет запуском приложения и не связан с каким-либо диалоговым окном. [1]
CKurs_LipinDlg связан с окном IDD_KURS_LIPIN_DIALOG. Этот класс организует постановку и решение задачи.
CSetting связан с окном IDD_DIALOG1. В окне вводятся параметры к задаче – расстояния между городами.
Класс CKurs_LipinDlg. В начале при вызове функции OnInitDialog() переменные заполняются начальными данными. Затем из файла «table.ini» считывается таблица расстояний между городами. И теперь диалоговое окно готово к работе с пользователем. Функция OnPaint() выводит на экран карту, позволяет выделять города, выбранные пользователем, а также соединяет города линиями-путями, когда задача решена. Кроме того, обеспечивается вывод информации для пользователя: пояснения, длина минимального пути и список расстояний между городами, составляющие минимальный путь.
При нажатии
левой кнопкой мыши вызывается функция
OnLButtonDown().
Она определяет по какому городу щелкнул
пользователь и ставит/снимает выделение
с него. Также здесь осуществляется
проверка на количество выделенных
городов, т.к. время ожидания решения
задачи для количества более 13 городов
станет не удовлетворительным (от 1,5
минут и более). Поэтому программа выдаст
сообщение, если мы попытаемся выйти за
допустимые пределы.
Кнопка «Выбрать стандартные города» выделяет города, которые требуется соединить в условии задачи, а именно Москва, Ярославль, Нижний Новгород, Самара, Саратов, Волгоград, Воронеж, Пенза, Липецк, Тамбов, Орел, Курск, Тула. Кнопка «Очистить» снимает выделение со всех городов и задает начальные значения ряду необходимых переменных.
Функция OnButton3() связана с кнопкой «Задать пункт отправления». После нажатия кнопки пользователь может щелчком мыши выбрать пункт отправления коммивояжера. Кнопка «Параметры» вызывает диалоговое окно «Параметры», где пользователь может редактировать таблицу расстояний между городами. Функция OnOK() обрабатывает нажатие кнопки «Рассчитать путь». Она подготавливает начальные значения для вызова рекурсивной функции: создается таблица расстояний только для выделенных городов, заполняется первоначальный минимальный путь, выводится поясняющая информация. Затем вызывается функция recursiv(), которая перебирает варианты маршрутов, отсекает лишние ветви путей и находит минимальный.
Класс CSetting.
Функция OnInitDialog() программным путем создает и выводит поля ввода, имитируя таблицу расстояний между городами. Затем считывается файл «table.ini», и заполняются поля ввода полученными значениями. Вызывается функция Proverka(), которая сканирует полученные данные на ошибки, т.е. определяет введены ли только цифры, и если нет, тогда удаляет все лишние символы.
По нажатию кнопки «Сохранить» программа передает данные в родительское окно, записывает данные из полей ввода в файл и закрывает диалоговое окно.
Описание интерфейса с пользователем
При загрузке приложения появляется основное диалоговое окно. Здесь пользователь может выбрать несколько городов и рассчитать для них минимальный путь.
Чтобы отменить выделение городов нужно щелкнуть по кнопке «Очистить». Нажав кнопку «Рассчитать путь», мы получим результат: города соединены минимальным путем, его длина дана в окне информации, в списке показаны расстояния между городами, входящими в полученный путь. Кнопка «Выбрать стандартные города» выделяет города, требуемые в задании.
Чтобы выделить пункт отправления коммивояжера нужно выбрать «Задать пункт отправления».
Кнопка «Параметры» вызывает диалоговое окно для ввода расстояний между городами (рис. 5). Это окно является модальным и его особенностью является то, что нет возможности перехода к родительскому окну.
Здесь пользователь может отредактировать расстояния между городами. Для этого нужно щелкнуть в поле ввода, и ввести другое значение. Перемещаться по этой «таблице» можно по строкам при помощи клавиш Tab или Shift+Tab.
По завершении ввода нужно нажать кнопку «Сохранить», чтобы программа записала измененные данные в файл. При этом автоматически проверится правильность введенный информации и все ошибки будут исправлены.
Кнопка «Отмена» позволяет не сохранять введенные изменения, если пользователь ошибся во введенной информации.
По нажатии любой из кнопок диалоговое окно «Параметры» закрывается и мы возвращаемся к главному окну .
Если в строке заголовка главного окна щелкнуть правой кнопкой мыши и выбрать пункт «О программе», то появится диалоговое окно, содержащее сведения о программе и об авторе (рис. 6). Нажав кнопку «OK» возвращаемся к главному окну.
Заключение
Был разработан алгоритм, позволяющий быстро найти кратчайший путь между городами. По алгоритму разработано приложение, решающее задачу о коммивояжере.
Литература
Круглински Д., Программирование на Microsoft Visual C++ 6.0 для профессионалов/Пер.с англ. –СПб:Питер; 2004г. – 861 с.: ил.
Беляев С.П. Курс лекций по «Исследованию операций».
Текст программы
// Kurs_LipinDlg.h : header file
//
#if !defined(AFX_KURS_LIPINDLG_H__FFEC63D9_17E7_4E43_805B_75F68CE9E55F__INCLUDED_)
#define AFX_KURS_LIPINDLG_H__FFEC63D9_17E7_4E43_805B_75F68CE9E55F__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
// CKurs_LipinDlg dialog
class CSetting;
class CKurs_LipinDlg : public CDialog
{
// Construction
public:
CKurs_LipinDlg(CWnd* pParent = NULL);// standard constructor
int koord[29][2],x0,y0;
bool flag_select[29];
bool flag_draw;
int count_selected, n;
int begin_point;
bool flag_Bpoint;
int **table;
int tableAllCity[29][29];
unsigned int *min_path;
int *sel_city;
CString name_city[29];
CFont myFont;
void CKurs_LipinDlg::recursiv (bool flag[],unsigned int cur_path[],int j);
// Dialog Data
//{{AFX_DATA(CKurs_LipinDlg)
enum { IDD = IDD_KURS_LIPIN_DIALOG };
CListBoxm_list1;
CStaticm_label;
CStringm_len;
//}}AFX_DATA
// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CKurs_LipinDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX);// DDX/DDV support
//}}AFX_VIRTUAL
// Implementation
protected:
HICON m_hIcon;
// Generated message map functions
//{{AFX_MSG(CKurs_LipinDlg)
virtual BOOL OnInitDialog();
afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
afx_msg void OnPaint();
afx_msg HCURSOR OnQueryDragIcon();
afx_msg void OnLButtonDown(UINT nFlags, CPoint point);
afx_msg void OnButton2();
afx_msg void OnButton1();
virtual void OnOK();
afx_msg void OnButton3();
afx_msg void OnButton4();
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.
#endif // !defined(AFX_KURS_LIPINDLG_H__FFEC63D9_17E7_4E43_805B_75F68CE9E55F__INCLUDED_)
// Kurs_LipinDlg.cpp : implementation file
//
#include "stdafx.h"
#include "Kurs_Lipin.h"
#include "Kurs_LipinDlg.h"
#include "math.h"
#include "Setting.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About
class CAboutDlg : public CDialog
{
public:
CAboutDlg();
// Dialog Data
//{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
//}}AFX_DATA
// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL
// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
//{{AFX_DATA_INIT(CAboutDlg)
//}}AFX_DATA_INIT
}
void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CAboutDlg)
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CKurs_LipinDlg dialog
CKurs_LipinDlg::CKurs_LipinDlg(CWnd* pParent /*=NULL*/)
: CDialog(CKurs_LipinDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CKurs_LipinDlg)
m_len = _T("");
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a sub>sequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CKurs_LipinDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CKurs_LipinDlg)
DDX_Control(pDX, IDC_LIST1, m_list1);
DDX_Control(pDX, IDC_STATIC1, m_label);
DDX_Text(pDX, IDC_STATIC1, m_len);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CKurs_LipinDlg, CDialog)
//{{AFX_MSG_MAP(CKurs_LipinDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_WM_LBUTTONDOWN()
ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
ON_BN_CLICKED(IDC_BUTTON4, OnButton4)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CKurs_LipinDlg message handlers
BOOL CKurs_LipinDlg::OnInitDialog()
{
CDialog::OnInitDialog();
// Add "About..." menu item to system menu.
// IDM_ABOUTBOX must be in the system command range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX < 0xF000);
CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
CString strAboutMenu;
strAboutMenu.LoadString(IDS_ABOUTBOX);
if (!strAboutMenu.IsEmpty())
{
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
}
}
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE);// Set big icon
SetIcon(m_hIcon, FALSE);// Set small icon
name_city[0] = "С.-Петербург";
name_city[1] = "Псков";
name_city[2] = "Новгород";
name_city[3] = "Смоленск";
name_city[4] = "Тверь";
name_city[5] = "Вологда";
name_city[6] = "Ярославль";
name_city[7] = "Кострома";
name_city[8] = "Москва";
name_city[9] = "Брянск";
name_city[10] = "Калуга";
name_city[11] = "Иваново";
name_city[12] = "Орел";
name_city[13] = "Тула";
name_city[14] = "Владимир";
name_city[15] = "Курск";
name_city[16] = "Рязань";
name_city[17] = "Белгород";
name_city[18] = "Липецк";
name_city[19] = "Н.Новгород";
name_city[20] = "Воронеж";
name_city[21] = "Тамбов";
name_city[22] = "Чебоксары";
name_city[23] = "Саранск";
name_city[24] = "Пенза";
name_city[25] = "Ульяновск";
name_city[26] = "Саратов";
name_city[27] = "Самара";
name_city[28] = "Волгоград";
x0=10;y0=10;// смещение карты относительно левого верхнего угла окна
koord[0][0]=x0+225;// Санкт-Петербург
koord[0][1]=y0+54;
koord[1][0]=x0+148; //Псков
koord[1][1]=y0+60;
koord[2][0]=x0+195; // Новгород
koord[2][1]=y0+92;
koord[3][0]=x0+93; // Смоленск
koord[3][1]=y0+171;
koord[4][0]=x0+191; //Тверь
koord[4][1]=y0+193;
koord[5][0]=x0+301; //Вологда
koord[5][1]=y0+200;
koord[6][0]=x0+261; //Ярославль
koord[6][1]=y0+231;
koord[7][0]=x0+279;//Кострома
koord[7][1]=y0+248;
koord[8][0]=x0+181;//Москва
koord[8][1]=y0+241;
koord[9][0]=x0+76;//Брянск
koord[9][1]=y0+240;
koord[10][0]=x0+133;//Калуга
koord[10][1]=y0+245;
koord[11][0]=x0+256;//Иваново
koord[11][1]=y0+264;
koord[12][0]=x0+88;//Орел
koord[12][1]=y0+275;
koord[13][0]=x0+139;//Тула
koord[13][1]=y0+272;
koord[14][0]=x0+227;//Владимир
koord[14][1]=y0+274;
koord[15][0]=x0+55;//Курск
koord[15][1]=y0+297;
koord[16][0]=x0+176;//Рязань
koord[16][1]=y0+297;
koord[17][0]=x0+29;//Белгород
koord[17][1]=y0+328;
koord[18][0]=x0+121;//Липецк
koord[18][1]=y0+338;
koord[19][0]=x0+276;//Нижний Новгород
koord[19][1]=y0+322;
koord[20][0]=x0+92;//Воронеж
koord[20][1]=y0+353;
koord[21][0]=x0+149;//Тамбов
koord[21][1]=y0+364;
koord[22][0]=x0+307;//Чебоксары
koord[22][1]=y0+373;
koord[23][0]=x0+237;//Саранск
koord[23][1]=y0+388;
koord[24][0]=x0+212;//Пенза
koord[24][1]=y0+408;
koord[25][0]=x0+280;//Ульяновск
koord[25][1]=y0+429;
koord[26][0]=x0+184;//Саратов
koord[26][1]=y0+456;
koord[27][0]=x0+292;//Самара
koord[27][1]=y0+491;
koord[28][0]=x0+91;//Волгоград
koord[28][1]=y0+506;
count_selected=0;
myFont.CreateFont(17,0,0,0,500,false,false,false,0,0,0,0,0,"Courier Cyr");
m_len="Выберите несколько городов.";
m_label.SetFont (&myFont);
UpdateData(false);
for (int i=0; i < 29; i++)
flag_select[i]=false;
flag_draw=false;
begin_point = -1;
flag_Bpoint=false;
CStdioFile f1;
f1.Open("table.ini",CFile::modeRead);
for ( i=0; i < 29; i++)
{
tableAllCity[i][i]=0;
CString s1;
f1.ReadString(s1);
int j=i+1;
int k=0;
while (j<29 && k < s1.GetLength())
{CString s2;
while (s1[k] == ' ') k++;
while (s1[k] != ' ')
{ s2 += s1[k]; k++;}
tableAllCity[j][i]=tableAllCity[i][j]=atoi(s2);
j++;
}
}
return TRUE; // return TRUE unless you set the focus to a control
}
void CKurs_LipinDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
CAboutDlg dlgAbout;
dlgAbout.DoModal();
}
else
{
CDialog::OnSysCommand(nID, lParam);
}
}
// If you add a minimize button to your dialog, you will need the code below
// to draw the icon. For MFC applications using the document/view model,
// this is automatically done for you by the framework.
void CKurs_LipinDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting
SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CClientDC pDC(this);
CDC temp;
CBitmap bmp;
bmp.LoadBitmap(IDB_BITMAP1);
temp.CreateCompatibleDC (&pDC);
temp.SelectObject(bmp);
for (int j=0;j<29;j++)
{
if (flag_select[j])
{
int x=koord[j][0]-x0;
int y=koord[j][1]-y0;
temp.SelectStockObject (BLACK_BRUSH);
temp.Ellipse(x-3,y-3,x+3,y+3);
}
}
if (begin_point>=0)
{
int x=koord[begin_point][0]-x0;
int y=koord[begin_point][1]-y0;
CBrush br (RGB(255,0,0));
temp.SelectObject (&br);
temp.Ellipse(x-4,y-4,x+4,y+4);
}
if (flag_draw)
{
for (int i = 0; i < n; i++)
{
int x1 = koord[sel_city[min_path[i]-1]][0];
int x2 = koord[sel_city[min_path[i+1]-1]][0];
int y1 = koord[sel_city[min_path[i]-1]][1];
int y2 = koord[sel_city[min_path[i+1]-1]][1];
temp.MoveTo(x1-x0,y1-y0);
temp.LineTo(x2-x0,y2-y0);
}
CString s1;
m_list1.ResetContent();
for (i=0;i < n; i++)
{
s1=name_city[sel_city[min_path[i]-1]];
s1+=" - "+name_city[sel_city[min_path[i+1]-1]];
CString s2;
s2.Format("%d",table[min_path[i]-1][min_path[i+1]-1]);
s1+=" ->"+s2;
m_list1.AddString(s1);
}
m_len.Format("Длина пути:\n%d км",min_path[n+1]);
for (i=0;i < n; i++)
{
if (i % 2 != 0) m_list1.SetSel(i);
}
}
else
{
m_len="Выберите несколько городов.";
}
UpdateData(false);
pDC.BitBlt(x0,y0,638,638,&temp,0,0,SRCCOPY);
CDialog::OnPaint();
}
}
// The system calls this to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CKurs_LipinDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
void CKurs_LipinDlg::OnLButtonDown(UINT nFlags, CPoint point)
{
for (int i=0;i<29;i++)
{
int x=point.x-koord[i][0],y=point.y-koord[i][1];
if((x*x+y*y)<=7*7)
{
if (flag_Bpoint)
{
if (count_selected >= 13 && flag_select[i]==false)
{
MessageBox ("Нельзя выбрать более 13 городов !!!\nВыберите выделенный город или снимите выделение \nс одного города и поставьте на другом.");
flag_Bpoint=false;
Invalidate(false);
}
else
{
begin_point=i;
flag_Bpoint=false;
if (flag_select[i]==false) count_selected++;
flag_select[i]=true;
flag_draw=false;
Invalidate(false);
}
}
else
{
if (count_selected >= 13 && flag_select[i]==false)
{
MessageBox ("Нельзя выбрать более 13 городов !!!");
}
else
{
if (flag_select[i]==false) count_selected++;
else
{
count_selected--;
if (i == begin_point)
{
begin_point=-1;
}
}
flag_select[i]=!flag_select[i];
flag_draw=false;
Invalidate(false);
}
}
}
}
CDialog::OnLButtonDown(nFlags, point);
}
void CKurs_LipinDlg::OnButton1()
{
m_list1.ResetContent();
for (int i=0; i < 29; i++)
flag_select[i]=false;
flag_select[6]=true;
flag_select[8]=true;
flag_select[12]=true;
flag_select[13]=true;
flag_select[15]=true;
flag_select[18]=true;
flag_select[19]=true;
flag_select[20]=true;
flag_select[21]=true;
flag_select[26]=true;
flag_select[27]=true;
flag_select[28]=true;
flag_select[24]=true;
count_selected=13;
flag_draw=false;
flag_Bpoint = false;
begin_point = -1;
Invalidate(false);
}
void CKurs_LipinDlg::OnButton2()
{
m_list1.ResetContent();
for (int i=0; i < 29; i++)
flag_select[i]=false;
flag_Bpoint = false;
begin_point = -1;
count_selected = 0;
flag_draw = false;
Invalidate (false);
}
void CKurs_LipinDlg::OnOK()
{
m_list1.ResetContent();
n = count_selected;
if (n <=1)
{
MessageBox ("Пожалуйста, выберите не менее 2 городов.");
return;
}
sel_city= new int[n];
int count = 0;
for (int i=0; i < 29; i++)
if (flag_select[i]) sel_city[count++] = i;
for (i=0; i < n; i++)// ставим исходный город на первое место в массиве
if (sel_city[i] == begin_point)
{
int tmp = sel_city[0];
sel_city[0] = sel_city[i];
sel_city[i] = tmp;
}
table = new int *[n];
for (i=0; i<n; i++)
table[i] = new int [n];
for (i=0; i<n; i++)
for (int j = 0; j < n; j++)
{
if (i>=j)
{
table[i][j]=table[j][i]=tableAllCity[sel_city[i]][sel_city[j]];
}
}
bool *flag = new bool[n]; // заполнение признаков посещения городов
flag[0] = true;
for (i=1; i < n; i++) flag[i]=false;
unsigned int *cur_path = new unsigned int[n+2];
min_path = new unsigned int[n+2];
// заполнение матриц минимального пути и текущего пути
min_path[0] = min_path[n]=1; min_path[n+1]=0;
for (i=1; i < n; i++)
{
min_path[i]=i+1; min_path[n+1]+=table[i-1][i];
cur_path[i]=0;
} min_path[n+1] += table [min_path[n-1]-1] [min_path[n]-1 ];
cur_path[n+1] =0;
cur_path[0] = cur_path[n] = 1;
m_len="Пожалуйста, подождите:\nидут вычисления...";
UpdateData(false);
recursiv (flag,cur_path, 1); // вызов рекурсивной функции*/
flag_draw = true;
Invalidate(false);
}
void CKurs_LipinDlg::recursiv (bool flag[],unsigned int cur_path[],int j)
{
for (int i = 0; i < n; i++) // для каждой точки
{
if (flag[i] == false) // где мы еще не были
{
flag[i] = true; // переходим в нее,
cur_path[j] = i+1; // вычисляя длину пройденного пути
cur_path[n+1] += table [cur_path[j-1]-1] [cur_path[j]-1];
// *** если длина текущего пути меньше минимальной ***
if (cur_path[n+1] < min_path[n+1])
// рассматриваем новую точку, если она не конечная
if (j < n-1) recursiv (flag, cur_path, j+1);
else
{ // или вычисляем длинув сего пути и ...
cur_path[n+1] += table [cur_path[n-1]-1] [cur_path[n]-1];
// ... сравниваем с минимальным
if (cur_path[n+1] < min_path[n+1])
{
for (int k=0; k <= n+1; k++)
min_path[k] = cur_path[k];
}
cur_path[n+1] -= table [cur_path[n-1]-1] [cur_path[n]-1];
}
flag[i]=false;
cur_path[n+1] -= table [cur_path[j-1]-1] [cur_path[j]-1];
}
}
return;
}
void CKurs_LipinDlg::OnButton3()
{
m_list1.ResetContent();
flag_Bpoint=true;
Invalidate(false);
}
void CKurs_LipinDlg::OnButton4()
{
CSetting dlg1(this);
dlg1.DoModal();
}
// Setting.h : header file
//
/////////////////////////////////////////////////////////////////////////////
// CSetting dialog
class CKurs_LipinDlg;
class CSetting : public CDialog
{
// Construction
public:
CSetting(CKurs_LipinDlg* pParent); // standard constructor
CKurs_LipinDlg *parent;
CEdit t_edit[29][29];
CFont myFont;
BOOL f_start;
void CSetting::Proverka();
// Dialog Data
//{{AFX_DATA(CSetting)
enum { IDD = IDD_DIALOG1 };
// NOTE: the ClassWizard will add data members here
//}}AFX_DATA
// Overrides
// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CSetting)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL
// Implementation
protected:
// Generated message map functions
//{{AFX_MSG(CSetting)
virtual void OnOK();
void CSetting::OnMyEdit();
void CSetting::OnMyEdit1() ;
virtual BOOL OnInitDialog();
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.
#endif // !defined(AFX_SETTING_H__23ABDE52_3A69_456A_A9DC_23A586A6699A__INCLUDED_)
// Setting.cpp : implementation file
#include "stdafx.h"
#include "Kurs_Lipin.h"
#include "Setting.h"
#include "Kurs_Lipin.h"
#include "Kurs_LipinDlg.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CSetting dialog
CSetting::CSetting(CKurs_LipinDlg* pParent)
: CDialog(CSetting::IDD, pParent)
{
f_start=false;
parent = pParent;
//{{AFX_DATA_INIT(CSetting)
// NOTE: the ClassWizard will add member initialization here
//}}AFX_DATA_INIT
}
void CSetting::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CSetting)
// NOTE: the ClassWizard will add DDX and DDV calls here
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CSetting, CDialog)
//{{AFX_MSG_MAP(CSetting)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CSetting message handlers
BOOL CSetting::OnInitDialog()
{
CDialog::OnInitDialog();
myFont.CreateFont(11,0,0,0,0,false,false,false,0,0,0,0,0,"Courier Cyr");
int count=1, w=30,h=20,x0=45,y0=10;
for (int i=0; i < 29; i++)
{
for (int j=i; j < 29; j++)
{
if (i == j)
{
t_edit[i][j].Create (WS_CHILD|WS_VISIBLE | WS_TABSTOP | WS_DLGFRAME|TA_LEFT,
CRect(j*w+x0-35,i*h+y0,(j+1)*w-1+x0,(i+1)*h-1+y0),this,100);
t_edit[i][j].SetFont (&myFont);
t_edit[i][j].SetWindowText(parent->name_city[i]);
t_edit[i][j].SetReadOnly ();
}
else
{
t_edit[i][j].Create (WS_CHILD|WS_VISIBLE | WS_TABSTOP | WS_DLGFRAME,
CRect(j*w+x0,i*h+y0,(j+1)*w-1+x0,(i+1)*h-1+y0),this,100);//count++);
t_edit[i][j].SetFont (&myFont);
t_edit[i][j].SetLimitText(4);
}
}
}
CStdioFile f1;
f1.Open("table.ini",CFile::modeRead);
for ( i=0; i < 29; i++)
{
CString s1;
f1.ReadString(s1);
int j=i+1;
int k=0;
while (j<29 && k < s1.GetLength())
{CString s2;
while (s1[k] == ' ') k++;
while (s1[k] != ' ')
{ s2 += s1[k]; k++;}
t_edit[i][j].SetWindowText(s2);
j++;
}
}
Proverka();
return TRUE; // return TRUE unless you set the focus to a control
// EXCEPTION: OCX Property Pages should return FALSE
}
void CSetting::OnOK()
{
Proverka();
CStdioFile f1;
f1.Open("table.ini",CFile::modeCreate | CFile::modeWrite);
for (int i=0; i < 29; i++)
{
parent->tableAllCity[i][i]=0;
CString s1;
for (int j=i+1; j < 29; j++)
{
CString s2;
t_edit[i][j].GetWindowText(s2);
parent->tableAllCity[j][i]=parent->tableAllCity[i][j]=atoi(s2);
s1 += s2+" ";
} s1 += "\n";
f1.WriteString(s1);
}
MessageBox("Введённые параметры проверены на ошибки и сохранены.");
CDialog::OnCancel ();
}
void CSetting::Proverka()
{
for (int i=0; i < 29; i++)
{
for (int j=i+1; j < 29; j++)
{
CString s1;
t_edit[i][j].GetWindowText(s1);
if (!s1.IsEmpty())
{
for (int k=0; k < s1.GetLength(); k++)
if (s1[k]<'0' || s1[k]>'9') {s1.Delete(k,1);k--;}
if (s1.IsEmpty()) s1='0';
}
else s1='0';
t_edit[i][j].SetWindowText(s1);
}
}
}