IT-Reviews    

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

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

18 02 2020 7:30:40

СУБЪЕКТИВНЫЕ БАРЬЕРЫ ОБЩЕНИЯ У ПОДРОСТКОВ

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

12 02 2020 21:11:48

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

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

10 02 2020 6:39:21

МЕЛКИЕ МЛЕКОПИТАЮЩИЕ В ТРАНСФОРМИРОВАННЫХ УРБАНИЗАЦИЕЙ ЛЕСНЫХ ЭКОСИСТЕМАХ

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

07 02 2020 10:15:16

ИНЖЕНЕРНАЯ ГРАФИКА (электронное учебное пособие)

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

05 02 2020 12:16:17

Изомерия и гомеостаз популяций

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

04 02 2020 3:56:48

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

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

02 02 2020 4:18:57

ЭКОЛОГИЯ СИБИРСКОГО РЕГИОНА: К ИСТОРИИ ПРОБЛЕМЫ

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

28 01 2020 19:35:18

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

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

25 01 2020 16:14:49

ПОДТВЕРЖДЕНИЕ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ ПРЕПАРАТА «КОРТЕКСИН» У ПОДРОСТКОВ МЕТОДОМ ИК-СПЕКТРОМЕТРИИ

Малоизученным направлением в диагностике психосоматических заболеваний является исследование физико-химических характеристик крови. Методы, применяемые в диагностике и контроле лечения психосоматических заболеваний в целом, и задержке психического развития в частности ( З П Р), являются достаточно субъективными. Во многом это обусловлено отсутствием однозначных лабораторно-диагностических методов, позволяющих осуществлять диагностику на ранних этапах заболевания. Целью нашего исследования явилось изучение особенностей И К – спектра сыворотки крови детей подросткового возраста. В качестве субстрата для исследования использовали сыворотку крови больных детей, которую затем подвергали И К-спектроскопии с регистрацией спектров поглощения в области 3500-963 см-1. Исследована сыворотка крови 30 детей с диагнозом З П Р и 30 здоровых, сопоставимых по возрасту и полу. Было проведено сравнение И К-спектра сыворотки крови больных с  З П Р и здоровых доноров. Достоверно выявлена разница показателей инфракрасной спектрометрии в норме и патологии, а так же проверена эффективность применяемой терапии. Таким образом, с помощью И К-спектрометрии установлены особенности спектров сыворотки крови детей подросткового возраста и выявлены отличия в спектре у детей с  З П Р и динамические изменения в процессе лечения, что может использоваться для диагностики данной патологии, а так же для контроля за эффективностью проводимого лечения. ...

18 01 2020 15:42:16

СТРОЕНИЕ И ТОПОГРАФИЯ ТКАНЕВЫХ КАНАЛОВ

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

17 01 2020 0:15:17

Методы лазеротерапии при астматическом бронхите

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

13 01 2020 7:35:11

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

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

12 01 2020 15:45:13

ЕСТЕСТВЕННОНАУЧНЫЕ ОСНОВАНИЯ СТЕРЕОХРОНОДИНАМИКИ

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

10 01 2020 0:56:50

Бозаджиев Владимир Лукьянович

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

08 01 2020 2:27:15

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

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

06 01 2020 7:16:32

ПРОГНОЗ ВВП РОССИИ ЗА 2007 ГОД С УЧЕТОМ ДАННЫХ LENTA.RU

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

03 01 2020 19:33:34

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

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

28 12 2019 6:12:24

ПРИДНЯ МИХАИЛ ВАСИЛЬЕВИЧ

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

26 12 2019 14:31:37

СТРУКТУРА ВИРУСНОЙ ПАТОЛОГИИ ЛОР-ОРГАНОВ

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

23 12 2019 16:11:12

Правовые аспекты эвтаназии

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

21 12 2019 9:45:22

ГРЕХОПАДЕНИЕ В КОНТЕКСТЕ ПСИХОАНАЛИЗА

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

20 12 2019 0:46:10

ЧИБИСОВ СЕРГЕЙ МИХАЙЛОВИЧ

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

19 12 2019 23:52:27

ПЕДАГОГИЧЕСКОЕ СОПРОВОЖДЕНИЕ ОДАРЁННЫХ ДЕТЕЙ

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

18 12 2019 13:35:14

О ЗАКОНЕ АРХИМЕДА

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

13 12 2019 2:24:58

Развитие стекловидного тела глаза человека

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

30 11 2019 23:40:46

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

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

27 11 2019 11:44:59

СИСТЕМА УПРАВЛЕНИЯ В ФОРМАЛИЗОВАННОМ ВИДЕ

Представлена система управления в формализованном виде, что облегчает анализ свойств системы, позволяет намечать пути ее совершенствования. ...

13 11 2019 9:54:52

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

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

12 11 2019 7:25:27

ШОШОНИТОВЫЕ ГРАНИТОИДЫ ТИГИРЕКСКОГО МАССИВА АЛТАЯ: ГЕОХИМИЯ, ПЕТРОЛОГИЯ И РУДОНОСНОСТЬ

риведены геологические, геохимические и петрологические данные по шошонитовым гранитоидам Тигирекского массива Алтая. В составе массива выделены 5 фаз: 1 – габбро; 2 – диориты, монцодиориты; 3 − сиениты, гранодиориты, граносиениты; 4 – граниты, умеренно-щелочные граниты; 5 – лейкограниты, умеренно-щелочные лейкограниты с флюоритом. Породные типы массива отнесены к нормальной известково-щелочной и высококалиевой шошонитовой сериям. Сиениты и монцодиориты тяготеют по составу к банакитам. В процессе становления массива проихсодила диффреренциация глубинного очага с фракционированием редкоземельных элементов, что отразилось на соотношении в породах элементов групп LILE и HFSE со значительной деплетированностью последних. В породах происходила смена типа тетрадного фракционрования редкоземельных элементов, что связано с различной насыщенностью расплавов флюидами и летучимим компонентами. С массивом связаны месторождения и проявления железа, вольфрамаа, молибдена, бериллия, аквамарина, горного хрусталя и раухтопаза. ...

08 11 2019 8:37:48

ИСКУССТВОВЕДЕНИЕ В СИСТЕМЕ ГУМАНИТАРНОГО ЗНАНИЯ

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

03 11 2019 22:14:50

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

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

23 10 2019 1:56:26

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

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

20 10 2019 2:39:34

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

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

18 10 2019 9:28:14

ЛЕЧЕНИЕ БОЛЬНЫХ С УКУШЕННЫМИ РАНАМИ

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

15 10 2019 18:20:22

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

Получены сведения о начальных стадиях развития. Согласно профильно-генетической классификации почв техногенных ландшафтов [5] морфологически выделены элювиоземы инициальные, эмбриоземы инициальные и органо-аккумулятивные. Экспериментально показано, что выделение этих типов почв вследствие низкой скорости почвообразования пока возможно только по почвенно-биологическими показателями. Установлено, что микробное сообщество молодых почв на отвалах Мирнинского Г О К имеет характерные черты для начальной стадии почвообразования: более высокую в сравнение зональной почвой численность; низкую активность утилизации целлюлозы; низкую инвентарную. Последнее свидетельствует о низкой скорости формирования органо-минерального комплекса почвы. Выявлено, возможности дифференциации типов молодых техногенных ландшафтов по способу субстратов поддерживать начальный рост тест растений. ...

12 10 2019 13:47:46

СЛЕНГ РУССКОЙ МОЛОДЕЖИ

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

11 10 2019 13:10:59

СТУПЕНЧАТЫЕ ПРЕДСТАВЛЕНИЯ НА ГРАФАХ

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

04 10 2019 18:44:23

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

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

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

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

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

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

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

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