Живая слизь решила математическую задачу на миллиарды лет
Японские ученые узнали, что слизевик физарум многоголовый (Physarum polycephalum) способен скоро отыскать оптимальное ответ задачи коммивояжера. Результаты изучения окажут помощь создать аналоговые компьютеры, каковые будут обнаружить более качественные ответы NP-тяжёлых задач в отличие от классических цифровых компьютеров. Статья исследователей размещена в издании Royal Society Open Science.
Задача коммивояжера (англ. Travelling salesman problem, TSP) содержится в поиске самого удачного (малейшего) маршрута, проходящего через пара городов, наряду с этим любой город возможно посетить лишь раз и наряду с этим необходимо возвратиться в исходную точку. При громадном количестве городов задача не разрешиться методом несложного перебора любыми компьютерами кроме того за миллиарды лет, поскольку число маршрутов с числом городов растет экспоненциально. К примеру, при четырех городов существует три вероятных маршрута, а при восьми — уже 2520. …
Живая слизь решила математическую задачу на миллиарды летПодробнее »