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

Авторы
Файлы

Булашкова М.Г. Ломакина А.Н. Чаузова Е.А. Зотова С.А. Статья в формате 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 116 KB...

15 08 2026 15:40:49

РАЗВИТИЕ ИННОВАЦИОННЫХ ТЕХНОЛОГИЙ В СИСТЕМЕ ДОПОЛНИТЕЛЬНОГО ОБРАЗОВАНИЯ (РЦ НТТУ)

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

14 08 2026 0:21:19

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

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

13 08 2026 14:30:47

ОЧИСТКА СТОЧНЫХ ВОД ОТ ИОНОВ ТЯЖЕЛЫХ МЕТАЛЛОВ С ИСПОЛЬЗОВАНИЕМ ГАЛЬВАНОШЛАМОВ

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

12 08 2026 8:39:59

ВНЕДРЕНИЕ ВЕРОЯТНОСТНЫХ МЕТОДОВ ОЦЕНКИ НАДЕЖНОСТИ ЭКСПЛУАТИРУЕМЫХ СООРУЖЕНИЙ С ПОВРЕЖДЕНИЯМИ В ПРАКТИКУ

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

11 08 2026 6:47:38

СОВРЕМЕННЫЕ ТЕНДЕНЦИИ В РАЗВИТИИ НАУЧНЫХ ИССЛЕДОВАНИЙ ПО МОРФОЛОГИИ

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

10 08 2026 15:35:18

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

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

09 08 2026 13:25:34

ГАНСБУРГСКИЙ АНДРЕЙ НИКОЛАЕВИЧ

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

08 08 2026 5:52:25

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

Цель. Изучить показатели пероксидного статуса и вариабельность сердечного ритма у больных ишемической болезнью сердца с пароксизмальной формой фибрилляции предсердий. Материалы и методы. В исследование было включено 22 больных ишемической болезнью сердца с пароксизмальной формой фибрилляции предсердий. Контрольную группу составили 15 относительно здоровых человек. Нейровегетативный статус изучали методом кардиоинтервалометрии. Активность перекисного окисления липидов у пациентов оценивали по уровню фоновой концентрации малонового диальдегида в эритроцитах крови. Концентрацию малонового диальдегида определяли при поступлении на фоне фибрилляции предсердий, а также в первые сутки после восстановления синусового ритма параллельно с проведением кардиоинтервалометрии. Результаты. По сравнению с контрольной группой у больных с фибрилляцией предсердий в момент нарушения ритма имеет место повышение концентрации малонового диальдегида и некоторое ее снижение в первые сутки после восстановления. Данные кардиоинтервалометрии указывают на достоверное повышение активности симпатоадреналовой системы, снижение активности парасимпатической системы и повышение активности регуляторных систем организма в целом у больных ишемической болезнью сердца с фибрилляцией предсердий после восстановления синусового ритма. Заключение. Дальнейшее изучение исследуемых показателей и их фармакологическая регуляция позволят улучшить лечение и прогноз у данной категории больных. ...

07 08 2026 13:26:39

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

Были построены модели: первая ─ модель деятельности специалиста в сфере безопасности жизнедеятельности на производственном объекте, состоящая из блоков знаний, умений, навыков, компетенций и компетентностей, выявленных на основе определения специфики его деятельности в условиях современных трудовых отношений (рассматривалась строительная отрасль) и составления списка умений, знаний, навыков и компетентностей. Вторая ─ модель специалиста (строится на основе первой), третья – модель обучения, включает в себя такие компоненты: цель обучения, функции, задачи, содержание, формы и методы, критерии оценки. ...

06 08 2026 13:23:45

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

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

05 08 2026 2:58:33

СПОСОБ ДЫМОГЕНЕРАЦИИ В СРЕДЕ ИНЕРТНОГО ГАЗА С ИНДУКТИВНЫМ ПОДВОДОМ ЭНЕРГИИ

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

04 08 2026 9:14:48

ЗАЩИТА ОКРУЖАЮЩЕЙ СРЕДЫ ОТ АНТРОПОГЕННЫХ КОМПОНЕНТОВ АЭРОЗОЛЯ

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

03 08 2026 20:18:26

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

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

02 08 2026 21:24:31

Клиническое наблюдение генерализованной формы ветряной оспы

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

01 08 2026 18:15:19

ИССЛЕДОВАНИЕ ФМР И СВР В ПЛЕНКАХ НАНОКРИСТАЛЛИЧЕСКИХ СПЛАВОВ (FE-NI)-P

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

31 07 2026 18:32:47

ПИЩЕВАЯ, ПЫЛЬЦЕВАЯ И ЛЕКАРСТВЕННАЯ АЛЛЕРГИЯ: ВОЗМОЖНЫЕ ПЕРЕКРЕСТНЫЕ АЛЛЕРГИЧЕСКИЕ РЕАКЦИИ

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

30 07 2026 0:39:40

ЛЕЧЕНИЕ МИОКАРДИТА У СОБАК

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

29 07 2026 7:52:39

Особенности функциональной активности иммунокомпетентных клеток при Helicobacter pylori-ассоциированной язвенной болезни двенадцатиперстной кишки с различными исходами эрадикационной терапии

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

28 07 2026 9:58:49

КАРДИОГЕМОДИНАМИЧЕСКИЕ ЭФФЕКТЫ ПОД ВЛИЯНИЕМ ГЕСПЕРИДИНА У ИНСУЛЬТНЫХ БОДРСТВУЮЩИХ КРЫС

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

27 07 2026 7:29:10

Влияние аллергизации на биоаминный статус коркового слоя почек и околопочечной бурой жировой ткани

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

26 07 2026 0:25:24

ФАЗОВЫЕ ПРЕВРАЩЕНИЯ ПРИ СИНТЕЗЕ КРЕМНЕЗЕМИСТОГО АМОРФНО-КРИСТАЛЛИЧЕСКОГО КОМПОЗИТА

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

25 07 2026 3:39:51

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

Цели исследования: определить нормальную динамику показателей вариабельности ритма сердца в ответ на физиологическую нагрузку у мужчин и женщин. Дать клинико-физиологическую оценку показателей. Материалы и методы. Нами было обследованы 48 здоровых пациентов, из них 32 – мужчины, 16 – женщины. Средний возраст 46 (± 3,6) года. Исследование проводилось на комплексе суточного мониторирования ЭКГ «ДНК» с программой вариабельности сердечного ритма при проведении лестничных проб. Определяли: ЧСС ночью и на нагрузке, депрессию ST, параметры ОНЧ, НЧ, ВЧ, НЧ/ВЧ – как в покое, так и на нагрузке, SDNN и pNN50 за сутки. Результаты. Обнаружено, что на нагрузках значительно повышается мощность ОНЧ (на 80,4%, t – 2,6) и синнергично снижается мощность НЧ (на 72%, t – 1,7) и ВЧ (на 65%, t – 1,6). Пoлoвых различий не выявлено (t – 0,8). Заключение: показатель «ОНЧ» отражает реализацию синусовым узлом симпатических влияний. «ВЧ» отражают активность парасимпатической нервной системы (что соответствует литературным данным). Показатель «Низкие Частоты» не может служить маркером активности симпатической системы (как предлагается в литературе), а скорее отвечает за реализацию вагуса или иной тормозящей структуры. НЧ/ВЧ не может служить показателем вегетативного баланса. ...