Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 29
Текст из файла (страница 29)
В', ТЬе Нипйапзп Мейоа (ог йе Лгмйпгпеп( РгоЫет, ((ача! ((е. зе«гсЬ 1 ойыНсз визг(ег!у, 2, Мо. 1, 2 (1955), 83 — 97 (Имеешя перевод: Кун Г. Венгерский метод решет<я задачи о пазначениях.— В сб.. Мегоды н алгоритмы решения транспортной задачи.— М. Госстатиз. дат, 1963.! В сино ггчередь алгоритм АЛЬФЛБЕТА, как отмечена в тексте, явился пред. течей общего прямо-двойственного алгоритма для задач ЛП. Преобразование зада пг о потоке минимальной стоимости в зада«э Хичкока приписывается в книге (ГГ) Вагнеру (%з! 1(ганпег Н М Оп а С(ат о( Сарае|(а(еб Тгапзрог(аНоп ргоЫегпз, Мапайепгеп( Бе|енсе, 5 (1959) 304 -3!8 Эта рзсггпа — замечашлыгьш предвестнвк мпапт более поздних результатов (см задачу 2 и гл 15) Форд и Фалкерсон пс считают это преобразование пранти.
ческнм мегтдом решения «значи о потоке минимальной стоимости, однако такой вывод пе пгвссм гн1евги(ен Задача Гб взята из работы (То) Тотйп «Л. Мпигпипг Соз( Ми((~согпп1ой!у Ке(вагу Г(очж. О((, 14, Мо, ! (Гейгиагу !966), 45 — 51 Частный случай задачи об погонном дереве с пропуснными способностями, при. веденный в задаче 11, упоминается в книге (Оу) Оагеу М К, 3о!шзоп О. 5 Согпри(егз апа (п(гас1аЫ(1(у А Оийе 1о йе ТЬе. огу о! (уР-сотр(с(епезз Бап Ггапсцсо, Сайогта: Ъ'.
Н. Ггеетап й Согпрапу, РиЫВЬегч, 1979. (Имеетси перевод Гэри М., Лжонсон Л. Вычислительные машины н труднирешаемые задачи.— М.. Мир, 1982.) Более подробно об этой задаче, которая в общем виде очень трудна, можно узнать из раба~ (ЪБС) )гап сйс1г1е 1, С!гаггау К. М Согпри(а1юпа( Сотр(ехйу о1 Ме1чоги Оемйп Л(йог(!Ьгпз, )п(оппаНоп Ргоссет(пй 77, еб В ОВсЬгм( Могй Но(!апй РиЬ- !ийппй Со., 1977. (Ра) Рарай(пи(пои С. Н ТЬе Сагир(ехг1у о( йе Сарае((а(ед Тгее РгоЫегп, Ые(- лчогйз, 8 (1978), 217 — 230.
Алгоритмы и сложность Вычиспммость Широкое применение симплекс-алгоритма и его разновидностей к задачам с сотнями и тысячами переменных и ограничений стало возможным лишь благодаря современным быстродействующим цифровым вычислительным машинам. То же самое справедливо для многих широко используемых методов решения численных задач, моделирования физических или социальных процессов и обработки информации„ибо применение этих методов вручную фактически невозможно: исключение составляют только задачи малого размера, не имеющие практической ценности.
Теперь уже общепризнано, что вычислительные возможности человеческого разума не могут удовлетворить потребностям современной науки и технологии Существует ли предел вычислительных возможностей ЭВА)й Очевидно, что вычислительные машины не могут выполнять некорректно поставленные, нематематические задачи, такие, как «решить энергетическую проблему» или «превзойти людей в остроумии».
ЭВМ могут выполнять толькоалгоритмы, т. е, точные и однозначно понимаемые последовательности команд, при помощи которых решаются произвольные строго определенные вычислительные задачи. Типичные алгоритмы — например, методы выполнения арифметических операций над десятичными целыми числами, изучаемые в начальной школе.
Это точные методы, которые можно применять к любым целым числам как угодно большим, и они корректны в том смысле, что гарантируют получение правильного ответа за конечное число шагов. Они настолько сухо и буквально описаны, что их выполнение можно доверить машинам. Не следуе1 удивляться тому, что интуитивное понятие алгоритма можно определить вполне строго. Соответствующий математический объект называется машиной Тьюринга в честь английского математика Алана М. Тьюринга, придумавшего ее в !935 г.
(см. й !5,5) А есть ли корректно определенные математические задачи, для которых нет алгоритма решения? Тьюринг показал, блестяще это аргументируя, что такие неразрешимые задачи действительно существуют. Типичным примером тому служит так называемая проблема оепановки: выяснить для конкретной программы и входных данных, остановится ли она когда-нибудь. Тьюринг доказал, что не существует алгоритма, который бы корректно решал все частные случаи 8.2. Времеиие1е оценки 161 этой задачи. Можно найти некоторые эвристические способы обнаружения отдельных бесконечных циклов по программе и входным данным, однако всегда останутся тонкости, ускользнувшие от нашего анализа.
Кояечно, можно просто запустить программу и выдать положительный ответ на поставленный выше вопрос, если программа достигнет оператора епе!. К сожалению, такая схема не будет алгоритмом, поскольку нет гарантии, что сима она остановится1 Временнйе оценки Если математические формализации, подобные машинам Тьюринга, привели математиков 30-х годов к изучению неразрешимых проблем, то современные ЭВМ поставили перед математиками вопросы иного рода. Все вычислительные задачи, рассмотренные в этой книге, разрешимы.
Иными словами, в принципе существует алгоритм, корректно решающий любой частный случай этой задачи. Однако этого не всегда достаточно, поскольку алгоритму может потребоваться так много времени, что он становится абсолютно бесполезным. Пример 8.1. Задача коммивояжера (ЗК, см. пример 1.1), очевидно, разрешима, поскольку любую индивидуальную ЗК можно решить, найдя наилучший обход среди конечного множества обходов. Таким образом, вычислительная машина может решить любую индивидуальную ЗК, систематически перебирая все обходы, вычисляя их длины и выбирая затем крагчайший обход. Число обходов и городов равно (и — 1)!!2. Поэтому реализация описанного алгоритма в вычислительной машине потребует около и! шагов (элементарных команд).
Решение с помощью этого алгоритма индивидуальной ЗК среднего размера (например, нахождение кратчайшего обхода столиц штатов США) потребовало бы многих миллиардов лет, даже при наиболее оптимистических прогнозах относительно скорости вычислительных машин в будущем (50! имеет около 65 десятичных знаков). П Пример 8.2. Задачу о минимальном остовном дереве (МОД, см, пример !.2) также можно решить методом полного перебора всех остовных деревьев и выбора наилучшего из них. Поскольку имеется п" * остовиых деревьев с п вершинами (доказательство см.
в [Еч)), то время, необходимое для работы такого алгоритма перебора, снова неприемлемо. Однако для этой задачи имеется намного лучший алгоритм. В гл. 12 будет построен алгоритм для МОД, число элементарных щагов которого при решении задачи с и точками пропорционально и'. Этот алгоритм очень хорошо работает на практике. Используя его, задачу МОД для столиц штатов США можно решить на большинстве вычислительных машин за несколько секунд.
[ ! м 3032 162 Гл. В. Алгоритмы и сложность Наиболее популярной мерой качества работы алгоритма является отрезок времени, затрачиваемый алгоритмом до получения окончательного ответа, Этот показатель зависит от типа ЭВЫ, на которой выполняется алгоритм; большую роль играет скорость и набор команд. При анализе алгоритмов в этой книге время работы алгоритмов будет выражаться в терминах числа элементарных шагов (арифметических операций, сравнений, команд ветвления и т. д.), необходимых для выполнения этого алгоритма на гипотетической вычислительной машине.
Иначе говоря, будем предполагать, что все эти операции требуют одну единицу времени. Число шагов, выполняемых алгоритмом, не одинаково для различных входов. Например, в симплекс-алгоритме число элементарных шагов, необходимых для решения задачи ЛП размера туси, гпах с'х при условиях Ах(Ь, х)0, может существенно меняться в зависимости от параметров А, Ь и с, даже если их размерности остаются постоянными.
В экстремальном случае, когда с(0, исходное допустимое решение оптимально, и не требуется производить операций замещения, тогда как при других значениях параметров для достижения оптимума может потребоваться значительное число итераций. Чтобы сгладить такие резкие контрасты в поведении алгоритма при переходе от одного входа к другому, будем рассматривать все входы данного размера и вместе и определим сложность алгоритма для этого размера входа как число шагов алгоритма в худшем случае по всем этим входам.
Тогда сложность алгоритма будет представляться в виде функции размера входа, такой, как 1Оп', 2" или и 1оа п '). При изучении сложности алгоритма часто интересуются только его поведением при применении к очень большим входам, поскольку именно эти входы определяют границы применимости алгоритма. Различия между алгоритмами сложности 1Ои* и 9п' можно сделать несущественными при помощи технологических достижений, дающих десятикратное увеличение скорости вычислительных машин. С другой стороны, медленно растущие слагаемые (такие, как 5п в оценке п 1оа и+5п) будут полностью поглощаться более быстро растущими слагаемыми при достаточно больших и (в нашем примере при п))1000).
Таким образом, нас интересует скорость роста сложности алгоритма При изучении скорости роста функций полезен следующий формализм. Определение 8.1, Пусть 1(п) и у(и) — функции, определенные на множестве целых положительных чисел и принимающие положительные действительные значения. а) Будем писать |(и) =0(д(п)), если существует такая константа с)0, что г" (п)(сд(п) для достаточно больших и. т) В тех случаях, когда основание логарифма явно не указано, подразумевается основание 2. д.д.
Рознер индивидуальной задачи б) Будем писать )'(п) =Я (у(п)), если существует такая константа с ~0, что ((и) ~с(д(п)) для достаточно больших и. в) Будем писать 1(п)=6(д(п)), если существуют такие константы с, с'- О, что сд(п)(1'(п)(сд'(и) для достаточно больших и. Вместо ~(п)=9(д(п)) можно писать ((п) мд(п). Легко видеть, что отношение ' является отношением эквивалентности. Класс эквивалентности относительно этого отношения, содержащий 1(п) (т. е. множество всех функций й(п), таких, что ~(п)=9(д(п))), называется скоростью роста 1'(п). Д Благодаря введенному понятию скорость роста сложности алгоритма можно оценить сверху, используя выражения типа етребует времени 0 (и')», в.з размер индивидуальной задачи Мы измеряем сложность алгоритма функцией размера входа алгоритма.
Но что такое размер входа? В комбинаторных задачах оптимизации входом является комбинаторный объект: граф, множество целых чисел (возможно, упорядоченных в виде векторов или матриц), семейство конечных множеств и т. д. Чтобы ввести этот вход в вычислительную машину для решения, необходимо каким- либо образом закодировать, или представить, его в виде последовательности символов над некоторым фиксированным алфавитом, таким, как двоичный алфавит, алфавит символов печатной машинки или буквы АБСП. Мы ие будем точно определять, как кодируются комбинаторные объекты последовательностями символов. Эти кодирования можно производить любым из многих очевидных и простых способов; некоторые из них будут проиллюстрированы ниже в примерах. Более того, почти всегда оказывается, что все эти кодирования, по существу, эквивалентны для наших целей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
