2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Оптимизация на графах
Сообщение15.09.2022, 13:07 


07/03/11
694
Подскажите, пожалуйста, как решать следующую прикладную задачу.
Пусть задан связный граф $G=(V, E)$ и отображение $c\colon V \to \mathbb R ^2$. Расстоянием $d\colon \mathbb R^2 \times E \to \mathbb R$ от точки $x\in \mathbb R^2$ до ребра $e=(v_1, v_2)\in E$ будем считать кратчайшее расстояние от $x$ до отрезка $[c(v_1), c(v_2)]$ в эвклидовой метрике. Расстоянием $d\colon \mathbb R^2 \times 2^G \to \mathbb R$ от точки $x\in \mathbb R^2$ до графа $G \in 2^G$ будет расстояние до ближайшего ребра $e\in G_E$, т.е. $d(x, G) = \min _{e\in G_E} d(x, e)$.
Для заданного набора точек $X=(x_1,..., x_n)$ нужно найти связный подграф $G'$ графа $G$ такой, чтоб суммарное расстояние от этих точек до $G'$ было минимальным.
Очевидно, что решений будет много, в том числе и тривиальное $G' = G$. Чтоб сделать решение единственным, введем регуляризацию на количество ребер в $G'$:
$$\arg \min _{G'\subset G}\sum _{x\in X}d(x, G') + \lambda |E_{G'}|,$$
где $\lambda > 0$ будет задаваться пользователем.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Padawan


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group