УДК 004.021

ВЛИЯНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ НА ЭФФЕКТИВНОСТЬ АЛГОРИТМА

Маркова Янина Сергеевна1, Угаров Андрей Сергеевич2
1Тульский государственный педагогический университет им. Л.Н.Толстого, студент факультета математики, физики и информатики
2Тульский государственный педагогический университет им. Л.Н.Толстого, студент факультета математики, физики и информатики

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

Ключевые слова: задача коммивояжера, задача о мостах Кенигсберга, математическое моделирование, программирование


INFLUENCE OF MATHEMATICAL MODEL ON EFFICIENCY OF ALGORITHM

Markova Yanina1, Ugarov Andrej2
1Tula State Lev Tolstoy Pedagogical University, student of mathematics, physics and computer science
2Tula State Lev Tolstoy Pedagogical University, student of mathematics, physics and computer science

Abstract
The article deals with the mathematical modeling of the development of algorithms for solving the problem of the bridges of Königsberg and the modified traveling salesman problem. Fragments software implementation of algorithms in the language C++. Article materials may be useful in the study of programming in high school and high school.

Рубрика: 01.00.00 ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Маркова Я.С., Угаров А.С. Влияние математической модели на эффективность алгоритма // Современные научные исследования и инновации. 2016. № 3 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2016/03/64967 (дата обращения: 20.11.2016).

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

Математическое моделирование есть метод исследования объектов и процессов реального мира с помощью их приближенных описаний на языке математики — математических моделей. Этот метод чрезвычайно плодотворен и известен уже несколько тысячелетий. Возможности математического моделирования и его влияния на научно-технический прогресс неизмеримо возросли в последние десятилетия в связи с переходом к информационному обществу. Однако и до момента появления компьютеров математическое моделирование  играло существенную роль в решении задач прикладного характера. Примером такого рода задач является знаменитая проблема семи мостов Кенигсберга, которую можно сформулировать следующим образом: возможно ли пройти по всем семи мостам через реку Преголя, не проходя ни по одному из них дважды?

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

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

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

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

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

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

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

Представим исходный граф в виде матрицы смежности со следующими уточнениями: значение элемента, располагающегося в i-ой строке j-ом столбце, равно количеству ребер, соединяющих i-ю и j-ю вершины. Данный подход позволит определить суммарный вес некоторой k-ой вершины путем сложения всех чисел, расположенных в k-ом столбце. В случае если сумма будет нечетна, необходимо увеличить на единицу значение счетчика, хранящего количество нечетных вершин.

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

Реализация данного алгоритма на языке программирования С++ может выглядеть следующим образом.

Первоначально обнуляется общее количество вершин, имеющих нечетную степень.

int numberOfOddVertex=0;

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

for(int i=0; i<rows; i++)

{

if (sum(adjacencyMatrix[i],columns)%2!=0)

numberOfOddVertex++;

}

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

int sum(int* array, int arraySize)

{

int result=0;

for (int i=0; i<arraySize; i++)

result+=array[i];

return result;

}

Завершается работа алгоритма анализом количества нечетных вершин. В случае если количество нечетных вершин четно и не превышает двух, функция возвращает значение true, иначе – false.

if ((numberOfOddVertex%2==0)&&(numberOfOddVertex<=2))

return true;

else

return false;

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

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

Вначале формализуем задачу. Поменяем множество мест на множество точек, а пути, соединяющие места между собой, на ребра, вес которых будет равен соответствующим длинам пути. Таким образом, от  реальных объектов (города и пути между ними) перейдем к графу, что позволит описать математическую модель решения задачи. Отметим, что полный перебор, как метод решения данной задачи, так же неэффективен, как и в предыдущей задаче. Даже в самом простом случае общее количество всевозможных маршрутов будет равняться (n-1)!/2 , что при 11 городах дает 1 814 400 возможных маршрутов, а при 13 городах уже 239 500 800 вариантов. Однако модификация перебора с возвратом, известная как метод ветвей и границ, относительно эффективно справляется с данной задачей.

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

Рассмотрим данный способ решения задач в общем виде. Условие может быть сформулировано следующим образом: пусть дано дискретное множество A и определенная на данном множестве функция f. Обозначим минимум функции f на множестве X как F(x) Тогда необходимо найти такое , что f(a)=F(A).

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

Введем дополнительную функцию φ, заданную на совокупности подмножеств исходного множества A так, что ее значение не превышает минимума функции f для любого из подмножеств в разбиении

.

Пусть  - произвольный элемент множества A и пусть. Тогда справедливо следующее утверждение:

.

Используя утверждения (1) и (2) можно использовать следующий способ поиска минимума.

Разобьем все множество A на некоторые подмножества , и для каждого из них найдем нижнюю оценку . После этого для всех элементов множества A вычислим значения функции f, запоминая наименьшее в качестве рекордного значения. Все подмножества, чья оценка превышает рекордное значение (f*), объединим во множество , тем самым исключив их из дальнейшего рассмотрения.

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

Полученные в результате классы и будут решением исходной задачи.

Вернемся к задаче о коммивояжере. Решение данной задачи методом ветвей и границ было предложено коллективом автором (Дж. Литл, К. Мурти, Д. Суини, К. Кэрол) в 1963 году, а алгоритм, который используется для решения задачи, получил название алгоритм Литла.

Входными данными для алгоритма Литла является матрица смежности графа, следующего вида: число k, стоящее на пересечении i-ой строки и j-того столбца означает, что i-ая и j-ая вершины графа соединены ребром, вес котором равен k. Отсутствующие дуги помечаются некоторым числом, которое на несколько порядков превосходит вес самого «тяжелого» ребра – это необходимо для того, чтобы сразу исключить из рассмотрения отсутствующие ребра. Что же касается структуры самого алгоритма, то он состоит из нескольких шагов:

1) Приведение исходной матрицы.

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

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

2) Определение степеней нулей.

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

3) Ветвление.

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

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

Если оказывается, что , то повторяем второй и третий шаг с матрицей смежности, получившейся в первом случае. Если получается, что  , то второй и третий шаг повторяем с матрицей, которая получилась во втором случае.

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

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

Данную задачу можно решить посредством построения минимального остового дерева, что позволяет использовать алгоритм Прима-Краскала.

Основная идея алгоритма заключается в следующем: в представленном графе с n вершинами n-1 раз выбирается самое короткое ребро, которое не образует цикла с уже включенными в дерево ребрами.

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

1)     находим минимальное ребро из не включенных в дерево и, если оно не образует цикл (то есть, если вершины, которые оно соединяет, не покрашены в один цвет), встраиваем данное ребро в конечное остовое дерево.

2)     меняем все цвета вершин, включенных в дерево, на один общий цвет.

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

Рассмотрим пример реализации данного алгоритма на языке С++.

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

for (int i=0; i<vertexCount; i++)

{

vertexArray[i]=i;

}

После этого в цикле n-1 раз (где n – количество вершин графа) выполняются следующие действия.

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

minimalVertexWeight = INT_MAX;

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

for (int i=0; i<vertexCount; i++)

{

for (int j=0; j<vertexCount; j++)

{

if ((vertexArray[i]!=vertexArray[j])&&(adjacencyMatrix [i][j]<minimalVertexWeight))

{

firstVertexIndex=i;

secondVertexIndex=j;

minimalVertexWeight=adjacencyMatrix[i][j];

}

}

}

3)    обновляется исходный граф – все вершины, окрашенные в цвет конечной вершины только что встроенного ребра, перекрашиваются в цвет исходной вершины этого ребра.

for (int i=0; i<vertexCount; i++)

{

if (vertexArray[i]==vertexArray[secondVertexIndex])

vertexArray[i]=vertexArray[firstVertexIndex];

}

В результате, совокупность ребер, окрашенных в общий цвет, будет образовывать искомое остовое дерево минимального веса.

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


Библиографический список
  1. Мартынюк, Ю.М. Использование математического моделирования при обучении программированию/Мартынюк Ю.М., Ванькова В.С., Ваньков Б.П. // Современная педагогика. 2014. № 11 (24). С. 41-44.


Все статьи автора «Мартынюк Юлия Михайловна»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться:
  • Регистрация