В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 58
Текст из файла (страница 58)
реализующий перебор всех возможных вариантов. Такой подход, однако, как правило, неприемлем из-за чрезвычайно большого числа этих вариантов. Поэтому нужен не просто алгоритм, а алгоритм, в некотором смысле эффективный, причем эффективность алгоритма важно уметь оценивать а рНоп'. Этой цели служит анализ алгоритма. Итак, под решением задачи «в алгоритмической постановке» мы будем понимать разработку и анализ соответствующего алгоритма. 5 72. Предварительные сведения При анализе алгоритма решения какой-либо задачи нас в первую очередь будет интересовать его трудоемкость, под которой мы понимаем время выполнения соответствующей программы на ЭВМ. Ясно, что этот показатель существенно зависит от типа используемой ЭВМ.
Чтобы сделать наши выводы о трудоемкости алгоритмов в достаточной мере универсальными, будем счктать, что все вычисления производятся на некой абстрактной вычислительной машине. Такая машина в состоянии выполнять арифметические операции, сравнения, пересылки и операции условной и безусловной передачи управ- зг7 ления. Эти операции считаются элементарными, Каждая из элементарных операций выполняется за единицу времени и, следовательно, время работы алгоритма равно числу выполненных им элементарных операций. Память абстрактной вычислительной машины состоит из неограниченного числа ячеек, имеющих адреса 1, 2, 3, ..., и, ...
Ко всем ячейкам есть прямой доступ. Остановимся особо на представлении чисел в памяти машины. При анализе алгоритмов наибольший интерес представляет зависимость времени работы алгоритма от числа вершин и (или) ребер графа. Выяснение этой зависимости удобнее проводить, если отвлечься от величины таких числовых параметров, как веса ребер взвешенного графа. Поэтому будем считать, что любое число, независимо от его величины, можно разместить в одной ячейке и каждая ячейка может содержать только одно число.
Сделанное допущение будет оставаться в силе на протяжении этого и следующих пяти параграфов, в которых анализируется трудоемкость конкретных алгоритмов. В последнем параграфе этой главы мы несколько изменим модель вычислительной машины, приняв, в частности, иной способ представления чисел. Алгоритмы можно описывать в терминах элементарных операций. Однако такая запись была бы перегружена непринципиальными деталями, заслоняющими основные идеи алгоритма. Поэтому ааписывать алгоритмы будем в виде последовательности пунктов. Каждый пункт содержит один или несколько операторов (инструкций, правил), которые следует выполнить. Внутри пункта эти инструкции выполняются последовательно в том порядке, как они записаны, Если некоторый пункт не содержит указаний па переход к другому пункту, то после выполнения всех его инструкций следует перейти к следующему по порядку пункту. Единственное требование, предъявляемое к инструкциям, состоит в том, чтобы каждая из них легко выражалась через элементарные операции.
В записи алгоритма некоторые его фрагменты будут сопровождаться комментариями. Комментируемый фрагмент может быть отдельным оператором или пунктом, а также группой последовательно расположенных операторов либо пунктов. Комментарии будем писать в квадратных скобках и помещать в начале или в конце комментируемого фрагмента. Хотя мы и условились при описании алгоритмов не ограничивать себя каким-либо набором стандартных операторов, всо же два таких оператора будут использоваться постоянно. Во-первых — это оператор присваивания а: =В.
В результате его выполнения переменная а получает новое значение, равное В. Во-вторых — оператор «копеи», выполнение которого означает прекращение вычислений. Рассмотрим теперь представление информации в памяти машины. Всякую конечную последовательность элементов произвольной природы будем называть списком, а число элементов списка — его длиной. Элементами могут быть числа, буквы алфавита, векторы, матрицы и т. п. В той ситуации, когда каждый элемент списка Я помещается в одной ячейке (например, является числом), этот список будем размещать в и последовательных ячейках памяти, где и — длина списка.
Через Я(к) будем обозначать й-й элемент списка Я. Аналогично список Я длины и будем размещать в па последовательных ячейках, если для размещения каждого его элемента достаточно Ы ячеек. Такое представление списка обычно называется последовательным, и ниже используется только это представление. Пусть А = ~~А;,'!! — матрица порядка и и Х = =(Ать Ам,, А1, Аю, А»п, А« щ ..., Л«ь А», ..., Л„„) — список ее элементов «по строкам».
Принятый нами принцип «одно число — одна ячейка» означает, что матрица порядка и занимает и» ячеек памяти. Рассмотрим теперь представление графа С в памяти машины. Пусть ИС = (оь оп ..., о„). Будем пользоваться тремя способами представления. Первый — задание графа матрицей смежности. Если граф С взвешенный и»а(л, у) обозначает вес ребра ху, то вместо матрицы смежности используется матрица весов И'(С) = И'. У этой матрицы И'е = и~(оо о»), если о»о; ~ь »и ЕС, Если же иги» Ф ЕС, то полагаем И'в = О или И'е = в зависимости от задачи, которую предстоит решить. Из сказанного выше о представлении матрицы в мапшне следует, что такой способ задания графа требует ~С~» ячеек памяти. В предыдущих главах веса предполагались неотрицательными.
Теперь снимем это ограничение и будем считать, что весами ребер могут быть любые вещественные числа. Второй способ — задание графа списком ребер Е =(еь еп ..., е ), где т = ~ЕС~, е; ~н ЕС, Поскольку ребро графа можно хранить, используя две ячейки (по од- 3»9 ной на каждую концевую вершину), то для хранения всего списка Р достаточно 2т ячеек. Если граф взвешенный, то под каждый элемент списка й можно отвести три ячейки — две для ребра и одну для его веса, т.
е. всего потребуется Зт ячеек. И, наконец, последний способ, который будет использоваться,— представление графа списками смежности. При таком способе каждой вершине о, ставится в соответствие список Л',«вершин, смежных с гь Под этот список достаточно отвести бея о, + 1 ячеек — по одной па каждый элемент и одну ячейку для обозначения конца списка. Кроме того, формируется список Л'=(Л'ь Хь ... ..., Л'„), где Л', — номер ячейки, в которой хранится первый элемент списка Лг»« Следовательно, такой способ представления графа требует ~', (бед и + 1) + и = ъыко = 2т + 2п ячеек памяти. Если граф С взвешенный, то для кая«дой вершины о; списка Л'„, отводится дополнительно одна ячейка, содержащая число ш(г„г,).
Хотя представление графа списком ребер является наиболее экономным «по памяти», оно имеет существенный недостаток. Чтобы определить, содержит ли граф данное ребро, надо просматривать поочередно элементы этого списка, а это может потребовать около 2т элементарных операций. Если же граф задан списками смежности, вычислительные затраты составят не более и + 1 таких операций. Представление графа матрицей смежности, требующее наибольших затрат памяти, обеспечивает, как принято говорить, «прямой доступ» к ребрам графа. Узнатть содержит ли граф ребро г;г„моя«по, вычислив адрес Й = 1п+1 и сравнив М(й) с нулем, где М вЂ” массив, в котором построчно размещена матрица смежности графа.
Сказанное с очевидными изменениями переносится на случай взвешенных и ориентированных графов. Выбор того или иного задания графа зависит от конкретной задачи, которую предстоит решать. Во всех рассматриваемых в этой главе задачах главной частью исходной информации служит граф. Кроме этого, исходные данные могут включить номера одной или нескольких выделенных вершин. Если, например, за,дача состоит в отыскании цепи, соединяющей две заданные вершины графа, то помимо графа необходимо задать номера этих двух вершин.
После того как всем исходным данным задачи при- 320 своены конкретные аначения и они размещены в памяти ЭВМ, будем называть их входом задачи, Размером (или длиною) входа считается число ячеек, запятых входом. При анализе алгоритма решения любой задачи пас в первую очередь будет интересовать зависимость времени его работы от размера задачи, т. е. от размера входа.
Однако, как правило, это время зависит не только от размера входа, но и от других параметров задачи, т. е. время работы алгоритма на входах одинаковой длины может быть не одинаковым. Поясним сказанное па простейшем примере. Пусть элементами списка Я =(ги ги ..., з ) являются натуральные числа и требуется определить, содержит ли Я число, кратное трем. Очевидный алгоритм решения атой простой задачи состоит в следующем; проверяем поочередно делимость элементов списка Я на 3 до тех пор, пока не встретится число г„, кратное трем, пли же не будут проверенывсе элементы Я. Время выполнения р таких проверок равно г = 2р (р делений и р изменений адреса). Следовательно, прн неизменной длине входа и время работы алгоритма будет изменяться в пределах 2 < 1 < 2п» в зависимости от расположения подходящего элемента г» в списке К Наихудшим, очевидно, будет случай, когда Я не содержит чисел, кратных трем, либо когда г — единственное такое число.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
