Математическая модель африканской электрификации

Министерство образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

Курсовая работа

по практикуму на ЭВМ: структуры данных и алгоритмы

Факультет:  ПМИ

Группа: ПМ-85

Студент: Рак А.В.

Преподаватель:  Шапошникова Т.А

Новосибирск, 2009

1.  Условие задачи

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

2.  Анализ задачи

1.  Исходные данные задачи:

n – количество домов (столбов); n=1,2,…; n20;  S – электрическая сеть,

S={(name1, name2, weight)| name1, name2дом (столб),  weightR\{0}, i=1,…,n},

дом (столб) N; weight - расстояние между домами (столбами);

2.  Результат:  Q={(name1, name2, weight) | name1, name2 дом (столб),  weightR\{0}, i=1,…,n}

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

                  Метод решения:

Задача построения остовного дерева с минимальным весом:

UkStr = голова списка, который содержит вершины графа

Root = корень дерева двоичного поиска, которое содержит ребра графа с весом каждого ребра.

повторять

    UkUzel1 = Root

    UkUzel  = Root.левый_потомок  

    если UkUzel=, то Т1=Root.X , T2 = Root.Y, Root = Root.правый_потомок

    иначе

                  повторять

                             UkUzel1 = UkUzel1.левый_потомок

                              UkUzel  = UkUzel.левый_потомок

                  пока UkUzel.левый_потомок ≠

                  T1 = UkUzel.X; T2 = UkUzel.Y;

                  UkUzel1.левый_потомок = UkUzel.правый_потомок

        Res1 = элемент списка вершин UkStr, который содержит элемент Т1

        Res2 = элемент списка вершин UkStr, который содержит элемент Т2

        Если Res1 ≠ Res2, то удалить Res2 из списка вершин UkStr

        Добавить ребро, которое соединяет вершины Т1 и Т2  в список ребер

        минимального веса

пока UkStr.следующий.следующий ≠

3.  Структуры данных, используемых для представления исходных данных и результатов задачи

1.  Входные данные

Внешнее представление

<Электрическая сеть> : : <множество кабелей>

<Множество кабелей> : : пробел | пробел <кабель>

<Кабель> : : <откуда> пробел <куда> пробел <длина кабеля>

<Откуда> : : <куда> : : натуральное число

<Длина кабеля> : : вещественное число

Внутренне представление

      struct Uzel

     {

        int X;

        int Y;

        int Pay;

         Ref Left;

         Ref Right;

     };

2.  Выходные данные

Внешнее представление

Q={(name1, name2) | name1, name2 дом (столб),  i=1,…,n}

Внутреннее представление

typedef struct list