ПОЛИНОМИАЛЬНЫЙ АЛГОРИТМ РЕШЕНИЯ КОМБИНАТОРНОЙ ЗАДАЧИ

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

Постановка задачи

Пусть дан полный неориентированный граф [1] с 5 вершинами, имеющими как положительные, так и отрицательные веса рёбер:

Рисунок 1. Полный неориентированный граф

По графу построим квадратную матрицу весов ребер:

Рисунок 2. Матрица весов ребер

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

Данная задача принадлежит классу NP в теории алгоритмов. Класс NP - класс языков (задач), ответ на которые можно проверить за полиномиальное время. [2]. Решение задач такого типа сводится к перебору и экспоненциально по времени. Есть ли алгоритм, который позволит решить задачу за полиномиальное время? Задачи, решаемые за время, не превышающее полинома от входных данных, принадлежат классу P. Принадлежит класс NP классу P? Это открытая математическая проблема равенства классов P и NP [3].

Решение поставленной задачи:

Для удобства графы будут представлены в виде матриц (Рисунок 2).

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

l – количество комбинаций;

Мною были проанализированы случайно сгенерированные матрицы размером 5x5 и выведены формулы, способствующие решению.

Формула для расчета суммы всех комбинаций при n>2:

 – сумма всех элементов матрицы;

n – порядок матрицы.

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

Обозначим матрицу графа буквой A. Разложим ее на сумму n новых матриц:

Каждую полученную матрицу обозначим буквой , где i – порядковый номер матрицы. Полученная сумма матриц  образует матрицу A:

n – порядок матрицы;

Теперь необходимо найти “выгодные” векторы O матрицы A по формуле:

 - i-ый выгодный вектор матрицы;

 – нулевая матрица.

Соберем из этих векторов квадратную матрицу n порядка для понимания “выгодных” векторов по примеру матрицы из задачи (Рисунок 2):

Рисунок 3. Матрица комбинаций

В рассматриваемом примере сумма комбинаций по (2) формуле равна:

Сумма всех элементов полученной матрицы равна . Такая матрица является матрицей всех комбинаций. Иными словами, сумма элементов всех векторов O равна сумме всех комбинаций.

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

y – сумма элементов матрицы для искомой комбинации;

r – разница суммы элементов матрицы для единственной комбинации из n графов.

Разница вычисляется по формуле:

 – элемент оптимальной матрицы O.

Как можно видеть (Рисунок 3), у оптимальной матрицы  есть лишь один отрицательный элемент -  равный -2. Значит r = 2. Подставив r в формулу (6) мы получим y = 10. Это и будет оптимальным решением матрицы графа.

Искомая комбинация является порядковыми номерами всех положительных элементов. Так для вектора  положительные элементы - , , , . Полученная комбинация – 1,3,4,5, является искомой.

Если сравнить число из комбинации 1,3,4,5 и y, то они равны. F(1,3,4,5) = 1+2+2+3-3+5=10, y=10.

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

Рисунок 4. Полный перебор комбинаций

Сумма элементов для комбинации 1,3,4,5 равна 10 и является максимальной из всех комбинаций.

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

1. В матрице  количество отрицательных чисел > 0, иначе искомой комбинацией является комбинация всех вершин графов.
2. Полученное оптимальное решение y > максимального числа в матрице, иначе оптимальным решением матрицы будет максимальное число и комбинация ему соответствующая.

Данный алгоритм позволяет вычислять оптимальную комбинацию для полного неориентированного графа за полиномиальное время, т.к. не зависит от количества комбинаций и общее количество шагов не превышает , где a и b константы, n – количество вершин графа.

Написанная мною программа на JavaScript находит оптимальное решение для случайно сгенерированной матрицы 50 порядка за 0.027 секунды, в то время как на перебор уйдет около года. Для матрицы 100 порядка за 0.048 секунды.

Заключение

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

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

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

1. Оре О. Теория графов. — М.: Наука, 1968. — 336 с.
2. Равенство классов P // Викиконспект [Электронный ресурс] – Режим доступа. – URL: http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NP (дата обращения 22.06.2016)
3. Равенство классов P и NP // Википедия [Электронный ресурс] – Режим доступа. – URL: https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_P_%D0%B8_NP (дата обращения 22.06.2016)