Аргументация к Мысли2.

Проблема Кука. Мысли о равенстве.

Проблема Кука. Мысли о равенстве.

Мысль№1.

Один из первых вопросов, озвучиваемых некоторыми авторами статей о проблеме Кука, это может ли сложность проверки ответа быть равной или больше, чем сложность решения задачи. Этот вопрос не имеет строгого отношения к собственно проблеме Кука, но мне стало интересно получить на него ответ именно в такой формулировке. Проверка решения задачи — это тоже задача, но это две разные задачи. Исходными данными проверки решения являются результаты выполнения первоначально решаемой задачи, но у неё свои цели, отличные от целей исходной задачи. Условия задачи проверки ответа также зависят от условий и ограничений выполнения решения, и они строго индивидуальны для каждого типа задач. Некоторые задачи изначально, на стадии формулирования и постановки условия, исключают возможность существования проверки ответа, которая была бы проще чем решение. К таковым, например, относится задача Коммивояжера. Обусловлено это тем, что в ней требуется найти самый маленький (по заданному параметру) маршрут. То есть найденный маршрут должен быть меньше, чем все остальные. Значит, нужно просчитать каждый возможный (допустимый?) маршрут и сравнить их. Ответ на задачу Коммивояжера должен содержать, как минимум, числовое множество, состоящее из величин вычисленных маршрутов с отдельным указанием самого соответствующего, наименьшего. В случае если ответом будет являться указание только одного, самого маленького, маршрута, с указанием его величины или без такового, то проверяющему ответ необходимо выполнить всё решение для поиска других значений и сравнения их с предоставленным. Если при проверке произвести только сравнение предоставленных величин маршрутов, то это не будет являться проверкой правильности решения задачи Коммивояжера — это проверка правильности поиска минимального числа из из предоставленного множества. Для проверки правильности решения задачи Коммивояжера необходимо проверить правильность каждого этапа вычислений:
- построение маршрутов,

- определение их величин,

- сравнение полученных значений,

то есть выполнить решение полностью.

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

Теперь рассмотрим вариант, когда решение проще (меньше, быстрее), чем проверка ответа. Исходя из соображения минимизации затрат, в качестве проверки, равно как и в качестве собственно решения, имеет смысл использовать кратчайший достоверный способ. Если метод решения достаточно краток, то тратить больше сил на альтернативное решение может быть целесообразным только на стадии доказательства достоверности этого способа решения как такового. Во всех других случаях, при прочих равных условиях, нет необходимости пользоваться заведомо более трудоёмким путём решения или проверки. Опять-таки, не забываем, что проверка и решение — взаимосвязанные, но разные задачи с разными условиями, выполнение которых разнесено во времени. В качестве ответа для проверки служат всего два состояния: «да» или «нет». Что позволяет выполнять только достаточный минимум действий, а очередность выполнения — использовать полученные при решении результаты, в том числе и данные о сложности (продолжительности) выполненного решения. Поэтому, если решение оказалось меньше, чем примененный способ проверки, то значит не выполнено условие равенства возможностей решающего и проверяющего, они пользуются разными программными, аппаратными, методическими или иными средствами или разными базами данных. Следовательно, допущена ошибка при оптимизации затрат, и необходимо заменить способ проверки на более лаконичный, или, в крайнем случае, принять за проверку путь решения задачи.

Первый вариант развития событий мы имеем, когда в качестве решающего используют человека, а в качестве проверяющего — машину. Или другого человека. Данные софизмы весьма популярны на просторах интернета. В случае, когда «с обеих сторон баррикад», стоят машины, мы можем оценить равенство алгоритмических, логических и прочих процессов, а также баз данных, используемых машинами. В случаях с людьми всё несколько иначе. Человек может знать ответ на основании знаний, полученных ранее, и которыми не располагает оппонент, или просто угадать. Или же, например, человек может одним взглядом увидеть всех присутствующих и узнать искомого гражданина А. Машина этого не может. В подобных ситуациях устойчиво игнорируется то, что проблема Кука ставилась для вычислительных машин, а не для ситуации «человек-против-машины». Исходя из сказанного, приходим к следующему выводу: решение может быть больше или равно проверке; проверка может быть равна или меньше решения.

Мысль№2.

Также на стадии ознакомления с проблемой Кука я узнал, что существует ещё и задача факторизации (разложения заданного числа на простые множители). Которая, как и задача Коммивояжера, относится к классу NP-полных задач, то есть:

- не имеет полиномиального решения,

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

- полиномиальный алгоритм решения задачи позволит решить остальные NP-полные задачи.

В данном состоянии знания я пребывал довольно долго. Потом решил начать практические действия в этом направлении. Начал с того, что попробовал переписать 617-значное число для знакомства и определения, что же с ним делать. Это оказалось затруднительным. Попытался просто перемножить два 150-значных числа — снова оказался в тупике. И тут мне впервые показалось, что что-то, вероятно, не так. Как проверить истинность утверждения, если оно сформулировано для больших чисел, эффективно работать с которыми могут только те, кто утверждает? Ответов нашел два: проверить его в формульном выражении или написать калькулятор, позволяющий работать с большими числами. Второе получилось быстрее. В результате относительно непродолжительного знакомства с основами программирования и опытов со свободно доступными приложениями я написал калькулятор, работающий практически на любом компьютерном устройстве (стационарный компьютер, ноутбук, нетбук, планшет...) и выполняющий действия сложения, вычитания, умножения, позволяющий определять квадратный корень из чисел. Деление отдельно не прописывал по причине отсутствия практической, для меня, необходимости, но вполне успешно выполнял. Максимальный размер обрабатываемых чисел и скорость выдачи результата зависят от параметров вычислительной машины, на которой выполняется работа — я вполне комфортно работал с 650-значными числами на обычных компьютерах со средними характеристиками производительности, и они были готовы работать с 800-значными числами, не впадая в ступор. Числа одинаковой разрядности обрабатываются с одинаковой скоростью, увеличение или уменьшение порядка числа соответственно увеличивает или уменьшает время обработки на конкретную величину машинного (алгоритмического) времени. Разные числа одного порядка разрядности обрабатываются с одинаковой производительностью вне зависимости от конкретного значения числа.   Инструкция по написанию и применению данного калькулятора выложена в свободный доступ отдельно в блоге "калькулятор для работы с большими числами"  ( https://kalkulyatordlyabolshihchisel.blogspot.com. ), чтобы не увеличивать объём данной статьи. Ссылка на ресурс с доступным к скачиванию рабочим образцом будет размещена там же. Этот калькулятор позволил мне убедиться в следующем:

- нет никакой практической алгоритмической разницы в разложении на множители 2-х значного числа и, например, 300-значного;

- последовательный перебор вариантов множителей кажется трудным (псевдоэкспоненциальным) именно для малых (1-, 2-, 3-значных чисел) и перестаёт казаться таковым при работе с более (например, 10, 200-, и т.д.)-значными числами.

Последний факт был обнаружен практическим путём и подтвержден аналитической работой с формулами. Попытаюсь сжато изложить основные результаты.

Пусть есть число:

И=а*б (1)

где И — исследуемое, произвольное целое число;

а, б — целые множители, произведение которых равно И.

Число И соответствует следующим условиям:

- не равно нулю или единице;

- не чётное;

- не кратно 5 и 10.

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

х=И/у (2)

где х — искомый целый множитель;

у — переменная, в последовательном переборе возможных вариантов которой собственно и состоит процесс поиска множителей.

Данный блог отказывается показывать вёрдовский рисунок, поэтому попытають описать словами:

1 блок) И=И; у=3
2 блок) х=И/у

3 блок) проверка: если Х - целое, то переход к блоку 5), если нет - к блоку 4)

4 блок) у=у+1, возврат к блоку 2)
5 блок) а=у; б=х

 

На первый взгляд, максимальное количество повторений цикла в худшем случае i равно максимальному значению переменной у, которая находится в пределах от 1 (но на единицу делить смысла нет, на 2 — тоже, так как мы условились, что число И не чётное, значит первое значение равно 3) до И (если оно простое). То есть, принимаем возможное максимальное количество повторений цикла

i=у_мах=И (3)

При изменении И на какую-либо величину, или в несколько раз, или ещё как, максимальное количество повторений цикла в худшем случае i₁ будет всё так же равно максимальному значению переменной у₁, которая останется равной новому значению И₁. Здесь нет экспоненциальной зависимости продолжительности (сложности) решения от размера исходных данных — она линейная. Значит, задача разложения на множители не является NP-полной задачей — алгоритмически это простая задача P-класса. Весь подвох в трудности работы с большими числами.

На этом можно было бы и остановиться, тем более, что есть и другие, менее зависящие от величины И, методы поиска простых множителей чисел. Добавлю только, что и этот путь решения задачи факторизации, на самом деле, значительно проще, чем кажется. В формуле (1) множитель а всегда меньше или равен множителю б. Множитель а может быть равен множителю б только в случае, если число И является квадратом числа в (в=а=б), во всех остальных случаях один множитель меньше (пусть будет а), другой — больше (б). При этом, множитель а изменяется в пределах от 1 до (√И) (корень квадратный от И), множитель б изменяется от (√И) до И, и они обратно пропорциональны. Учитывая, что далеко не каждое число имеет целый, не дробный, квадратный корень, максимальное значение а равняется целой части значения (√И) без округления, а минимальное значение б равно ((целая часть значения (√И) без округления) плюс 1). Существенным здесь является то, что а_1мах=а_мах при И₁=(И+с) если на участке между числами И и И₁ нет такого И_кк, которое имело бы целый корень квадратный, то есть:

а_1мах=а_мах+м (4)

где м — количество чисел И_кк имеющих корень квадратный и находящихся между числами И и И₁; может быть равно нулю.

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

В самом оптимальном, для данной постановки вопроса, случае переменная i равняется не собственно максимальному значению переменной у, а количеству потенциальных переменных у, которое равно количеству простых чисел в диапазоне от 1 до (√И), и составляет примерно 12,3% от (√И) (это для диапазона от 1 до 10000, точнее для больших числовых диапазонов знает статистика). Также имеет смысл немного дополнить блок-схему:

- блок идентификации: является ли исследуемое число нулем, является ли число единицей, является ли последняя цифра числа чётной, является ли последняя цифра числа цифрой пять, является ли последняя цифра числа нулем;

- первое вычислительное действие: определение квадратного корня исследуемого числа;

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

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

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

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

Дополню. Тема разложения числа на множители, по сути, полностью и окончательно раскрыта в статье под названием "Как не искать множители. к Мысли2" в этом же блоге.

Мысль№3.

Поэтому я вернулся к рассмотрению полноправной представительницы класса NP-полных задач — к задаче Коммивояжера.

Взял карту, карандаш, линейку, нанёс несколько произвольных точек, подсчитал количество вариантов связей между точками, добавил ещё, опять подсчитал — впечатлило. Если кого-нибудь, из читающих данную статью, заинтересовало, почему в 11-м предложении Мысли№1 после слова «возможный» стоит «(допустимый?)», то это потому, что потом я попытался проложить маршруты и просчитать длины полученных путей. Не получилось. Я прошу прощения за риторический вопрос, но Вы карту видели? Любую, географическую. Не каждый возникший отрезок между точками на карте становится потенциально возможным путём движения Коммивояжера. Исходя из этого, у меня возникло условное разделение задачи Коммивояжера на практическую и теоретическую. Теоретическая, абстрактная, задача более полна и сложна, чем практическая, «приземленная». Но и в теоретической всё не так однозначно. Это логическая задача с элементами не только математики, но и геометрии. Если взять произвольное количество точек на плоскости (или в объёме), то не все возникшие связи будут иметь аналитический смысл. И обусловлено это взаимным расположением точек друг относительно друга. Количество несущественных связей возрастает так же экспоненциально, как и общее количество связей, поэтому игнорировать их нельзя. Полиномиальное решение задачи Коммивояжера возможно только с предварительным анализом исходных данных, в том числе с «геометрическим». Как я понимаю, практически воплотить в алгоритм действие, которое можно описать словами «взял и посмотрел», весьма затруднительно, но в настоящее время существуют и применяются методики решения задачи Коммивояжера, основанные на группировке части точек. В общем виде это похоже на эффект масштаба в компьютерных приложениях:

- разбиваем все точки на группы точек;

- производим расчет решения для точек внутри каждой группы;

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

- производим окончательный расчет решения.

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

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

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

Июль 2013г.