2014 dxdy logo

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

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




 
 Оптимизация на графах
Сообщение15.09.2022, 13:07 
Подскажите, пожалуйста, как решать следующую прикладную задачу.
Пусть задан связный граф $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 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group