КаталогИндекс раздела
НазадОглавлениеВперед

Нахождение кратчайшего остовного поддерева графа

Я выбрал следующий пример по ряду причин. Во-первых, хотя его конечная программа относительно короткая, решение далеко не тривиально. Во-вторых, объект, с которым мы имеем дело - "структура", а не простой числовой материал, как результат, решения, принимаемые для представления информации (с использованием числовых значений), являются более декларативными. Наконец, он знакомит нас с некоторыми типовыми стратегическими решениями.

Две точки могут быть соединены одним прямым соединением; три точки могут быть соединены между собой двумя прямыми соединениями; в общем случае N могут быть соединены при помощи N-1 прямых соединений. Такой набор взаимных соединений называется "деревом"; прямые соединения, которые составляют дерево, называются "его ветвями". Кейли первым доказал, что количество возможных деревьев между N точками равно NN-2.

Теперь предположим, что задана длина для каждой возможной ветви. Определяя длину ветви как сумму длин ее ветвей, мы можем потребовать кратчайшего дерева между этими точками. (На данный момент мы предполагаем, что заданные длины таковы, что кратчайшее дерево является уникальным. Из нашего анализа будет следовать, что две ветви одинаковой длины не являются достаточным условием для этого предположения.)

Примечание. Точки не обязаны лежать в евклидовой плоскости и заданные расстояния не обязаны удовлетворять неравенство треугольника.

Очевидным решением является генерация всех деревьев между N точками, вычисление их длин и выбор кратчайшего, но теорема Кейли показывает, что при возрастании N это будет слишком дорого. Следующая теорема позволяет нам найти кратчайшее дерево со значительно меньшим трудом. Если мы имеем поддерево кратчайшего дерева, то может быть найдена кратчайшая ветвь между одной из точек, входящих в это поддерево, и одной из точек, не входящих в это поддерево, что и будет частью кратчайшего дерева между всеми N точками.

Эта теорема легко доказывается. Выкрасим ветви поддерева и все соединенные им точки в красный цвет; выкрасим все остальные точки в синий цвет и выкрасим все ветви, ведущие от красных точек к синим, в фиолетовый цвет. Теорема утверждает, что кратчайшая фиолетовая ветвь является также частью кратчайшего дерева. Назовем эту кратчайшую фиолетовую ветвь V' и предположим, что она не является частью кратчайшего дерева T; тогда мы можем сконструировать дерево T', которое будет короче, чем T, что противоречит условию. Добавим в дерево T фиолетовую ветвь V; в результирующем графе фиолетовая ветвь должна содержаться в замкнутой петле. Поскольку фиолетовая ветвь соединяет красную точку с синей, ясно, что, идя по петле, мы должны найти в этой петле, по крайней мере, еще одну фиолетовую ветвь в петле. Назовем эту ветвь V' и удалим V'. Результирующий граф опять имеет N-1 ветвей; он соединяет все N точек (мы удалили ветвь из петли) и, следовательно, он является деревом, соединяющим все N точек. Назовем его T'. Из T' = T + V - V' следует: 

      length(T') = length(T) + length(V) - length(V')

Поскольку V была кратчайшей ветвью, мы имеем: 

      length(V) < length(V')

так что 

      length(T) < length(T')

Вышеприведенная теорема говорит нам, что красное поддерево кратчайшего дерева может быть расширено точкой и ветвью ведущей к ней: кратчайшая фиолетовая ветвь и синяя точка, к которой она ведет, могут быть перекрашены в красный цвет. Как результат, если мы можем найти красное поддерево, чтобы начать с него, то мы можем дать ему возможность расти по одной ветви за раз. Но очень легко начать с красного поддерева, а именно, с красного поддерева, содержащего единственную точку (любую) и без ветвей. Начиная с такого поддерева, мы можем заставить его вырасти в кратчайшее дерево за шагов, в каждом шаге добавляя к нему новую красную ветвь и новую красную точку. Мы можем представить каркас этого алгоритма следующим образом: 

    ОКРАСИТЬ ОДНУ ТОЧКУ КРАСНЫМ, А ОСТАЛЬНЫЕ СИНИМ
    while ЧИСЛО КРАСНЫХ ТОЧЕК < N do
    begin ВЫБРАТЬ КРАТЧАЙШУЮ ФИОЛЕТОВУЮ ВЕТВЬ;
          ОКРАСИТЬ ЕЕ И ЕЕ СИНЮЮ КОНЕЧНУЮ ТОЧКУ КРАСНЫМ
    end

Понятно, что главной задачей будет "ВЫБРАТЬ КРАТЧАЙШУЮ ФИОЛЕТОВУЮ ВЕТВЬ", потому что число фиолетовых ветвей может быть очень большим, а именно, k * (N - k), где k = ЧИСЛО КРАСНЫХ ТОЧЕК. Если бы "ВЫБРАТЬ КРАТЧАЙШУЮ ФИОЛЕТОВУЮ ВЕТВЬ" была изолированной операцией, с ней было бы не очень много работы; в вышеприведенной программе, однако, операция должна последовательно выполняться N - 1 раз, и последовательные ряды фиолетовых ветвей сильно связаны: это ветви между красной и синей точками, и каждый раз только одна точка меняет свой цвет. Мы захотим это использовать, чтобы уменьшить набор ветвей, из которого каждый раз должна быть выбрана кратчайшая ветвь: мы будем искать удобное подмножество набора фиолетовых ветвей. Мы все еще не знаем, существует ли такой действительно удобный поднабор, но давайте на секунду предположим, что он может быть найден и назовем его "ультрафиолетовым". Если такой набор существует (всякий раз) будет очень полезным иметь дешевый способ для конструирования поднабора, и мы надеемся, что он может быть найден в предшествующей истории вычислений, например, в наборе ультрафиолетовых ветвей, использовавшихся в предыдущий раз. Это приводит к программе следующей структуры. 

    ОКРАСИТЬ ОДНУ ТОЧКУ КРАСНЫМ, А ОСТАЛЬНЫЕ СИНИМ;
    СКОНСТРУИРОВАТЬ НАБОР УЛЬТРАФИОЛЕТОВЫХ ВЕТВЕЙ;
    while ЧИСЛО КРАСНЫХ ТОЧЕК < N do
    begin ВЫБРАТЬ КРАТЧАЙШУЮ ФИОЛЕТОВУЮ ВЕТВЬ;
          ОКРАСИТЬ ЕЕ И ЕЕ СИНЮЮ КОНЕЧНУЮ ТОЧКУ КРАСНЫМ;
          МОДИФИЦИРОВАТЬ НАБОР УЛЬТРАФИОЛЕТОВЫХ ВЕТВЕЙ
    end

Где набор ультрафиолетовых ветвей должен быть определен таким образом, что

  1. он гарантированно содержит кратчайшую фиолетовую ветвь
  2. набор ультрафиолетовых ветвей в общем случае много меньший, чем набор просто фиолетовых
  3. операция "МОДИФИЦИРОВАТЬ НАБОР УЛЬТРАФИОЛЕТОВЫХ ВЕТВЕЙ" является дешевой, иначе выгода, которой мы пытаемся достичь, будет упущена

Можем ли мы найти такое определение "ультрафиолетового"? Ну, не зная большего, я могу только сказать, что мы попытаемся.

Рассмотрим набор фиолетовых ветвей, ведущих от красных точек к синих, который имеет элементов и, учитывая критерий 1, немедленно представляются два очевидных возможных поднабора:

  1. Сделать для каждой красной точки кратчайшую фиолетовую ветвь, заканчивающуюся в ней, ультрафиолетовой. В этом случае набор ультрафиолетовых точек имеет k элементов
  2. Сделать для каждой синей точки кратчайшую фиолетовую ветвь, начинающуюся в ней, ультрафиолетовой. В этом случае набор ультрафиолетовых точек имеет N - k элементов

Нашей целью является иметь ультрафиолетовый поднабор небольшим, но мы не получили ключа к его размеру: в первом варианте размер будет изменяться от 1 до N - 1, во втором варианте - наоборот. Так что, если есть какой-то вариант решения, мы должны искать его в операторе "МОДИФИЦИРОВАТЬ НАБОР УЛЬТРАФИОЛЕТОВЫХ ВЕТВЕЙ"

Даже не пробуя различные модификации ультрафиолетового набора, мы можем сделать одно наблюдение, которое предполагает предпочтение для первого варианта. В первом варианте ультрафиолетовых ветвей могут вести от красного дерева к одной и той же синей точке; мы знаем априори, что не более, чем одна из них будет окрашена в красный, тогда как во втором варианте каждая синяя точка соединена только одним путем с красным деревом (сумма чисел красных и ультрафиолетовых ветвей постоянно равна N - 1 и возможно, что все ультрафиолетовые в данный момент точки будут в конце концов окрашены красным - в таком случае оператор модификации будет пустым, с удалением ветвей, ставших красными. Следовательно, давайте попробуем второй вариант критерия ультрафиолетового. (В начальном состоянии этот набор содержит N - 1 ветвей, ведущих от одной красной точки к остальным N - 1 синим, так что он не представляет проблемы.)

Предположим теперь, что мы имеем красное поддерево R и что из соответствующего набора ультрафиолетовых ветвей (в соответствии со вторым вариантом - я больше не буду повторять это уточнение) кратчайшая ветвь ведет к синей точке P, и синяя точка P должна быть окрашена в красный. Число ультрафиолетовых ветвей должно уменьшиться на 1. Хороши ли оставшиеся ветви? Для каждой синей точки они представляют кратчайшее соединение с красным деревом R и они должны представлять кратчайшее возможное соединение с новым красным деревом R + P. Но это устанавливается посредством простого сравнения для каждой синей точки B: если ветвь BP короче, чем ультрафиолетовая ветвь, соединяющая B с R, последняя должна быть заменена ветвью BP - ее ультрафиолетовый цвет смывается, а вместо нее ультрафиолетовой становится ветвь BP; иначе считается, что расширение красного дерева точкой P не обеспечивает кратчайшего пути соединения B с красным деревом. В результате стоимость оператора модификации - который должен иметь дело с N- k синими точками - является линейной функцией N и k (а не квадратичной, как k * (N - k))), и введение концепции ультрафиолета действительно обеспечивает экономию, как мы и надеялись.

Упражнение. Убедитесь, что забракованная альтернатива концепции ультрафиолета не так полезна.

Давайте попробуем представить наш алгоритм в его текущей стадии совершенствования: 

    ОКРАСИТЬ ОДНУ ТОЧКУ КРАСНЫМ, А ОСТАЛЬНЫЕ СИНИМ;
    СКОНСТРУИРОВАТЬ НАБОР УЛЬТРАФИОЛЕТОВЫХ ВЕТВЕЙ;
    while ЧИСЛО КРАСНЫХ ТОЧЕК < N do
    begin ВЫБРАТЬ КРАТЧАЙШУЮ УЛЬТРАФИОЛЕТОВУЮ ВЕТВЬ И НАЗВАТЬ ЕЕ СИНЮЮ КОНЕЧНУЮ ТОЧКУ P;
          ОКРАСИТЬ ЕЕ И ТОЧКУ P КРАСНЫМ;
          МОДИФИЦИРОВАТЬ ДЛЯ КАЖДОЙ СИНЕЙ ТОЧКИ B СРАВНЕНИЕМ С ВЕТВЬЮ BP
    end

Теперь пришло время рассмотреть представление нашей информации. Мы предполагаем N точек, нумерованных от 1 до N, мы предполагаем, что длины ветвей задаются двумерным массивом 

    real array distance[1:N, 1:N],
так, что для 1 i, j N, 
    distance[i,j] = distance[j,i] = длина ветви, соединяющей точки i и j.

Результат требует дерева из ветвей, каждая ветвь будет идентифицироваться номером ее конечной точки, результат будет (неупорядоченным) набором (неупорядоченных) пар номеров. Мы можем представит его двумя массивами 

    integer array from, to [1:N-1]

где для каждого , удовлетворяющего пара "" задает конечные точки (их номера) для -ой ветви. В нашем конечном решении ветви будут нумерованы (при помощи ); единственным имеющим смысл порядком является порядок, в котором они будут окрашиваться красным. Сделанное выше наблюдение о том, что общее число ветвей, которым мы манипулируем, остается постоянным (красные и ультрафиолетовые вместе), предполагает, что мы храним из в том же массиве:

если k = ЧИСЛО КРАСНЫХ ТОЧЕК
     from[h], to[h] будут красными для 1 h &l; k
     from[h], to[h] будут ультрафиолетовыми для k h &l; N

Ультрафиолетовые ветви будут представлены ведущими от красных точек к синим. Массив "length" должен быть введен для уменьшение числа индексов: 

    length[h] = расстояние[from[h], to[h]]

будет сохраняться и будет немедленно восстанавливаться, если временно сделается неправильной.

Точка выбирается как начальная точка для окраски в красный цвет. "ВЫБРАТЬ КРАТЧАЙШУЮ УЛЬТРАФИОЛЕТОВУЮ ВЕТВЬ" - простой поиск минимального значения. "ОКРАСИТЬ ЕЕ И ТОЧКУ P КРАСНЫМ" выполняется перестановкой в массивах дерева (если необходимо), за которой следует увеличение . В операции "МОДИФИЦИРОВАТЬ ДЛЯ КАЖДОЙ СИНЕЙ ТОЧКИ B СРАВНЕНИЕМ С ВЕТВЬЮ BP" проходит по фиолетовым ветвям, будут синей точкой, а используется для сохранения длины ветви . Итоговая программа приведена ниже. 

begin integer array from, to[1:N-1]; real array length[1:n-1]; real len, minlen; integer k, h, minh, p;
      ОКРАСИТЬ ОДНУ ТОЧКУ КРАСНЫМ, А ОСТАЛЬНЫЕ СИНИМ:
              k:= 1;
      СКОНСТРУИРОВАТЬ НАБОР УЛЬТРАФИОЛЕТОВЫХ ВЕТВЕЙ:
              h:= 1; while h < N do begin from[h]:= N; to[h]:= h; length[h]:= distance[N,h]; h:= h + 1; end;
      while k < N do
      begin ВЫБРАТЬ КРАТЧАЙШУЮ УЛЬТРАФИОЛЕТОВУЮ ВЕТВЬ И НАЗВАТЬ ЕЕ СИНЮЮ КОНЕЧНУЮ ТОЧКУ P:
                    minh:= k; minlen:= length[k]; h:= k + 1;
                    while h < N do begin len:= length[h]; if len < minlen do begin minlen:= len; minh:= h end; h:= h + 1 end;
                    p:= to[minh];
            ОКРАСИТЬ ЕЕ И ТОЧКУ P КРАСНЫМ:
                    if k  minh do begin h:= from[k]; from[k]:= from[minh]; from[minh]:= h;
                                         h:= to[k]; to[k]:= to[minh]; to[minh]:= h;
                                         len:= length[k]; length[k]:= length[minh]; length[minh]:= len
                                   end;
                    k:= k + 1;
            МОДИФИЦИРОВАТЬ ДЛЯ КАЖДОЙ СИНЕЙ ТОЧКИ B СРАВНЕНИЕМ С ВЕТВЬЮ BP:
                    h:= k;
                    while h < N do
                    begin len:= distance[p, to[h]]; if len < length[h] do begin length:= len; from[h]:= p end; h:= h + 1 end
      end;
      h:= 1; while h < N do begin print(from[h])); print(t[h])); newline; h:= h + 1 end
end

Упражнение. Пусть distance[i,j] является расстоянием от точки i до точки j именно в таком направлении. Поскольку мы имеем однонаправленный путь, отношение 

      distance[i,j]  distance[j,i]

является допустимым. Сделайте программу, находящую в графе кратчайший путь, ведущий из точки I в точку J. Это трудное упражнение, поэтому стоит попытаться его выполнить!





НазадОглавлениеВперед






КаталогИндекс раздела