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

Толкование

Приближенный алгоритм поиска p-медиан: Связать^?

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

Содержание

1 Алгоритм

2 Пример

3 Литература

4 Ссылки

Алгоритм

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

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

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

а) Если $\Delta_{i^{1}j} \le 0$ , то назвать вершину $x_j$ «опробованной» и перейти к шагу 2.

б) Если $\Delta_{i^{i}j} \ge 0$ , то $S \gets (S \cup {x_j}) \setminus {x_i}$ , назвать вершину $x_j$ «опробованной» и перейти к шагу 2.

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

Шаг 5. Стоп. Текущее множество $S$ является подходящей аппроксимацией p-медианного множества $X_p^*$ .

Пример

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

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

Литература

Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

Майника Э. Алгоритмы оптимизации на сетях и графах.

Ссылки

Медиана графа

Визуализатор

Размещение медиан

Категория:
Алгоритмы на графах

Игры ⚽ Поможем написать курсовую

Полезное

Смотреть что такое "Приближенный алгоритм поиска p-медиан" в других словарях:

Медиана графа — Связать? Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная. Пусть необходимо выбрать место для размещения телефонного коммутатора, электроподстанции, баз снабжения в сети дорог или… … Википедия

Пометить текст и поделиться
Искать во всех словарях
Искать в переводах
Искать в Интернете

Поделиться ссылкой на выделенное