Оптимизация на графах

[vlad_light]

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