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

Поиск наилучшей последовательности просмотра списка 250 лучших фильмов с помощью языка Wolfram Language (Mathematica)

Время на прочтение 7 мин
Количество просмотров 56K
Всего голосов 100: ↑93 и ↓7 +86
Комментарии 36

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

Я долго думал, как описать этот пост и его автора, но цензурного ничего в голову не лезет…
Просто шикарно.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Просто потому, что с него начинается поиск последовательности.
Насколько я вижу, вся магия происходит в FindShortestTour. Какой конкретно алгоритм используется — сходу непонятно — в том числе непонятно, предполагается ли, что путь должен быть замкнутым и минимизируется длина цикла — хотя на первый взгляд, по условию задачи — речь не о цикле, а о поиске кратчайшего пути обхода N точек. Если это так, то это в чистом виде задача коммивояжёра и там оптимальное решение не всегда будет начинаться с одной и той же точки.

Тривиальный контрпример: поиск кратчайшего пути на 3 точках A, B, C, где |AB|=1, |BC|=10, |AC|=1 => кратчайший путь B-A-C (он же C-A-B) длины 2, а любой путь, начинающийся с A будет очевидно длиннее (A-B-C или A-C-B — все получается по 11).
Путь замкнут, но, естественно, последний элемент списка устранен, чтобы не дублировать первый (функция Most).

В эту функцию «зашито» несколько методов: «AllTours», «CCA», «Greedy», «GreedyCycle», «IntegerLinearProgramming», «OrOpt», «OrZweig», «RemoveCrossings», «SpaceFillingCurve», «SimulatedAnnealing» и «TwoOpt».

Ввиду того, что число точек в данной задаче невелико, автоматически применяется «IntegerLinearProgramming».
Вообще, я так понимаю, если хочется решить таки задачу «побывать в каждой точке полного графа ровно 1 раз с минимальной стоимостью», то это она по сути сводится к задаче коммивояжера => получению гамильтонова цикла => дополнительному поиску, какое ребро в этом цикле выгоднее всего разорвать (очевидно, ребро с максимальной стоимостью), чтобы, соответственно, запустить путь начиная с одной точки разрыва, чтобы он в итоге пришел в другую точку.

Я так понимаю, это должно быть в целом несложно дореализовать в вашем алгоритме в Mathematica?
Где же сделано-то? В filmsOptimalSequence по сути единственное, что делается — это вызывается Most(FindShortestTour(...)). В свою очередь FindShortestTour ищет цикл, а вот где его оптимально разорвать — никто не ищет, Most тупо разрывает на последнем элементе (т.е. по сути — первом попавшемся). Если его разорвать на каком-то другом элементе — вероятно, общая сумма расстояний между фильмами в цепочке будет ниже.
Может быть я выразился не очень ясно. FindShortestTour решает задачу коммивояжера.
Что касается вашего контрпримера — неравенство треугольника не выполнено.
В каком пространстве этот путь будет существовать, чтобы существовал такой треугольник?
Никто не говорил, что это длины прямых в двумерном пространстве. Это могут быть просто стоимости, времена путешествия или какие-то подобные метрики. Есть 3 города и прямая дорога между B и C проходит через горный перевал, поэтому ехать 10 часов. Если объехать с заедом в A, т.е. B-A-C, то получается всего 2 часа.
Тогда и расстояние между B и C будет 2 часа, а не 10. Неравенство треугольника о том и говорит, что расстояние есть кратчайший путь.
Вот простейшее решение задачи, о которой говорите вы:



Код для копирования
distanceMatrix={{\[Infinity],1,1},{1,\[Infinity],10},{1,10,\[Infinity]}};
distance[pts_]:={pts,Total[Extract[distanceMatrix,Partition[pts,2,1]]]};
fspf=FindShortestPath[WeightedAdjacencyGraph[distanceMatrix]];
distance /@ Select[fspf@@@Subsets[{1,2,3},{2}],Length[#]==Length[distanceMatrix]&]
Ну, это по сути совсем полный перебор, если я правильно понимаю. Сколько будет вычисляться такое на графе фильмов из 250 точек? Есть подозрение, что очень долго.
Я написал вам, что это простейшая реализация.
Интересная Огромная, интересная и сложная реализация, но не проще ли было бы распарсить через регулярки лишь imdb на любой прикладном языке, залить это дело в ДБ (к примеру MySQL), а далее проявить магию SQL для получения тех или иных выборок?
Конечно графики придется реализовывать через сторонний софт или библиотеки (например на JS+CSS).
IMDb не имеет статей на русском, к сожалению. Так как я хотел включить в анализ описаний фильмов в функцию расстояния, то это критично. Про КиноПоиск я написал в начале — не очень хочется иметь дело с юр. вопросами, хотя полный парсер с него у меня есть, но показывать его нет возможности.

Что касается баз данных — то можно их подключать к Mathematica (Database Connectivity), но в рамках данной статьи это излишне, так как можно очень удобно пользоваться встроенным форматом баз данных (Association и Dataset).

В целом то, о чем говорите вы — скорее второй шаг после того, как все R&D сделано в Mathematica, и то, только если необходимо все ставить на «промышленные рельсы». Идея статьи — именно возможность быстрой разработки новых объектов, алгоритмов, реализация идей.
распарсить через регулярки
лишь imdb
залить это дело в ДБ (к примеру MySQL)
проявить магию SQL
графики придется реализовывать через сторонний софт или библиотеки (например на JS+CSS).

Хм, пожалуй нет, не проще.
Стоило учесть серии фильмов. IV и V эпизоды Звёздных Войн, например, рядом, а VI от них фильмов через двадцать. С Властелином Колец, кстати, удачно получилось, хоть порядок и перепутан.
Да, согласен с вами. Это интересная идея и ее можно было бы сделать через анализ названий, на основе уже имеющихся конструкций:

In[1]:=



Out[3]:=



Код для копирования
filmSeriesQ[PatternSequence[{i_,j_}]/;i>j]:=filmSeriesQ[{j,i}]

filmSeriesQ[{i_,j_}]:=filmSeriesQ[{i,j}]=Module[{lcs,f1,f2,replaceEnd,whiteSpaceCount},
{f1,f2}=filmsData[[{i,j},«название»]];

replaceEnd=StringReplace[#,":"~~___:>""]&;

lcs=replaceEnd[LongestCommonSubsequence@@{f1,f2}];

whiteSpaceCount=StringCount[StringTrim@lcs," "]+1;

Quiet@If[Or[UnsameQ@@(StringSplit[#][[1;;whiteSpaceCount]]&/@{lcs,replaceEnd@f1}),StringLength[lcs]<=4],

False,

And[StringMatchQ[f1,lcs~~x___],StringMatchQ[f2,lcs~~x___],Or@@(StringMatchQ[#,lcs~~x___/;Not[StringFreeQ[x,Alternatives@@({":"}~Join~(ToString/Range[0,9]))]]]&/@{f1,f2}),

Equal@@(StringFreeQ[#,"."]&/@{f1,f2})]]];

filmsData[[#,«название»]]&/@(DeleteDuplicates/@(Flatten/Gather[DeleteDuplicates[Sort/Cases[Table[{i==j,filmSeriesQ[{i,j}],{i,j}},{i,1,Length[wikiFilmPagesData]},{j,1,Length[wikiFilmPagesData]}],{False,True,x_}:>x,Infinity]],Intersection[#1,#2]=!={}&]))
Это все весьма занимательно, но не имеет отношения к заголовку. В чем оптимальность какой-либо из придуманных последовательностей? Почему я должен захотеть посмотреть фильмы в порядке близости их постеров? Я получу какой-то особенный кайф при этом?

Я ожидал увидеть какой-то глубокий анализ на основе массива оценок, например те, кто смотрят такой-то драматический фильм сразу после такого-то комедийного, ставят выше в среднем оценки, таким образом метрикой оптимальности последовательности будет ожидаемый средний балл при просмотре всех 250 фильмов, интегральный показатель полученных впечатлений.
Анализ постеров — это несущественный элемент статьи и построенной метрики. Жаль, что вы обратили на это внимание, хотя я специально вначале говорил недостатки метрики, созданной в статье Маттиаса.

Довольно серьезный показатель — анализ описаний фильмов.

То о чем говорите вы — потребовало бы подгрузки комментариев всех фильмов (но уже с КиноПоиска) и доступа к статистике переходов и оценок пользователей (хотя бы на том же сайте). Реализовать это — более чем возможно, но не в рамках статьи и исходники и подробное описание таких проектов уже вряд ли можно выкладывать, так как это в принципе это уже — коммерческий продукт — для тех же телекомпаний, которые хотят зимними вечерами привлечь к экранам как можно больше людей, предлагая им оптимально показывать фильмы (не обязательно топовые).
В комментарии я намекнул, что если фильмы похожие, даже по идее/сюжету, вовсе не значит что их надо смотреть подряд. Умозрительно кажется, что даже скорее наоборот, чтобы одна тема не надоедала. Хотя кратчайший обход очень легко превратить в длиннейший.
Вы можете заменив функцию расстояния f на 1-f смотреть максимально разные фильмы.
Если хотите, развейте идею поста в предложенном вами направлении, думаю, это будет интересно.
Можно было проследить еще авторов правок к статьям в википедии. Какой-никакой, но уже человеческий фактор группировки.
Статья любопытная, но ничего общего с заголовком не имеющая. Эти 250 фильмов можно смотреть в любом порядке (не считая фильмов с сиквелами). Плохих фильмов в этом списке нет, в общем-то. Shuffle — и вперёд!
Не хотите спрятать под спойлер краткое изложение сюжета Интерстеллара? ) А то вдруг кто-то еще не посмотрел?
НЛО прилетело и опубликовало эту надпись здесь
Спасибо за похвалу, но позволю себе не согласиться. Графы все же отражают структуру связей между фильмами, в то время как пути — это всего лишь сухая выжимка в виде оптимального гамильтонова пути.

Соглашусь, что обилие картинок может создать такое впечатление, правда, думаю, лишь при беглом просмотре.
НЛО прилетело и опубликовало эту надпись здесь
Как-то странно алгоритм предлагает смотреть «крёстных отцов». Сперва второй, а потом первый. Причём сразу один за другим :)
Выше AraneusAdoro по сути говорил об этом, в ответе приведен код для получения серий фильмов, так что можно затем учитывать их последовательность или рассматривать их как единое целое.
Интересно было бы сравнить с анализом английских описаний — там, по идее, связи будут больше, и может даже другие, поскольку обилие русских синонимов умещаются в двух словах.
Вы правы, так как фильмы английские в целом, то сравнение на английском может дать новые грани.

Один раз я писал о таком, при этом вышли довольно интересные результаты: Анализ текста в Mathematica: выделение цитат, цветов и многое другое... Основная цель заключалась в построении цветового портрета произведения.

Офигенно! Осталось только теперь найти время все это посмотреть.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий