Математическое моделирование на графах. Часть 1. Берцун В.Н. - 36 стр.

UptoLike

Составители:

Рубрика:

36 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

Всякий алгоритм сортировки, основанный на попарном сравне-

нии, имеет свое дерево решений, где самый короткий путь из корня

в лист соответствует наилучшему случаю. Для оптимального алго-

ритма каждая перестановка из N элементов массива появится только

один раз, а в дереве решений должно быть не меньше N! листъев.

Так как

log

N! = log

(N(N – 1)(N – 2)…1) ≈ N log

то количество операций в такой сортировке О(N log

N).

На рис. 1.41 изображено кодовое дерево азбуки Морзе [31], где

используется не более пяти знаков (•, ⎯) для кодирования букв рус-

ского языка.

ЬЪ

Рис. 1.41

Кодирование начинается с вершины двоичного дерева. В каждом

узле поворот к левому дереву добавляет в коде буквы точку, а к пра-

вому – тире.

Рассмотрим пример построения и анализа дерева в задаче о лаби-

ринте. В лабиринте (см. рис. 1.42, a) морская свинка должна найти

пищу [32]. Сколькими способами она может это сделать, если ни в

один тупик она не заходит более одного раза. Причём, попав в ту-

пик, она возвращается на перекрёсток, с которого свернула. Дерево

маршрутов для этого лабиринта изображено на рис. 1.42, б. Как сле-

дует из этого графа, всего существует 8 возможных маршрутов, а

самый оптимальный из них имеет длину 4.