Рішення задачі про комівояжера

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Анотація
Задача про комівояжера полягає в тому, щоб об'їхати задані міста по одному разу в такому порядку, щоб пройдена відстань була мінімальна.
Таке завдання актуальна у багатьох областях, таких як автомобільні, суднові та залізничні перевезення, розрахунок авіаційних ліній, конвеєрне виробництво.


Зміст

Вступ 3
Постановка задачі 4
Метод рішення 5
Мова програмування 7
Опис алгоритму 8
Опис основних структур даних 12
Опис інтерфейсу з користувачем 14
Висновок 16
Література 17
Текст програми 18


Введення

Завдання полягає в тому, щоб комівояжер (торговець) обійшов всі намічені міста один раз і в такому порядку, щоб його шлях був найменшим.
Це завдання зацікавила мене тому, що її рішення цікаво з точки зору програмування і складання алгоритму. Важливо знаходження такого алгоритму, який дозволить найбільш оптимально вирішити задачу.
Зараз рішення даної задачі необхідно в багатьох областях пов'язаних із замкнутими і при цьому жорстко пов'язаними за часом системами, такими як: конвеєрне виробництво, багатоопераційні обробні комплекси, суднові та залізничні вантажні системи, перевезення вантажів по замкнутому маршруту, розрахунок авіаційних ліній.
Тому дана проблема на сучасному етапі розвитку суспільства має не найостанніше за значимістю місце.

Постановка завдання

Є N міст, які повинен обійти комівояжер з мінімальними витратами. При цьому на його маршрут накладається два обмеження:
· Маршрут повинен бути замкненим, тобто комівояжер повинен повернутися в те місто, з якого він почав рух;
· У кожному з міст комівояжер повинен побувати точно один раз, тобто треба обов'язково обійти всі міста, при цьому не побувавши в жодному місті двічі.
Для розрахунку витрат існує матриця умов, що містить витрати на перехід з кожного міста у кожний, при цьому вважається, що можна перейти з будь-якого міста в будь-який, окрім того ж самого (в матриці діагональ заповнена нулями). Метою рішення є знаходження маршруту, що задовольняє всім умовам і при цьому має мінімальну суму витрат.

Метод рішення

Для початку слід сказати, що в основі будь-якого методу вирішення даної задачі лежить повний перебір всіляких варіантів шляхів. [2]
Ми проходимо по кожному маршруту: одні відкидаємо, інші порівнюємо з мінімальним шляхом. В кінці перебору ми отримуємо найкоротший шлях.
Особливістю цього завдання є те, що зі збільшенням кількості міст зростає загальна кількість різних комбінацій проходження шляху. А разом з тим зростає і час розрахунку результату. Тому головним рішенням оптимізації алгоритму можна звести до того, щоб під час обчислень відкидати свідомо не мінімальні шляху. Необхідно поставити такий критерій, який відсікав б зайві гілки в дереві пошуку найкоротшого шляху.
Для пояснення мого варіанту розв'язання задачі слід ввести кілька понять. Проміжну довжину шляху можна визначити наступним чином: уявімо, що торговець вибрав якийсь шлях, він вийшов з першого міста і зараз знаходиться в якомусь місті i. Тоді все пройдене відстань з початку до міста i будемо називати проміжна довжина шляху. Якщо виходити з того, що торговець у кожен момент часу буде перебувати в якомусь i-му місті, то завжди можна підрахувати яку відстань він пройшов з початку до цього міста, тобто проміжну довжину шляху.
Мінімальним шляхом будемо називати маршрут, що проходить по всіх містах і має мінімальну довжину.
Мій критерій будується на одному простому твердженні: якщо проміжна довжина шляху більше мінімального шляху, тоді очевидно наступне:
1. проміжна довжина буде рости, коли торговець буде рухатися до кінцевого місту,
2. а значить довжина всього шляху буде більше довжини мінімального маршруту.
отже такий маршрут можна відкинути.
40
30
28
14
32
1
2
3
5
4
1
Проміжна довжина шляху = 102
18
27
30
10
15
1
5
2
4
3
1
i = 4
100
Мінімальний шлях
Поточний шлях
Пояснення показані на малюнку 1.
У даній програмі використовується наступний критерій: при переході від одного міста до іншого розраховується проміжна довжина шляху, і якщо вона більше поточного мінімального шляху, то обчислення з даної гілки припиняються. Таким чином, відсікаються зайві гілки.
Рішення даного завдання призводить до перебору можливих варіантів шляху, але критерії такого роду можуть значно скоротити обчислення і зменшити час роботи програми.

Мова програмування

Для написання програми була обрана мова Сі + + з наступних причин:
1. Середовище програмування Windows-додатків Microsoft Visual C + + 6.0 дозволяє в моїй завданню наочно відобразити карту міст і схему їх з'єднання.
2. Це одна з мов, в якому я непогано розбираюся. Тому мені зручніше писати програму з допомогою Visual C + +.

Опис алгоритму

У програмі міститься рекурсивна функція, яка забезпечує перебір можливих шляхів для пошуку найкоротшого. Саме тут укладено алгоритм вирішення задачі «комівояжера». Розглянемо його докладніше:
1. Для кожного міста (i = від 1 до n), де ми ще не були.
2. Припустимо, що ми прийшли в якесь місто i. Позначаємо його, що ми тут вже були.
3. Підраховуємо довжину пройденого шляху.
4. Якщо вона більше ніж довжина мінімального шляху,
4.1. Тоді немає сенсу йти по цьому шляху далі.
4.1.1. позначаємо місто як не відвіданий, виходимо з міста.
4.2. Інакше,
4.2.1. Якщо ми в кінці шляху
4.2.1.1. Тоді, порівнюємо з мінімальним шляхом, якщо він менше найкоротшого шляху, тоді мінімальний шлях = найкоротший шлях.
4.2.1.2. Інакше переходимо до пункту 1.
5. Переходимо до наступного міста, де ми не були.
Слід розглянути один з основних моментів алгоритму, пов'язаних з перебором маршрутів. З малюнка № 2 можна простежити порядок формування шляхів і розглянути на конкретному прикладі, як працює алгоритм. Тут наведено приклад для 4 міст. Зупинимося на малюнку по докладніше.
А) Ми починаємо шлях з пункту 1. У нашому маршруті записаний перший місто. Розглядаємо ті міста, де ми не були: це 2, 3 і 4. Спочатку переходимо до другого.
Б) Додаємо до маршрутом 2 місто. Дивимося, чи можна кудись перейти з другого міста. Можна відвідати третій і четвертий. Ми вибираємо третє місто.
В) Ставимо на третє місце в нашому маршруті місто 3. Далі ми дивимося, куди можна відправитися - до пункту 4.
Г) На четверте місце в маршруті ставимо місто 4. Тут ми бачимо, що в нашому маршруті заповнені всі чотири місця і значить наш шлях закінчений. Порівнюємо довжину нашого шляху з мінімальним. Потім ми виходимо назад з пункту 4 до пункту 3 і в маршруті переміщаємося на третє місце. Дивимося, що в місті 3 ми були, тоді беремо наступний не відвіданий місто - четвертий.
Д) Ставимо на третє місце маршруту четверте місто. З четвертого пункту можна відвідати тільки третій.
Е) Прийшли в третій пункт. Ставимо на четверте місце маршруту місто 3. Бачимо, що всі чотири місця в нашому шляху заповнені і значить шлях закінчений. Порівнюємо довжину нашого шляху з мінімальним. Виходимо тому - з пункту 3 до пункту 4 і в маршруті переміщаємося на третє місце. Бачимо що тут теж немає не відвіданих міст. Знову переходимо на рівень вгору: з пункту 4 в пункт2 і в маршруті переміщаємося на друге місце. У пункті 2 ми були, але залишилися не відвідуванними міста 3 і 4. Переходимо до третьої. На друге місце в маршруті записуємо третє місто.
Ж) Звідси можна потрапити у другий і четвертий. Переходимо до другого. На третє місце в маршруті ставимо друге місто. І так далі.
З наведеного прикладу вже можна виділити, як алгоритм перебирає шляху. Він діє за такою схемою:
0. Початкове значення j = 1 (перше місце в маршруті).
1. Ми знаходимося в місті k.
2. Для кожного міста (i = від 1 до n)
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).

1
2
3
4
1
2
3
4
32
43
1
2
3
4
32
43
432
1
2
3
4
32
43
432
1
2
3
4
32
43
432
3
1
2
3
4
32
43
432
3
243
4
1
2
3
4
32
43

432
3
243
4
432
А
Б
У
Г
Д
Е
Ж
Малюнок № 2

Опис основних структур даних
Тепер розглянемо структуру програми, опишемо класи та процедури, які були змінені і наповнені кодом.
Програма складається з 4 класів:
1. CAboutDlg пов'язаний з вбудованим діалоговим вікном «Про програму».
2. CKurs _ LipinApp управляє запуском програми, але не пов'язаний з яким-небудь діалоговим вікном. [1]
3. CKurs _ LipinDlg пов'язаний з вікном IDD _ KURS _ LIPIN _ DIALOG. Цей клас організовує постановку і рішення задачі.
4. CSetting пов'язаний з вікном IDD _ DIALOG 1. У вікні вводяться параметри до задачі - відстані між містами.
Клас CKurs _ LipinDlg. На початку при виклику функції OnInitDialog () змінні заповнюються початковими даними. Потім з файлу «table.ini» зчитується таблиця відстаней між містами. І тепер діалогове вікно готове до роботи з користувачем. Функція OnPaint () виводить на екран карту, дозволяє виділяти міста, вибрані користувачем, а також з'єднує міста лініями-шляхами, коли задача вирішена. Крім того, забезпечується висновок інформації для користувача: пояснення, довжина мінімального шляху і список відстаней між містами, складові мінімальний шлях.
При натисненні лівої кнопкою миші викликається функція
OnLButtonDown (). Вона визначає за якого міста клацнув користувач і ставить / знімає виділення з нього. Також тут здійснюється перевірка на кількість виділених міст, тому що час очікування рішення задачі для кількості понад 13 міст стане не задовільним (від 1,5 хвилин і більше). Тому програма видасть повідомлення, якщо ми спробуємо вийти за допустимі межі.
Кнопка «Вибрати стандартні міста» виділяє міста, які потрібно з'єднати в умові завдання, а саме Москва, Ярославль, Нижній Новгород, Самара, Саратов, Волгоград, Воронеж, Пенза, Липецьк, Тамбов, Орел, Курськ, Тула. Кнопка «Очистити» знімає виділення з усіх міст і задає початкові значення ряду необхідних змінних.
Функція OnButton3 () пов'язана з кнопкою «Поставити пункт відправлення». Після натискання кнопки користувач може клацанням миші вибрати пункт відправлення комівояжера. Кнопка «Параметри» викликає діалогове вікно «Параметри», де користувач може редагувати таблицю відстаней між містами. Функція OnOK () обробляє натискання кнопки «Розрахувати шлях». Вона готує початкові значення для виклику рекурсивної функції: створюється таблиця відстаней тільки для виділених міст, заповнюється початковий мінімальний шлях, виводиться пояснюючий інформація. Потім викликається функція recursiv (), яка перебирає варіанти маршрутів, відсікає зайві гілки шляхів і знаходить мінімальний.
Клас C Setting.
Функція 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 divvious 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 ())
{
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 divvious 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);
}
}
}
Додати в блог або на сайт

Цей текст може містити помилки.

Економіко-математичне моделювання | Курсова
69.9кб. | скачати


Схожі роботи:
Рішення задачі комівояжера методом гілок і меж
Експертна система для вирішення задачі про комівояжера
Рішення прикладної задачі
Рішення задачі оптимального управління
Рішення транспортної задачі методом потенціалів
Рішення транспортної задачі з правильним балансом
Приклад рішення задачі по розділу Перехідні процеси
Симплекс метод рішення задачі лінійного програмування
Графічне рішення задачі лінійного програмування в економіці
© Усі права захищені
написати до нас