Метка «кристофидес»

Спустя десятилетия застоя, найдены новые короткие пути для задачи коммивояжёра

image

Не так давно команда исследователей из Стэнфорда и Университета Макгилла побили 35-летний рекорд по информатике на невообразимо малую величину – на четыре сотых триллионной триллионной триллионной доли процента. Прорыв – сделанный в классической для информатики задаче коммивояжёра – был слишком малым для какого бы то ни было практического значения, но он вдохнул новую жизнь в поиски улучшенных приближённых решений.

Задача формируется так: для набора городов, соединённых дорогами, необходимо найти кратчайший путь посещения каждого города с возвратом в точку старта. У решений задачи есть практические применения от сверления отверстий в печатных платах до управления расписанием задач на компьютере и упорядочивания свойств генома.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js