Научная литература
booksshare.net -> Добавить материал -> Физика -> Гоппа В.Д. -> "Введение в Алгебраическую теорию информации" -> 19

Введение в Алгебраическую теорию информации - Гоппа В.Д.

Гоппа В.Д. Введение в Алгебраическую теорию информации — М.: Наука, 1995. — 112 c.
Скачать (прямая ссылка): vvedenievalgebraicheskuu1995.pdf
Предыдущая << 1 .. 13 14 15 16 17 18 < 19 > 20 21 22 23 24 25 .. 31 >> Следующая

обозначается Root, а пустой узел-символом
68
Например, возможна следующая таблица записей, образующих бинарное дерево:
Address Key ЦР) R(P) Inform
0001 />43 0010 0011
0010 123 0101 0111
0011 850 0110
0101 087 1000
1000 061
0111 276 1001
1001 321 Л
0110 720
Поиск со вставкой по дереву осуществляется следующим способом. Допустим,
что требуется найти запись с ключом К = 276. Сравниваем этот ключ с
ключом, содержащимся в корне дерева: К < Key (Root)! В данном случае 276
< 643, поэтому обращаемся к левому указателю L(Root) = 0010. Теперь
сравниваем ключ с величиной Хеу(0010): 276 < 123? Неравенство не
выполняется. Убедившись, что 276 * 123, обращаемся к правому указателю
/2(0010) = 0111. Сравнение К < Кеу{0\\\) = 216 позволяет обнаружить
нужный ключ. Если бы оказалось i?(0010) = это свидетельствовало бы о том,
что записи с ключом К не существует, и можно было бы "подвесить" эту
запись к нашему дереву (вставка записи на свободное место в памяти).
4.8. Кратчайший маршрут (алгоритм Дикстры)
Допустим, что в орграфе заданы расстояния р(х, у) для каждого ребра
(неотрицательные вещественные числа):
X 0 0 1 1 2 2 3 3 4 5 5 6
7
У 1 3 3 6 1 6 4 5 5 2 7 7
Л
Р 3 2 1 2 1 3 1 3 1 2 2 7
Л
Требуется найти кратчайший маршрут 0 -* 7, т.е. маршрут с минимальным
суммарным расстоянием.
Алгоритм, который решает эту задачу, является модификацией алгоритма
"Поиск пути" и заключается в расстановке меток. Каждая метка представляет
собой пару (s, d), где s-номер
69
вершины, из которой мы попадаем в данную вершину, а d-накопленное
расстояние к данной вершине.
Начнем с объявления "ведущей" стартовой вершины маршрута. Затем находим
вершины 1-го поколения:
Метка
S d
0
1 0 3
2
3 0 2
4
5
6
7
Теперь "закрываем" вершину 0, приписывая ей слева знак "+".
Ведущая вершина назначается следующим образом. Просматривая все
помеченные, но не закрытые вершины, находим вершину с наименьшим
значением d (ею оказалась вершина 3). Эта вершина определяет 2-е
поколение вершин: {4, 5}.
Метка d(4) для вершины 4 получается теперь как сумма rf(3) + р(3, 4) = 2
+ 1 = 3:
Метка
S d
0
1 0 3
2
3 0 2
4 3 3
5 3 5
6
7
Закрываем вершину 3 и находим новую ведущую вершину. Ею может быть
выбрана любая из двух вершин {1, 4}. Допустим, что мы выбрали вершину 4:
Метка
S d
+ 0
1 0 3
2
+ 3 0 2
- 4 3 3
5 3 4 5 4
6
7
70
У вершины 5 появляется, кроме старой (3, 5), новая метка (4, 4). Из этих
двух меток оставляем одну-ту, у которой величина d меньше. У закрытых
вершин меток не меняем.
Следующие итерации не требуют дополнительных пояснений:
Метка Метка
S d S d
+ 0 + 0
- 1 0 3 + 1 0 3
2 2 5 6
+ 3 0 2 (4) + 3 0 2
+ 4 3 3 + 4 3 3
5 4 4 - 5 4 4
6 1 5 6 1 5
7 7 5 6
Метка Метка
S d S d
+ 0 + 0
+ 1 0 3 + 1 0 3
2 5 6 - 2 5 6
+ 3 0 2 (6) 3 0 2
+ 4 3 3 + 4 3 3
+ 5 4 4 + 5 4 4
- 6 1 5 + 6 1 5
7 5 6 7 5 6
Метка
S d
+ 0
+ 1 0 3
+ 2 5 6
+ 3 0 2
+ 4 3 3
+ 5 4 4
+ 6 1 5
+ 7 5 6
Процесс заканчивается, когда все помеченные вершины оказываются
закрытыми. Строим искомый маршрут:
Путь = (0, 3, 4, 5, 7) с длиной d(7) = 6.
Точно так же по заключительной таблице мы можем найти кратчайший путь до
любой вершины, а соответствующая метка d равна длине этого пути.
Например, найдем путь 0 •" 2:
(О, 3, 4, 5, 2).
71
То, что алгоритм Дикстры действительно решает поставленную задачу, можно
доказать следующим образом.
Пусть на некотором шаге алгоритма W обозначает множество закрытых вершин.
Тогда для любой помеченной вершины х, как следует из описания алгоритма,
метка d(x) равна кратчайшему пути из 0 в х, в котором все промежуточные
вершины принадлежат W. Выбираем теперь очередную ведущую вершину х ? W.
Допустим, что существует путь 0 -* х, длина которого меньше, чем d(x).
Тогда этот путь должен проходить через последовательность вершин из W,
затем через некоторую вершину у ? W и далее через некоторый отрезок >' -*
л;. Должно, таким образом, выполняться неравенство
d(y) + Р(У> х) < d(x)-
Но это невозможно, поскольку р(х, у) > 0 и d(x) < d(y) по определению
ведущей вершины.
Таким образом, когда мы закрываем очередную вершину х, мы уже знаем
кратчайший маршрут 0 -* х (его длина равна d(x), и эта метка не может
измениться в дальнейшем).
4.9. Максимальный маршрут.
Сетевая модель комплекса операций.
При планировании работ обычно составляется перечень необходимых операций
с указанием продолжительности и непосредственно предшествующих операций.
Можно представить себе, например, комплекс мероприятий, который выполняет
режиссер любительской студии для постановки спектакля:
Но- Наименование операции Продолжительность Непосредственно
мер (в днях) предшествующие операции
а Выбор пьесы 30 -
Ь Чтение пьесы в студии 1 а
с Распределение ролей 7 Ь
d Размножение пьесы 3 Ь
е Репетиции с главными героями 30 с, d
f Репетиции с другими участниками 20 с, d
Предыдущая << 1 .. 13 14 15 16 17 18 < 19 > 20 21 22 23 24 25 .. 31 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed