Читать курсовая по финансовому менеджменту, финансовой математике: "Решение задачи о коммивояжере" Страница 3


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

На четвертое место в маршруте ставим город 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).

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 классов:

    CAboutDlg связан со встроенным диалоговым окном «О программе». CKurs_LipinApp управляет запуском приложения и не связан с каким-либо диалоговым окном. [1] CKurs_LipinDlg связан с окном IDD_KURS_LIPIN_DIALOG. Этот класс организует постановку и решение задачи. CSetting связан с окном IDD_DIALOG1. В окне вводятся параметры к задаче – расстояния между городами.

Класс CKurs_LipinDlg. В начале при вызове функции OnInitDialog() переменные заполняются начальными данными. Затем из файла «table.ini» считывается



Интересная статья: Основы написания курсовой работы