ВВЕДЕНИЕ 3
1 Теоретическая часть 6
1.1 Определения и обозначения 6
1.2 Алгоритм расстановки пометок (Форда-Фалкерсона) 7
1.3 Трудоемкость алгоритма 8
1.4 Описание задач 11
2 Руководство по программе 16
2.1 Описание технологии WPF 16
2.2 Подробное руководство пользователя 17
3 Эксперименты и исследование поставленной проблемы 26
3.1 Зависимость практической трудоемкости от размера входных данных 26
3.2 Сравнение экспериментально вычисленного количества операций с максимально
возможным значением 31
ЗАКЛЮЧЕНИЕ 37
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 39
ПРИЛОЖЕНИЕ А
В наш век быстро сменяющих друг друга технологий, огромное значение имеет время и качество выполнения тех или иных задач. Они же в свою очередь зависят от объема того, что предстоит сделать, на что приложены усилия, будь то количество проектов для строительной бригады, объем продукции для производства или входящие данные для алгоритма.
На практике довольно часто возникают прикладные задачи в сетевой постановке (напр., [1 - 3]). При решении многих из них приходится строить потоки максимальной величины в естественно возникающих или специально построенных сетях (напр., [2,3]). Поэтому исследования, касающиеся работы алгоритмов, позволяющих строить такие потоки, являются актуальными.
Одним из методов, предназначенных для построения максимального потока в ориентированной сети с пропускной способностью дуг, является известный метод расстановки пометок [2]. Целью данной выпускной работы является экспериментальное исследование трудоемкости этого метода на примерах прикладных задач. Требуется на некоторых классах прикладных задач экспериментально установить трудоемкость применяемого при их решении метода расстановки пометок и сравнить ее с известной теоретической оценкой трудоемкости, полученной для сетей общего вида.
В данной работе проводится эксперимент в области дискретной оптимизации для исследования зависимости трудоемкости одного определенного алгоритма от типа задач, к решению которых он применяется. Эксперимент этот важен с практической точки зрения следующим. Сравнивая теоретическую трудоемкость с трудоемкостью, полученной на практике, можно выяснить, является ли оправданным и оптимальным применение данного алгоритма для решения той или иной прикладной задачи. Также при сравнении числа операций можно выяснить, насколько практическая трудоемкость отличается от теоретической и сохраняется ли порядок теоретической оценки сложности алгоритма. Если трудоемкость, полученная на практике, будет намного отличаться от теоретически доказанной, то их сравнение, возможно, даст ответ на вопрос: зависит ли значение числа операций и порядок его оценки от всех параметров задачи, или тот или иной параметр можно опустить.
Оцениваемым ресурсом в выпускной работе является вычислительная сложность (процессорное время). Проведенные в работе исследования позволяют оценить эффективность алгоритма расстановки пометок для трех прикладных задач, а именно, для задачи о спросе и предложении (частный случай), задачи о циркуляции и одной задачи о назначениях.
Основоположниками алгоритма являются американские математики Л.Р. Форд и Д.Р. Фалкерсон. В 1955 году они сформулировали этот алгоритм для решения важной военной задачи. Данный алгоритм применяется в различных сферах: в логистике, задачах планирования, коммуникациях, экономике и т.д. С помощью поиска максимального потока решаются некоторые задачи транспортного типа, задачи о назначениях, задачи о циркуляции и т.д. Теоретическая трудоемкость алгоритма Форда-Фалкерсона известна для каждого типа вышеперечисленных задач. В работе на основе проведенных исследований сделаны выводы о том, для какой из задач алгоритм расстановки пометок работает быстрее, и есть ли наглядная и существенная зависимость между параметрами задачи и трудоемкостью ее решения. Кроме того, оценено времени работы алгоритма для каждого типа задач.
Итак, во введении работы обозначены цель, задачи, предмет и объект исследования, подчеркнута актуальность темы исследования. В первой главе работы раскрываются теоретические аспекты: определения, описание исследуемого алгоритма, постановки прикладных задач и методы их сведения к задаче построения максимального потока в сети, понятие трудоемкости. Во второй главе представлено подробное руководство по программе. В руководстве описывается, как пользователю решить тот или иной вид прикладных задач. В третьей главе описаны проведенные эксперименты по сравнению теоретической и практической трудоемкости для каждого вида задач. В заключении делаются основные выводы по дипломному проекту.
В результате исследования, проведенного в дипломной работе, можно сделать вывод, что поставленные задачи решены, и цель работы достигнута.
Была написана программа, предназначенная для реализации алгоритма поиска максимального потока в ориентированных сетях. Кроме того, был написан ряд программ для решения прикладных задач. В программах заложена возможность подсчета числа операций, требуемых алгоритму для решения каждой задачи.
На основе полученных данных было проведено исследование, заключавшееся в сравнении практической трудоемкости алгоритма с известной теоретической. Экспериментально был определен порядок оценки сложности алгоритма для трех типов задач. После проведенного анализа были построены графики сравнения экспериментально полученного количества операций с максимально возможными значениями, а на основании полученных результатов были сделаны следующие выводы.
Во-первых, по сформированной статистике можно утверждать, что процент задач, для которых трудоемкость алгоритма не соответствует теоретической, очень мал (2 - 4 % для задач о циркуляции, а для задач о спросе и предложении и для задач о назначениях в 100% случаев порядок трудоемкости, вычисленной экспериментально, совпадает с порядком теоретической трудоемкости). Это значит, что реализованные программы могут быть использованы для поиска максимального потока в сетях, а также для решения прикладных задач, сводящихся к данному алгоритму.
Во-вторых, метод сведения прикладных задач к задаче поиска максимального потока эффективен, так как вычисленная на практике трудоемкость соответствует теоретической оценке сложности.
Итак, в целом практически полученная трудоемкость исследуемого алгоритма соответствует известной теоретической трудоемкости. Кроме того, для решения задачи о назначениях и задачи о циркуляции количество операций оказалось гораздо ниже максимально возможного значения, а для задачи о спросе и предложении количество операций близко к максимально возможному значению.
