IT-Reviews    

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

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

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

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

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

.

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

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

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

 

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

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

  

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

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

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

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

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

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

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

  

Рис.4




Отзывы (через Facebook):

Оставить отзыв с помощью аккаунта FaceBook:

ВИНДЖАММЕРЫ – «ВЫЖИМАТЕЛИ ВЕТРА»

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

20 11 2020 14:23:40

ИСПОЛЬЗОВАНИЕ МЕТОДА ПРОЕКТОВ В ЛИЦЕЕ ПРИ ВУЗЕ

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

19 11 2020 11:21:42

Анализ взаимодействия техносферы и окружающей среды

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

14 11 2020 16:48:24

УПРАВЛЕНИЕ АДАПТИВНЫМИ ОБРАЗОВАТЕЛЬНЫМИ СИСТЕМАМИ

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

10 11 2020 16:41:46

КОНФОРМАЦИОННАЯ ИЗОМЕРИЗАЦИЯ МЕТИЛБОРНОЙ КИСЛОТЫ

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

31 10 2020 4:18:38

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

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

28 10 2020 10:55:43

ФЕНОТИПИЧЕСКАЯ ДИАГНОСТИКА СЕЛЬСКОЙ МЕСТНОСТИ

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

14 10 2020 7:47:49

Влияние фонового квч излучения на биологические объекты и циркадные ритмы больных гипертонической болезнью

Ф Р И-терапия ( С Е М-терапия) основана на использовании материалов с управляемой энергетической структурой (CEM – Controlled Energy Material). Излучателем сверхслабых излучений К В Ч-диапазона при интенсивности 10–16–10–20  Вт/см2 является диод Ганна. Представлена оценка влияния фонового миллиметрового излучения на стафилококки, на нативную кровь, а также на вегетативный статус пациента гипертонической болезнью в сравнительном аспекте по графикам циркадных ритмов пульса при приеме: препаратов, не влияющих на ритм сердца; структурированной воды, активированной посредством аппарата «Cem-Tech»; полной дозы препарата лодоза; воды, содержащей информацию о порошкообразном лодозе. Рассмотренная индивидуальная динамика параметров ритмограммы, вычисленных на основе регистрации 500 межпульсовых интервалов, оценивалась с вычислением показателей уровня статистической значимости различий. Показано, что прием препарата Лодоз и воды содержащей информацию о препарате Лодоз сопровождается сходными изменениями, как частоты пульса, так и внутренней структуры информационного паттерна HRV. Динамика параметров ритма сердца свидетельствует о мобилизации холинергических механизмов регулирования. ...

06 10 2020 18:14:12

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

В данной работе предложена эволюционная модель формирования двумерных структур. Определены алгоритмы формирования структур в априори структурированном двумерном пространстве путем заполнения его в соответствии с определенными эволюционными правилами. ...

05 10 2020 17:11:31

НОВЫЕ МОЛЕКУЛЯРНО-ГЕНЕТИЧЕСКИЕ МОДЕЛИ ЭПИЛЕПСИИ

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

04 10 2020 18:51:38

ПРЕПАРАТИВНЫЕ МЕТОДЫ СИНТЕЗА СУЛЬФИДОВ МЕТАЛЛОВ В СРЕДЕ Н-АЛКАНОВ

Разработаны препаративные методы синтеза сульфидов металлов в среде жидких н-алканов. Представлены результаты «дробного» и «свернутого» методов синтеза сульфидов металлов. Состав соединений установлен методами химического, рентгенофазового и рентгенофлуоресцентного анализов. ...

30 09 2020 17:49:13

ОСНОВНЫЕ ПРИНЦИПЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

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

28 09 2020 9:39:22

«КОНСУЛЬТАТИВНАЯ ПСИХОЛОГИЯ»

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

23 09 2020 10:53:39

ЭКОЛОГИЧНАЯ ДРЕНАЖНАЯ ТЕХНИКА

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

22 09 2020 8:30:59

МОДЕРНИЗАЦИЯ ГРОХОТА С ЭЛЕМЕНТАМИ ДИНАМИЧЕСКОГО СИНТЕЗА

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

21 09 2020 10:14:48

УНИВЕРСАЛЬНЫЙ БЛОК УПРАВЛЕНИЯ ЭНЕРГОНАГРУЗКАМИ

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

14 09 2020 4:32:43

НОВЫЙ СПОСОБ ОПЕРАТИВНОГО ЛЕЧЕНИЯ ПАХОВЫХ ГРЫЖ

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

11 09 2020 16:35:14

ТЕПЛОВОЙ РАЗГОН В ЩЕЛОЧНЫХ АККУМУЛЯТОРАХ

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

04 09 2020 16:44:14

БИОХИМИЯ КРОВИ (учебное пособие)

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

01 09 2020 3:49:22

ПЕРСПЕКТИВЫ ПОЛУЧЕНИЯ БЕЛКА ИЗ ПШЕНИЦЫ

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

23 08 2020 10:35:13

ПЛАНЕТАРНЫЙ МЕХАНИЗМ С БЕЗВОДИЛЬНЫМ САТЕЛЛИТОМ

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

17 08 2020 22:30:19

ХАШАЕВ ЗАУР ХАДЖИ-МУРАДОВИЧ

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

10 08 2020 12:36:48

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

Обучение взрослых дипломированных специалистов существенно отличается от обучения студентов. Если на додипломном уровне приемлема педагогическая модель обучения с доминантой обучающего, то на этапе же последипломного образования необходимо руководствоваться продуктивной андрагогической моделью обучения. Её главный постулат: обучающийся – ведущее звено в процессе образования. Исходя из этого, в течение ряд лет мы используем методику психологического типирования личности американского исследователя Д. Кейрси. И на основании выявления уровней подготовки, психофизиологических и личностных особенностей обучающихся практикуем деловые игры, мастер-классы, создание взрослыми обучающимися порт-фолио непосредственно на рабочем месте. Результаты положительные. ...

07 08 2020 16:59:17

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

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

06 08 2020 8:11:55

КОНКУРЕНТОСПОСОБНОСТЬ ЭКОНОМИКИ ТОМСКОЙ ОБЛАСТИ

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

04 08 2020 17:25:32

ШАТОВ АЛЕКСАНДР АЛЕКСЕЕВИЧ

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

01 08 2020 6:25:37

ИНФОРМАЦИОННЫЙ АНАЛИЗ СПИННОМОЗГОВОЙ ЖИДКОСТИ

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

27 07 2020 4:45:50

ИННОВАЦИОННЫЕ ТЕХНОЛОГИИ В ЛЕСНОЙ ОТРАСЛИ

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

23 07 2020 17:34:51

Хирургическое лечение острого холецистита

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

18 07 2020 8:27:58

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

В статье отражены результаты комплексного исследования подготовленности спортсменок, специализирующихся в беге на 300-400 м с барьерами. Дан анализ статистически достоверных различий по педагогическим, физиологическим и биометрическим показателям в ответственейший момент спортивной карьеры - момент перехода с «детской» дистанции (бега на 300 м с барьерами) на олимпийскую дисциплину (400 м с барьерами). Выявлены взаимосвязи между различными сторонами подготовленности: физической, функциональной и технической. Представленный материал можно использовать в виде модельных характеристик для девушек в возрасте 15-16 лет и закономерностей становления спортивного мастерства при уточнении Учебной программы для детско-юношеских спортивных школ, специализированных детско-юношеских школ олимпийского резерва и школ высшего спортивного мастерства по разделу « Барьерный бег». ...

17 07 2020 9:52:47

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

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

16 07 2020 2:49:27

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

Цитомегаловирусная инфекция ( Ц М В И) относится к числу самых распространенных вирусных заболеваний. Наиболее уязвимыми являются плод и новорожденный. Целью данного исследования явилась ранняя диагностика нарушений внутриутробного состояния плода у беременных с Ц М В И. Благодаря разработке новой ультразвуковой аппаратуры, основанной на эффекте Допплера проводились исследования кровотока в магистральных сосудах, а именно маточных артериях. Согласно поставленной цели по разработанной нами методике были рассмотрены анкеты клинико-лабораторного исследования у беременных с Ц М В И. Всего обследовано 115 женщин с различными сроками беременности и 40, составляющих контрольную группу. Из общего числа беременных у 64 (55,7 %) Ц М В И протекала в легкой форме, первично-латентную инфекцию наблюдали у 48 (41,7 %) пациенток. Ультразвуковое сканирование проводилось в разные сроки беременности, преимущественно во II-III триместрах, однако, по показаниям в некоторых случаях У З И осуществляли и в более ранние сроки. Исследование проводилось на аппарате «Aloka» 1700 SSD с допплерометрическим блоком пульсирующей волны, с использованием трансдьюсеров 3,5 и 5 м Гц и трансвагинальным датчиком 6,5 м Гц. При допплерографии в акушерстве применяется качественный анализ кривых скоростей кровотока ( К С К). Определяются систоло-диастолическое соотношение ( С Д О), индекс резистентности ( И Р), пульсовый индекс ( П И). В нашем исследовании наиболее неблагоприятным признаком явилось появление дикротической выемки на фоне двухстороннего нарушения маточно-плацентарного кровотока. У беременных с латентной формой Ц М В И нами выявлена также ассиметрия маточно-плацентарного кровотока. Изменение кровотока в правой М А более выражено, что, по-видимому связано с наличием плацентации одноименной стороны. Снижение маточно-плацентарного кровотока в правой М А постепенно приводит к снижению в левой М А, и связано с наличием морфологических изменений в плаценте. Более выраженные нарушения маточно-плацентарного кровотока встретились у беременных с С З Р П. Из этого следует, что основная причина гипотрофии – это нарушение маточно-плацентарного кровотока. ...

06 07 2020 17:24:27

МОДУЛЬНЫЕ ТЕХНОЛОГИИ РЕАЛИЗАЦИИ УЧЕБНОГО ПРОЦЕССА

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

05 07 2020 7:22:13

ПОЧЕМУ ДВИЖЕНИЕ – ЭТО ЖИЗНЬ

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

04 07 2020 11:15:20

ИММУНОЛОГИЯ (учебное пособие)

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

02 07 2020 9:48:21

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

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

30 06 2020 8:11:19

Еще:
Обзоры -1 :: Обзоры -2 :: Обзоры -3 :: Обзоры -4 :: Обзоры -5 :: Обзоры -6 :: Обзоры -7 :: Обзоры -8 :: Обзоры -9 :: Обзоры -10 :: Обзоры -11 ::

Последовательность подготовки научной работы может быть такой:

Выбор темы. Это важный этап. Во-первых, тема должна быть интересна не только вам, но и большинству слушателей, которым вы будете её докладывать, чтобы вы видели заинтересованность в их глазах, а не откровенную скуку.

Выбор целей и задач своей научной работы. То есть, нужно сузить тему. Например, тема: «Грудное вскармливание», сужение темы: «Грудное вскармливание среди студенток нашего ВУЗа». И если общая тема мало кому интересна, то суженная до рамок собственного института или университета, она становится интересной практически для всех слушателей. Целью может стать: «Содействие оптимальным условиям вскармливания грудью детей студентов нашего ВУЗа», а задачей — доказать, что специальные условия, созданные для кормящих студенток, не помешают их успеваемости, но уменьшат количество пропусков, академических отпусков и способствуют выращиванию здоровых детей — нашего будущего. Понятно, что эта тема подходит для студентов медицинских и педагогических ВУЗов, но и в других учебных учреждениях можно найти темы, интересные всем.

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

Систематизировать материал и подготовить презентацию.

Подготовиться к выступлению.

Выступить и получить: награду, удовольствие и опыт, чтобы в следующем году выступить ещё лучше и сорвать шквал аплодисментов, стать узнаваемым, а значит — более конкурентоспособным!