Недавно на научном небосводе появилась новая сенсация, озарившая оный небосвод зарницами новых надежд и далеко простирающихся перспектив. Одна из публикаций по этому поводу называется "Биокомпьютер, построенный на основе одноклеточной амебы, решил знаменитую «задачу коммивояжера» для 8 городов быстрее современного компьютера".
Исходная научная статья была опубликована еще 19 декабря прошлого года в журнале «Royal Society Open Science» под названием «Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism» («Замечательная решающая способность одноклеточного амебоидного организма и механизм этой способности»).
Группа исследователей из Университета Кейо в Токио доказала (так они утверждают), что одноклеточное животное, амеба, может успешно решать знаменитую NP-полную задачу «Коммивояжер», причем при определенных условиях она с точки зрения скорости вычислений может обогнать современный компьютер.
Это чрезвычайно смышленое простейшее называется Physarum polycephalum («Многоголовая слизь»).
У амеб нет ничего похожего на центральную нервную систему, что делает их не слишком подходящими кандидатами для решения тех фундаментальных математических задач, над которыми десятилетия бьются лучшие специалисты. Однако японские исследователи доказали (во всяком случае, они в этом убеждены), что некоторые виды амёб можно использовать как своего рода «процессорные модули» в биокомпьютерах будущего.
Physarum polycephalum уже использовалась в качестве биологического компьютера в нескольких других экспериментах. Данное существо считается особо полезным в биологических экспериментах с вычислениями, так как что оно, во-первых, ненавидит свет и, во-вторых, способно расширять различные области своего тела в поисках более эффективного способа получения пищи.
Исследователи поместили амёбу на специальную пластину с 64 каналами, в направлении которых животное могло вытягивать тело. Амёба постоянно пытается расширить себя, чтобы покрыть как можно большую площадь с питательным веществом. Каждый канал в пластине можно осветить: это заставляет амебу из инстинктивного отвращения к свету уйти из этого канала.
Для воздействия на амёбу люди использовали нейронную сеть, которая учитывала данные о текущем положении амебы и о расстояниях между городами. Сеть была обучена с большей вероятностью освещать города (каналы) с бОльшими расстояниями между ними. При воздействии на амёбу она принимает форму, которая представляет приблизительные решения данной задачи.
Здесь я вынужден заметить, что приблизительные решения задачи коммивояжера не стОят того, чтобы добывать их настолько сложным и ненадежным способом. Известно много сугубо математических алгоритмов, справляющихся с этим намного быстрее.
Нелишне также заметить, что решением задачи в математике считается гарантированное получение ее ТОЧНОГО ответа при ВСЕХ возможных в природе ее исходных данных (в рассматриваемой задаче – при любом наборе городов, при любом «узоре» дорог между ними и при любых длинах этих дорог). Приближенные алгоритмы, о которых часто говорят с не очень понятным придыханием – это не очень интересно и не очень серьезно. Что-то вроде игр в детсадовской песочнице.
Самое интересное, что количество времени, которое требуется амёбе для получения этих почти оптимальных решений, растёт линейно, хотя количество вариантов решения увеличивается экспоненциально. В ближайшее время исследователи собираются изготовить чипы с десятками тысяч каналов, чтобы амёба могла попробовать решить задачу коммивояжера на сотнях городов.
Исследователи выяснили, что микроорганизм почти всегда решает эту задачу идеально точно (во всяком случае, они так говорят). И что скорость принятия решений увеличивается линейно при усложнении задачи, хотя в IT-науке рост вычислительных операций в этом случае должен расти по экспоненте (т.е. не постепенно, а взрывообразно).
Это трудно объяснить с позиции науки, поэтому опыты продолжаются. Сейчас готовятся пробирки с архитектурой, в которой имитируются не семь, а десятки тысяч объектов-кормушек. Ожидается, что наблюдать за поведением амебы при таком лавинообразном усложнении условий задачи будет весьма интересно.
Ученые пока не очень понимают, почему одноклеточному организму удается выбрать кратчайший маршрут. Но они полагают, что если удастся поставить на службу человечеству таких амеб, то они помогут фундаментально изменить подходы как к существующим вычислительным алгоритмам, так и к компьютерным системам безопасности.
Словом, команда из фармаколога, управленца, химика и только одного компьютерщика сделала попытку "расколоть" чисто математическую фундаментальную проблему. Дожили: вся надежда мировой математической и компьютерной науки - на амебу.
Помнится, несколько лет назад на передовых рубежах современной науки заблистало, было такое дело, что-то очень похожее и тоже заманчиво-эпохальное. Специалисты в области оптимизационных и труднорешаемых задач (реально работающие алгоритмы тогда, как и сейчас, еще не были найдены) предложили заставить молекулы ДНК искать кратчайшие маршруты в задаче «Коммивояжер».
Примечательно, что и в том случае ученые занимались явно не своим делом: мастистые математики-теоретики – молекулами (единственное объяснение такого кульбита - очевидная беспомощность там, где вопросы касаются задач класса "NP").
Что-то там такое математики-теоретики смешивали в обычных химических пробирках, выдерживали некоторое время, пока эти молекулы ДНК (даже не подозревающие о том, что их внаглую и бесплатно эксплуатируют) сцеплялись в каком-то естественном для них при заданных условиях порядке.
Потом их хитрым образом фильтровали, сепарировали, опознавали искомую кратчайшую цепочку и т.д. Вся эта банно-прачечная возня для заданных в условиях задачи "Коммивояжер" семи городов (т.е. семи вершин математического графа) занимала примерно неделю. Подтверждение о искомой доброкачественности полученного результата выдавали, на бланке с подписью и печатью, надо полагать, сами молекулы ДНК.
Очень трудным оказалось не прокомментировать это передовое достижение. В конце одной из статей того времени я, каюсь, предложил логичное развитие-усовершенствование этой идеи: использовать модель лабиринта и бегающих в нем живых кухонных рыжих тараканов. И встроить это всё в, например, корабельную систему целеуказания для артсистемы ближнего рубежа самообороны (зона ответственности - в радиусе полутора-двух километров от защищаемого объекта, там все решает та же задача "Коммивояжер", т.е. минимальность времени на перевод ствола последовательно на все приближающиеся цели).
Далее всякий желающий может самостоятельно, в красках, представить себе, что именно будет во время массированной атаки крылатыми ракетами через 2-3 секунды (это - время преодоления прорвавшимися боеголовками этих полутора-двух километров). Как эти ошалевшие тараканы вместе с обломками и клочками других тараканов летят во все стороны из эпицентра взрыва.
В завершение остается пояснить (ибо журналисты, даже научные, уж очень любят приврать ради красного словца), что даже «в лоб», на неторопливом простеньком домашнем двухгигарцевом «пентиуме», задача «Коммивояжер» для 7 городов полностью и абсолютно точно решается меньше, чем за секунду. А со столь устрашающими журналистов 8 городами – примерно за 5 или 6 секунд.
Причем без всяких крайне уязвимых капризных амеб и молекул ДНК. Которые, к слову, все равно не справятся, как бы не надеялись наши новоявленные изобретатели, со сколь-нибудь большим, интересным с практической точки зрения, количеством городов.
Такими вершинами графа, понятно, могут быть не только города и подлежащие поражению цели, но и конкретные аэропорты, магазины, стеллажи на больших складах и т.д. и т.п.).
- - -
(*) – иллюстрация из интернета, открытые источники
Если понравилось рассказанное – не стесняйтесь кликнуть по значку «Во!» (это где большой палец вверх, что в Дзене означает вовсе не респект автору, а «давайте ещё чего-нибудь примерно такого же», «требую продолжения банкета!»). И – подписывайтесь на канал, оставляйте комментарии.