Структуры данных и алгоритмы (1021739), страница 3
Текст из файла (страница 3)
От задачи к программеПоловина дела сделана, если знать, что исходная задача имеет решение. Впервом приближении большинство задач, встречающихся на практике, не имеютчеткого и однозначного описания. Определенные задачи, такие как разработкарецепта вечной молодости или сохранение мира во всем мире, вообще невозможно сформулировать в терминах, допускающих компьютерное решение.
Даже еслимы предполагаем, что наша задача может быть решена на компьютере, обычнодля ее формального описания требуется огромное количество разнообразных параметров. И часто только в ходе дополнительных экспериментов можно найтиинтервалы изменения этих параметров.Если определенные аспекты решаемой задачи можно выразить в терминах какой-либо формальной модели, то это, безусловно, необходимо сделать, так как вэтом случае в рамках формальной модели мы можем узнать, существуют ли методы и алгоритмы решения нашей задачи.
Даже если такие методы и алгоритмы несуществуют на сегодняшний день, то привлечение средств и свойств формальноймодели поможет в построении "подходящего" решения исходной задачи.Практически любую область математики или других наук можно привлечь кпостроению модели определенного круга задач. Для задач, числовых по своейприроде, можно построить модели на основе общих математических конструкций, таких как системы линейных уравнений (например, для задач расчетаэлектрических цепей или напряжений в закрепленных балках), дифференциальные уравнения (задачи прогноза роста популяций или расчета скорости протекания химических реакций). Для задач с символьными или текстовыми даннымиможно применить модели символьных последовательностей или формальныхграмматик.
Решение таких задач содержит этапы компиляции (преобразованиепрограмм, написанных на языке высокого уровня, в программы на машинноориентированных языках) и информационного поиска (распознавание определенных слов в списках заголовков каких-либо библиотек и т.п.).АлгоритмыКогда построена (подобрана) подходящая модель исходной задачи, то естественно искать решение в терминах этой модели.
На этом этапе основная цель заключается в построении решения в форме алгоритма, состоящего из конечной последовательности инструкций, каждая из которых имеет четкий смысл и может бытьвыполнена с конечными вычислительными затратами за конечное время. Целочисленный оператор присваивания х := у + г — пример инструкции, которая будетвыполнена с конечными 'вычислительными затратами.
Инструкции могут выполняться в алгоритме любое число раз, при этом они сами определяют число повторений. Однако мы требуем, чтобы при любых входных данных алгоритм завершился после выполнения конечного числа инструкций. Таким образом, программа,написанная на основе разработанного алгоритма, при любых начальных данныхникогда не должна приводить к бесконечным циклическим вычислениям.Есть ещё один аспект определения алгоритмов, о котором необходимо сказать.Выше мы говорили, 'что алгоритмические инструкции должны иметь "четкийсшйсл" и выполняться с "конечными вычислительными затратами".
Естественно,то, .что понятно одному человеку и имеет'для него "четкий смысл", может совершенно иначе представляться: другому. То же самое можно сказать о понятии"конечных затрат": на практике часто трудно доказать, что при любых исходныхданных, выполнение последовательности инструкций завершится, даже если мычетко понимаем смысл каждой инструкции.
В этой ситуации, учитывая все аргументы за и против, было бы полезно попытаться достигнуть соглашения о"конечных затратах" в отношении последовательности инструкций, составляющихалгоритм. Однако кажущаяся сложность подобных доказательств может быть обманчивой. В разделе 1.5 мы оценим время выполнения основных структур языковпрограммирования, что докажет конечность времени их выполнения и соответственно конечность вычислительных затрат»Кроме программ на языке Pascal, мы часто будем представлять алгоритмы спомощью псевдоязыка программирования, который комбинирует обычные конструкции языков программирования с выражениями на "человеческом" языке. Мы используем Pascal как язык программирования, но практически любой другой языкпрограммирования может быть использован вместо него для представления алгоритмов, рассматриваемых в этой книге.Следующие примеры иллюстрируют основные этапы создания компьютернойпрограммы.Пример 1.1.
Рассмотрим математическую модель, используемую для управлениясветофорами на сложном перекрестке дорог. Мы должны создать программу, которая вкачестве входных данных использует множество всех допустимых поворотов на перекрестке (продолжение прямой дороги, проходящей через перекресток, также будемсчитать "поворотом") и разбивает это множество на несколько групп так, чтобы все повороты в группе могли выполняться одновременно, не создавая проблем друг для друга.
Затем мы сопоставим с каждой группой поворотов соответствующий режим работысветофоров на перекрестке. Желательно минимизировать число разбиений исходногомножества поворотов, поскольку при этом минимизируется количество режимов работы светофоров на перекрестке.Для примера на рис. 1.1 показан перекресток возле Принстонского университета,известный сложностью его преодоления. Обратите внимание, что дороги С и £ односторонние, остальные — двухсторонние. Всего на этом перекрестке возможно 13 поворотов. Некоторые-из этих поворотов, такие как АВ (поворот с дороги А на дорогуВ) и ЕС, могут выполняться одновременно.
Трассы других поворотов, например АО иЕВ, пересекаются, поэтому их нельзя выполнять одновременно. Режимы работы светофоров должны учитывать эти обстоятельства и не допускать одновременного выполнения таких поворотов, как AD и ЕВ, но могут разрешать совместное выполнениеповоротов, подобных АВ и ЕС.16ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВiРис.
1.1. Сложный перекрестокДля построения модели этой задачи можно применить математическую структуру,известную как граф. Граф состоит из множества точек, которые называются вершинами, и совокупности линий (ребер), соединяющих эти точки. Для решения задачиуправления движением по перекрестку можно нарисовать граф, где вершины будутпредставлять повороты, а ребра соединят ту часть вершин-поворотов, которые нельзявыполнить одновременно. Для нашего перекрестка (рис. 1.1) соответствующий графпоказан на рис. 1.2, а в табл.
1.1 дано другое представление графа — в виде таблицы,где на пересечении строки i и столбца j стоит 1 тогда и только тогда, когда существуетребро между вершинами i и j.Рис. 1.2. Граф, показывающий несовместимые поворотыМодель в виде графа поможет в решении исходной задачи управления светофорами. В рамках этой модели можно использовать решение, которое дает математическая задача раскраски графа: каждой вершине графа надо так задать цвет, чтобыникакие две соединенные ребром вершины не имели одинаковый цвет, и при этом повозможности использовать минимальное количество цветов.
Нетрудно видеть, чтопри такой раскраске графа несовместимым поворотам будут соответствовать вершины, окрашенные в разные цвета.Проблема раскраски графа изучается математиками уже несколько десятилетий, но теория алгоритмов мало что может сказать о решении этой проблемы. Ксожалению, задача раскраски произвольного графа минимальным количеством1.1. ОТ ЗАДАЧИ К ПРОГРАММЕ17цветов принадлежит классу задач, которые называются NP-полнылш задачами идля которых все известные решения относятся к типу "проверь все возможности"или "перебери все варианты".
Для раскраски графа это означает, что сначала длязакраски вершин используется один цвет, затем — два цвета, потом — три и т.д.,пока не будет получена подходящая раскраска вершин. В некоторых частных случаях можно предложить более быстрое решение, йо в общем случае не существуетболее эффективного (в значительной степени) алгоритма решения задачи раскраски, чем алгоритм полного перебора возможных вариантов.•.?:••!;;Таблица 1.1.
Таблица несовместимых поворотовАВACADАВАСADВАВСBDDADBDCЕАЕВЕСED1111ВАВСBDDA11111DB111111111111111111DCЕАЕВЕС111111111ED1111Таким образом, поиск оптимального решения задачи раскраски графа требуетбольших вычислительных затрат. В этой ситуации можно воспользоваться однимиз следующих трех подходов. Если граф небольшой, можно попытаться найтиоптимальное решение, перебрав все возможные варианты раскраски. Однако этотподход не приемлем для больших графов, так как программно трудно организовать эффективный перебор всех вариантов. Второй подход предполагает использование дополнительной информации об исходной задаче. Желательно найти какие-то особые свойства графа, которые исключали бы необходимость полного перебора всех вариантов раскраски для нахождения оптимального решения.
Втретьем подходе мы немного изменяем постановку задачи и ищем не оптимальное решение, а близкое к оптимальному. Если мы откажемся от требования минимального количества цветов раскраски графа, то можно построить алгоритмыраскраски, которые работают значительно быстрее, чем алгоритмы полного перебора. Алгоритмы, которые быстро находят "подходящее", но не оптимальное решение, называются эвристическими.Примером рационального эвристического алгоритма может служить следующий"жадный" алгоритм раскраски графа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
