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:

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

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

04 09 2020 2:46:43

НЕКОТОРЫЕ АСПЕКТЫ СОВРЕМЕННОЙ КВАНТОВОЙ ХИМИИ

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

22 08 2020 10:17:19

МЕТОДИКА ПРЕПОДАВАНИЯ DELPHI: ОТ ПРОСТОГО К СЛОЖНОМУ

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

21 08 2020 23:31:22

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

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

17 08 2020 22:40:27

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

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

14 08 2020 3:59:49

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

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

11 08 2020 13:32:10

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

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

01 08 2020 20:53:36

СЛЕПАЯ КИШКА У БЕЛОЙ КРЫСЫ

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

30 07 2020 22:18:12

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

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

24 07 2020 11:57:39

АГАФОНОВ АЛЕКСАНДР ТИМОФЕЕВИЧ

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

21 07 2020 22:14:54

ВОДНЫЙ РЕЖИМ РЕК СЕВЕРО-ЗАПАДНОГО КАВКАЗА

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

18 07 2020 0:49:29

СЛИНКИН СЕРГЕЙ ВИКТОРОВИЧ

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

17 07 2020 18:19:42

О НАХОЖДЕНИИ ОБЪЕМОВ ТЕЛ ВРАЩЕНИЯ

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

13 07 2020 2:43:37

КЛАССИЧЕСКАЯ ФИЗИКА НА ГНИЛОМ ФУНДАМЕНТЕ (КАТАСТРОФА В МЕХАНИКЕ )

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

02 07 2020 11:27:10

ЭНДОЭКОЛОГИЯ И ПРОБЛЕМА ПЕКТИНА

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

30 06 2020 15:11:35

СОВРЕМЕННЫЕ GRID – ТЕХНОЛОГИИ

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

29 06 2020 5:54:25

Никитюк Надежда Федоровна

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

26 06 2020 16:43:17

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

В статье описываются математические модели в виде уравнения регрессии, которое позволяет по клиническим признакам хронической сердечной недостаточности со статистической достоверностью предсказать результаты 6-минутного теста. ...

16 06 2020 15:57:46

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

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

14 06 2020 6:12:27

КОРЯК ЮРИЙ АНДРЕЕВИЧ

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

13 06 2020 15:15:31

Селицкий Александр Яковлевич

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

31 05 2020 12:53:48

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

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

26 05 2020 11:57:34

ГРИПП. КЛИНИЧЕСКАЯ СИМПТОМАТИКА

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

21 05 2020 13:25:25

Американский студенческий сленг начала 21 века

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

17 05 2020 9:48:12

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

В эксперименте в сравнительном плане, изучено влияние радиационного облучения, ртутной интоксикации и гипотиреоза на систему иммунитета, на активность ферментов обмена пуриновых нуклеотидов: 5’-нуклеотидазы, А М Ф-дезаминазы и аденозиндезаминазы, на активность ферментов антиоксидантной системы: супероксиддисмутазы ( С О Д), глутатионпероксидазы ( Г П О), глутатионредуктазы в ткани печени, почек и в сыворотке крови. Установлены значительные сходства в механизме клеточных и метаболических эффектов радиации, гипотиреоза, ртутной интоксикации. Независимо от ткани и воздействующего на организм фактора (радиация, гипотиреоз, ртутная интоксикация) имеет место однотипные изменения активности супероксиддисмутазы, глутатионпероксидазы и глутатионредуктазы, что свидетельствует о том, что указанные воздействия являются стрессорными. Изменения в иммунной системе, обнаруженные при ионизирующем излучении, практически однотипны изменениям иммунитета при гипотиреозе. При ртутной интоксикации в отличие от гипотиреоза и радиации имеет место снижение уровня В-лимфоцитов, что в какой-то мере объясняется особенностями эффектов ртутной интоксикации на систему иммунитета и ферменты метаболизма пуриновых нуклеотидов. В определенной степени эти различия можно объяснить разной степенью становления защитных механизмов и степенью целостности регуляторной функции адрено-тиреоидной системы. ...

12 05 2020 15:58:37

НОВЫЙ ПОДХОД К ОЦЕНКЕ УЩЕРБА ВОДНЫМ РЕСУРСАМ

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

10 05 2020 1:49:11

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

Изучено влияние высококремнистых природных добавок на качество птицеводческой продукции. Установлено, что включение природных добавок в рацион кур-несушек улучшает прочность скорлупы, что непосредственно ведет к снижению процента боя яиц, повышению инкубационных показателей яиц и увеличению процента вывода цыплят. ...

09 05 2020 17:23:26

Взаимодействие науки и технологии

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

04 05 2020 13:58:19

ПОДЖЕЛУДОЧНАЯ ЖЕЛЕЗА У БЕЛОЙ КРЫСЫ

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

03 05 2020 18:30:20

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

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

26 04 2020 13:15:23

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

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

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

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

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

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

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

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