Посоветуйте с мат-формализмом алгоритма.

[MGM]

Есть алгоритм, работающий с заданным графом. $G = \left\{ {V,E} \right\}$
Алгоритм близкий по реализации к схеме классического Breadth-first search (BFS).
Разница: ребра имеют разные веса, целевая функция: значение наикратчайшего расстояния от корня графа ко всем вершинам. Алгоритм итеративный. С неизвестным числом шагов сходимости.
Требует доказательства нескольких утверждений относительно результатов работы алгоритма.
Два вопроса:
1. Eсть ли такой алгоритм помимо моего? Я знаю несколько эвристических алгоритмов, которые не являются точными и реализованы они на регулярных графах. И хотя журналы, где опубликованны такие алгоритмы дастаточно рейтинговые, у меня есть сомнение, что кто-то из математиков не решил эту проблему в рамках совсем другой задачи.
2. Проще всего для меня было бы доказать утверждения, описав алгоритм в стиле Питона. Однако есть сомнение, как математики отнесутся к смешению формализма.

[mihaild]

Это классическая задача. У Кормена ("Алгоритмы: построение и анализ") про неё целая глава, так и называется "Кратчайшие пути из одной вершины". Основные алгоритмы для неё - Дейкстры, Форда-Беллмана, Флойда и $A^*$-поиск (есть еще куча модификаций).
Довольно странно, что Вы не нашли, потому что по запросу

MGM в сообщении #1598452 писал(а):

значение наикратчайшего расстояния от корня графа ко всем вершинам

гугл первой ссылкой выдает https://neerc.ifmo.ru/wiki/index.php?ti ... 0%BD%D1%83, где есть ссылка на алгоритм Дейкстры, а второй - https://www.hse.ru/data/2010/10/14/1223 ... _Graph.pdf, где он сразу описан.

MGM в сообщении #1598452 писал(а):

Проще всего для меня было бы доказать утверждения, описав алгоритм в стиле Питона. Однако есть сомнение, как математики отнесутся к смешению формализма

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

[MGM]

Спасибо за ссылку. Собственно форум альмататер меня неоднократно выручал и ранее.
Придумал алгоритм к задаче сегментации. И относительно уже опубликованных, алгоритм обладает достаточной новизной. В этой области туго с читателями учебников классической математики. Придумывают к конкретной задаче, и вперед к публикации. С другой стороны, есть очень много алгоритмов, придуманных за последние 15-20 лет, которые похожи на классические, однако, как выясняется явно лучше классических.
Алгоритм я уже опубликовал. Однако вдруг подумалось, не наваять ли мне что-то не для тех. наук, а для физ-мат. А там надо теоремки или что еще. Какие-то алгоритмы уде имеют доказательства, и явно из не самых популярных ни по формулировке задач, ни по области применения. Но хотелось бы как можно больше.

[mihaild]

Существенная часть придуманного за последние 15-20 лет - это улучшение на конкретном виде данных или архитектуре - что важно для практики, но как правило не очень интересно с точки зрения теории, потому что очень сложно сказать что-то содержательное.

MGM в сообщении #1598458 писал(а):

Алгоритм я уже опубликовал

А ссылку на публикацию не дадите?

[MGM]

С ссылкой пока туго, русскоязычный журнал опубликует статью с этим алгоритмом только через месяц, а перевод и вовсе через полгода. Да и сам алгоритм там не главное достижение. И я бы не хотел терять анонимность.
Могу дать ссылку неточный алгоритм, опубликованный в:

Pham, T. Q. (2013, November). Parallel implementation of geodesic distance transform with application in superpixel segmentation. In 2013 International Conference on Digital Image Computing: Techniques and Applications (DICTA) (pp. 1-8). IEEE.

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

mihaild в сообщении #1598455 писал(а):

Это классическая задача. ссылка на алгоритм Дейкстры, а второй - https://www.hse.ru/data/2010/10/14/1223 ... _Graph.pdf, где он сразу описан.
Впрочем - я, извините, сомневаюсь, что Вы придумали что-то лучше известного. Задача знаменитая и исследована вдоль и поперек. Если Вам интересно, правильно ли вообще придумали - то для форума сойдет и питон.

Еще раз большое спасибо за ссылки. Особенно на описание алгоритма Дейкстры. То что нужно именно с точки зрения описания алгоритмов в стиле теории множеств.
И кстати, символ $: = $например: ${D_n}: = A + B$ входит в систему классического формализма?


По поводу алгоритма Дейкстры. Он в лекциях обозначен, как (greedy). Если я не ошибаюсь, этот термин означает, что алгоритм неточный.
Кроме того, смущает сложность алгоритма $ O\left( {{v^2}} \right)$. Мой, например, $ O\left( {{v}} \right)$. Ну и отсутствие понятия связанности по ребрам и множдесва окрестности вершины.

[mihaild]

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

MGM в сообщении #1598472 писал(а):

И кстати, символ $: = $например: ${D_n}: = A + B$ входит в систему классического формализма?

А в каком контексте?
В псевдокоде - да, скорее всего всем будет понятно.

MGM в сообщении #1598472 писал(а):

Он в лекциях обозначен, как (greedy). Если я не ошибаюсь, этот термин означает, что алгоритм неточный

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

MGM в сообщении #1598472 писал(а):

Кроме того, смущает сложность алгоритма $ O\left( {{v^2}} \right)$.

В зависимости от того, как реализовывать алгоритм Дейкстры, у него получается разная сложность - если использовать кучу, то будет $O(|E| \log |V|)$, если использовать Фибоначчиеву кучу - то $O(|E| + |V|\log |V|)$. Есть всякие совсем хитрые реализации, например за $O(|E| + |V| \log \log |V|)$, но я не знаю, как они устроены.
Известен и алгоритм, работающий за $O(|E| + |V|)$ (Thorup, "Undirected Single Source Shortest Paths in Linear Time"), причем сравнительно новый - 1999 года. Но на практике он сильно сложнее и не сильно быстрее алгоритма Дейкстры.

MGM в сообщении #1598472 писал(а):

Мой, например, $ O\left( {{v}} \right)$.

Вы учитываете, что в графе рёбер может быть сильно больше, чем $v$, и нам как минимум их веса прочитать надо?

MGM в сообщении #1598472 писал(а):

Ну и отсутствие понятия связанности по ребрам и множдесва окрестности вершины

Не очень понял - это Вы про то, что в Вашем алгоритме эти понятия не нужны, или что в описании алгоритма Дейкстры они используются, но не определяются?

[MGM]

Пока не совсем разобрался, в чем глич, но алгоритм Форда-Беллмана также квадратичный отосительно вершин (разве что количество ребер явно меньше числа вершин ).
Это очень странно. Беллман один из первых авторов ДП, если не самый первый. А этот алгоритм демонстрирует глобальный матричный подход к задаче, которая может быть решена именно по принципу ДП.
Значит у меня есть шанс проскочить с моим доказательством. Если, конечно, сложность этого алгоритма имеено такая, какая обозначена https://habr.com/ru/articles/119158/.

[mihaild]

MGM в сообщении #1598475 писал(а):

алгоритм Форда-Беллмана также квадратичный отосительно вершин

Это что-то странное. Он за $O(|V|\cdot |E|)$ работает.

MGM в сообщении #1598475 писал(а):

разве что количество ребер явно меньше числа вершин

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

MGM в сообщении #1598475 писал(а):

А этот алгоритм демонстрирует глобальный матричный подход к задаче

Его можно и как ДП воспринимать - динамика по числу рёбер в пути.

MGM в сообщении #1598475 писал(а):

Если, конечно, сложность этого алгоритма имеено такая, какая обозначена

Ну в алгоритм со сложностью $O(|V|)$ я не верю совсем. В $O(|V| + |E|)$ теоретически можно поверить (такой алгоритм уже известен), но это очень серьезный результат (если Вы случайно не переоткрыли алгоритм Thorup). На это мне бы очень хотелось посмотреть.

[Null]

mihaild в сообщении #1598476 писал(а):

Ну в алгоритм со сложностью $O(|V|)$ я не верю совсем.

Можно работать с $\le2|V|$ вершинами этих ребер. Если нам не нужно перебирать все вершины(Например нужно расстояние между двумя вершинами) сложность можно получить $O(|V|)$

[mihaild]

Изначально говорилось о путях от одной вершины до всех.

Но даже если просто между двумя - я не очень представляю, как это можно сделать. Допустим что у нас полный граф на $n$ вершинах, и ребра $v_i \to v_{i + 1}$ имеют вес $1$, остальные имеют вес $2$, ищем путь из первой вершины в $n$-ю.
Тогда изменение веса любого ребра вида $v_x \to v_y$ при $x + 1 < y$ на $1$ меняет кратчайший путь, значит нам надо проверить их все. А таких ребер $\Omega(n^2)$.

[Null]

mihaild, да ошибка думал $V$ это ребра. $O(|E|)$ получается.

[MGM]

Извиняюсь, соврал. Cложность моего алгоритма (в самом деле достаточно похож на Ф-Б) для случайного веса ребер равна:
$o\left( {\frac{{\left| V \right|\left| E \right|}}{{20}}} \right)$
Поэтому верхняя оценка вполне может быть и $O\left( {{\left| V \right|\left| E \right|}} \right)$.
Просто до сих пор я свой алгоритм использовал без попытки застолбить научную новизну в области физ-мата.
А для реальных весов ребер (градиент фунции изображения) вычислительная сложность порядка:
$O\left( {{{\log }_2}\left( V \right)\left| E \right|} \right) $
Которую принял за линейное оценку (тем более, что граф в конце концов распадается на более мелкие подграфы, см ниже). Так что здесь облом с новизной.
Однако оснавная задача найти минимальные расстотояния всех вершин до ближайшей корневой вершины, которых более одной. Естественно со знанием до какой это расстояние минимальное.
Скорее всего алгоритм Ф-Б можно адаптировать и под эту задачу и наверняка кто-то уже это сделал.
Одна надежда, может быть пока никому в голову не пришло доказыать, что в результате работы такого обобщенного алгоритма , все вершины с минимальным расстоянием до какой-то конкретной корневой вершины, представляют собой связанный подграф.
Как вы думаете? Может такое быть? В смысле, что никому это ранее не потребовалось доказывать? Куда ближе доехать - задача практическая, но знание того, что все поселки, ближайшие к конкретному городу являются связанной областью, возможно никому и не надо. Или забить на публикацию такого доказательства? а попытаться доказать вот эту оценку $O\left( {{{\log }_2}\left(\left| V \right)\right|\left| E \right|} \right) $ для коррелированных данных?
Просто жалко тратить время на передоказательства.

[mihaild]

MGM в сообщении #1598662 писал(а):

$o\left( {\frac{{\left| V \right|\left| E \right|}}{{20}}} \right)$

$o$ или $O$? И обычно внутри асимптотических обозначений мультипликативные константы не пишут.

MGM в сообщении #1598662 писал(а):

А для реальных весов ребер (градиент фунции изображения) вычислительная сложность порядка:
$O\left( {{{\log }_2}\left( V \right)\left| E \right|} \right) $

Для реальных - это для вещественных, или для встречающихся на практике?

MGM в сообщении #1598662 писал(а):

Скорее всего алгоритм Ф-Б можно адаптировать и под эту задачу и наверняка кто-то уже это сделал

Да, просто в инициализации записав нулевое расстояние до всех корневых вершин.

MGM в сообщении #1598662 писал(а):

что в результате работы такого обобщенного алгоритма , все вершины с минимальным расстоянием до какой-то конкретной корневой вершины, представляют собой связанный подграф

Вы имеете в виду, что если мы зафиксировали набор корневых вершин $v_1, \ldots, v_k$, то вершины, расстояние от которых до $v_i$ меньше, чем расстояние от них же до всех остальных корневых вершин, образуют связный подграф?
Это по сложности выглядит как среднего уровня сложности задача для начального курса по алгоритмам. Я не знаю обычаев в Вашей области, но вообще не выглядит как достаточно сложный результат.

MGM в сообщении #1598662 писал(а):

а попытаться доказать вот эту оценку $O\left( {{{\log }_2}\left(\left| V \right)\right|\left| E \right|} \right) $ для коррелированных данных?

А тут я не очень понял, в чем результат, и что такое "коррелированные данные". Но время $O(|E| \log |V|)$ даёт алгоритм Дейкстры с бинарной кучей, который опять же рассказывают первокурсникам (я пытался рассказывать и с фибоначчиевой кучей, но это была плохая идея).

[MGM]

mihaild в сообщении #1598682 писал(а):

MGM в сообщении #1598662 писал(а):

а попытаться доказать вот эту оценку $O\left( {{{\log }_2}\left(\left| V \right)\right|\left| E \right|} \right) $ для коррелированных данных?

А тут я не очень понял, в чем результат, и что такое "коррелированные данные". Но время $O(|E| \log |V|)$ даёт алгоритм Дейкстры с бинарной кучей, который опять же рассказывают первокурсникам (я пытался рассказывать и с фибоначчиевой кучей, но это была плохая идея).

Проблема как раз именно в том, что область компьютерного зрения не является частью единой математической дисциплины. А сейчас и вовсе филиал нейросетевых технологий.
Технические науки.
Формально данные вещественные. Однако порождены натуральными числами. Корреляция - термин из Тервера. Степень согласованости случайной велечины с другими СВми. Вы должны знать.
Впрочем, я уже понял, что именно этот алгоритм врядли можно считать чем-то новым в классической алгоритмике.
Но у меня много публикаций, по быстым (но не точным) алгоритмам. Где есть какие-то доказателььства физ-мат характера. И куда более значимые по рейтингу журоналов, чем эта последняя игрушка с геодезическим расстоянием.
Однако повернуть это все в русло диссертации для физ-мат совета, видимо не получится.
Однако еще раз большое спасибо за поддержку дискуссии.

[mihaild]

MGM в сообщении #1598868 писал(а):

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

Насколько я понимаю, там сейчас смесь всяких сложных математических результатов, которые никем не используются, и алхимия stack more layers, которая используется на практике.

MGM в сообщении #1598868 писал(а):

Корреляция - термин из Тервера. Степень согласованости случайной велечины от других. Вы должны знать.

Это я знаю, но что с чем коррелирует - непонятно.

MGM в сообщении #1598868 писал(а):

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

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