Алгоритмы для выведения временной шкалы/хронологии

Question

Я ищу выводы по алгоритмам, чтобы вывести хронологию/хронологию серии романов. Я разделил тексты на несколько дней и создал базу данных отношений между ними, например: X за месяц до того, как Y, Y и Z являются последовательными, дата Z известна, X - во вторник и т. Д. Существует неопределенность («месяц» действительно означает только около 30 дней), а также противоречия. Я могу отметить некоторые отношения как более надежные, чем другие, чтобы помочь устранить двусмысленность и противоречия.

Какие существуют алгоритмы, чтобы вывести хронологию наилучшего соответствия из этого вида данных, присваивая дату наибольшей вероятности каждому дню? По крайней мере, время 1-мерное, но рассмотрение сложного графика отношений с несогласованностью кажется нетривиальным. У меня есть CS-фон, поэтому я могу что-то кодировать, но было бы полезно некоторое представление об именах применимых алгоритмов. Я предполагаю, что у меня есть график с днями как узлы, как отношения как ребра.

Answer 1

Программирование ограничений - это то, что вам нужно. В CP на основе распространения вы чередуете (a) принятие решения в текущей точке выбора в дереве поиска и (б) распространение последствий этого решения, насколько это возможно. Понятно, что вы делаете это, поддерживая домен D возможных значений для каждой проблемной переменной x такой, что D(x) - это набор значений для x, которые еще не исключены вдоль текущего пути поиска. В вашей проблеме вы можете свести ее к большому набору логических переменных, x_ij, где x_ij истинно. Iff event i предшествует событию j. Изначально D(x) = {true, false} для всех переменных. Решение просто уменьшает область неопределенной переменной (для булевой переменной это означает, что ее домен сводится к одному значению, истинному или ложному, что совпадает с назначением). Если в любой точке пути поиска D(x) становится пустым для любого x, вы достигли тупика и должны вернуться.

Если вы умны, вы попытаетесь учиться на каждом провале, а также отступить, если требуется, чтобы избежать поиска в поиске, чтобы избежать избыточного поиска (это называется backjumping - например, если вы идентифицируете это тупик, который вы достигли на уровне 7, был вызван выбором, который вы сделали на уровне 3, нет никакого смысла в отступлении до уровня 6, потому что не существует решения в этом поддереве, учитывая выбор, сделанный вами на уровне 3!).

Теперь, учитывая, что у вас есть определенная степень доверия к вашим данным, у вас действительно есть проблема оптимизации. То есть вы не просто ищете решение, которое удовлетворяет всем ограничениям, которые должно быть должно быть истинным, но которое также наилучшим образом удовлетворяет другим «мягким» ограничениям в зависимости от степени доверия, который у вас есть. Что вам нужно сделать здесь, это решить объективную функцию, присваивая оценку заданному набору удовлетворенных/нарушенных частичных ограничений. Затем вы хотите сократить ваш поиск, когда найдете, что текущий путь поиска не может улучшить наилучшее найденное ранее решение.

Если вы решите пойти на логический подход, вы можете с удовольствием изучить SAT-решатели, которые разрывают эти проблемы. Но первое место, которое я бы посмотрел, - это MiniZinc, язык CP, который отображает на множество различных современных решателей ограничений.

Удачи!

Answer 2

Простым, грубым первым приближением к вашей проблеме было бы хранить информацию, подобную «A, произошедшая до B» в ориентированном графе с краями типа «A -> B». Проверьте график, чтобы увидеть, является ли он прямым ациклическим графиком (DAG). Если это так, информация последовательна в том смысле, что существует согласованная хронология того, что произошло до того, что еще.Вы можете получить образец линейной хронологии, напечатав «топологическую сортировку» (верхнюю часть) DAG. Если события C и D происходили одновременно или нет информации, чтобы сказать, что было раньше другого, они могут отображаться в верхнем массиве как ABCD или ABDC. Вы даже можете получить алгоритм topsort для печати всех возможностей (так ABCD и ABDC) для дальнейшего анализа, используя более подробную информацию.

Если полученный график не является DAG, вы можете использовать алгоритм, подобный алгоритму Тарьяна, для быстрого определения «сильно связанных компонентов», которые являются областями графика, которые содержат хронологические противоречия в виде циклов. Затем вы могли бы более тщательно их проанализировать, чтобы определить, какие менее надежные края могут быть удалены для разрешения противоречий. Другой способ идентифицировать края для удаления для исключения циклов - поиск «минимальных наборов дуги обратной связи». Это NP-жесткий вообще, но если ваши сильно подключенные компоненты малы, поиск может быть осуществим.