Как стать автором
Обновить

Комментарии 15

А разве таким алгоритмам не сто лет в обед и раньше это не называлось AI и ML?

Ага, в универе проходят такое. Задача о рюкзаке там, задача о раскрое, имитация отжига. Наверное, суть новости в том, что сделали удобную обёртку, которую можно использовать не учёным.

Канторович — наше все.

Хм, когда я учился в кораблестроительном институте (самый конец 90-х), нам на технологии судостроения рассказывали, что задача эффективного раскроя до сих пор не решена. Так как это был не мой профильный предмет, я просто запомнил и углубляться не стал.
А на самом деле, выходит, что есть общеизвестные алгоритмы?

Ну тут же как. Задача раскроя — известная NP-полная задача. Если кто-то придумает алгоритм, который сможет за полиномиальное время (т.е. эффективно) её точно решить, то это перевернет современную информатику с ног на голову (в особенности криптографию), а автор получит премию в миллион баксов. Если кто-то докажет, что такого алгоритма не существует, то он тоже получит премию и всеобщее признание, но фурор произведет гораздо меньший (поскольку за 50 лет никто не придумал таких алгоритмов, многие считают, что это таки невозможно).


Тем не менее, придуманы эвристические алгоритмы, которые за полиномиальное время находят достаточно хорошее решение (они перебирают разные варианты решений, просто гораздо меньше, чем полный перебор всех вариантов). Когда я учился в универе, это были всякие симуляции отжига, генетические алгоритмы, муравьиные колонии. Сейчас наверное ещё нейросети подтянулись.

Задача одна, а алгоритмов решения мнрго разных, ведь идеальный слишком ресурсозатратен. Раньше была эвристика, сейчас нейронные сети.

Если лет десять назад, чтобы "продать" инвесторам банальные или посредственные изобретения, надо было добавлять приставку "нано", то теперь в моде ИИ.


А задача про раскрой как была NP-полной, так и осталась…

Так-то шахматы тоже NP-полные. Однако жешь

Так-то шахматы тоже NP-полные

Обоснуйте. В шахматах поле фиксированного размера (и соот-но чичло перестановок тоже).

Это не особо имеет значение, при условии что даже 8*8 шахматы полным перебором решить фактически невозможно.

Извините, оценка вычислительной сложности задач работает немножко не так.

НЛО прилетело и опубликовало эту надпись здесь

Да там вообще больше похоже на курсовую работу стьюдентов.

В 2д геймдеве популярна программа Texture Packer. По поему делает все тоже самое. Совершенно не ясно какое отношение ML имеет к этому чуду.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Другие новости

Истории