Комментарии 36
Я долго думал, как описать этот пост и его автора, но цензурного ничего в голову не лезет…
Просто шикарно.
Просто шикарно.
+5
НЛО прилетело и опубликовало эту надпись здесь
Просто потому, что с него начинается поиск последовательности.
+1
Насколько я вижу, вся магия происходит в 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).
Тривиальный контрпример: поиск кратчайшего пути на 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).
+3
Путь замкнут, но, естественно, последний элемент списка устранен, чтобы не дублировать первый (функция Most).
В эту функцию «зашито» несколько методов: «AllTours», «CCA», «Greedy», «GreedyCycle», «IntegerLinearProgramming», «OrOpt», «OrZweig», «RemoveCrossings», «SpaceFillingCurve», «SimulatedAnnealing» и «TwoOpt».
Ввиду того, что число точек в данной задаче невелико, автоматически применяется «IntegerLinearProgramming».
В эту функцию «зашито» несколько методов: «AllTours», «CCA», «Greedy», «GreedyCycle», «IntegerLinearProgramming», «OrOpt», «OrZweig», «RemoveCrossings», «SpaceFillingCurve», «SimulatedAnnealing» и «TwoOpt».
Ввиду того, что число точек в данной задаче невелико, автоматически применяется «IntegerLinearProgramming».
+1
Вообще, я так понимаю, если хочется решить таки задачу «побывать в каждой точке полного графа ровно 1 раз с минимальной стоимостью», то это она по сути сводится к задаче коммивояжера => получению гамильтонова цикла => дополнительному поиску, какое ребро в этом цикле выгоднее всего разорвать (очевидно, ребро с максимальной стоимостью), чтобы, соответственно, запустить путь начиная с одной точки разрыва, чтобы он в итоге пришел в другую точку.
Я так понимаю, это должно быть в целом несложно дореализовать в вашем алгоритме в Mathematica?
Я так понимаю, это должно быть в целом несложно дореализовать в вашем алгоритме в Mathematica?
0
Это и сделано.
Для этого служат 3 основные функции: FindShortestTour, FindHamiltonianCycle и HamiltonianGraphQ.
Для этого служат 3 основные функции: FindShortestTour, FindHamiltonianCycle и HamiltonianGraphQ.
0
Где же сделано-то? В filmsOptimalSequence по сути единственное, что делается — это вызывается Most(FindShortestTour(...)). В свою очередь FindShortestTour ищет цикл, а вот где его оптимально разорвать — никто не ищет, Most тупо разрывает на последнем элементе (т.е. по сути — первом попавшемся). Если его разорвать на каком-то другом элементе — вероятно, общая сумма расстояний между фильмами в цепочке будет ниже.
0
Что касается вашего контрпримера — неравенство треугольника не выполнено.
В каком пространстве этот путь будет существовать, чтобы существовал такой треугольник?
В каком пространстве этот путь будет существовать, чтобы существовал такой треугольник?
0
Никто не говорил, что это длины прямых в двумерном пространстве. Это могут быть просто стоимости, времена путешествия или какие-то подобные метрики. Есть 3 города и прямая дорога между B и C проходит через горный перевал, поэтому ехать 10 часов. Если объехать с заедом в A, т.е. B-A-C, то получается всего 2 часа.
0
Вот простейшее решение задачи, о которой говорите вы:
Код для копирования
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]&]
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]&]
0
Конечно графики придется реализовывать через сторонний софт или библиотеки (например на JS+CSS).
+1
IMDb не имеет статей на русском, к сожалению. Так как я хотел включить в анализ описаний фильмов в функцию расстояния, то это критично. Про КиноПоиск я написал в начале — не очень хочется иметь дело с юр. вопросами, хотя полный парсер с него у меня есть, но показывать его нет возможности.
Что касается баз данных — то можно их подключать к Mathematica (Database Connectivity), но в рамках данной статьи это излишне, так как можно очень удобно пользоваться встроенным форматом баз данных (Association и Dataset).
В целом то, о чем говорите вы — скорее второй шаг после того, как все R&D сделано в Mathematica, и то, только если необходимо все ставить на «промышленные рельсы». Идея статьи — именно возможность быстрой разработки новых объектов, алгоритмов, реализация идей.
Что касается баз данных — то можно их подключать к Mathematica (Database Connectivity), но в рамках данной статьи это излишне, так как можно очень удобно пользоваться встроенным форматом баз данных (Association и Dataset).
В целом то, о чем говорите вы — скорее второй шаг после того, как все R&D сделано в Mathematica, и то, только если необходимо все ставить на «промышленные рельсы». Идея статьи — именно возможность быстрой разработки новых объектов, алгоритмов, реализация идей.
+4
распарсить через регулярки
лишь imdb
залить это дело в ДБ (к примеру MySQL)
проявить магию SQL
графики придется реализовывать через сторонний софт или библиотеки (например на JS+CSS).
Хм, пожалуй нет, не проще.
+15
Стоило учесть серии фильмов. IV и V эпизоды Звёздных Войн, например, рядом, а VI от них фильмов через двадцать. С Властелином Колец, кстати, удачно получилось, хоть порядок и перепутан.
+1
Да, согласен с вами. Это интересная идея и ее можно было бы сделать через анализ названий, на основе уже имеющихся конструкций:
In[1]:=
Out[3]:=
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]=!={}&]))
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]=!={}&]))
+1
Это все весьма занимательно, но не имеет отношения к заголовку. В чем оптимальность какой-либо из придуманных последовательностей? Почему я должен захотеть посмотреть фильмы в порядке близости их постеров? Я получу какой-то особенный кайф при этом?
Я ожидал увидеть какой-то глубокий анализ на основе массива оценок, например те, кто смотрят такой-то драматический фильм сразу после такого-то комедийного, ставят выше в среднем оценки, таким образом метрикой оптимальности последовательности будет ожидаемый средний балл при просмотре всех 250 фильмов, интегральный показатель полученных впечатлений.
Я ожидал увидеть какой-то глубокий анализ на основе массива оценок, например те, кто смотрят такой-то драматический фильм сразу после такого-то комедийного, ставят выше в среднем оценки, таким образом метрикой оптимальности последовательности будет ожидаемый средний балл при просмотре всех 250 фильмов, интегральный показатель полученных впечатлений.
+12
Анализ постеров — это несущественный элемент статьи и построенной метрики. Жаль, что вы обратили на это внимание, хотя я специально вначале говорил недостатки метрики, созданной в статье Маттиаса.
Довольно серьезный показатель — анализ описаний фильмов.
То о чем говорите вы — потребовало бы подгрузки комментариев всех фильмов (но уже с КиноПоиска) и доступа к статистике переходов и оценок пользователей (хотя бы на том же сайте). Реализовать это — более чем возможно, но не в рамках статьи и исходники и подробное описание таких проектов уже вряд ли можно выкладывать, так как это в принципе это уже — коммерческий продукт — для тех же телекомпаний, которые хотят зимними вечерами привлечь к экранам как можно больше людей, предлагая им оптимально показывать фильмы (не обязательно топовые).
Довольно серьезный показатель — анализ описаний фильмов.
То о чем говорите вы — потребовало бы подгрузки комментариев всех фильмов (но уже с КиноПоиска) и доступа к статистике переходов и оценок пользователей (хотя бы на том же сайте). Реализовать это — более чем возможно, но не в рамках статьи и исходники и подробное описание таких проектов уже вряд ли можно выкладывать, так как это в принципе это уже — коммерческий продукт — для тех же телекомпаний, которые хотят зимними вечерами привлечь к экранам как можно больше людей, предлагая им оптимально показывать фильмы (не обязательно топовые).
+1
В комментарии я намекнул, что если фильмы похожие, даже по идее/сюжету, вовсе не значит что их надо смотреть подряд. Умозрительно кажется, что даже скорее наоборот, чтобы одна тема не надоедала. Хотя кратчайший обход очень легко превратить в длиннейший.
+3
Можно было проследить еще авторов правок к статьям в википедии. Какой-никакой, но уже человеческий фактор группировки.
0
Статья любопытная, но ничего общего с заголовком не имеющая. Эти 250 фильмов можно смотреть в любом порядке (не считая фильмов с сиквелами). Плохих фильмов в этом списке нет, в общем-то. Shuffle — и вперёд!
+4
Не хотите спрятать под спойлер краткое изложение сюжета Интерстеллара? ) А то вдруг кто-то еще не посмотрел?
-3
НЛО прилетело и опубликовало эту надпись здесь
Спасибо за похвалу, но позволю себе не согласиться. Графы все же отражают структуру связей между фильмами, в то время как пути — это всего лишь сухая выжимка в виде оптимального гамильтонова пути.
Соглашусь, что обилие картинок может создать такое впечатление, правда, думаю, лишь при беглом просмотре.
Соглашусь, что обилие картинок может создать такое впечатление, правда, думаю, лишь при беглом просмотре.
0
Как-то странно алгоритм предлагает смотреть «крёстных отцов». Сперва второй, а потом первый. Причём сразу один за другим :)
+1
Выше AraneusAdoro по сути говорил об этом, в ответе приведен код для получения серий фильмов, так что можно затем учитывать их последовательность или рассматривать их как единое целое.
0
Интересно было бы сравнить с анализом английских описаний — там, по идее, связи будут больше, и может даже другие, поскольку обилие русских синонимов умещаются в двух словах.
0
Вы правы, так как фильмы английские в целом, то сравнение на английском может дать новые грани.
Один раз я писал о таком, при этом вышли довольно интересные результаты: Анализ текста в Mathematica: выделение цитат, цветов и многое другое... Основная цель заключалась в построении цветового портрета произведения.
Один раз я писал о таком, при этом вышли довольно интересные результаты: Анализ текста в Mathematica: выделение цитат, цветов и многое другое... Основная цель заключалась в построении цветового портрета произведения.
0
Офигенно! Осталось только теперь найти время все это посмотреть.
0
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Поиск наилучшей последовательности просмотра списка 250 лучших фильмов с помощью языка Wolfram Language (Mathematica)