При нажатии левой кнопкой мыши вызывается функция
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 : headerfile
//
#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 subsequent 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())
{