Приближённый алгоритм поиска p-медиан

Эвристический метод для нахождения p-медианы состоит в следующем: случайным образом выбираются $p$$p$ вершин, они образуют начальное множество $S$$S$, аппроксимирующее p-медианное множество $X_p^{\ast <!--\; \ast \; -->}$$X_{p}^{*}$. Затем выясняется, может ли некоторая вершина $x_j\in <!--\; \in \; -->X\setminus <!--\; \setminus \; -->S$$x_{j}\in X\setminus S$ заменить вершину $x_i\in <!--\; \in \; -->S$$x_{i}\in S$ (как медианная вершина), для чего строят новое множество $S^{\ast <!--\; \ast \; -->}=(S\cup <!--\; \cup \; -->x_j)\setminus <!--\; \setminus \; -->x_i$$S^{*}=(S\cup {x_{j}})\setminus {x_{i}}$ и сравнивают передаточные числа $\mathrm{\sigma <!--\; \sigma \; -->}(S^{\ast <!--\; \ast \; -->})$$\sigma (S^{*})$ и $\mathrm{\sigma <!--\; \sigma \; -->}(S)$$\sigma (S)$. Если $\sigma (S^{*})<\sigma (S)$, то $S$$S$ заменяют на $S^{\ast <!--\; \ast \; -->}$$S^{*}$, которое лучше аппроксимирует p-медианное множество $X_p^{\ast <!--\; \ast \; -->}$$X_{p}^{*}$. Затем аналогично исследуется множество $S^{\ast <!--\; \ast \; -->}$$S^{*}$ и т. д., пока не будет построено множество $S$$S$', которое нельзя будет изменить по вышеуказанному принципу.

АлгоритмПравить

Шаг 1. Выбрать некоторое множество $S$$S$  из p вершин в качестве начального приближения к p-медиане. И назовём все вершины $x_i\notin <!--\; \notin \; -->S$$x_{i}\notin S$  «неопробованными».

Шаг 2. Взять произвольную «неопробованную» вершину и для каждой вершины $x_i\in <!--\; \in \; -->S$$x_{i}\in S$  вычислить «приращение» Δij, соответствующие замене вершины $x_i$$x_i$  вершиной $x_j$$x_{j}$ , то есть вычислить ${\mathrm{\Delta <!--\; \Delta \; -->}}_{ij}=\mathrm{\sigma <!--\; \sigma \; -->}(S)-<!--\; -\; -->\mathrm{\sigma <!--\; \sigma \; -->}((S\cup <!--\; \cup \; -->x_j)\setminus <!--\; \setminus \; -->x_i)$$\Delta _{ij}=\sigma (S)-\sigma ((S\cup {x_{j}})\setminus {x_{i}})$ .

Шаг 3. Найти ${\mathrm{\Delta <!--\; \Delta \; -->}}_{i^{1}j}=max[{\mathrm{\Delta <!--\; \Delta \; -->}}_{ij}]$$\Delta _{i^{1}j}=max[\Delta _{ij}]$  по всем $x_i\in <!--\; \in \; -->S$$x_{i}\in S$ .

а) Если ${\mathrm{\Delta <!--\; \Delta \; -->}}_{i^{1}j}\le <!--\; \le \; -->0$$\Delta _{i^{1}j}\leq 0$ , то назвать вершину $x_j$$x_{j}$  «опробованной» и перейти к шагу 2.

б) Если ${\mathrm{\Delta <!--\; \Delta \; -->}}_{i^{i}j}\ge <!--\; \ge \; -->0$$\Delta _{i^{i}j}\geq 0$ , то $S\leftarrow <!--\; \leftarrow \; -->(S\cup <!--\; \cup \; -->x_j)\setminus <!--\; \setminus \; -->x_i$$S\gets (S\cup {x_{j}})\setminus {x_{i}}$ , назвать вершину $x_j$$x_{j}$  «опробованной» и перейти к шагу 2.

Шаг 4. Повторять шаги 2 и 3 до тех пор, пока все вершины из $X\setminus <!--\; \setminus \; -->S$$X\setminus S$  не будут опробованы. Эта процедура оформляется как цикл. Если при выполнении последнего цикла совсем не будет замещений вершин на шаге 3(a), то перейти к шагу 5. В противном случае, то есть если осуществлено некоторое замещение, назвать все вершины «неопробованными» и вернуться к шагу 2.

Шаг 5. Стоп. Текущее множество $S$$S$  является подходящей аппроксимацией p-медианного множества $X_p^{\ast <!--\; \ast \; -->}$$X_{p}^{*}$ .

ПримерПравить

Легко заметить, что приведённый выше алгоритм не во всех случаях даёт оптимальный ответ. Рассмотрим пример (числа, стоящие около рёбер, равны соответствующим рёберным стоимостям, все вершины одинакового единичного веса):

 

Если искать 2-медиану и в качестве начального множества S взять {x3, x6} с передаточным числом $\mathrm{\sigma <!--\; \sigma \; -->}(S)=8$$\sigma (S)=8$ , то никакое замещение только одной вершины не приводит к множеству с меньшим передаточным числом. Однако множество {x3, x6} не является 2-медианой данного графа, так как существуют два 2-медианных множества с передаточным числом 7: {x1, x4} и {x2, x5}.

ЛитератураПравить

• Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
• Э. Майника. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981. — 324 с.

СсылкиПравить

• Медиана графа
• Визуализатор
• Размещение медиан