СЕТЕВЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЁРА

Авторы
Файлы

Булашкова М.Г. Ломакина А.Н. Чаузова Е.А. Зотова С.А. Статья в формате PDF 423 KB

В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города. Обязательным условием являлось требование посетить каждую вершину однократно и возвратиться в исходную.

Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений - задача коммивояжёра, имеющая ряд применений в исследовании операций, в частности при решении некоторых трaнcпортных проблем.

Прокомментируем сетевые методы решения ЗК для таблицы данных, представленной в виде матрицы:

Прочерки по диагонали означают, что из пункта i в пункт i ходить нельзя.

Вообще говоря, цикл можно задать системой из пяти подчеркнутых элементов матрицы С. Сумма чисел подчеркнутых элементов есть стоимость цикла. Для данного случая стоимость равна 29. Но как определить цикл меньшей стоимостью?

Жадный алгоритм - алгоритм нахождения наикратчайшего расстояния путём первоначального выбора самого короткого ребра и присоединения к нему следующего самого короткого ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. Для нашего примера:

«Жадным» алгоритм назван потому, что на последних шагах можно жестоко расплатиться за жадность, присоединяя оставшиеся ребра большой длины.

Деревянный алгоритм - алгоритм решения ЗК через построение кратчайшего остовного дерева (рис. 1), для которого строится Эйлеров цикл (рис. 2) и затем Гамильтонов (рис. 3).

Рис. 1 Рис.2 Рис.3

Длина полученного цикла:

Но такие эвристические алгоритмы (жадный, деревянный) являются приблизительными и дают далеко не всегда оптимальный вариант решения.

Следующий метод - «brute-force enumeration» - «перебор животной силой», который основан на переборе всех различных циклов . Для этого составляется граф-дерево. Для исходного примера: что достаточно трудоёмко.

Для сокращения числа вариантов перебора может быть применен метод ветвей и границ. Метод заключается в том, что «ветвится» та вершина дерева-графа, содержащая определенный класс вариантов решений, которая получает лучшую оценку. Преимущество данного метода состоит в возможности отбрасывать варианты не по одному, а целыми классами. Трудность метода - в определении оценки (снизу для задач минимизации; сверху для задач максимизации), чтобы процеДypa была эффективной. Поэтому метод ветвей и границ не гарантирует того, что в ходе решения не произойдет перебор всех вариантов решения.

Удовлетворительные результаты по быстродействию демонстрирует алгоритм Литтла, который является одним из разновидностей метода ветвей и границ. Пpaктика показывает, что на современных ЭВМ он позволяет решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Система оценивания и выбора класса, который необходимо продолжать «ветвить», достаточно быстро дала решение нашей задачи (рис. 4).

Достраивая выбранный класс, содержащий ребра (1, 2), (3, 1), (2, 5), до контура, получим искомый цикл и его длину: Полученная стоимость L = 26 меньше оценок любой из висячих вершин. Следовательно, полученное решение оптимально.

Рис.4

МУЛЬТИМЕДИЙНОЕ ОБРАЗОВАНИЕ НА СОВРЕМЕННЫХ ЭТАПАХ ОБУЧЕНИЯ СТУДЕНТОВ СТАРШИХ КУРСОВ МЕДИЦИНСКИХ ВУЗОВ

Статья в формате PDF 217 KB...

18 10 2026 17:20:45

ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ СОЗДАНИЯ ИММОБИЛИЗОВАННЫХ СТРУКТУР НА БАЗЕ ПРОБИОТИКОВ

Рассмотрена современная классификация и номенклатура пробиотических средств. Проведен анализ по составу и форме выпуска препаратов, представленных на российском фармацевтическом рынке. Даны рекомендации по оптимальному дозированию препаратов пробиотиков и повышению их устойчивости с помощью метода иммобилизации. ...

17 10 2026 18:57:45

ФИЗИОЛОГИЧЕСКИЕ ОСНОВЫ КОНКУРЕНТОСПОСОБНОСТИ АМАРАНТА

Статья в формате PDF 119 KB...

16 10 2026 22:25:48

ПРОБЛЕМЫ ВЫБОРА И ОЦЕНКИ ХАРАКТЕРИСТИК ДИВЕРСИФИКАЦИИ ЭКОНОМИЧЕСКОГО РАЗВИТИЯ РЕГИОНА

Статья в формате PDF 167 KB...

15 10 2026 13:32:39

Стрессовый психогеноцид человечества и возможные пути выхода

Статья в формате PDF 107 KB...

14 10 2026 18:43:57

ДИСКОЛЕТ И ЕГО АВТОМОДЕЛЬНОСТЬ

Измерена подъемная сила, создаваемая скошенным экранированным кольцевым крылом. Показано, что экспериментальные результаты удовлетворяют свойству автомодельности. ...

13 10 2026 0:23:30

МОЛОЧНЫЙ КОКТЕЙЛЬ «ДИАБЕТИЧЕСКИЙ»

Статья в формате PDF 244 KB...

12 10 2026 1:23:38

СОСТОЯНИЕ ПРО – И АНТИОКСИДАНТНОЙ СИСТЕМЫ У БОЛЬНЫХ С ХРОНИЧЕСКИМ ПИЕЛОНЕФРИТОМ

