Разработка алгоритма и обоснование выбора языка программирования

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Формализация исходных данных

1.1 Анализ современного состояния проблемы поиска кратных центров графа

1.2 Анализ существующих методов

1.3 Перспективы развития методов поиска кратчайших путей

Выводы

2. Разработка алгоритма и программы поиска кратных центров графа

2.1 Разработка алгоритма

2.2 Обоснование выбора языка программирования

2.3 Разработка программы

Выводы

3. Экспериментальное исследование алгоритма и программы

3.1 Тестовый пример

3.2 Тестирование программы

3.3 Вычислительный эксперимент

Выводы

Заключение

Список литературы

Введение

Современное планирование мероприятий в Вооружённых Силах тесно связано с применением теории графов. Так как охрана государственной границы, учебные мероприятия и проведение боевых операций требуют частой перегруппировки войск, совершения маршей, а время и ресурсы на их проведение ограничены, то теория графов с её богатым математическим аппаратом оказывает помощь при решении поставленных задач. Часто бывает полезно и наглядно изображать некоторую ситуацию в виде рисунка, состоящего из точек вершин, представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графов. Благодаря своему широкому применению теория графов в последние годы интенсивно развивается. В большой мере этому способствует также прогресс в области развития больших быстродействующих вычислительных машин. Непосредственное и детальное представление практических систем, таких, как распределительные сети и системы связи, приводит к графам большого размера успешный анализ которых зависит в равной степени как от существования "хороших" алгоритмов, так и от возможности использования быстродействующих вычислительных машин.

В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования (или средств обслуживания) в сетях или графах. В частности, если граф представляет сеть дорог и вершины соответствуют отдельным районам, то можно поставить задачу оптимального размещения больниц, полицейских участков, пожарных частей и многих других крайне необходимых предприятий и служб. В таких случаях критерий оптимальности может состоять в минимизации расстояния (или времени проезда) от пункта обслуживания до самой отдаленной вершины графа, т. е. в оптимизации «наихудшего варианта». В более общей задаче требуется разместить несколько таких пунктов обслуживания (а не только один). При этом самая отдаленная вершина графа должна находиться по крайней мере от одного пункта обслуживания на минимально возможном расстоянии. К таким задачам относятся задачи размещения аварийных служб, и поэтому объективным требованием здесь является минимизация наибольшего расстояния от произвольной вершины графа до ближайшего к ней пункта обслуживания. По очевидным причинам задачи такого типа называются минимаксными задачами размещения. Полученные при решении этих задач места размещения пунктов обслуживания называются центрами графа. В некоторых задачах размещения лучше всего было бы минимизировать сумму всех расстояний от вершин графа до центра обслуживания (если предполагать, что ищется место для размещения только одного такого пункта обслуживания). Такой критерий является наиболее подходящим, например, в задаче о размещении склада в сети дорог, где вершины представляют потребителей, обслуживаемых этим складом, или в задаче размещения телефонных станций в телефонной сети, где вершины представляют абонентов. Задачи такого типа вообще относятся к минимаксным задачам размещения, хотя целевая функция является часто не просто суммой расстояний, а суммой различных функций от расстояний.

1. Формализация исходных данных

1.1 Анализ современного состояния проблемы поиска кратных центров графа

Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов - граф и его обобщения.

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах.

Родившись при решении головоломок и занимательных игр, теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы буквально вездесущи. В XX в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике, биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. Не обошла она и Вооружённые Силы.

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

За последние три десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико- графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок - схем программ, в экономике и статистике, химии и биологии, в теории расписании и дискретной оптимизации. Таким образом, теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики.

На практике часто имеет место такая ситуация, когда одного пункта обслуживания недостаточно, поскольку он не в состоянии обслужить все поступающие вызовы, и тогда возникает задача о наилучшем размещении нескольких таких пунктов обслуживания. Эту задачу можно сформулировать так. Найти наименьшее число пожарных депо (например) и такое их размещение, чтобы расстояние от каждого жилого района до ближайшего к нему пожарного депо не превышало наперед заданной величины. Если же число пожарных депо известно, то требуется разместить их так, чтобы было минимально возможным расстояние от любого района до ближайшего к нему депо. Если предположить, что пожарные должны размещаться в вершинах соответствующего графа G, то задача будет состоять в нахождении р-центров графа для p = 1, 2, 3, ... и т. д. до тех пор, пока число разделения р-центра не станет меньше или равно заданному расстоянию. Полученное (последнее) значение числа p будет наименьшим числом пожарных депо, а р-центр -- их

оптимальным размещением, удовлетворяющим предъявляемым требованиям.

1.2 Анализ существующих методов

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

Пусть Х_p-- подмножество (содержащее p вершин) множества X вершин графа G = (X, Г). Через d (Х_p, x_i) будем обозначать наикратчайшее из расстояний между вершинами множества Х_p и вершиной x_i, т. е. d(X_p , x_i)=min[d(x_j,x_i)].

Аналогично, символом d (x_t, Х_p) обозначается min [d (x_i, x_j)]. Подобно тому, как определялись числа разделения вершин , мы можем определить числа разделения для множеств вершин:

s₀ (X_p) = max [v_j d(Х_p, x_j)] (1)

s_t(X_p) = max [v_j d(x_j, Х_p)]

где s₀ (Х_p) и s_t (Х_p) -- числа внешнего и внутреннего разделения множества X_p.

Множество Х_p0, для которого

S₀(X_p0)= min [s₀(X_p)], (2)

называется р-кратным внешним центром графа G; аналогично определяется р-кратный внутренний центр X_pt. Центры графа легко могут быть получены из матрицы взвешенных расстояний (полным перебором). При таком подходе надо построить всевозможные множества вершин Х_p, содержащие p вершин, а затем, используя формулы (1) и (2), непосредственно найти множества X_p0 и X_t0, образующие р-центры.

1.3 Перспективы развития методов

Достоинством данного метода является его простота и понятность. К недостаткам можно отнести необходимость составлять всевозможные подмножества из вершин графа заключенные в p-центре. Для достаточно больших графов число таких подмножеств достигает огромной величины.

Необходима разработка новых методов, которые основывались бы на уже известных, но включали дополнительный набор параметров, позволяющих минимизировать время поиска p-центров графа.

Выводы

1) Произведён анализ современного состояния проблемы поиска кратчайшего расстояния;

2) Рассмотрены существующие методы поиска кратчайшего расстояния;

3) Выявлены их недостатки;

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

алгоритм кратный центр граф

2. Разработка алгоритма и программы поиска кратных центров графа

2.1 Разработка алгоритма

1) Составим всевозможные подмножества состоящие из р вершин.

2) Найдем минимальные расстояния от вершин подмножества до оставшихся вершин графа. Данную процедуру проделаем для всех подмножеств из р вершин.

3) Выберем из этих минимальных расстояний максимальное и припишим его данному подмножеству.

4) Выберем из всех подмножеств те, для которых минимаксное расстояние минимально. Они и будут р-центрами графа.

2.2 Выбор языка программирования

Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов - языков программирования. Смысл появления такого языка - оснащённый набор вычислительных формул дополнительной информации, превращает данный набор в алгоритм. Язык программирования служит двум связанным между собой целям: он даёт программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать.

С++ - это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьёзного программиста. За исключением второстепенных деталей С++ является надмножеством языка программирования С. Помимо возможностей, которые дает С, С++ предоставляет гибкие и эффективные средства определения новых типов. Используя определения новых типов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определённых пользователем. Такие объекты просты и надёжны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным. При правильном использовании этот метод даёт более короткие, проще понимаемые и легче контролируемые программы.

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

С++ поддерживает указатели не переменные и функции. Указатель на объект программы соответствует машинному адресу этого объекта. Посредством разумного использования указателей можно создавать эффективно-выполняемые программы, так как указатели позволяют ссылаться на объекты тем же самым путём, как это делает машина. Си ++ поддерживает арифметику указателей, и тем самым позволяет осуществлять непосредственный доступ и манипуляции с адресами памяти.

В своём составе С++ содержит препроцессор, который обрабатывает текстовые файлы перед компиляцией. Среди его наиболее полезных приложений при написании программ на С++ являются: определение программных констант, замена вызова функций аналогичными, но более быстрыми макросами, условная компиляция. Препроцессор не ограничен процессированием только исходных текстовых файлов С++, он может быть использован для любого текстового файла.

С++ - гибкий язык, позволяющий принимать в конкретных ситуациях самые разные решения.

В языке С++ полностью поддерживаются принципы объектно-ориентированного программирования, включая три кита, на которых оно стоит: инкапсуляцию, наследование и полиморфизм. Инкапсуляция в С++ поддерживается посредством создания нестандартных (пользовательских) типов данных, называемых классами. Язык С++ поддерживает наследование. Это значит, что можно объявить новый тип данных (класс), который является расширением существующего.
Хотя язык С++ справедливо называют продолжением С и любая работоспособная программа на языке С будет поддерживаться компилятором С++, при переходе от С к С++ был сделан весьма существенный скачок. Язык С++ выигрывал от своего родства с языком С в течение многих лет, поскольку многие программисты обнаружили, что для того, чтобы в полной мере воспользоваться преимуществами языка С++, им нужно отказаться от некоторых своих прежних знаний и приобрести новые, а именно: изучить новый способ концептуальности и решения проблем программирования. Перед тем как начинать осваивать С++, Страуструп и большинство других программистов, использующих С++ считают изучение языка С необязательным.

Исходя из вышеизложенного для написания программы, был выбран язык программирования Visual С ++ версии 6.0.

2.3 Разработка программы

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

Далее производится объявление вспомогательных функций:

void threecentr(int N,int pc,int kol)-данная функция предназначена для поиска 3-центров графа;

void fourcentr(int N,int pc,int kol)-данная функция предназначена для поиска 4-центров графа;

void fivecentr(int N,int pc,int kol)-данная функция предназначена для поиска 5-центров графа;

int faktorial(int N,int pc)-данная функция предназначенна для поиска числа множеств вершин образующих p-центр.

Далее следует главная функция. В ней объявляется двумерный массив mas[100][100]. Затем предлагается ввести код операции. В зависимости от введенного значения массив mas инициализируется либо из файла (если введена 1), либо с клавиатуры (если введена 2), либо случайными числами (если введена 3). При вводе числа, не предусмотренного программой, выводится сообщение о неправильности ввода. Далее программа преобразует массив mas, после чего он представляет собой матрицу полных расстояний.

Затем массив mas записывается в файл matr.txt.

Далее происходит обращение к объявленным ранее функциям.

В функцию factorial() передается размерность массива mas и число вершин в p-центре. Возвращает функция максимальное число различных сочетаний из p вершин.

В функцию threecentr() передается размер массива mas, число вершин в p-центре и число, вычисленное функцией factorial(). В начале функция считывает из файла matr.txt массив mas. Затем производится вычисление 3-центров и вывод их на экран.

Функции fourcentr() и fivecentr() аналогичны функции threecentr(). В них вычисляются и выводятся на экран 4- и 5-центры соответственно.

Выводы:

1) Произведённые в предыдущих главах исследования позволили составить

алгоритм поиска p-центров;

2) Обоснован выбор языка программирования;

3) На основе алгоритма составлена программа поиска

p-центров.

3. Экспериментальное исследование алгоритма и программы

3.1 Тестовый пример

Для тестового примера был выбран граф, состоящий из шести вершин (рис. 1). Для него была записана матрица смежности.

7

10 8

1

6

Рис. 1

Матрица смежности.

Далее матрица смежности была преобразована в матрицу полных расстояний при помощи алгоритма Флойда.

Матрица расстояний.

Найдем 3-центры данного графа. Составим все возможные подмножества вершин графа состоящие из трех вершин. Возьмем первое подмножество из вершин Х₁, Х₂, Х₃.

Найдем минимальное расстояние от вершин подмножества до оставшихся вершин графа.

Теперь найдем максимальное из этих минимальных расстояний, назовем его минимаксным расстоянием для данного подмножества. Аналогично найдем минимаксные расстояния для всех подмножеств. Подмножества, у которых минимаксное расстояние минимально и будут 3-центрами графа.

Аналогично найдем 4- и 5-центры соответственно.

Для 4-центров:

Для 5-центров:

3.2 Тестирование программы

При запуске программа предлагает ввести код операции.

В зависимости от введенного значения заполняется матрица смежности. Если введена единица, матрица смежности заполняется из файла. Если введена двойка, матрица смежности заполняется с клавиатуры. Если введена тройка, матрица смежности заполняется случайными числами. Далее предлагается ввести размер массива. Затем программа преобразует матрицу смежности и выводит на экран матрицу полных расстояний.

Далее программа вычисляет р-центры и выводит результат на экран.

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

3.3 Вычислительный эксперимент

Измерим время выполнения программы для различного количества вершин графа и запишем результаты в таблицу.

Выводы:

1) В данной главе произведен поиск р-центров тестового графа;

2) Произведено решение тестового примера с помощью составленной программы;

3) На основании совпадения результатов сделан вывод о работоспособности программы;

4) Указаны необходимые требования для пользования программой.

Заключение

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

Для решения поставленной задачи был применен математический аппарат теории графов, которая имеет широкое применение в Вооруженных Силах не только для поиска кратных центров графа, но и для принятия оптимального решения и т.д. Преимуществом рассмотренного метода является его простота и лёгкость для понимания.

Основные результаты работы сводятся к тому, что указывается важная роль применения теории графов в Вооруженных Силах, разрабатывается математическая модель поиска р-центров графа и проводится её экспериментальное исследование.

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

Список литературы

1. Н. Кристофидес, Теория графов. М.: «Мир» 1978г. ;

2. Вялых Б.И,, Сукманов С.А. Дискретная математика. ТАИИ 2004г;

3. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965г;

4. Е.П. Липатов. Теория графов и её применения. - М., Знание, 1986г.

Размещено на Allbest.ru