Сегодня попалось на глаза видео про них:
Хоть это и просто перевод, проблема, типа, до сих пор открытая.
И как раз сегодня появились новости о её решении:
раз и
два.
Интересно, что так долго это было проблемой (или проблемой неуловимого Джо?). А ещё кажется, что задачу на поиск суперперестановок для заданного числа можно давать чуть ли не на собеседовании. Решить полным перебором, вроде, несложно. Или нет?
Здравствуйте, Nuzhny, Вы писали:
Посмотрел только видео.
NP-complete же
https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem#Shortest_common_superstring...
Из последнего по этой теме вот тут было недавно:
https://www.youtube.com/watch?v=wdOttwuGhCw
Но там обсуждают не точное решение, а жадное приближенное.
Здравствуйте, watchmaker, Вы писали:
W>Это другая задача.
Да, я прошляпил