Статья в формате PDF 121 KB...

11 10 2026 11:55:50

ПРИМЕНЕНИЕ ТЕСТИРОВАНИЯ ПО ХИМИИ ДЛЯ ОЦЕНКИ ЗНАНИЙ В ШКОЛЬНОМ ОБРАЗОВАНИИ

Статья в формате PDF 264 KB...

10 10 2026 3:59:51

ПРОБЛЕМА ФОРМИРОВАНИЯ КОМПЕТЕНТНОСТЕЙ В УЧЕБНО-ВОСПИТАТЕЛЬНОМ ПРОЦЕССЕ НАЧАЛЬНОЙ ШКОЛЫ

Стратегия социально-экономического развития РФ поставило на государственном уровне вопрос о достижении нового качества общего образования – готовности и способности учащихся к непрерывному образованию. В настоящее время в соответствии с основными тенденциями развития современного образования меняются целевые, процессуальные и результативные компоненты учебно-воспитательного процесса и прежде всего в начальной школе. ...

09 10 2026 16:36:13

ЖАК СЕРГЕЙ ВЕНИАМИНОВИЧ

Статья в формате PDF 115 KB...

08 10 2026 4:56:53

ПОЛУЧЕНИЕ СЕЛЕКТИВНО-МЕЧЕНОГО ВОЛЬТ-СЕНСОРНОГО ДОМЕНА ПОТЕНЦИАЛОЗАВИСИМОГО ИОННОГО КАНАЛА KVAP В БАКТЕРИАЛЬНОЙ БЕСКЛЕТОЧНОЙ СИСТЕМЕ

Статья в формате PDF 118 KB...

07 10 2026 0:49:46

БИОСФЕРА, НООСФЕРА И УПАКОВКА

Статья в формате PDF 111 KB...

06 10 2026 7:32:32

ЭТНОПЕДАГОГИЧЕСКИЕ ВОЗЗРЕНИЯ НАРОДА САХА (НА МАТЕРИАЛЕ ОЛОНХО) (монография)

Статья в формате PDF 112 KB...

05 10 2026 17:15:47

ИССЛЕДОВАНИЕ ВЛИЯНИЯ ВЕЛИЧИНЫ УРАБОТКИ ОСНОВНЫХ И УТОЧНЫХ НИТЕЙ НА СВОЙСТВА ТКАНИ ВЕЛЬВЕТ-КОРД

Статья в формате PDF 106 KB...

04 10 2026 20:21:36

ЭКОНОМИЧЕСКИЕ АСПЕКТЫ УЩЕРБА ОТ СТИХИЙНЫХ БЕДСТВИЙ

Статья в формате PDF 130 KB...

03 10 2026 12:15:34

ПРАВОВОЕ РЕГУЛИРОВАНИЕ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ИНТЕЛЛЕКТУАЛЬНОЙ ДЕЯТЕЛЬНОСТИ

Статья в формате PDF 166 KB...

02 10 2026 9:40:24

РЕСУРСЫ БИОСФЕРЫ ЗЕМЛИ И ПРОДУКТИВНОСТЬ СЕЛЬСКОХОЗЯЙСТВЕННЫХ КУЛЬТУР

Статья в формате PDF 345 KB...

01 10 2026 12:11:43

ИЗУЧЕНИЕ БИОТИЧЕСКОЙ ПРИУРОЧЕННОСТИ ЛИШАЙНИКОВ СМЕШАННОГО ЛЕСА ОЗЕРА КУЧАК

Статья в формате PDF 127 KB...

30 09 2026 22:52:25

ОСОБЕННОСТИ НАРУШЕНИЙ В СИСТЕМЕ ИММУННОГО СТАТУСА ГОМЕОСТАЗА У ЛИЦ, СТРАДАЮЩИХ ПРОФЕССИОНАЛЬНЫМ ЗАБОЛЕВАНИЕМ ОТ ВОЗДЕЙСТВИЯ РТУТЬСОДЕРЖАЩИХ СОЕДИНЕНИЙ

Статья в формате PDF 111 KB...

29 09 2026 4:51:39

АНАЛИЗ ЭКОЛОГИЧЕСКОГО ФОНА КАК ОСНОВА ИЗУЧЕНИЯ ЗАБОЛЕВАЕМОСТИ НАСЕЛЕНИЯ ТЕРРИТОРИИ

Статья в формате PDF 120 KB...

28 09 2026 4:35:23

ПРОФЕССИОНАЛЬНЫЕ СТИЛИ ЧЕЛОВЕКА И ЭФФЕКТИВНОСТЬ ЕГО ДЕЯТЕЛЬНОСТИ

В статье дается концептуальное видение профессиональных стилей человека в зависимости от его профессиональных и жизненных приоритетов. Стиль отражает стратегию адаптации человека. Индивидуальный стиль профессиональной деятельности рассматривается как функция составляющих ее эффективности. Выделено 16 вариантов стилей, в зависимости от значимых для человека составляющих эффективности его труда. В зависимости от профессиональной успешности, степени удовлетворенности трудом и ценностных ориентаций выделено 8 профессиональных стилей, хаpaктеризующих (выявляющих, демонстрирующих) хаpaктер специалиста. ...