Какие метрики для путей в ор.графах?

muto

Граф простой -прямоугольная матрица из элементов, соединённых каждый с каждым.
Какие есть метрики близости для ориентированных путей разной длины?

Vitaminka

в качестве элементов что выступает?
число ребер

muto

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

stm7543347

Минимальный из минимальных путей от произвольной вершины одного пути до произвольной другого не покатит?
(Чё-то я, кажись, гоню...)

Xephon

> прямоугольная матрица из элементов, соединённых каждый с каждым.
каждый с каждым? или каждый с соседним?
напиши понятнее

Sander

я бы сказал, что:
1. для 1-го пути для каждой вершины берем минимальную длину пути до второго пути
2. по всем длинам сумму.
3, 4. - для второго пути аналогично.
складываем.
вот и <<мера>> получилась.
только у настоящей меры еще и свойства разные есть
хз. - понятно ли написал, ну да ладно, если не понятно - скажете.
да, и еще - все зависит от того, в каких целях ты использовать эту меру собираешься ---
просто может случиться так, что меру ты придумаешь, да вот применять ее к остальной теории получится настолько геморно, что караул.

stm7543347

Да, поди теперь, проверь неравенство Петра Треугольника...

Sander

даже пример могу привести, когда оно не выполняется
вершины - 1, 2,3 , 4,5
ребра:
(1,2);(1,3);(1,5);(2,4);(2,3);(3,4);(4,5);
пути -
1. Вырожденный - вершина 2.
2. Вырожденный - вершина 4.
3. ребро (1,3)
расстояние 1-2 = 2
2-3 = 6
1-3 = 3
2+3<6 - ЛАЖА!
такую лажу можно убрать, вводя нормировку по количеству вершин в пути, т.е.
для путей
t_1x_1,x2\dotsx_1,x_n
t_2y_1,y2\dotsy_1,y_m
было
\rho(t_1,t_2)=\sum_{k=1}^{n}{\mbox{мин расстояние от x_k до t2}}+\sum_{k=1}^{m}{\mbox{мин расстояние от y_k до t1}}
а сделаем
\rho(t_1,t_2)=\frac{\sum_{k=1}^{n}{\mbox{мин расстояние от x_k до t2}}}{n}+\frac{\sum_{k=1}^{m}{\mbox{мин расстояние от y_k до t1}}}{m}
но все равно, до меры далековато пока

muto

да, именно с такой метрики я и начал, но треугольник в ней не выполняется.
Контрпример нашёл програмкой. Смысл такой, что если промежуточный путь y3 содержит больше рёбер,
чем y1 и y2, то метрики rho(y1,y3 rho(y2,y3) уменьшаются из-за слагаемого с множителем 1/{m}.

muto

Соединения - каждый с каждым, а не только с соседними. Т.е. допустимы произвольные скачки по матрице вершин.

natunchik

Для начала надо определиться, что такое "Нулевой Путь". Потому что
Нормированным называется такое пр-во Х над полем К, если опре¬делена функция нормы ||*|| из Х в R, такая, что для нее справедливы следующие условия:
1. Норма неотрицательна и равна нулю лишь в том случае, когда сам элемент равен нулю: ||х|| = 0 титт, х=0.
2. Для любого скаляра a из К выполнена аксиома уравновешенности: ||aх||= |a|*||х||.
3. Выполнено нер-во треугольника: ||х|| + ||у|| <= ||х+у||.
Метрическим пр-вом называется мн-во Х на котором задана бинарная функция p(х,у для которой справедливы следующие условия:
p(х,у)=0 титт х=у. p(х,у)= p(у,х). p(х,z) <= p(х,у) + p(у,z).

Имхо, пока вы не определитесь с нулевым элементом множества путей (а так же со сложением путей и умножением путей на число(т.е. элемент того поля, над которым построено ваше множество путей [...] у вас получится ввести норму.
Или тебе именно метрика нужна хоть какая-нить?
Тогда очень сложно сделать p(х,у)=0 титт х=у

Sander

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

natunchik

Ок.
Ты прав, конечно.
Значит, нужна метрика.
Тогда немедленно встает вопрос - а что чувак собирается с этой метрикой делать?
Потому что какую-нибудь метрику я щаз подумаю и введу. Но она же никакого отношения к его интуитивному понятию "близости" относительно того, что он с ними собирается делать, может и не иметь.

natunchik

Вот например: р(х,у) = сумма вершин в х, которые не принадлежат у, и вершин у, которые не принадлежат х. Типа, симметрическая разность подмножеств множества вершин. Метрика. Даже треугольник, вроде, выполняется - потому что симметрическая разность.
Можно брать не вершины а ребра, тогда надо потребовать, чтобы в любом пути было хотя бы одно ребро.

muto

Или тебе именно метрика нужна хоть какая-нить?

Да, нужна именно метрика, а не норма.
Определение метрики по У.Рудину:
L p,q из X
a) d(p,q)>0 если p~=q; d(p,p)=0
b) d(p,q)=d(q,p)
c) d(p,q) <= d(p,r)+d(r,q) , при любом r из X
Нулевой элемент не нужен, умножение на скаляр - тоже не нужно.

muto

По этой метрике нужно искать визуально "похожие" пути. Моей интуиции тут столько же, сколько и вашей.
Пути отображаются в виде ломаных на прямоугольной матрице из вершин.

Пути, которые проходят "близко" (визуально, или по расстоянию "чило рёбер") - должны быть близки
и в этой метрике.

natunchik

Ну вот, я тебе там повыше аж две метрики дал. Условно пригодные.
Кста, ты уже определился, у тебя путь может самопересекаццо, иметь в составе себя одно и то же ребро два раза?

kachokslava

Что делать, если путя из одной вершины в другую нет?
обязательно требовать ориентированность?
В ориентированном графе никак не построить метрику, чтобы d(p,q)=d(q,p)
(если он не эквивалентен неориентированному, т.е. у каждого ребра "туда" есть пара - "обратно")

muto

Рёбра графа - неориентированны. Ориентированы сами пути.
Самопересечения и петли - допустимы.
Попробую пояснить где эта метрика применяется.
Вот картинка, на которой изображён один путь: всё, что ниже colorbar'a и есть граф. В каждой вершине - картинка.
Около картинки в нижнем левом углу - номер, под которым она встречается в пути. Т.е. путь начинается с цифры "1",
потом переходит в вершину, помеченную "2",..., "10". Длина пути на рисунке 10-1=9 рёбер. Но вообще говоря, длина колеблется
где-то от 1 до 200.
[image]\\m3\print\image001.png[/image]

natunchik

Во-первых, картинку не видно.
Во-вторых, ты можешь внятно объяснить, зачем тебе метрика?
В-третьих, аааахуеть. Так граф-та не ориентированный, оказывается...

kachokslava

Я кажися понял. - требуется метрика не на вершинах, а на путях!

kachokslava

или не понял.. пусть автор прояснит.
ему нужна функция двух аргументов - метрика.
в качестве аргументов выступают вершины или пути?

stm7543347

Пути. Заголовок треда видел?

kachokslava

чем не устраивает модуль разности длин путей?
понятно. равенством нулю для разных путей

natunchik

Тем что это не метрика, я думаю.
А что, мои посты реально никому не видны?

stm7543347

Профакторизовать бы...

electricbird

>А что, мои посты реально никому не видны?
-доктор, меня все игнорируют
-следующий!

valds75

Правильно я понял, что нужна метрика, использующая ориентированность? То есть есил взять один и тот же путь и пройти в разные стороны - должны получиться "далекие" пути? Тогда такой вариант: берем все отображения из вершин одного пути в вершины другого, такие что более "передним" точкам одного пути соответствуют более "передние" точки другого (разные вершины могут отображаться в одну). Для каждого такого отображения считаем расстояние между соответствующими вершинами, и складываем. Потом берем минимум по всем отображениям. Это и есть метрика.

stm7543347

Гы. Теперь заиппёт проверять свойства, но похоже на правду.

natunchik

А одна вершина может отображаццо в разные?

stm7543347

Это не отображение будет.
Кстати, надо сперва хотя бы доказать симметричность такой "метрики".

natunchik

Дык я о том же. Если в пути а) вершин меньше, чем в пути б то некоторым вершинам а) придеццо отображаться более чем в одну вершину б иначе у тебя симметричности не будет ни за что.
А наоборот, очевидно, будет. Если объявить, что мы всегда строим отображение из путя с большей длиной. А если длины одинаковы, то отображение вообще единственное.
На самом деле довольно песдатая метрика (если она метрика).
Только севершенно неочевидно - что надо брать, минимум или максимум. Возможно, нер-во треугольника выполняется только в одном из случаев, если вообще выполняется?
ЗЫ: Аффтор треда уверен, что ему нужна именно метрика, а вот такой вот ф-ции которая возможно является метрикой не хватит.

naami_moloko

Автору топика - бери расстояние от каждой вершины до любой другой, кроме неё самой, единичным. Предполагаю, что это единственное верное решение в тех ограничениях, которые были наложены на метрику(типа что визуально ближе и тд....)

valds75

Действительно, там не совсем отображение - вообще говоря, можно и одной вершине отображаться в разные. Вариант, который изначально пришел мне в голову, такой: берем все "монотонные" (в смысле, номер вершины вдоль пути возрастает) отображения из отрезка [0, 1] в оба пути. Обозначим их m(t) и n(t). Метрика - \inf \limits_{m, n} \int \rho(m(x n (x d x. Здесь \rho - расстояние между вершинами. Как его лучше определить, думать надо. Еще, конечно, вопрос, как такой инфинум считать.

valds75

Ерунду написал. Так не получится:)

filippov2005

Почему не получится? Только не понимаю зачем инфинум
Назовем кривой, соответствующей ориентированному пути в таком графе - отображение Г: [0,1] -> R^2, такое что, если представить, что параметр t (t \in [0,1]) - время, а Г(t) - положение точки в пространстве, то получится движение с равной по модулю скоростью.
Т.е. разбиваем [0,1] на N равных кусков, где N=кол-во ребер в пути, в узлах полученного разбиения определяем Г(t) как соответствующую вершину. Далее на каждом отрезке Г(t) доопределяем линейно. Получаем кусочно-линейную функцию из [0,1] в R^2.
Теперь расстоянием между путями назовем расстояние между кривыми, которые им соответсвуют.
Определим расстояние между кривыми.
Например:
A). P(Г_1, Г_2) = sup_{t \in [0,1]}{ p(Г_1(t Г_2(t }
B) .P(Г_1, Г_2) = \int_0^1{p(Г_1(t Г_2(t dt}
C). P(Г_1, Г_2) = \sqrt{ \int_0^1{ p(Г_1(t Г_2(t^2 dt} }
Осталось опредилить метрику p(x, y) в R^2. Это можно сделать, например, так:
Пусть x=(x1, x2 y=(y1, y2)
1). p(x ,y) = \sqrt{(x1-x2)^2+(y1-y2)^2}
2). p(x, y) = |x1 - x2| + |y1 - y2|
3). p(x, y) = max(|x1 - x2|, |y1 - y2|)
Наверно, проще всего для вычислений вариант A) 2).
Так как максимум может достигаться только в одном из узлов, то достаточно подсчитать расстояние p(Г_1(t Г_2(t в прообразах вершин путей. Т.е. если у первого пути кол-во вершин N_1, а у второго - N_2. То надо подсчитать p(Г_1(t Г_2(t не более, чем в N_2 + N_1 точках, а затем выбрать максимальное.
Возможно, я где-то нагнал , но схема вроде ясна.

muto

похоже, решение уже близко. Благодарю всех за интересные идеи.
--
2: Подход что надо. Этого мне вполне хватит. Единственное, что мне надо ещё придумать
- это обработку случая, когда пути полностью накладываются, но имеют противоположные направления:
тогда p(Г_1(t Г_2(t=0 для всех t, и пути окажутся близкими по твоей метрике.

valds75

По-моему, если пути по разному направлены, то расстояние между ними не 0. \rho(Г(t Г(1-t != 0.

filippov2005

Не-не. Ты не прав! Все нормально и в этом случае.
Если Г_2 это Г_1 наоборот, то
p(Г_1(t Г_2(t = 0 гарантировано только в одной точке - при t = 0.5.
Например, осмысли следующее : p(Г_1(0 Г_2(0 = расстояние между концом и началом пути != 0.

muto

да, всё правильно. Я сразу не вник.

naami_moloko

С другой стороны любой граф возможно вложить в R3 без самопересечений, а там взять индуцированную метрику, но это такое, геoм. решение...

UltraLoko

доопределяем линейно

Вместо доопределения линейно можно оставить кусочно постоянную функцию. Она будет лежать в пространстве Скорохода и там есть метрика Скорохода. Могу написать поподробнее...
Оставить комментарий
Имя или ник:
Комментарий: