3. Рассматриваем город i.
4. Если этот город еще не посещен,
4.1. тогда переходим в город i; j увеличиваем на единицу. Добавляем номер города в маршрут на место j. Помечаем город как посещенный. Переходим к пункту 1 (k = i).
4.2. иначе идти некуда, т.е. все города мы посетили.
4.2.1. если j = количеству городов (n), т.е мы добрались до последнего пункта в маршруте и наш путь сформирован, тогда сравниваем длину пути с длиной минимального маршрута.
4.2.2. Помечаем город как не посещенный и выходим из него. Уменьшаем j на единицу.
5. Берем следующий город (i=i+1).
Теперь рассмотрим структуру приложения, опишем классы и процедуры, которые были изменены и наполнены кодом.
Программа состоит из 4 классов:
1. CAboutDlg связан со встроенным диалоговым окном «О программе».
2. CKurs_LipinApp управляет запуском приложения и не связан с каким-либо диалоговым окном. [1]
3. CKurs_LipinDlg связан с окном IDD_KURS_LIPIN_DIALOG. Этот класс организует постановку и решение задачи.
4. 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» возвращаемся к главному окну.
Был разработан алгоритм, позволяющий быстро найти кратчайший путь между городами. По алгоритму разработано приложение, решающее задачу о коммивояжере.
1. Круглински Д., Программирование на Microsoft Visual C++ 6.0 для профессионалов/Пер.с англ. –СПб:Питер; 2004г. – 861 с.: ил.
2. Беляев С.П. Курс лекций по «Исследованию операций».
Текст программы
// 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_)
