Комментарии 15
Ага, в универе проходят такое. Задача о рюкзаке там, задача о раскрое, имитация отжига. Наверное, суть новости в том, что сделали удобную обёртку, которую можно использовать не учёным.
Канторович — наше все.
Хм, когда я учился в кораблестроительном институте (самый конец 90-х), нам на технологии судостроения рассказывали, что задача эффективного раскроя до сих пор не решена. Так как это был не мой профильный предмет, я просто запомнил и углубляться не стал.
А на самом деле, выходит, что есть общеизвестные алгоритмы?
Общеизвестный алгоритм: "Семь раз отмерь — один раз отрежь".
Ну тут же как. Задача раскроя — известная NP-полная задача. Если кто-то придумает алгоритм, который сможет за полиномиальное время (т.е. эффективно) её точно решить, то это перевернет современную информатику с ног на голову (в особенности криптографию), а автор получит премию в миллион баксов. Если кто-то докажет, что такого алгоритма не существует, то он тоже получит премию и всеобщее признание, но фурор произведет гораздо меньший (поскольку за 50 лет никто не придумал таких алгоритмов, многие считают, что это таки невозможно).
Тем не менее, придуманы эвристические алгоритмы, которые за полиномиальное время находят достаточно хорошее решение (они перебирают разные варианты решений, просто гораздо меньше, чем полный перебор всех вариантов). Когда я учился в универе, это были всякие симуляции отжига, генетические алгоритмы, муравьиные колонии. Сейчас наверное ещё нейросети подтянулись.
Задача одна, а алгоритмов решения мнрго разных, ведь идеальный слишком ресурсозатратен. Раньше была эвристика, сейчас нейронные сети.
Если лет десять назад, чтобы "продать" инвесторам банальные или посредственные изобретения, надо было добавлять приставку "нано", то теперь в моде ИИ.
А задача про раскрой как была NP-полной, так и осталась…
В МТИ придумали, как с помощью машинного обучения уменьшить отходы листового металла