Cтраница 4
В настоящее время он пишет книгу о вероятностном анализе комбинаторных алгоритмов. [46]
Задачи автоматизации конструкторского проектирования делятся на задачи топологического и геометрического проектирования. Формализация задач топологического проектирования наиболее просто производится с помощью теории графов. Для автоматизации решения задач компоновки и размещения в основном используются комбинаторные алгоритмы и алгоритмы, основанные на методах математического программирования. Для решения задач трассировки применяются распределительные и геометрические алгоритмы. [47]
Какое бы удовлетворение ни доставило мне такое признание, я нахожу, что мое величайшее удовлетворение как исследователя связано с выполнением самого исследования и с дружескими связями, которые я при этом приобрел. Я хотел бы описать вам все 25 лет исследований в области комбинаторных алгоритмов и вычислительной сложности и рассказать о некоторых понятиях, которые мне кажутся важными, и о некоторых людях, которые меня вдохновляли и влияли на меня. [48]
Один из наиболее удивительных феноменов теории вероятностей - закон больших чисел, согласно которому кумулятивный эффект большого числа случайных событий в высокой степени предсказуем, даже если исходы индивидуальных событий совершенно непредсказуемы. Например, мы можем уверенно лредсказать, что в длинной серии бросаний монеты примерно половина исходов - орел. Вероятностный анализ обнаружил, что то же явление управляет поведением многих комбинаторных алгоритмов оптимизации, когда входная информация лодчинена простому распределению вероятностей: с очень высокой вероятностью выполнение алгоритма развивается хорошо предсказуемым образом и полученное решение близко к оптимальному. Например, статья 1960 г. Бердвуда, Холтона и Хам-мерсли показывает, что если п городов в задача о коммивояжере выбираются независимо с равномерным распределением на единичном квадрате, то при достаточно большом п длина оптимального маршрута будет почти наверняка очень близкой к некоторой универсальной константе, умноженной на корень квадратный из числа городов. Алгоритм стартует с разбиения области, где расположены города, на прямоугольники, каждый из которых содержит малое число городов. Затем он строит юптимальный маршрут для городов каждого прямоугольника. Объединение всех этих маленьких маршрутов сильно напоминает общий маршрут, но отличающийся от него лишними посещениями пограничных городов. Наконец, алгоритм выполняет своего рода локальную хирургию с целью исключения этих излишних посещений и образования маршрута. [49]
Логической формуле может соответствовать несколько конъюнктивных и дизъюнктивных нормальных форм. Нормальная форма называется минимальной, если она содержит минимально возможное число литер. При составлении алгоритмов логического управления целесообразно минимизировать нормальные формы логических формул, что можно выполнить либо путем полного перебора формул, эквивалентных минимизируемой, либо с помощью специальных комбинаторных алгоритмов, позволяющих сократить число анализируемых вариантов нормальных форм логической формулы. [50]
Применение в проектировании и прозводстве, в которой рассматриваются проблемы геометрического моделирования. И вот спустя 6 лет в книге по существу с таким же названием речь идет совсем о другом, а именно об оценке сложности геометрических вычислений, об анализе и построении эффективных комбинаторных алгоритмов для решения геометрических задач. Парадокс объясняется просто: как одно, так и другое научное направление родилось совсем недавно, около 15 лет назад, их становление и интенсивное развитие протекали одновременно, оба направления имеют глубокие геометрические корни и самым непосредственным образом связаны с применением ЭВМ. [51]
Я должен сказать, что это решение потребовало некоторой храбрости, так как имело своих оппонентов, которые совершенно правильно указывали, что нет никакого способа узнать, какая именно входная информация поступит на входы алгоритма, и что лучший вид гарантий, если можно получить, их, - гарантии для худшего случая. Я чувствовал, однако, что в случае NP-полных задач мы не получим желаемых гарантий для худшего случая и что вероятностный подход - лучший путь - и, возможно, единственный - к пониманию того, почему эвристические комбинаторные алгоритмы работают так хорошо на практике. [52]