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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Работа № 56077


Наименование:


Диплом АЛГОРИТМЫ И ПРОГРАММЫ РЕШЕНИЯ ЗАДАЧОПТИМИЗАЦИИ НА ГРАФАХ

Информация:

Тип работы: Диплом. Предмет: Информатика. Добавлен: 10.05.2013. Сдан: 2010. Страниц: 92. Уникальность по antiplagiat.ru: < 30%

Описание (план):


ВВЕДЕНИЕ 4
ГЛАВА 1 12
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 12
1.1 Основные определения графов 12
1.2 Типы графов 15
1.3 Цепи и циклы. Разрезы 18
1.4 Эйлеровы, гамильтоновы, бесконечные графы 22
1.5 Транспортные сети. Построение максимального потока 31
ГЛАВА 2 34
МАТЕМАТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ НА ГРАФАХ 34
2.1 Задача построения максимального потока 34
2.2 Задача построения минимального остовного дерева 39
Алгоритм Краскала 39
Жадный алгоритм 43
Алгоритм ближайшего соседа 44
2.3 Задача о пути максимальной длины между двумя вершинами ориентированного графа 46
2.4 Задача нахождения кратчайшего пути между двумя заданными вершинами ориентированного графа 48
Случай неотрицательной матрицы весов 49
Случай общей матрицы весов 52
2.5 Задача нахождения кратчайших путей между всеми парами вершин ориентированного графа 55
ГЛАВА 3 57
ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ С ПОМОЩЬЮ ПРОГРАММЫ GraphOptima 57
3.1 Технология работы с программой GraphOptima 57
3.2 Решение задач, поставленных для неориентированного графа 58
3.3 Решение задач, поставленных для ориентированного графа 63
ЗАКЛЮЧЕНИЕ 68
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 69
ПРИЛОЖЕНИЕ 72
Технология создания программного продукта GraphOptima 72
Листинг программы GraphOptima 74

ВВЕДЕНИЕ

Высокие темпы информатизации различных видов деятельности в настоящее время привели к тому, что появилась возможность компьютерного моделирования и проектирования сложных систем, изучения их свойств и управления ими в условиях дефицита времени, ограниченности ресурсов, неполноты информации. Однако для исследования характеристик любой системы математическими методами должна быть обязательно выполнена формализация, то есть построена математическая модель. Исследования с помощью математических моделей зачастую являются единственно возможным способом изучения сложных систем и решения важнейших практических задач управления.
Графы оказались хорошей математической моделью широкого класса объектов и процессов. Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электроника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. При этом обычно на графе решаются задачи о достижимости, задачи сетевого планирования, потоковая задача.
Цель исследования, осуществляемого в данной работе, - совершенствование процесса оптимизации сложных задач экономического и сетевого планирования путем разработки технологий и программных средств, использующих графовое моделирование.
Сформулированная цель предопределила следующую совокупность решаемых задач:
1. исследовать эффективность стандартных алгоритмов решения задач оптимизации;
2. разработать и реализовать алгоритмы, позволяющие автоматизировать решение задач оптимизации;
3. реализовать разработанную процедуру в виде программного продукта, соответствующего современным требованиям;
4. провести исследование эффективности разработанной процедуры на представительном множестве тестовых задач;
5. установить параметры, существенно влияющие на эффективность разработанной процедуры, и выработать рекомендации по их настройке;
6. провести апробацию разработанного подхода на реальных практических задачах.
Объект исследования - графовые методы в теории информации.
Предмет исследования - модели структур и сложность решения задач оптимизации.
Использованные методы исследования: теоретический анализ математической литературы, учебников и учебных пособий; изучение и анализ состояния исследуемой проблемы в теоретических основах информатики и дискретной математике; при выполнении работы использовался аппарат системного анализа, теоретических основ информатики, дискретной математики, теории оптимизации, методика создания прикладных интеллектуальных систем.
В основу исследования положена гипотеза: если разработать концептуальные основы графового моделирования структур решений задач оптимизации и реализовать их в виде программных продуктов, то это даст возможность активизировать математическую деятельность изучающих теоретические основы информатики и дискретную математику, повысит качество и результативность решения прикладных задач в экономическом и сетевом планировании.
Научная новизна и теоретическая значимость исследования состоит в том, что в нем:
1. выявлены структурные элементы решения задачи;
2. выявлены отношения, связывающие эти структурные элементы;
3. построены семантические графы первого порядка сложности, моделирующие эти отношения;
4. дана количественная характеристика сложности решения задач;
5. выявлены и систематизированы структуры решений задач оптимизации по числовой характеристике - сложности решения;
6. разработана технология организации работы с программными средствами при решении задач с применением графовых моделей.
Практическая значимость выпускной квалификационной работы состоит в том, что разработанные в работе теоретические положения и практические рекомендации по работе в созданном приложении могут быть использованы учителями математики, преподавателями вузов, авторами учебников, методических пособий и сборников задач по теории информации, методистами в научных исследованиях, а также специалистами в экономике и логистике для решения прикладных задач.
Обоснованность и достоверность результатов обеспечивается использованием различных методов исследования, адекватных предмету, целям и задачам работы; проведенным анализом сложившейся к настоящему времени практики решения задач дискретной оптимизации с целью выявления неиспользованных резервов совершенствования процесса создания программных средств в аспекте исследуемой проблемы; положительной оценкой материалов экспертами, учителями и методистами, участвующими в экспериментальной и опытной работе.
В главе 1 изложена теория графов: основные определения, способы задания графов. Рассмотрены следующие типы графов: вполне несвязные, связные, полные, регулярные степени n, двудольные, бесконечные и другие. Исследование связных графов проведено в двух направлениях: в зависимости от ограничений, накладываемых на маршрут в графе и в зависимости от того, насколько сильно связан граф. В результате определены цепи и циклы и множество графов разбито на виды: эйлеровы, гамильтоновы и полугамильтоновы графы. При исследовании связности графов введены понятия разреза и разделяющего множества. Сформулированы и доказаны более 20 лемм и теорем, касающихся свойств графов и действий над ними. Подготовка математического аппарата заканчивается формулировкой определений двуполостной транспортной сети и потока в сети и доказательством теоремы Форда-Фалкенсона, определяющей алгоритм построения максимального потока в сети.
Во второй главе реализованы такие этапы решения задач дискретной оптимизации, как постановка задачи, построение ее математической модели средствами теории графов и построение алгоритма. Третья глава посвящена программированию алгоритмов, тестированию и сопровождению программы. В данной главе разработана технология организации работы с разработанным программным средством GraphOptima при решении задач с применением графовых моделей.
Рассмотрим подробнее понятие задачи дискретной оптимизации.
Задача дискретной оптимизации является частным случаем более общей дискретной задачи выбора. Сформулируем задачу выбора. Пусть Х – конечной множество вариантов, P(x) – одноместный предикат, т.е. отображение вида P: X {И, Л}, где И, Л – истинностные значения. Одноместный предикат принято также называть свойством; при этом, если для x X выполняется P(x)=И, то говорят, что х обладает свойством Р. Различаются два типа задач выбора: в слабом и сильном смысле. В задаче выбора в слабом смысле требуется определить любой вариант x* X, обладающий свойством Р, либо убедиться что такого варианта не существует. Напротив, в задаче выбора в сильном смысле требуется определить множество X* X всех вариантов, обладающих свойством Р, т.е. X*={x X | P(x)}. Задачей дискретной оптимизации является задача выбора, в которой свойство P(x) означает минимальность (или максимальность) х по некоторой целевой функции (критерию) f(x), где f: X R. Например, в случае задачи минимизации P(x)=( y X f(x)<=f(y)).
Приведем примеры некоторых классических задач выбора, в т.ч. и дискретных задач оптимизации.
Задача о разбиении. Имеется n объектов, каждому из которых приписывается вес ai R, i=1,2,…,n. Вариантом будет любое разбиение множества этих объектов на два непересекающихся подмножества. Общее число вариантов равно 2n-1. Требуется определить вариант (или все такие варианты), разбивающий множество объектов на подмножества с одинаковыми суммами весов (очевидно, что эти суммы будут равны (a1+a2+…+an)/2), либо убедиться, что такого варианта не существует.
Задача о рюкзаке. Дано n предметов, для каждого из которых известен объем vi и стоимость ci. Требуется этими предметами заполнить рюкзак ограниченного объема так, чтобы суммарная стоимость предметов, упакованных в рюкзак, была максимально возможной. Здесь вариантом является любое подмножество множества предметов, суммарный объем которых не превосходит V. Общее число вариантов не превышает 2n. Это задача максимизации в слабом смысле. Значение целевой функции в ней – сумма стоимостей предметов, упакованных в рюкзак.
Задача коммивояжера. Представим себе ситуацию, когда путешественник хочет объехать n городов, побывав в каждом из них ровно один раз, вернуться в исходный город и при этом затратить минимальную сумму денег на поездку, которая складывается из затрат на переезды между парами городов, а эти затраты известны и заданы в виде таблицы C=[cij], где cij – стоимость переезда между городами i, j. Здесь вариантом будет являться любая последовательность (1, i1, …, in-1, 1), где { i1, …, in-1}={2, …, n}. Общее число вариантов равно (n-1)!. Это задача минимизации в слабом смысле. Значение целевой функции при варианте (1, i1, …, in-1, 1) равно c1i1+ci1,i2+…+cin-2,in-1+cin-1,1.
Задача о комиссиях. Имеется n комиссий, т.е. групп людей Ai, A2, …, An (при этом возможно, что Ai Aj<>Ø и даже Ai=Aj при i<>j) . Требуется в каждой комиссии выбрать председателя таким образом, чтобы ни один человек не был председателем более чем в одной комиссии, либо убедиться, что такой выбор осуществить невозможно. Здесь вариантом является последовательность (a1, …, an) такая, что ai Ai, i=1, …, n и ai<>aj при i<>j. Общее число вариантов не превосходит m!/(m-n)!, где m=|A1 … An| (если mЗадача о минимальном остовном дереве. Представим себе, что для фиксированного множества городов некоторой области известны все попарные расстояния между городами и требуется так проложить сеть дорог, чтобы их суммарная длина была минимальной, но из любого города области можно было бы проехать в любой другой город этой области. Здесь вариантом является остовное дерево полного n-вершинного графа, вершины которого соответствуют городам области. Известно, что число остовных деревьев в полном n-вершинном графе равно nn-2, что соответствует числу вариантов выбора. Указанный граф является нагруженным, при этом длиной ребра, соединяющего i-ую и j-ую вершины, является расстояние между городами i и j. Это задача минимизации в слабом смысле. Значением ее целевой функции является сумма длин ребер, входящих в остовное дерево.
Задача о назначениях. Имеется n человек и n должностей. Каждого человека можно назначить на любую из этих должностей, причем выгода от назначения i-го человека на j-ую должность выражается числом aij. Требуется осуществить назначение n людей на n должностей таким образом, чтобы суммарная выгода от этого назначения была максимальной. Здесь вариантом является последовательность (j1, …, jn) такая, что {j1, …, jn}={1, 2, …, n}; это означает, что i-ый человек назначен на ji-ую должность. Общее число вариантов здесь равно n!. Это задача максимизации в слабом смысле. Значением ее целевой функции является суммарная выгода от назначения.
Задача о минимальном пути. Пусть имеются n городов и известны попарные расстояния cij>0 между ними. Требуется минимальный путь из города I в город n. Здесь вариантом является последовательность вида (I, i1, …, ik, n ), где i1, …, ik {2, …, n-1} попарно различны (минимальный путь на содержит контуров). Общее число вариантов равно (n-2)!(1/0!+1/1!+…+1/(n-2)!). Это задача минимизации в слабом смысле. Значение ее целевой функции при варианте (I, i1, …, ik, n) равно с1i1+ci1,i2+…+cik-1,ik-1+cik,n.
Рассмотрим вопрос о вычислительной сложности алгоритмов решения задач дискретной оптимизации.
Максимально возможное число шагов работы алгоритма как функция от размерности задачи, представленной входными данными, называется сложностью алгоритма (трудоемкостью). Например, если алгоритм принимает в качестве входных данных произвольный граф G=(V, X), то под размерностью задачи можно понимать пару (n, m), где n=|V|, m=|V|. Тогда сложностью является функция двух переменных f(n, m). Значение f(n, m) при каждых фиксированных n, m равно наибольшему числу шагов, выполняемых алгоритмом для произвольного графа с n вершинами и m ребрами.
Определенную нами сложность иногда называют временной сложностью. Отметим, что для одного и того же алгоритма решения некоторой задачи понятие сложности алгоритма можно вводить и другими способами, например в смысле сложности в среднем (для определения которой суммируется число шагов работы алгоритма для каждой из задач данной размерности и полученное число делится на число этих задач).
В данной работе реализованы решения следующих задач оптимизации:
1. задача построения минимального остовного дерева;
2. задача построения максимального потока в сети;
3. задача о пути максимальной длины между двумя вершинами ориентированного графа;
4. задача о кратчайшем пути между двумя вершинами ориентированного графа;
5. задача о кратчайших путях между всеми парами вершин ориентированного графа.
В заключении приводятся основные результаты, полученные в работе и соответствующие поставленным задачам.











Подать заявку на покупку Диплом по Информатике

Ваше предложение по стоимости за работу: