Полиномиальный алгоритм для комбинаторной задачи (P=NP?)

В этой статье я хотел бы рассказать о моем исследовании на тему равенства классов P и NP. Оригинал статьи вы можете прочитать здесь.

Небольшое введение.

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

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

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

image

Это полный неориентированный граф. Полный — потому что все вершины взаимодействуют с другими, неориентированный — потому что у графа нет направлений.

И удобнее графы рассматривать в виде разных матриц, к примеру мы будем рассматривать матрицу ребер, соединяющих вершины:

image

Можем представить эти 5 вершин как 5 сотрудников. Представим, что у нас есть для них поручение и мы знаем как сотрудники взаимодействуют друг с другом. К примеру 1 и 2 сотрудники справятся с этой задачей хуже (их комбинация -3), чем 1 и 4 (их комбинация 2). А допустим 1,3 и 4 сотрудники (их комбинация 1+2+3=6) выполняют задачу уже лучше. Главное понять как устроено нахождение комбинации. Если все еще сложно понять, то вот видео youtu.be/7rKXqprYR2E?t=1h8m52s. Постановка задачи такая же.

Задача сводится к тому, чтобы найти максимальное число в комбинациях.

Теперь решение.
Вообще обнаружить данное решение мне помогла формула: image
Sэлементов — найденное число в самой большой комбинации, в данном случае 12345. Либо сумма всех элементов матрицы, только поделенная на 2. Так как матрица симметричная относительно диагонали, делить мы можем.

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

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

image

Мы складываем по вертикали (по горизонтали, не принципиально) все элементы и смотрим, есть ли здесь отрицательные числа, если нет, то комбинация будет максимальной, то есть 1,2,3,4,5. Однако здесь присутствует -2, идем дальше.

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

Зачеркиваем строку, соответствующую выгодному вектору, а остальные элементы суммируем:

image
Выгодный вектор O1
image
Выгодный вектор O2
image
Выгодный вектор O3
И так далее до О5, и следом сразу же посчитаем сумму элементов в каждом векторе:

image

Находим самое большое число из сумм — 18, значит вектор O2 будет оптимальным и в нем содержится решение.
Рассмотрим алгоритм, как достать это решение. Находим в этом векторе отрицательные элементы и суммируем их, в нашем случае просто -2. Если мы домножим на минус единицу, поменяем знак, то получится разница. Разница между числом для самой большой комбинации и ответом, который нам нужно найти, если просто, то это x+r=y. x — либо сумма всех элементов деленная на 2, либо просто число от самой большой комбинации. Подставим в формулу, получим 8+2=10. Это будет числовое решение матрицы. Однако нам нужно узнать именно вершины (рабочие) составляющие комбинацию. Просто берем номера столбцов для всех положительных чисел вектора O2: 1,3,4,5. Эта комбинация и является искомой.

Зачем мы искали максимальный элемент (5) — если вдруг решение будет меньше, чем этот элемент, то комбинация будет соответствовать этому элементу, а не комбинации в векторе O.

Есть способ быстрее определить искомую комбинацию, без векторов O, однако мне важно, чтобы вы обратили внимание на полученную матрицу векторов O, если все ее элементы сложить, то получим сумму всех комбинаций (в данном случае 64, можете проверить по формуле выше). Тем самым, матрица является матрицей всех комбинаций графа (рабочих). То, как, например для графа размером 20х20, количество комбинаций — 1048575 и все они умещаются в эту матрицу 20 порядка, да еще и находится оптимальное решение, просто поражает!

А теперь немного шустрее решим эту задачу:

1. Выпишем сумму всех элементов и максимальное число.
2. Тут нам пригодится вектор B, от суммы всех элементов отнимаем каждый элемент и самый наибольший ответ определит выгодный вектор.

image
По примеру с O2: 16-(-2)=18. Мы намного сократили время выполнения алгоритма.
3. Дальше таким же способом как и ранее получаем вектор O2 и находим решение.

Количество шагов не превышает полинома второй степени, сами можете убедиться.

Немного скриншотов из программы по проверке:

image
Матрица 4х4, метод разложения и перебора

image
Матрица 50х50, 0,039 сек. на решение

image
Матрица 100х100, 0,069 сек. на решение

Как же дела обстоят с другими задачами? С задачей коммивояжера дела обстоят хорошо, однако и не очень. Например если получить матрицу векторов O и матрицу векторов O для транспонированной матрицы, то мы опять же получим матрицу всех комбинаций, однако тут уже комбинаций гамильтоновых циклов:

image

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

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

Матрица комбинаций — вещь не до конца известная мне и я был бы рад, если бы вы помогли понять, что это такое и как с этим работать.

Upd: нахождение наибольшей клики по данному алгоритму:

image

-2 — для обозначения, что вершины не связаны, 1 — что связаны, в графе из картинки всего 5 клик и максимальная клика — 1,2,3,4. Принцип нахождения клики такой же.
Поделиться публикацией

Комментарии 14

    +8
    Это троллинг?
      –3
      Да почему, я же не говорю, что классы равны, а этот алгоритм можно легко самому проверить
        +4
        Ну как. Вы либо говорите это, либо вводите людей в заблуждение заголовком.

        1. Если вы говорите, что ваш алгоритм полиномиальный и он решает NP-полную задачу, то вы утверждаете, что P=NP.
        2. Если поставленная задача не NP-полная, то вы утверждаете, что она принадлежит P. Доказательство этого факта никаким образом не приближает к решению задачи P vs. NP.
          –3
          Хорошо, на самом деле, я не знаю по поводу полноты этой задачи, давайте тогда так поступим, есть задача по поиску клики, она NP-полная, если мы поступим с задачей по поиску клики так же, как и в этой задачке, то максимальная клика находится по такому же алгоритму: https://pp.vk.me/c626723/v626723520/1693c/yrJf8r_pbBQ.jpg
          В примере в графе всего 5 клик, видно, что клика 1,2,3,4 является наибольшей, что доказывает и перебор и алгоритм
            +4
            В задаче о клике (которая является NP-полной) граф произвольной формы. Задача о максимальной клике без весов на ребрах в полносвязном графе очевидно решается за O(1). Тут задача maximum weighted clique в полносвязном графе (я сходу не уверен что она NP-полная, хочется почитать обоснование), и судя по всему предлагается ее решать жадным алгоритмом методом последовательного удаления вершин с минимальной суммарной стоимостью удаленных ребер, и все равно непонятно что делать если после удаления одной вершины получатся подклики одинакового суммарного веса и почему делается всего один шаг.
              0
              Можно взять произвольный граф, ребрам назначить вес 1, несуществующим рёбрам назначить вес -INF. Размер вырастет полиномиально. Клика с ребрами исходного графа даст максимальный вес.
          +3

          А что вы тогда вообще сказать-то хотели? Я даже не про некоторую кривизну перевода — это бывает. Я вот про это например:


          Ведь при положительном ответе, программисты смогут гораздо оптимизировать многие аспекты программы

          Вы в курсе, что доказательства бывают неконструктивные, от противного, например? И даже если кто-то что-то докажет — это совершенно не будет означать в общем случае наличия способа решения проблемы. Это будет значить, что он существует — но возможно ни на шаг не приблизит к его построению.

            +4
            Думаю, автору тяжело будет продолжить дискуссию.
        +2
        Гениально. Срочно дуйте в институт Клея! (и это не опечатка!)
          +3
          а можно где-нибудь увидеть обоснование принадлежности этой задачи к классу NP?
            +3
            У вас в статье по ссылке гениальное заключение: P ⊂ NP. Скажу по секрету: мы все это и так знали.
              +1
              Нет там написано не так, так написано, что P ∈ NP — и у меня это вызывает вопрос, а что именно автор имеет ввиду под P (NP)?

              Другой вопрос касается формулы 5 почти в самом начале статьи (на которую дана ссылка), автор предлагает вычесть две матрицы размера nxn, а потом прибавить нулевую матрицу размера nx1, если я правильно понял обозначения… У меня вопрос, а как предлагается складывать матрицы разных размерностей? И что подразумевается под «нулевой» матрицей и как прибавление «нулевой» матрицы должно изменить результат?

              Наконец, неплохо бы иметь хоть какое-то обоснование этих формул, кроме загадочного упомянутого в статье анализа «случайно сгенерированных матриц размером 5x5».
              +1
              Спасибо за статью. Тема интересная и злободневная. Не исключено, что вы, автор, действительно нашли решение, над которым человечество бьется не один десяток лет. Но когда я пытался вникнуть в описание вашего метода, кое-что сразу бросилось в глаза, а именно — стилистика.
              Ведь при положительном ответе, программисты смогут гораздо оптимизировать многие аспекты программы,

              Автор, не в обиду, но эта фраза достойна списка цитат великого боксера Кличко.
              Мне же, как программисту, не мыслим отрицательный ответ

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

              Слово «разных» здесь к чему относится? К тому, что графы удобнее рассматривать в виде матриц? Или к тому, что матричные представления могут быть разными? Или это просто лишнее слово в предложении?

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

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

              Ну и для придания вашей статье убедительности вам необходимо показать, что:
              1) рассматриваемая вами задача является NP-полной;
              2) ваше решение работает, причем за полиномиальное время, для любой конфигурации рассматриваемой задачи.

              Понятно, что проверить решение «традиционными» методами для достаточно больших задач невозможно, но есть приближенные методы, всякие там «simulated annealing» и т.д. Для экспериментальной проверки вашего решения вам достаточно будет показать, что оно лучше или, по крайней мере, не хуже решений, полученных приближенными методами.
                0
                Нет постановки задачи.
                Каждый абзац(за редким исключением) со слов «теперь решение» порождает вопрос: «Почему так». Только после этого можно как-то продолжать дискуссию, касательно NP-полноты и т.д. Прошу, переделайте более формально (примеры оставьте), добавьте комментарии и пояснения к действиям, переход к другим задачам — вот тогда будет интересно и возможно разобраться в таком труде за адекватное время.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое