Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 59
«Папа, а с кем ты сейчас разговаривал?»
Жму руку тому, кто это понимает.
Жму руку тому, кто это понимает.
del
Да ладно. Все ж понятно:
Паун ввел ввел свою алгоритмическую модель и описал, как в ней решаются классические задачи.
Да и к тому же эта алгоритмическая модель не вырожденная и не искусственная, а очень даже естественная и простая для понимания. Да еще и автор ее хорошо и популярно ее описал.
Ну для людей, которые не знакомы с базовыми знаниями дискретной математики или теории сложности это возможно покажется сложным, но как подсказывает мой опыт — сложным оказывается только то, во что не хочешь вникать, а стоит разобраться — все становится ясным как день.
Паун ввел ввел свою алгоритмическую модель и описал, как в ней решаются классические задачи.
Да и к тому же эта алгоритмическая модель не вырожденная и не искусственная, а очень даже естественная и простая для понимания. Да еще и автор ее хорошо и популярно ее описал.
Ну для людей, которые не знакомы с базовыми знаниями дискретной математики или теории сложности это возможно покажется сложным, но как подсказывает мой опыт — сложным оказывается только то, во что не хочешь вникать, а стоит разобраться — все становится ясным как день.
Заголовок сломал мой мозг. Хабр еще торт
ппц :(
Спасибо, очень интересно. Похоже на эдакую смесь классического метода ветвей и границ со спуском по дереву и генетических алгоритмов.
Отдаленно напоминает lambda calculus, тоже по-марсиански, тоже все на подстановках.
Как дерево мембраны в процессе вычислений выглядит не посмотреть?
Как дерево мембраны в процессе вычислений выглядит не посмотреть?
спасибо, ничего не понял
Стоп. А Разве тогда задача не является не-NP-полной? :)
Почему-то создалось ощущение, что речь идёт о фактически цепях Маркова.
Вероятно, на биологических клетках это не так, но оцифровка — таки они.
Вероятно, на биологических клетках это не так, но оцифровка — таки они.
Нет. Приведенный алгоритм (как и любой другой впрочем) решает задачу за полиномиальное время только на «удачных» для алгоритма конфигурациях. При этом если мы формализуем критерии этой конфигурации и добавим в условие задачи — она станет разрешимой за полиномиальное время. Просто зачастую при решении NP'шных задач мы реально не нуждаемся в решении для произвольных входных данных, а вот в зависимости от специфики нашых входных данных подобные алгоритмы и разрабатываются.
Мне кажется (более того, я уверен), что приведенный алгоритм все-таки решает задачу за полиномиальное время всегда! Правда, используя для этого слишком много пространства…
Обращения к памяти не мгновенные. Следовательно, если мы используем n байт памяти, а n — экспоненциально зависит от размерности входных данных, то суммарное время доступа к памяти тоже будет экспоненциально зависеть от размерности входных данных.
А что Вы скажете о колонии бактерий, размер которой увеличивается по экспоненте? Просто они делают это (делятся) одновременно, не используя никаких общих ресурсов (память, энергия и т.д.), по крайней мере на начальном этапе роста… :)
А тогда у них экспоненциально увеличивается число вычислителей, т.к. каждая бактерия — независимый вычислитель. В итоге вычислительное время все равно требуется экспоненциальное.
ОК, время от получения условий задачи до его решения — полиномиально, а общее время, затраченное на решение (например, в мембрано-часах) — экспоненциально… :)
Согласно современной физике, для нашего трехмерного пространства — при экспоненциальном увеличении числа необходимой материи — экспоненциально увеличивается расстояние до нее (в самом лучшем случае, где все пространство заполнено материей — расстояние до ближайшей материи определяется пропорционально корню третьей степени от уже использованной материи), а т.к. в данный момент не открыто возможности перемещаться или передавать информацию быстрее света — то получаем конечную скорость и экспоненциально определяемое расстояние. А следовательно и в реальном времени задача эмеет экспоненциальную сложность по времени. Это относится конечно к существующей доказанной физической теории, если ее дополнят/опровергнут — возможно я окажусь неправ, но все же алгоритм мы рассматриваем здесь и сейчас.
Уговорили! :) Кстати, интересно, а что, если пространство, в котором мы собираемся реализовать предложенный алгоритм, будет бесконечномерным? :)
Если оно все будет заполнено материей, имеет постоянную кривизну, изотропно, лоренц-инвариантно и прочая канитель — то на каждом шаге достаточно будет сделать движение вдоль произвольного направления в пространстве, чтобы найти новую материю, это математически, физически — наличие такого пространства очень сомнительно.
Хотя тут я не могу гарантировать, что алгоритм выполнится за полиномиальное время, наверняка есть еще какие-то хитрые аспекты, вносящие экспоненту.
Хотя тут я не могу гарантировать, что алгоритм выполнится за полиномиальное время, наверняка есть еще какие-то хитрые аспекты, вносящие экспоненту.
Является-является! :) Так как NP-полнота задача определяется не по времени ее решения, а скорее, наоборот: если задача NP-полная, то ее решение на любом последовательном вычислителе потребует экспоненциального времени.
Неправда, еще никто не доказал что P!=NP.
А что, есть шанс? :)
Ну, тут статей примерно 50/50 :)
Поставил плюс за название.
Забавная модель, интересный алгоритм.
И что, на реальном биологическом «железе» с этим экспериментировали? Можно где-то результаты увидеть?
И что, на реальном биологическом «железе» с этим экспериментировали? Можно где-то результаты увидеть?
Да, как раз с биологического «железа» все и началось, Адлеман (Adleman, кстати, тот самый, чья буковка A стоит в аббревиатуре RSA) в начале 1990-х собственоручно провел опыт по решению задачи HPP с помощью ДНК-молекул для графа с 6 вершинами. Потратив на это несколько дней. :) Ссылка в начале топика есть. Если публике будет интересно, то я мог бы про это написать…
«Чувак я ни**я не понял, но ты заговорил со мной и достучался до моего сердца» (с) Джей и Молчаливый Боб
Ох уж эти громкие названия :)
Конечно, алгоритм не полиномиальный. Вы не подменяли временную сложность пространственной. Корректней сказать вы разложили ее по разным вычислительным устройствам. То же самое, что использовать машину тьюринга с очень большим количесвом лент и считывающих гловок. Но сложность алгоритма от этого не меняется.
В остальном, интересно, спасибо.
Конечно, алгоритм не полиномиальный. Вы не подменяли временную сложность пространственной. Корректней сказать вы разложили ее по разным вычислительным устройствам. То же самое, что использовать машину тьюринга с очень большим количесвом лент и считывающих гловок. Но сложность алгоритма от этого не меняется.
В остальном, интересно, спасибо.
Ну, я же честно сказал, что полиномиальным является только время! :) Кстати, я совсем не уверен, что какая-нибудь модификация МТ (со сколь угодно большим числом головок) сможет решить данную задачу за полиномиальное время, по крайней мере, если начальные данные записаны только на одной ее ленте…
Я к тому, что само понятие сложности алгоритмов имеет смысл только если мы рассматриваем машину тьюринга (или подобное вычисл.устройство). По этому сложность алгоритма по времени, строго говоря, не полиномиальна.
Это не совсем так. Сложность алгоритма действительно обычно меряется на машине Тьюринга, просто потому что эта модель наиболее адекватно (и в то же время просто) описывает устройство современных компьютеров.
Сложность можно и по другим моделям мереть. И в рамках указанной модели сложность действительно не экспоненциальная получается. Другое дело, что если мембраны эмулировать на машине Тьюринга (а другого пути у нас пока нет), то так красиво уже не получится.
Сложность можно и по другим моделям мереть. И в рамках указанной модели сложность действительно не экспоненциальная получается. Другое дело, что если мембраны эмулировать на машине Тьюринга (а другого пути у нас пока нет), то так красиво уже не получится.
Проблема этого алгоритма в том, что он в процессе работы создает экспоненциальное количество мембран, и например при n=1000 для его реализации не хватит всего вещества Вселенной. Кроме того, совершенно непонятно причем здесь мембранная модель, абсолютно то же самое можно реализовать и на параллельном компьютере с достаточным (экспоненциальным) количеством процессоров.
И кстати совсем не обязательно использовать вероятностный алгоритм, можно сделать и полный перебор, чтобы каждая мембрана проверяла свой путь, так временная сложность будет вообще линейной
Если не использовать вероятностный алгоритм, то придется усложнять модель, например введением приоритета операций (правил). А линейного времени (для произвольных графов) мембранному коммьюнити при решении этой задачи пока не удалось достичь, и есть подозрение, что и не удастся. Но, кто знает, может у Вас получится!
Мне кажется, это очень тонкий троллинг. :)
Я не понял двух вещей:
1) Где здесь показано, что время выполнения алгоритма действительно является полиномиальной функцией от размера задачи?
2) В чем причина «блaгоговейного страха» народа перед заголовком? У нас тут клуб выпускников филфака?
1) Где здесь показано, что время выполнения алгоритма действительно является полиномиальной функцией от размера задачи?
2) В чем причина «блaгоговейного страха» народа перед заголовком? У нас тут клуб выпускников филфака?
Без конкертной аппартной реализации это простое бла-бла-бла. Если реализовывать такие алгоритмы на классических ЭВМ, то временная сложность алгоритма просто заменяется на пространственную.
del
Конкретно для поиска гамильтонова пути это далеко не самый лучший алгоритм. Кстати не знал что он мембранным называется, хотя уже использовал, спасибо что просветили )
Мембранный он просто потому, что реализован в рамках мембраной модели, а так (почти) обычный алгоритм полного перебора. Был бы рад (без подколок) услышать от Вас описание лучшего алгоритма!
В практических целях в большинстве случаев разумнее использовать модифицированные алгоритмы поиска в глубину. Кто-то делает поиск с возвратом, кто-то поиск от разных вершин. Я предпочитаю первичное разбиение графа на сегменты, так чтобы каждый сегмент удовлетворял правилу Дирака разумеется и после нескольких циклов дробления и составления участков пути поиском в глубину снова объединяю. Я таким образом в университете решал эту задачу, можно было бы найти код, но возможно не я один так делал, с терминологией у меня к сожалению несколько печально, так что может я также не знаю название этого алгоритма )
> Кстати, мембранные системы с приоритетом правил как раз и являются алгоритмически универсальными моделями, совместимыми с машиной Тьюринга
Насколько мне помнится, и без приоритетов тоже эквивалентны универсальной машине Тьюринга. Правда я не уверен, что там не нужно какие-то другие типы правил вводить, кроме описанных вами. По крайней мере, близкая по духу идея химических абстрактных машин (в которой нет приоритетов) так точно эквивалентна.
Почему бы не перебрать все варианты, т.е. не делать алгоритм вероятностным? Алгоритм останется полиномиальным (квадратичным, по прикидкам в уме, но наверно можно и лучше).
П.С. Я бы правила-схемы 3-5 в одно объединил: Xi Aij Uj Lk -> Xj Lk+1
Оно так и понятней становится, как по мне: «Если мы в вершине i, есть дуга из нее в j, мы не были в j, и длина пути k, то переходим в j и увеличиваем длину на 1»
Насколько мне помнится, и без приоритетов тоже эквивалентны универсальной машине Тьюринга. Правда я не уверен, что там не нужно какие-то другие типы правил вводить, кроме описанных вами. По крайней мере, близкая по духу идея химических абстрактных машин (в которой нет приоритетов) так точно эквивалентна.
Почему бы не перебрать все варианты, т.е. не делать алгоритм вероятностным? Алгоритм останется полиномиальным (квадратичным, по прикидкам в уме, но наверно можно и лучше).
П.С. Я бы правила-схемы 3-5 в одно объединил: Xi Aij Uj Lk -> Xj Lk+1
Оно так и понятней становится, как по мне: «Если мы в вершине i, есть дуга из нее в j, мы не были в j, и длина пути k, то переходим в j и увеличиваем длину на 1»
Насколько мне помнится, и без приоритетов тоже эквивалентны универсальной машине Тьюринга.Во всех просмотренных мною статьях по этой тематике алгоритмически универсальные мембранные системы снабжались всегда какими-то дополнительными условиями, правилами и т.д. Навскидку, я помню два таких ограничения — приоритет правил и поляризация мембран (фактически, динамическая смена идентификатора мембраны). Наверное, дело в символьных мультимножествах, если их заменить на строки (упорядоченные мультимножества), то все будет пучком.
Почему бы не перебрать все варианты, т.е. не делать алгоритм вероятностнымЯ по этому поводу общался с человеком, входящим в мембранное братство, у нас не получилось превзойти линейно-логарифмическое время, не вводя тех самых доп. условий — приоритета или поляризации.
Я бы правила-схемы 3-5 в одно объединилЕсть такой вариант! Но мне нравятся бинарные отношения :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск гамильтонова пути с помощью мембранной системы за полиномиальное время