CFA LogoCFA Logo Computer
Новости Статьи Магазин Драйвера Контакты
Новости
RSS канал новостей
В конце марта компания ASRock анонсировала фирменную линейку графических ускорителей Phantom Gaming. ...
Компания Huawei продолжает заниматься расширением фирменной линейки смартфонов Y Series. Очередное ...
Компания Antec в своем очередном пресс-релизе анонсировала поставки фирменной серии блоков питания ...
Компания Thermalright отчиталась о готовности нового высокопроизводительного процессорного кулера ...
Компания Biostar сообщает в официальном пресс-релизе о готовности флагманской материнской платы ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

В графском парке

Юрий ДОВГАНЬ freeyuran@ukrpost.net

Продолжение, начало см. в МК № 33-34, 38, 43 (256-257, 261, 266).
Если кто уже успел забыть, в прошлый раз мы познакомились с топологической сортировкой, подграфами, и достижимостью вершин за определенное количество шагов. Сегодня нас ждет довольно серьезное и тяжелое испытание. Главную роль в нашем шоу будут исполнять сети — или, как их еще иногда называют, взвешенные графы.

Для тех, кто пропустил по уважительной причине первое наше знакомство с графами, напоминаю: сеть — это граф, элементам которого поставлены в соответствие некоторые параметры. Мы сегодня будем рассматривать графы, ребра которых будут нести определенную функцию — длину ребра или его стоимость. Примеров взвешенных ребер можно привести немало: длины участков дорог между двумя соседними городами (представленные в виде двух смежных вершин), стоимости перевозки товара (транспортные затраты) из пункта изготовления в пункт потребления. Стоимость и длина — те самые функции ребер, которые могут служить параметрами сети.

Маршруты, как и последовательности ребер (дуг), тоже имеют свои длины. Длина маршрута — это всего-навсего сумма длин всех ребер, из которых он состоит. Не исключены такие ситуации, что между двумя вершинами может существовать несколько маршрутов. Природное свойство человека — лень, двигатель прогресса, — понуждает отыскивать его наиболее оптимальные пути решения той или иной задачи. Зачем платить больше? — мы за ценой не постоим :-), найдем самый экономный путь! За ценой интеллектуальных усилий, разумеется.

Часть 9. Задача о самых коротких маршрутах.

Проблему отыскания самых коротких путей между вершинами графа можно разрешить (легко или нелегко — это мы сейчас выясним), поставив перед собой одноименную задачу. Если же ребрам «приписаны» функции стоимостей, то задача переименовывается в «задачу о самых экономных маршрутах». Углубляясь, будем сужать условие: найти самый короткий и экономный путь из одной заданной вершины в другую.

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

Пускай задан ориентированный граф из дуг и вершин. Всем ребрам приписаны некоторые неотрицательные числа wi (i=1, 2,…, M) — длины или стоимости ребер. — номер корневой вершины, вершины, из которой мы начинаем путь. К счастью, метод Минти позволяет находить самые короткие пути из одной вершины графа во все остальные, из нее достижимые. Таким образом, задача, которую мы взялись решать раньше, является частным случаем той, которую нам поможет решить алгоритм.

В процессе алгоритма будут происходить странные вещи. Во-первых, некоторым вершинам будут приписываться «черные» :-) метки pj — неотрицательные числа. Во-вторых, избранные дуги будут «выделятся». Также нам не обойтись без одного важного определения: сечение сети — это такое множество дуг, каждая из которых имеет помеченную начальную вершину и непомеченную конечную. По каким правилам помечаются вершины и выделяются дуги? Алгоритм метода следующий.

начальное состояние. Все дуги невыделенные. Все вершины непомечены;

на 0-м шагу начальная (корневая) вершина K позначается меткой pk=0. Множество помеченных вершин на нулевом шагу I(1)={K} состоит из одной вершины K.

пускай на (r-1)-м шагу мы имеем 2 множества: помеченных и непомеченных вершин. В сечение на r-м шагу войдут все те дуги, которые имеют свойство: их начальная вершина помечена меткой p, а конечная — нет. Из всех дуг, которые входят в сечение, выбираем ту, которая имеет минимальное значение w+p, то есть сумма длины дуги и метки ее начала. Эта выбранная дуга (где достигается минимальное значение w+p) выделяется. Допустим, дуг, у которых эта сумма минимальна, в сечении имеется несколько. То есть минимум w+p достигается не на одной дуге. Рассмотрим два случая:

1). Если эти дуги заканчиваются в одной вершине, то выделяем только одну (любую) из них.

2). Если эти дуги заканчиваются в разных вершинах, то выделяем все.

После выделения дуги ее конечная вершина помечается числом w+p — самым минимальным. За счет этого множество помеченных вершин расширяется, в то время как множество непомеченных сокращается.

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

С первого раза, наверно, не все понятно. Рассмотрим пример (Рис. 1).

Рис. 1.

Рисунок изображает начальное состояние алгоритма. Представьте, что сначала у нас есть граф. Все дуги имеют значения «длины». На рисунке, например, дуга (1,2) имеет длину 5. Вершины пока не имеют меток, ни одна дуга еще не выделена. Алгоритм начинает свою работу. Вершина 1 — начальная. Помечаем ее: метка [0] вершины 1. Первый шаг опишем подробно.

1). Рассматриваем дуги, начала которых помечены, а концы нет. На первом шагу, таковыми дугами являются: дуга (1,2) длины 5 и дуга (1,3) длины 3. Рассматриваем числа 0+5=5 и 0+3=3 (метка начала дуги плюс ее длина). Для дуги (1,3) эта сумма минимальна: min=3. Ее выделяем. Конец выделенной дуги (вершину 3) помечаем меткой min. Таким образом, вершина 3 получает метку 3.

Давайте для удобства остальные шаги опишем в виде таблицы. Для каждого шага описываем входящие данные: помеченные и непомеченные вершины, выделенные дуги. В колонке действия алгоритма описываем состав сечения для текущего шага: дуга и значение (сумма метки начальной вершины и длины дуги). Затем выбираем наименьшее из этих значений, дугу, которой оно соответствует, выделяем. Ее конец помечаем меткой, равной этому минимальному значению. Вторая колонка — условие окончание алгоритма. Условие становится справедливым: 1) если все вершины помечены 2) если оставшиеся вершины не могут быть помеченными (сечение пусто) по причине их недостижимости из начальной.

После четвертого шага условие становится справедливым: есть вершина 6, которую нельзя пометить. Алгоритм заканчивает работу. (Рис. 2)

Рис. 2.

Выпишем все выделенные дуги с метками их вершин:

1) (1,3): [0]-[3],

2) (3,2): [3]-[4],

3) (2,4): [4]-[8],

4) (3,5): [3]-[5].

Как ни странно, но это решение нашей задачи :-).

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

Путь строится следующим образом. Берется вершина, в которую мы ищем самый короткий путь. Идем от нее к начальной по выделенным дугам, то есть в противоположную сторону их ориентации. Такой маршрут будет описываться однозначно, так как он единственный самый короткий.

1). Берем вершину 5. До вершины 1 добираемся, проходя следующие выделенные дуги с противоположной ориентацией: (5,3), (3,1). Длина этого пути выражается меткой у вершины 5 (то есть конечной вершины пути). Легко проверить, что сумма выделенных дуг, по которым мы продвигаемся, будет равна именно 5.

2). Аналогично с вершиной 4. Самый короткий путь к ней из вершины 1 — (4,2), (2,3), (3,1), длиной 8.

3). Вершина 3. Путь (3,1) длиной 3.

4). Вершина 2. Путь (2,3), (3,1) длиной 4.

Как уже выяснилось, длину самого короткого пути из вершины K в вершину S мы определяем значением метки вершины S. Об этом гласит соответствующая теорема. Доказательства теорем вы можете прочитать в любом пособии по «Методам оптимизации»(«Исследованию операций»/«Математическому программированию»/«Линейному программированию») в теме «Потоки на сетях». Ищите «Задачу о самых коротких путях», «Метод Минти».

Теперь перед нами стоит более сложная задача: реализовать алгоритм метода Минти с помощью языка программирования.

Удобно будет для такой задачки использовать список ребер. Кроме привычных полей начала и конца ребра, его длины, будем использовать также поля меток начала и конца вершины и логическое поле «выделена ли дуга?» Если вершина непомечена, значение ее метки будет (-1). Если значение поля для метки вершины 0, значит, вершина помечена. Будем разбирать задачу с целыми длинами ребер. Для вещественных чисел стратегия аналогична. Создадим массив записей из трех полей: начало и конец дуги, сумма длины дуги с меткой ее начала.

начальное состояние. Все метки равны (-1). Все дуги невыделенны;

на вход подается начало маршрута — вершина с номером K. Она помечается меткой со значением 0.

Если есть дуги, начало которых помечено (0), а конец нет, то выполняем:

1. Просматриваем список ребер. Все дуги с помеченным началом и непомеченным концом добавляем в список дуг, который представляет собой сечение сети. При этом в третье поле ячейки заносится сумма длины дуги и метки ее начала.

2. Просматриваем список сечения сети и находим ячейки с минимальным значением в третьем поле. При этом запоминаем номера вершин: начала и концы дуг, где достигается минимум.

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

Вот, собственно, и все! Все, к чему мы так долго стремились, наконец-то осуществилось. Осталась маленькая формальность: написать для всего этого код :-).

Примечание {*}. Например, экран содержит следующую информацию:

Длина пути — 6. Путь следующий:

3 — 2

2 — 1

Тогда наш путь записывается такой последовательностью: (1,2), (2,3). Его длина равна 6.

Таблица

Пожалуй, это все, что я хотел вам сегодня рассказать. В следующий раз нас ждут еще несколько интересных алгоритмов. Ждите продолжения!

Продолжение следует.

Рекомендуем ещё прочитать:






Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы или вычислите пример: *
captcha
Обновить





Хостинг на серверах в Украине, США и Германии. © sector.biz.ua 2006-2015 design by Vadim Popov