Пусть дан ориентированный граф (достаточно общий, могут быть циклы и петли, например) и два пути в нем (последовательность вершин и ребер, их соединяющих).

Задача: придумать метрику, которая бы считала меру "похожести" путей друг на друга.

Естественно, ожидается выполнение всех свойств метрики.

Жизненная интерпретация: есть врачи в поликлинике, двое человек проходят медосмотр. Узнать, насколько похожими были их пути следования. Ясно, что человек может дважды подряд зайти к одному и то му же, вернуться в любой момент к какому-то врачу (это регулируется ребрами графа) и так далее.

В голову почти сразу приходит метрика Левенштейна, сравнивающая последовательности, однако, она не совсем отвечает требованиям задачи. Например, она не учитывает другие вершины и ребра, не участвующие в данных путях. Хотя количество альтернатив прохождений метрика точно должна учитывать, чтоб отражать реальность.

UPD: Стоит сказать, что на данный момент я думаю сделать набор элементарных преобразований просто совпадающим с множеством элементарных в метрике Левенштейна. Просто, пути отстают друг от друга на 1, если их записи через слова N-буквенного алфавита отличаются на замену/вставку/удаление. Пусть пока так будет, всегда можно изменить. Суть моей проблемы вот в чем. Пусть есть два конкретных пути. Между ними посчитано расстояние d по правилу выше. Однако, есть две очень разные ситуации (см. картинку). alt text

Первая: пусть весь граф -- это ровно эти два пути и больше ничего. Вторая: кроме этих двух путей еще еще очень много обходов, альтернатив и так далее. Вторая ситуация должна накладывать некий штраф и увеличить расстояние между путями относительно первой ситуации. Ну потому что одно дело -- когда больше некуда идти (либо одинаково, либо врозь), а другое -- когда были варианты для путей быть ближе, но они достаточно далеко. В общем, как-то вот это нужно обыграть. Придумать поправку к основной метрике так, чтоб она сама свойства метрики не "сломала". Все штрафы, что я вводил ранее, нарушали, например, правило треугольника.

задан 6 Мар '19 16:00

изменен 7 Мар '19 15:35

@andreykol13: видимо, вместо штрафов лучше ввести элементарные преобразования с "весами", делая переход от пути к "далёкому" от него достаточно "тяжёлым". Свойства метрики для переходов с "весами" будут выполнены в любом случае.

(7 Мар '19 17:15) falcao
10|600 символов нужно символов осталось
0

Я сейчас что-то напишу, а потом ещё при необходимости добавлю.

В частном случае, когда граф состоит из m ориентированных петель, получаются в точности слова в m-буквенном алфавите, и их "близость" можно измерять при помощи метрики типа Левенштейна. То есть эта идея всё равно будет присутствовать.

Далее, надо заметить, что на любом множестве можно задать метрику тривиальным способом, считая, что различные элементы находятся на расстоянии 1. Ясно, что здесь это не подходит. Но можно указать общую конструкцию, которая позволяет в изобилии создавать метрики -- в том числе подходящие по условиям реальной задачи.

Пусть X есть некоторое множество, на котором надо задать метрику. (В данном случае это множество путей в графе.) Зададим произвольным образом множество элементарных преобразований, то есть переходов от элемента x к элементу y. Это аналогично вставкам/удалениям символов и их заменам для метрики Левенштейна. То есть надо решить, какие пути оказываются "совсем похожими", где преобразование можно осуществить за один шаг.

Далее, когда такое множество задано, расстояние между элементами считается минимальное число элементарных преобразований, превращающих один элемент в другой. Это всегда будет метрика, если преобразования обратимы, и если от любого элемента к любому можно хоть как-то перейти.

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

Дополнительно можно заметить, что преобразования можно рассматривать с "весами", то есть какие-то изменения путей мы можем считать имеющими "сложность" 2 или 3 вместо одного, и тогда вместо их числа учитывается сумма "весов" того, что мы сделали.

ссылка

отвечен 6 Мар '19 19:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,825
×643
×234
×55
×36

задан
6 Мар '19 16:00

показан
584 раза

обновлен
7 Мар '19 17:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru