Амеба решает проблему коммивояжера

Задача коммивояжера NP-сложна, так что вы действительно не ожидаете, что безмозглая амеба решит ее — или вы бы стали?

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

Если вы можете найти решение проблемы TSP за полиномиальное время, то есть такое, которое выполняется за разумное время для большого количества городов, то у вас есть быстрое решение более ограниченной формы проблемы TSP. Более ограничительная форма — это просто ответ на вопрос «является ли путь короче заданного». Эта проблема возникает во времени NP (недетерминированный полином) — потому что, если вы дадите мне путь, который предлагается как более короткий, я могу проверить этот факт очень быстро — просто определите длину предлагаемого более короткого пути. Обратите внимание: если я могу решить TSP за полиномиальное время, я могу решить эту ограниченную версию проблемы за полиномиальное время. Поскольку эта проблема также была NP-полной, мы также решили все проблемы в NP за полиномиальное время и, следовательно, только что выиграли 1 миллион долларов за доказательство того, что NP = P.

Пока никто не доказал, что NP = P или обратное. Время от времени кто-то изобретает аналоговое решение проблемы и иногда предполагает, что это доказывает, что NP = P. Это не так, и причина, по которой это не так, очень очевидна. Например, рассмотрим амебу:

Фото: Масаси Аоно

«Известно, что амеба максимально эффективно усваивает питательные вещества, деформируя свое тело. Она показала, что находит приблизительное решение проблемы коммивояжера (TSP) …»

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

Это открытие вдохновило профессора Сейя Касаи из Университета Хоккайдо имитировать динамику амебы в электронном виде с помощью аналоговой схемы, как описано в журнале Scientific Reports. «Ядро амебы ищет решение в электронной среде, где значения сопротивления на пересечении поперечных полос представляют собой ограничения и требования TSP», — говорит Касаи. Используя поперечины, план города можно легко изменить, обновив значения сопротивления без сложной предварительной обработки ».

Это звучит интересно, поскольку обеспечивает простой и быстрый аналоговый способ решения проблемы TSP, что, помимо того, что важно в теории информатики, также имеет практическое значение.

«Система имеет высокий прикладной потенциал, поскольку она может найти высококачественное юридическое решение за время, которое растет пропорционально размеру проблемы, не страдая от недостатков машин Ising».

Видео ниже расскажет вам намного больше о биологической системе и ее электронном исполнении:

Так что NP = P решено?

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

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

«Эта надежная и быстрая возможность поиска решений может быть полезна для определенных приложений, которые отдают приоритет времени поиска качеству найденного решения. Например, в ситуации на месте бедствия, когда необходимо предоставить надежные маршруты эвакуации для жителей, быстрое объявление должно быть приоритетом, чем определение оптимальных маршрутов «.

Предоставлено: Amoeba Energy.

Майк Джеймс — автор «Руководства программиста по теории: объяснение великих идей», книги, которая ставит своей целью представить фундаментальные идеи информатики, включая проблему NP = P, в неформальной и в то же время информативной форме.