Математическая морфология.

Электронный математический и медико-биологический журнал. - Т. 9. -

Вып. 2. - 2010. - URL:

http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM

http://www.smolensk.ru/user/sgma/MMORPH/N-26-html/TITL-26.htm

http://www.smolensk.ru/user/sgma/MMORPH/N-26-html/cont.htm

УДК 519.1

ПОЛИНОМИАЛЬНОЕ РЕШЕНИЕ ТРУДНОРЕШАЕМЫХ ЗАДАЧ: P=NP

Ó2010 г. Пятлин Л. А.

(piatlin.doc)

Способ решения задачи Гамильтона с полиномиальными затратами седьмой степени путем определения всех негамильтоновых звеньев маршрутов и их удаления из описания всех маршрутов графа. Обоснование истинности алгоритма и его полиномиальности.

Ключевые слова: негамильтоново звено, гамильтоновы граф, маршрут, труднорешаемые, NP-полные задачи, P=NP.

1. Автор запатентовал, как изобретение и полезную модель, способ моделирования маршрутов и устройство для его осуществления на примере решения задачи Гамильтона, которые можно использовать для решения всех труднорешаемых – переборных – задач с полиномиальными затратами до седьмой степени. В известных технических решениях [1, 2, 3] временные или конструктивные затраты экспоненциальны – 2ⁿ. Их сравнение с запатентованными техническими решениями проиллюстрировано графиком (Рис. 1.).

Этот результат многолетней работы Пятлина Л. А. (1986 – 2010 годы) может быть реализован, путем создания специализированных устройств и программ для универсальной вычислительной техники, например, при решении любых труднорешаемых задач большого размера, в планировании, в прогнозировании, в моделировании, в фундаментальных и прикладных научных исследованиях, при создании искусственного интеллекта и тому подобном.

Всякое использование этих запатентованных изобретений возможно только на основе лицензионного соглашения с автором в соответствии с действующим законодательством. Сайт автора http://www.polinomill.lact.ru/ .

Абсолютное большинство математиков считает невозможным создание алгоритмов решения NP-полных задач, в частности задачи Гамильтона, с полиномиальными затратами, т.е. считает невозможным доказательство того факта, что P=NP.

Автор изобретения, по образованию философ, свои научные изыскания, с 1974 года, посвятил, в частности, раскрытию тайны работы нейронов и их сетей, с того момента, когда впервые увидел под микроскопом структуру нейрона коры головного мозга и понял принцип функционирования нейрона.

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

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

Таким образом, полученный результат возник на стыке философии, нейрофизиологии, морфологии ЦНС, психологии, электроники, кибернетики и математики, в виде части теории графов, относящейся к задаче Гамильтона.

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

Определения: граф G_n (Рис. 2.) – это точки – вершины (узлы), пронумерованные от 1 до n, например, А и В, соединенные линиями – ветвями (дугами, ребрами) в количестведо n², например, соответственно, АВ и ВА. Количество вершин n – размер задачи. В описании изобретения введено понятие модели маршрутов – матрицы маршрутов Мграфа G_n.

Модели маршрутов – матрицы маршрутов М,М(1) и т.д. графа G_n (Рис. 3., 4. и т.д.) состоят из звеньев маршрутов «k» (далее – звеньев):P-ых звеньев-вершин (А.Р.)- «q» (при длине маршрутов n их количество равно (n+1)n), каждое из которых соответствует определенному Р-му вхождению данной вершины A во все возможные маршруты графа G_n, описываемые матрицей маршрутов M в количестве до n!, а так же P-ых звеньев-ветвей (A.P.B.) - «j» в количестве не более n³, каждое из которых связывает данное Р-е звено-вершину (А.Р.), в соответствии с топологией маршрутов, с (P+1)-ым звеном-вершиной (В.P+1.) этой матрицы маршрутов M.

[Матрицу маршрутов M желающие могут считать ориентированным графом размера (n+1)n (количество звенье-вершин - вершин этого орграфа), матрицей смежности вершин Р-ых пунктов маршрутов (А.Р.) с вершинами (Р+1)-ых пунктов маршрутов (В.P+1.) через ветви маршрутов(A.P.B.), но это не будет использоваться автором далее].

Часть маршрута, состоящая из нескольких (от 1 до n) простых, смежных по отношению друг к другу, звеньев, например, из «z», «k» и других, и рассматриваемая как целое, называется сложным звеном «zk».

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

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

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

Звено, не входящее ни в один гамильтонов цикл, называется негамильтоновым звеном.

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

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

3. Для обеспечения и описания работы алгоритма примем новое определение негамильтонова звена, которое позволит выявить и удалить, все негамильтоновы звенья, в процессе анализа - в процессе обработки алгоритмом, по очереди, всех матриц маршрутов М(b) и всех их звеньев, с точки зрения их гамильтоновости.

Определение негамильтонова звена (авторское). Звено маршрута (Рис. 3.) «k» - (С.2.) или (С.2.В.) матрицы маршрутов М(b) графа G_n (bравно от 1 до n), из которой удалены все ранее выявленные алгоритмом в матрице маршрутов М(b-1) негамильтоновы звенья, называется негамильтоновым звеном в том случае, если все маршруты длины n+1 и менее, содержащие данное звено «k», или звенья «k» и «z», или сложное звено «kz» и не проходящие более связанных с данным звеном «k» вершин (соответственно, вершин С или С и В) других пунктов маршрутов (соответственно, не 2 для С и не 3 для В), не включают в себя, по крайней мере, одну, общую для всех этих маршрутов, вершину, например, «v».

4. Сущность изобретения Пятлина Л.А. заключается в выявлении и уничтожении всех негамильтоновых звеньев, на основании их авторского определения, в матрицах маршрутов М(b) графа G_n, при моделировании маршрутов во встречных направлениях (просматривая маршруты и данное ориентированное звено-ветвь «j» - (А.Р.В.) - как в прямом, так и в обратном направлениях) и сохраняя только те звенья «k», которые просмотрены во встречных направлениях, что позволит сохранить только гамильтоновы звенья и описать все гамильтоновы маршруты в итоговой матрице IM графа G_n, решив, тем самым, задачу Гамильтона с полиномиальными затратами.

Способ решения задачи Гамильтона.

1. Алгоритм начинается с просмотра во встречных направлениях на матрице маршрутов M графа G_n, начиная с выбранных вершин, например, 1, всех маршрутов заданной длины n+1, уничтожая те звенья, которые не могут быть просмотрены во встречных направлениях (Рис. 4., 5.), создавая матрицу М(1).

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

Если, по крайней мере, одна вершина не включена ни в один просмотренный во встречных направлениях на матрице М(1) маршрут, то граф G_n признается негамильтоновым – решение задачи завершено. Сложность операции равна О(n³) - затраты составляют порядка третьей степени n.

В этом случае, алгоритм определяет, что все звенья матрицы М(1) негамильтоновы и уничтожает их.

2. В противном случае, просматривают во встречных направлениях все маршруты на матрице М(1) графа G_n, начиная с выбранных вершин, всех маршрутов заданной длины n+1, уничтожая те звенья, которые не могут быть просмотрены во встречных направлениях (Рис. 4., 5.). При этом выявляют и удаляют негамильтоновы звенья, в результате просмотра во встречных направлениях на матрицах M(1)(k), по отношению к каждому звену «k» отдельности, всех маршрутов, содержащих данные звенья «k» и не проходящих более связанных с ними вершин, уничтожая те звенья, которые не могут быть просмотрены во встречных направлениях (Рис. 6., 7.). Связанные с данным звеном «k» - (3.3.) или (3.3.4.) вершины, например, 3 или 3 и 4, других пунктов маршрутов – звенья-вершины, например, соответственно, 3.2. (Рис. 6.) или3.2. и 4.2. (Рис. 7.) блокируются для входа-выхода звеньев-ветвей маршрутов.

Если, по крайней мере, одна вершина не включена ни в один,просмотренный во встречных направлениях на матрице маршрутов M(1)(k) маршрут, то данное звено «k» считается, в соответствии с определением, негамильтоновым и уничтожается в матрице М(1). Сложность – О(n⁶).

3. Если, по крайней мере, одна вершина не включена ни в один просмотренный во встречных направлениях на матрице М(1) маршрут, то граф G_n признается негамильтоновым и решение задачи завершается: все звенья матрицы М(1) уничтожаются как негамильтоновы.

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

Для завершения решения задачи, осуществляют проверку маршрутов матрицы М(1) на гамильтоновость, описание которой приведено ниже в виде специального подалгоритма. Сложность – О(n⁶).

В результате проверки, граф G_n признается или гамильтоновым, а матрица М(1), соответственно, итоговой матрицей всех гамильтоновых циклов IM, или негамильтоновым и решение задачи завершается. Во втором случае, уничтожаются все звенья матрицы М(1) как негамильтоновы.

5. В том случае, если в матрице М(1) было уничтожено, по пункту 2. алгоритма, хотя бы одно звено, то повторяют описанный просмотр маршрутов по пункту 2. уже на матрице M(2), в которой отсутствуют все ранее выявленные в матрице M(1) негамильтоновы звенья и так далее в матрицах М(b), при b равным от 1 до n.

Последовательный просмотр по пункту 2. матриц маршрутов М(b) графа G_n повторяют до того момента, когда прекратится выявление и уничтожение новых негамильтоновых звеньев в матрице М(i) – в итоговой матрице IM. Поскольку, при каждом повторении уничтожают те звенья, которые входят в неустранимые циклы длины от 1 до n, то количество таких повторений может быть не более n. Сложность – до О(n⁷).

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

В противном случае, граф G_n признается гамильтоновым и матрица IM становится итоговой матрицей всех гамильтоновых циклов.

Решение задачи завершено.

Общая сложность алгоритма Пятлина Л.А. при решении задачи Гамильтона равна от третьей до седьмой степени: О(n³)+О(n⁶)+О(n⁶)+О(n⁷)=О(n⁷).

В пункте 4 способа решения задачи Гамильтона была выявлена необходимость проверки матрицы М(1) и, соответственно, графа G_n на гамильтоновость. Такую проверку осуществляют следующим образом.

5. Подалгоритм проверки матрицы маршрутов М(1) на гамильтоновость.

1. Создают возможность результативного применения авторского определения негамильтонова звена, в соответствии с приведенной далее теоремой 2., тем, что матрицу М(1) графа G_n заменяют смешанной матрицей М(1) графаG_ni, путем введения в граф G_n, по крайней мере, одного дополнительного гамильтонова цикла, превращая его в граф G_ni.

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

3. Если в матрице маршрутов M(1) графа G_ni не было удалено ни одного звена, то граф G_n признается гамильтоновым, а матрица M(1)графа G_nстановится итоговой матрицей всех гамильтоновых циклов IMграфа G_n.

4. Если в матрице маршрутов M(1) графа G_ni было унитожено, по крайней мере, одно звено маршрутов, граф G_nпризнается негамильтоновым и все его звенья уничтожаются.Завершение решения задачи. Сложность – О(n⁶).

Пояснение: если граф G_n гамильтонов, то введение дополнительных гамильтоновых циклов сохранит гамильтоновость графа G_ni и в матрице М(1) графаG_ni не будет выявлено и уничтожено ни одного негамильтонова звена. В противном случае, матрица М(1) графаG_ni станет смешанной, что позволит алгоритму выявить и уничтожить в ней, по крайней мере, одно негамильтоново звенои, тем самым, доказать негамильтоновостьграфа G_n.

6. Обоснование истинности авторского определения негамильтонова звена.

Теорема 1: множество всех выявленных, в процессе работы алгоритма Пятлина Л.А., негамильтоновых звеньев всех матриц маршрутов М(b) графа G_n (где b равно от единицы до n) в процессе работы алгоритма, является множеством всех негамильтоновых звеньев.

Доказательство: 1. Если выявленное, в процессе работы алгоритма, например, по пункту 1., негамильтоново звено «k» содержится только в маршрутах длины n и менее матрицы М(b) графа G_n, то оно негамильтоново, поскольку все эти маршруты не удовлетворяют требованию длины – (n+1) – гамильтоновых циклов.

2. Если выявленное алгоритмом негамильтоново звено маршрутов «k» матрицы М(b) графа G_n, из которой удалены все ранее выявленные негамильтоновы звенья, входит во все маршруты длины (n+1), содержащие данное звено «k», или звенья «k» и «z», или сложное звено «kz» и не проходящие более связанных со звеном «k» вершин, которые не включают в себя, по крайней мере, одну, общую для всех этих маршрутов, вершину, например, «v», то оно негамильтоново, поскольку все эти маршруты не проходят всех вершин графа, как того требует определение гамильтонова цикла.

3. Если при построении матрицы М(b) алгоритмом было выявлено и уничтожено, по крайней мере, одно негамильтоново звено «i», то при построении матрицы М(b+1), если еще существуют негамильтоновы звенья, по пункту 2. алгоритма, будет выявлено и уничтожено, по крайней мере, одно негамильтоново звено «j» и так до тех пор, пока не останется ни одного негамильтонова звена, которое можно было бы выявить и удалить из матрицы М(b+1).

Доказательство от противного 1: допустим, что в матрице М(b+1), при наличии негамильтоновых звеньев, в процессе анализа каждого звена, с точки зрения их гамильтоновости, в процессе работы алгоритма по пунктам 5. 6., не будет выявлено и уничтожено ни одно негамильтоново звено. Это приводит к противоречию: на основании принятого авторского определения негамильтонова звена, по пункту 2. способа решения задачи Гамильтона, в матрице М(b+1) неизбежно выявляется новое негамильтоново звено «j» и удаляется из нее, поскольку негамильтоново звено «i», выявленное в матрице М(b), было звеном множества маршрутов с неустранимыми циклами длины не более n, содержащих звено «j», которые не проходят, во встречных направлениях, по крайней мере, одну, общую для всех маршрутов, вершину «v», как и при выявлении негамильтонова звена «i» матрицы М(b). То есть звено «j» не входит ни в один гамильтонов цикл и является негамильтоновым, что и требовалось доказать.

Другими словами, доказательство от противного 2: допустим, что в матрице М(b+1), при наличии негамильтоновых звеньев, в процессе работы алгоритма не будет определено и уничтожено ни одно негамильтоново звено. Это приводит к противоречию: негамильтоново звено «i», выявленное в матрице М(b), было звеном множества неустранимых циклов длины не более n, которые не проходят, по крайней мере, одну, общую для всех циклов, вершину«v». Это отсутствие, по крайней мере, одной, общей для всех маршрутов, вершины «v» определяется при просмотре во встречных направлениях всех этих маршрутов, содержащих звено «j», смежное с выявленным в матрице М(b) негамильтоновым звеном «i», и не проходящих более связанных с этим звеном «j» вершин, с определением и уничтожением тех звеньев, которые не могут быть просмотрены во встречных направлениях. Таким образом, в результате этого выполнения пункта 2. алгоритма неизбежно выявляется новое негамильтоново звено «j» и удаляется из матрицы М(b+1), что и требовалось доказать.

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

Это позволяет выявить и уничтожить все негамильтоновы звенья, как всех маршрутов длины n и менее, так и всех маршрутов длины n+1, не проходящих все вершины графа G_n в точности по одному разу, матриц маршрутов М(b) графа G_n. То есть, в процессе выявления и уничтожения алгоритмом всех негамильтоновых звеньев, уничтожаются абсолютно все негамильтоновы звенья, на основании противоречия с принятым авторским определением гамильтонова звена.

Следствие 2: множество всех выявленных алгоритмом негамильтоновых звеньев всех матриц М(b) графа G_n, в процессе работы алгоритма, является множеством всех негамильтоновых звеньев, что и требовалось доказать.

Другими словами, по мере выявления и удаления во всех матрицах М(b) всех негамильтоновых звеньев, установлен факт абсолютного тождества множества всех выявленных негамильтоновых и множества всех негамильтоновых звеньев. Таким образом, именно авторское определение позволило алгоритму описать все гамильтоновы циклы, благодаря уничтожению всех негамильтоновых звеньев.

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

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

Введем три типа матриц маршрутов М.

1. Матрица исключительно гамильтоновых циклов.

Из нее нельзя удалить ни одного звена, поскольку в ней отсутствуют негамильтоновы звенья по определению гамильтоновых маршрутов.

2. Матрица исключительно негамильтоновых маршрутов.

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

3. Матрица смешанных маршрутов – смешанная матрица – возникает в том случае, если ее звенья могут входить как в гамильтоновы, так и в негамильтоновы маршруты.

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

Теорема2: в каждой смешанной матрице М(b) графа Gn, в процессе работы алгоритма Пятлина Л.А. обязательно осуществляется выявление, по крайней мере, одного негамильтонова звена.

Доказательство от противного: допустим, что в смешанной матрице М(b), в процессе ее анализа, с точки зрения гамильтоновости, по пункту 2. алгоритма, невозможно выявление ни одного негамильтонова звена. Это противоречит тому, что в ней найдется, по крайней мере, одно звено «z» негамильтонова маршрута, смежное с каким-либо звеном «j» гамильтонова маршрута, создающее неустранимый цикл длины не более n, несодержащий вершину «v» и уничтожающий все возможные гамильтоновы циклы вхождением в них негамильтонова звена «z». Другими словами, в матрице М(b) все маршруты длины n+1, содержащие сложное звено «zj» и не проходящие более связанных с данным звеном «z» вершин, не включают в себя, по крайней мере, одну, общую для всех этих маршрутов, вершину «v». Итак, на основании определения негамильтонова звена, в каждой смешанной матрице М(b) обязательно осуществляется выявление, по крайней мере, одного негамильтонова звена «z», что и требовалось доказать.

Следствие: поскольку, как доказано, только в смешанных матрицах возможно обязательное выявление, по крайней мере, одного негамильтонова звена по пункту 2. алгоритма и, если в матрице М(b) не выявлено ни одного негамильтонова звена, то это значит, что все маршруты длины n+1 матрицы М(b) графа G_n или исключительно гамильтоновы, или исключительно негамильтоновы.

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

8. Истинностьизобретения – алгоритма Пятлина Л.А. доказывается в следующей теореме 3.

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

Теорема 3: каждое звено итоговой матрицы маршрутов IМ графа G_n, построенной путем удаления из матрицы маршрутов М графа G_n всех негамильтоновых звеньев по описанному способу Пятлина Л.А. с полиномиальными затратами седьмой степени, является звеном, по крайней мере, одного гамильтонова цикла. Другими словами, задача Гамильтона на машине Тьюринга решается с полиномиальными затратами: P=NP.

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

Настоящее доказательство может быть проиллюстрировано доказательствами от противного. Например, допустим, что в матрице маршрутовIМ графа G_n существует, по крайней мере, одно звено «k», через которое не может пройти ни один гамильтонов цикл. То есть, каждый из возможных маршрутов матрицы IМ графа G_n длины n+1, содержащий данное звено «k», обязательно проходит, по крайней мере, дважды, хотя бы одну, вершину, например, вершину «v».

Это допущение приводит к противоречию, поскольку, в этом случае, при выполнении пункта 2. способа решения задачи Гамильтона по отношению к звену «k», это звено «k» было бы уничтожено как негамильтоново и не могло бы войти в матрицу IМ при ее построении по условиям теоремы.

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

Следовательно, невозможно обязательное вхождение указанной вершины «v» в маршруты длины n+1 матрицы IM графа G_nдва и более раз.

Следовательно, существует, по крайней мере, один, содержащий данное гамильтоново звено «k», маршрут длины n+1 и построенный в соответствии с требованиями гамильтоновости, который включает в себя все вершины графа G_nв точности по одному разу, то есть гамильтонов цикл, что и требовалось доказать.

Все операции этого способа решения труднорешаемых задач выполняются последовательно, то есть все основанные на нем программы успешно осуществляются в машине Тьюринга. Следовательно, задача Гамильтона в машине Тьюринга решается с полиномиальными затратами седьмой степени, что и требовалось доказать: P=NP.

9. В точности по описанному выше алгоритму, Клещев Олег Андреевич создал, работоспособную программу решения задачи Гамильтона при затратах шестой степени с выявлением и удалением всех негамильтоновых звеньев-вершин, разумеется, без алгоритма чтения гамильтоновых циклов. Этого достаточно для экспериментального подтверждения успешной работы алгоритма при решении задачи Гамильтона (Рис. 8.).

Ознакомиться с программой и получить ее код для тестирования желающие могут на сайте автора http://www.polinomill.lact.ru/

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

решений всего многочисленного класса труднорешаемых задач [см. 3].

Рис. 8. Пример результата работы программы Клещева О.А.

Доказано, что труднорешаемая, NP–полная задача Гамильтона решается описанным способом Пятлина Л.А. с полиномиальными затратами до седьмой степени в машине Тьюринга.

Следовательно, P=NP в машине Тьюринга для задачи Гамильтона.

11. Приложение 1. Алгоритм чтения гамильтоновых маршрутов на итоговой матрице гамильтоновых циклов IМ.

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

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

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

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

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

В просмотренных во встречных направлениях маршрутах матрицы IМ выбирают по пункту 1 звено-вершину следующего (Р+1)-го или, соответственно, Р-го пункта маршрута, по отношению ней осуществляют операции пункта 3. и так далее до конечного пункта.

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

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

6. Алгоритм завершают, когда будет установлен, по крайней мере, один гамильтонов цикл.

Разумеется, если поставить задачу прочитать каждый маршрут в отдельности, то затраты будут экспоненциальны – 2ⁿ, поскольку количество маршрутов составляет n!.

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

12. Приложение 2. Дополнительно, для обеспечения возможности применения изобретения в любых труднорешаемых задачах, в матрице М(b) (На Рис. 7 и 9 изображен случай, когда b равно 1) на каждой матрице М(1)(k) по пункту 2 способа решения задачи Гамильтона просматривают во встречных направлениях все маршруты, определяя и удаляя негамильтоновы звенья в результате просмотра во встречных направлениях на матрицах М(1)(k)(h), по отношению к каждому звену в отдельности, всех маршрутов, содержащих данные звенья «h» и не проходящих более связанных с ними вершин, уничтожая те звенья, которые не могут быть просмотрены во встречных направлениях. Здесь очевидно построение алгоритма по принципу «матрешки», когда в целом, в качестве его части, используется подобие этого целого, в этой части, в свою очередь, опять используется подобие этого целого и так далее…

Если, по крайней мере, одна вершина не включена ни в один просмотренный во встречных направлениях на матрице М(1)(k)(h) маршрут, то данное звено «h» считается, в соответствии с определением, негамильтоновым и уничтожается в матрице М(1)(k).

При этом дополнительном моделировании, сложность алгоритмов решения всех труднорешаемых задач, создаваемых на основе освещенного изобретения, может увеличиваться в n³раз, соответственно, до девятой – десятой степени: О(n⁹) – О(n¹⁰).

Следовательно, P=NP в машине Тьюринга для всех труднорешаемых задач, что и требовалось доказать.

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

Литература

1. В. Липский. Комбинаторика для программистов. – М., Мир, 1988 г.

2. К. Берж. Теория графов и ее применения. – М., Иностранная литература, 1962 г.

3. Гэри Майкл Р. и Джонсон Дэвид С. Вычислительные машины и труднорешаемые задачи. М., Мир. 1982 г.

Polynomial solving of the hard-to-solve problems by Piatlin L. A.: P = NP

Piatlin L. A.

How to solve the Hamilton problem with polynomial cost of the seventh degree, by identifying all non-Hamiltonian links in the routes and their removal from the description of all routes of the graph. Rationale for the truth of the algorithm and its polynomial: P = NP.

Key words: Non-Hamilton link, Hamilton graph, route, hard-to-solve, NP-complete problems, P=NP.

Рисунки для статьи были созданы в AutoCAD 2009 и экспортированы в формат wmf. Рис. 8 был отсканирован и доработан в графическом редакторе GIMP. Рисунки были вставлены в текст статьи, созданный в текстовом редакторе Word 2003.

Екатеринбург.

Поступила в редакцию 11.05.2010.