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


Примеры использования компьютерных программ для распутывания узлов



Скачать 184.19 Kb.
страница6/8
Дата05.11.2018
Размер184.19 Kb.
Название файлаРеф.Проблема распутывания узла.docx
ТипРеферат
1   2   3   4   5   6   7   8
5. Примеры использования компьютерных программ для распутывания узлов

Плоские диаграммы узлов двадцатых годах прошлого столетия начинал свои обстоятельные исследования немецкий математик Курт Рейдемейстер, будущий автор знаменитой «Knottentheorie», первой монографии, посвященной узлам. Как классифицировать узлы? Проблема систематизации всевозможных положений кривой в пространстве представляется чрезвычайно трудной [3].



Аналитический подход (при котором узлы задаются уравнениями) ничего не дает; комбинаторный подход (при котором мы задаем узел как замкнутую ломаную линию, перечисляя последовательно координаты вершин) также безрезультатен. В этих двух случаях данные, задающие узел, не позволяют ни видеть его, ни манипулировать им. На практике, чтобы увидеть узел, его рисуют, т. е. проектируют на удобно выбранную плоскость, получая так называемую диаграмму узла. Когда манипулируют бечевкой, задающей положение узла в пространстве, его диаграмма претерпевает непрерывные изменения. Они позволяют отслеживать на плоскости эволюцию положений узла в пространстве. А можно ли обратить этот процесс? Можно ли осуществлять непрерывные модификации проекции таким образом, чтобы в результате получить все возможные положения бечевки в пространстве? Вот вопрос, который ставит Рейдемейстер [3].

Попробуем составить такой алгоритм, используя достижения Рейдемейстера.

Берем первый узел и сравниваем его со вторым. Если количество перекрестков и их взаимное расположение одинаковы, то узлы эквивалентны и мы достигли цели. В противном случае применяем (наугад) какое-нибудь преобразование Рейдемейстера к первому узлу — и сравниваем результат со вторым узлом. Если они совпадают, то эквивалентность узлов вновь установлена. В противном случае нужно взять из памяти первый, исходный, узел и применить к нему другое преобразование Рейдемейстера, затем опять сравнить со вторым узлом и т. д. Если все преобразования, которые можно применить к первому узлу, не дают результата, нужно вернуться к модифицированному первому узлу, применить к нему еще одно преобразование, сравнить и т. д. Если два узла эквивалентны, то рано или поздно получится последовательность преобразований Рейдемейстера, переводящая первый узел во второй.

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

В дальнейшем придумывание плохо распутываемых тривиальных узлов стало важной частью исследований алгоритмов распутывания. Особенно варварский пример узла такого типа принадлежит немецкому математику Вольфгангу Хакену. Это он разрешил проблему развязывания узлов (Haken, 1961), но его алгоритм (слишком сложный для реализации на компьютере) основывается на идеях совсем другого порядка [3].

Описанный алгоритм с точки зрения теории не будет настоящим алгоритмом развязывания, если не будет доказано, что процесс полного перебора операций Рейдемейстера для развязывания обязательно приводит к цели за ограниченное число шагов. Именно это недавно доказали Дж. Хасс (Joel Hass) и Дж. Лагариас (Jerey Lagarias). Но увы, оценка числа шагов, полученная авторами, астрономическая, и нет надежд реализовать соответствующий алгоритм на компьютере [3].

Есть и другие подходы к этой задаче, позволяющие компьютеру (достаточно мощному) распутывать узлы, с которыми не удается справиться «вручную». В частности, Иван Дынников придумал красивый способ развязывания: его компьютер справляется с гордиевым узлом Хакена за несколько микросекунд [1].

Если же действовать вручную, нам для развязывания гордиева узла Хакена остается лишь «алгоритм» Александра Македонского — разрубить этот узел!



Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8


База данных защищена авторским правом ©rppna.ru 2017
обратиться к администрации

    Главная страница