Введение в прикладную комбинаторику, Кофман А. (984071), страница 40
Текст из файла (страница 40)
307. 310 х, Хз Хз Ов /в О~' я Е/БПЕББ Е 4ПЕи 07 ЕППЕиПЕ65 Е7,ПЕМПЕБ5 Е7,ПЕ56ПЕ7 Е74ПЕ55ПЕП /б в' и Об /в Сб.'7 и ЕППЕППЕППЕ57 ЕППЕипЕББПЕ67 Е74ПЕипЕБ/пЕ76 Е/БПЕиПЕ47ПЕ7 ЕмпЕ пЕ БпЕ.7ПЕ5ПЕ7 ПЕдпЕБ" Е/БПЕипЕ БПЕБ/ПЕ47ПЕ> ПЕББПЕ 6 УПРАЖНЕНИЯ 54А. Найти минимальные гамильтоновы контуры графов с матрипами! Х! Хз Хз Х4 Хь Х! Хз Хз Х4 Хб х, Х! Х4 Хб б) Х! Хз Х! Хв Хб Хб Х! Хз Хз Хв Хб Хб Х) х, Хз ХЗ Хв Х7 в) Х! Х2 Хз Х4 Хб Хб Х! Хз Хз Х4 Хз Хб Хт Ха Х! Х! Х2 Хз Хз Хз Х4 Х4 Хб Ха 54Б. Найти максимальные гамильтоновы контуры пля графов из упрзжне. иия 54А. 545. Найти все минимальные гамильтоновы контуры для каждого из тра.
фов из упражнения 54А. Хз х Хз Хб Хб Х7 Хз ХЗ Хз Х4 54Г. Для каждого из графов в упражнении 54А найти минимальный га. мильтонов путь. 54Д. Для каждого из графов в упражнении 54А найти назначение с минимальным значением. 54Е. Указать все назначения с минимальным значением длн графов с матрицами: Х! Хз Хз Х! Хз Х! Хз Хз Хч Хз Х! Хз Хз Х! Хз Хб х, х, х, х, Х3 Хз Хз Х4 Хз Хз а) Хб 54Ж.
Для матриц а) и б) из упражнения 54Е определить назначения с максимальным значением. 543. Указать минимальный гамильтонов контур графа с матрицей: 30 33 3! 19 26 24 18 32 1б 25 31 28 18 19 18 18 22 23 23 1б 27 27 31 !3 24 18 19 18 34 20 25 31 21 24 1О 12 17 1б 18 27 21 19 15 35 19 13 18 13 13 22 25 21 17 18 27 24 3! 18 18 19 17 29 1б 23 18 31 й 55. Нахождение хорошего решения эвристическим методом На практике часто требуется найти оптимальное решение некоторой задачи, для которой не имеют алгоритма оптимизации. В этом случае используют эвристический метод, позволяющий улучшить исходное решение без уверенности в том, что получат оптимальное решение. В качестве примера мы рассмотрим эвристический метод для задачи о перевозках, предложенный Ф л е т ч е р о м н К л а рком (Р1е1с )т е г, С) а г й е), Мапаиегпеп1 апс1 Ма1)1егпа1)сб.
Воз)пебб, РцЫ, 1Ы. 1 опт)оп, 19б4. 324 Пусть предприятие Р, снабжаег и складов ЄЄ..., Р., используя неограниченный парк машин, каждая из которых грузоподъемности С. Известна стоимость ь(!! перевозки из Р; в Р; (41!! может не быть равной ь(!!). Каждая отправляющаяся с предприятия машина должна вернуться обратно. Вместимость склада Р, равна Сь При какой минимальной общей стоимости перевозок можно заполнить все склады при условии, что маршруты перевозок представляют собой контуры, попарно пересекающиеся лишь в Рой Можно рассматривать также различные обобщения этой задачи, вводя, например, условия на грузоподъемность машин, проходимость дорог, количество заездов на склад и т.
п. Пусть задача о перевозках задана таблицей 60 34 24 33 зз 52 62 63 46 зз зз 38 35 58 83 76 34 57 75 Зб 5З 60 72 94 48 Зб о ю 70 60 70 15 0 35 44 6! 7З 39 зз зб 21 50 70 48 26 43 8О 8! 34 62 94 73 72 44 52 зо зо 55 105 96 70 65 (55. 1) 2 Рб ! Р7 ЗР, 24 0 23 26 зо 47 зз 94 61 8З 23 0 зо зо 62 86 80 зз 70 39 55 58 50 46 59 48 21 8 Ро 47 62 70 86 79 з! 26 31 0 46 57 105 10 Р!о З Р„ 80 58 26 63 53 Зб 65 80 8! 50 с=в Граф на рис.
351 представляет одно из возможных решений (направления всех стрелок можно изменить на обратные). Значения для составляющих его контуров: (Ро Рь, Рп Рь Ро): 60+ 53+ 36+ 34 = 183; (Ро Р„Р! Ро): 50+ 34+ ЗЗ = 117; (Ро Рь Рь Рг Рь Ро): 52+ 30+ 23+ 30+ 33 = 168; (55.2) (Ро, Р!о, Ро): 62+ 62 = 124; (Ро Ро Ро): 46 + 46 = 92 (такие перевозки возможны, так как вместимость складов на контурах не превосходит С). Общая стоимость 183+ 1!7+ + 168 + 124 + 92 = 684. с! Ро 8 Р! 3 Рь ь 5 Рь 4 Рь РО 1 Рь ь !4 Рь Рь 7 Рь Ро !О ьп Изложим теперь метод Флетчера и Кларка. А) Для каждой пары вершин Р, и Рб (2', 1=1, 2, ... л) вычислим величины ам = АО + ~(ОУ вЂ” 2(О, (55.3) записывая их в таблицу, Б) Для решения Я вычисляем у;; У~= О, если ребро (Р„РО) не входит в Я, 1, если ребро (Ро РО) входит в 5. (55.4) Все вершины Р», Р», ..., Р» (исключая РО) контура, входящего в 5, объединим в класс (Р,, Р», ..., Р» ) и через Я (Р», Р,, Р» ~ обозначим стоимость перевозки по этому маршруту.
Если вершины Р, и Р1 принадлежат различным классам (Рь Р»,, ..., Р» ) и (РО Р», ..., Р, )) то можем объединить их в класс (Ро Рь Р»,, ..., Р», Р2, ..., Р» ') прн условии, что а) у,=1 и уб — — 1; (55.5) б) Я~(Ро Р»,, ..., Р»,(+ЯДРО Р~,, ..., Р2 (~(С. (55.6) В) Начинаем с тривиального решения (РО, Р„РО), (РО Рм РО)» (РО Рп1 РО)' Г) Среди Ц, ) О выбираем наибольшее, не выбиравшееся ранее (если таковых несколько, то берем любое из ннх).
Если условия (55.5) и (55.6) выполняются, то объединяем Рб классы, содержащие Р, и Р; в один и отмечаем полу- Р жирным шрифтом выбран» Р~ ное ) О. Если же одно из 'б этих условий не выполняется, то в клетку с этим Хн Рб ставим крестик и ищем но- Р в вое ХО, как указано в начале этого пункта. Д) Выписываем соответствующие уь Е) Возвращаемся к Г). Поиск решения продолжаем до тех пор, пока имеем возможность выбрать ).О ) О. Таким образом, мы придем к наилучшему решению (относнтельно данного метода).
Пример 1. По формуле (55.3), исходя нз таблицы (55.1), вычисляем Х;; и составляем матрицу на рис. 352. Начинаем с Р26 тривиального решения, представленного на рис. 353. В матрице 11Л4911 находим (55.7) гпахЛОг — — ЛОо,г — — 86 4,/ Имеем Я (РОО] + Я 1Рг~ = СОО+ Сг = 10+ 3 = 13 ( 15 (55 8) Объединяем классы (РОО) и (Рг) в (Рци Рг) и выделяем ЛОюд на Рис. 333. рис. 352 полужирным шрифтом. Таблица для у, не меняется.
Новое решение дает рис. 354. Затем находим ? их 9 = 82 у ~о = т'9 = 1 Я (Р9о Рг~ + Я (РО1= 13+ 8=21) 15. (55.9) (55.10) 32? Р4 Рг Ра Р4 Рб Рб Рт Рб Ро Рго Рц РО Р, РО Рз Р, Р, Р, РО РО Рм Р, О РО РО РО РО РО РО РО О РО 49 Ри К О О с Рис. 332. Матрица Ло = йОО+ лат — АО Клетку (10, 9) помечаем крестиком. Далее Лз.
2 = 79 и Л, ц го = 79. Берем Лз,д —— 79. Имеем у,= уз=! и Я )Рз) + Я )Рд Рго) =8+!3= 21 >!5. Клетку Лз,, помечаем крестиком. Затем берем Лц и — — 79. Имеем (55.11) (55,12) (55.13) уц=у„=1, Я )Рц) + Я )Рг Рго) = 3+!3 = 16 > 15 (55.14) У; Р) Рд Рз Рд Рз Ро Рд Рз Рд Рго Ргг Рис 354. Клетку Лц,о помечаем крестиком. Далее Лц д — — 78 (55.15) гг (Рц) + гг )Рд) = 3+ 8= 1! < 15.
(55.16) Классы (Рц) и )Р,) объединяем в [Ргг, Рд) (рис, 355). Берем Лз,, = 74. (55.17 ) Имеем У~=У~=1 Я)Р,) +Я(Р,) =4+5=9 < 15. (55.18) Классы )Р,) и (Р,) объединяем в )Рз, Р,). Новое решение представлено на рис. 356. Затем берем Лц 2 = 70. (55.19 ) Тогда Угг = уз= 1г гг (~ ггг Рд! + гсг )Рг, Рю) = 11 + 13 =24 > 15, (55 20) Клетку Лц,, помечаем крестиком.
Далее Лго,з=63 (55.21) Я (Ркь Р,) + Я (Рз) = 13 + 8 = 21 > 15. (55.22) Помечаем крестиком клетку 1о1о, з Аналогично поступаем дальше: )о1ь з — — 61; (55.23) ум=уз=1 Я [Рн Ро)+Я(Рз) =11+ 8=19 > 15' (5524) У; Р, Рз Рз Р4 Рз Рз Ро Р„ Ро Р|о Ри Рис. 355. Рис. 355. уо уз 1> уо уз 1 'с (~ о уз у ! Уз Р, Рз Рз Рз Рз Ро Рз Рз Ро Р~о Рп ио,з=59' (Ро Рп)+Я(Рз) =11+8=19>15' 1оо,з = 58; Рн) +Я(Рз Р~о) =11+13=24 > 15 Х, и — — 55; с7 (Рз) + с7 (Р„Р4) = 4+ 9 = 13 < 15. (55.25) (55.26) (55. 27) (55. 28) (55.29) (55.30) 329 Классы (Рд) и )Р„Р,) объединяются в (Р„Р,, Р,); таблица для у! меняется: у,=О; получаем новое решение, представленное на рис. 357, Далее Л,,=55; (55.31) тд = у! = 1, Я (ЄРд) + Я )Р ) = 13 + 8 = 21 ) 15. (55 32) Помечаем крестиком клетку Лд,!.
у! Р, 1 Р, ! Рд ! Р, ! о Рб Р, ! ! 8 Рд РО Рас. 357. Выбрав Л4 ! = 49 и пометив крестиком соответствующую клетку, переходим к Л8,4=48; (55.33) Уд=у4= !г !'! )Р!) + Я (Р4~ Рм Рд) = 2+ 13 = 15. (55 34) Классы (Рд) и (Р4, Рд, Р!) объединяем в (ЄЄР8, Р,); таблица для у; меняется: у4 — — О; получаем новое решение, представленное на рис. 358. Имеем Лд,8=48; (55.35) Уд = Уд = 1 4'! (Рд Рп) + 4 ! ) Рд) = 1 1 + 3 = 14 < 15. (55,36) Классы (Р„Р4!) и (Рд) объединяем в (Рд, Рон Рд); таблица для т! меняется: уд = О; получаем новое решение, изображенное на рис. 359. Имеем Лн, 8 — — 46; (55.37 ! Уо=У8=1, Я )Рп Рд) + 0(Р8) =11+3=14 < 15. (55.38) Приходим к уже встретившемуся классу (Рц, Рь Рд) (55.39) Имеем уо = 1, у, = О, поэтому помечаем крестиком клетку Хо,о ли 4 = 40. (55.40) 1, у, = О, поэтому помечаем крестиком клетку !22,4.
Имеем уд = Р4 Рд Рд Р4 Ро Ро Р7 Ро Рд Р4о Рис. 388. Продолжая далее, мы не получим новых классов (см. рис. 352, столбцы Я). Таким образом, приходим к решению (рис. 359), не улучшаемому с помощью такого способа: (Ро Р» Ро): 33 + 33 = 66, (Ро Р„Р48 Ро): 60+ 36+ 62 = 158, (Ро Рд Ро): 34+ 34= 68, (Ро Р,4, Рд, Рд Ро): 63+31+31+33=158, (Р84 "2 Ро Р4 г'и Ро): 33+30+28+26+24=!41. Общая стоимость 66+ 158+ 68+!58+ 141 = 591.
Пример 2. Так как Сп = 14 больше С = 10, то в 0 тре- буется специальная поездка. Результаты вычислений приведены на рис. 360 и 361, а решение — на рис. 362. (О, А, В, О): 3+3+5=11, 2 единицы в А, 3 единицы в В; (О, О, С, Е, О): 7+2+4+3=16, 4 единицы в О, 4 единицы в С, 1 единица в Е; (55.42) 5+5=10, 8 единиц в Р; 7+ 7 = 14, 10 единиц в В.
(О,Е, О) (0,0,0) Общая стоимость 11 + 16+ 10+ 14 = 51. (55.43) П р и м е р 3. Этот пример показывает, что укаэанным способом не всегда можно получить оптимальное решение. зз! Рис. 359, 2 1 4 С 140 1В С= !О Рис. 360. о А В С В Е Г о о,йА 53'В 9,5',4'С 95',4'Ю 9/Е вЕ В,А СДЕ ВСЕ Е Е,С4Р Е Рис. 361, Р! Рв Рв Р4 Рв Рв Ру Рв Рв 1!с Р!! 7! ! 1 1 о о 1 1 ! о 1 ! О А В С В В Р о Согласно изложенному методу имеем (рис.
363 — 366) (О, А, 0): 4+ 4=8, (О, В, С, 0): 6+3+6=15, (О, О, 0); 4 + 4 = 8. Общая стоимость (55.44) (55.45) 8+ 15+ 8=31. О А В С В с=ю Рис 363. Рис. 364. Решение на рис. 366 дает (О, А, В, 0): 4+3+6=!3, (О, С, О, 0): 6+ 3+ 4 =- 13 Общая стоимость (55.46) 13+ 13 = 26. (55. 47) О А В С В О зв зс ап Рис. 366 Рис. 665.
)г~ — — (хп, х„, ..., х;„), (55.48) ззз Оптимизация с помощью перечисления. Для небольших ком« бинаториых задач их оптимальное решение можно найти перечислением. Рассмотрим «задачу о музыкантах». Пусть репертуар оркестра состоит из т произведений. Каждое произведение требует различного состава исполнителей, каждый из которых известен. Этот состав можно представить в виде п-выборки где хи обозначает число инструментов класса 1, требующихся для исполнения произведения 1.
Предполагается, что оркестр должен дать концерт из й (й ( Ру) произведений. Требуется выбрать й произведений с наименьшим общим количеством исполнителей, т. е. найти )тм пц'п ~у гпаххи, удсу Г=~ уеду» (55.49) где 1=(1, 2, ..., Ру). При простом переборе нужно вычислить С' значений х) пшххи. Это, очевидно, возможно сделать при не слишком 1=1 У =Уд большом С'„. П р и м е р, Рассмотрим матрицу ~11х;1~0 с т = 5, и = 8: а Ь с Н е 1 Х Ь Сумма 29 17 (55.50) 19 Сумма манон- мумов Сумма (волн наадмд иузмнант играет толнно одно лронзведенне1 а Ь е е е 1 4 Д АВС 65 л! ВР 81 80 '140) АСР (55.51) 82 50 98 41 71 ВСЕ 70 45 ВРВ 86 СРЕ 88 49 Требуется выбрать х = 3 произведения с исполнителей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
