Вершинная задача k -центра

Задача вершинного k- центра - это классическая NP-сложная задача в информатике . Он имеет применение в размещении объектов и кластеризации . ^[1]^[2] По сути, задача вершинного k- центра моделирует следующую реальную задачу: задан город с ${\ displaystyle n}$ удобства, найди лучшее ${\ displaystyle k}$ объекты, где строить пожарные депо. Поскольку пожарные должны проявлять чрезвычайную помощь как можно быстрее, расстояние от самого дальнего объекта до ближайшего пожарного депо должно быть как можно меньшим. Другими словами, расположение пожарных депо должно быть таким, чтобы устранять все возможные пожары как можно быстрее.

Формальное определение

Задача вершинного k- центра является классической NP-трудной задачей в информатике . Впервые она была предложена Хакими в 1964 году. ^[3] Формально проблема вершинного k -центра состоит в следующем: задан полный неориентированный граф ${\ Displaystyle G = (V, E)}$ в метрическом пространстве и положительное целое число ${\ displaystyle k}$ , найдите подмножество ${\ Displaystyle C \ substeq V}$ такой, что ${\ displaystyle | C | \ leq k}$ и целевая функция ${\ Displaystyle г (С) = \ макс _ {v \ in V} \ {d (v, C) \}}$ сводится к минимуму. Расстояние ${\ displaystyle d (v, C)}$ определяется как расстояние от вершины ${\ displaystyle v}$ до ближайшего центра в ${\ displaystyle C}$ .

Алгоритмы аппроксимации

Если ${\ Displaystyle P \ neq NP}$ , задача вершинного k -центра не может быть (оптимально) решена за полиномиальное время. Однако есть несколько алгоритмов с полиномиальным временем, которые близки к оптимальным решениям. В частности, 2-приближенные решения . Собственно, если ${\ Displaystyle P \ neq NP}$ наилучшее возможное решение, которое может быть достигнуто с помощью алгоритма с полиномиальным временем, - это 2-приближенное решение. ^[4]^[5]^[6]^[7] В контексте задачи минимизации, такой как проблема вершинного k- центра, 2-приближенное решение - это любое решение ${\ displaystyle C '}$ такой, что ${\ Displaystyle г (С ') \ Leq 2 \ раз г ({\ текст {OPT}})}$ , куда ${\ displaystyle r ({\ text {OPT}})}$ размер оптимального решения. Алгоритм, который гарантирует генерацию 2-приближенных решений, известен как алгоритм 2-приближения. Основными 2-приближенными алгоритмами для задачи вершинного k- центра, описанными в литературе, являются алгоритм Sh, ^[8] алгоритм HS, ^[7] и алгоритм Гона. ^[5]^[6] Несмотря на то, что эти алгоритмы являются (полиномиальными) наилучшими из возможных, их производительность на большинстве наборов данных тестов очень низка. Из-за этого с течением времени было разработано множество эвристик и метаэвристик . Вопреки здравому смыслу одна из наиболее практичных (полиномиальных) эвристик для вершины k-центровая задача основана на алгоритме CDS, который является 3-приближенным алгоритмом ^[9]

Алгоритм Sh

Алгоритм Sh, формально охарактеризованный Дэвидом Шмойсом в 1995 г. ^[8] , принимает в качестве входных данных полный неориентированный граф. ${\ Displaystyle G = (V, E)}$ , положительное целое число ${\ displaystyle k}$ , и предположение ${\ displaystyle r}$ от того, каков оптимальный размер решения. Алгоритм Sh работает следующим образом: выбирает первый центр ${\ displaystyle c_ {1}}$ случайно. Пока решение состоит только из одной вершины, ${\ Displaystyle C = \ {c_ {1} \}}$ . Далее выбирает центр ${\ displaystyle c_ {2}}$ случайным образом из множества, содержащего все вершины, удаленные от ${\ displaystyle C}$ больше, чем ${\ displaystyle 2 \ times r}$ . На этой точке, ${\ Displaystyle C = \ {c_ {1}, c_ {2} \}}$ . Наконец, выбирает оставшиеся ${\ displaystyle k-2}$ центры точно так же ${\ displaystyle c_ {2}}$ был выбран. Сложность алгоритма Sh составляет ${\ displaystyle O (kn)}$ , куда ${\ displaystyle n}$ количество вершин.

Алгоритм HS

Предложенный Дорит Хохбаум и Дэвидом Шмойсом в 1985 году алгоритм HS берет за основу алгоритм Sh. ^[7] Заметив, что ценность ${\ displaystyle r ({\ text {OPT}})}$ должна быть равна стоимости некоторого преимущества в ${\ displaystyle E}$ , а так как есть ${\ Displaystyle О (п ^ {2})}$ края в ${\ displaystyle E}$ , алгоритм HS в основном повторяет алгоритм Sh с каждой стоимостью ребра. Сложность алгоритма HS составляет ${\ Displaystyle О (п ^ {4})}$ . Однако, выполняя двоичный поиск по упорядоченному набору граничных затрат, его сложность снижается до ${\ Displaystyle О (п ^ {2} \ журнал п)}$ .

Алгоритм Гона

Предлагаемые независимо друг от друга Теофило Гонсалес , ^[5] и Мартин Дайер и Алан Фриз ^[6] в 1985 году, алгоритм Гон в основном более мощная версия алгоритма Sh. Хотя алгоритм Sh требует предположения ${\ displaystyle r}$ на ${\ displaystyle r ({\ text {OPT}})}$ , алгоритм Гона предупреждает о таком предположении, замечая, что если любой набор вершин на расстоянии больше, чем ${\ displaystyle 2 \ times r ({\ text {OPT}})}$ существует, то самая дальняя вершина должна находиться внутри такого множества. Следовательно, вместо вычисления на каждой итерации набора вершин на расстоянии, превышающем ${\ displaystyle 2 \ times r}$ а затем выбирая случайную вершину, алгоритм Гона просто выбирает самую дальнюю вершину из каждого частичного решения ${\ displaystyle C '}$ . Сложность алгоритма Гона составляет ${\ displaystyle O (kn)}$ , куда ${\ displaystyle n}$ количество вершин.

Алгоритм CDS

Предложено Гарсиа Диасом и др. в 2017 г. ^[9] алгоритм CDS представляет собой алгоритм с 3 приближениями, который берет идеи из алгоритма Гона (эвристика самой дальней точки), алгоритма HS (параметрическое отсечение) и взаимосвязи между задачей k- центра вершины и доминирующим множеством. проблема. Алгоритм CDS имеет сложность ${\ Displaystyle О (п ^ {4})}$ . Однако, выполняя двоичный поиск по упорядоченному набору стоимостей ребер, предлагается более эффективная эвристика с именем CDSh. Сложность алгоритма CDSh составляет ${\ Displaystyle О (п ^ {2} \ журнал п)}$ . Несмотря на неоптимальную производительность алгоритма CDS и эвристическую производительность CDSh, оба они имеют гораздо лучшую производительность, чем алгоритмы Sh, HS и Gon.

Экспериментальное сравнение

Некоторые из наиболее широко используемых эталонных наборов данных для задачи вершинного k -центра - это экземпляры pmed из OR-Lib., ^[10] и некоторые экземпляры из TSP-Lib. ^[11] Таблица 1 показывает среднее значение и стандартное отклонение экспериментальных коэффициентов аппроксимации решений, сгенерированных каждым алгоритмом для 40 экземпляров pmed из OR-Lib ^[9]

Таблица 1. Коэффициент экспериментальной аппроксимации для экземпляров pmed из OR-Lib
Алгоритм	${\ displaystyle \ mu}$	${\ displaystyle \ sigma}$	Сложность
HS	1,532	0,175	${\ Displaystyle О (п ^ {2} \ журнал п)}$
Гон	1,503	0,122	${\ displaystyle O (kn)}$
CDSh	1.035	0,031	${\ Displaystyle О (п ^ {2} \ журнал п)}$
CDS	1.020	0,027	${\ Displaystyle О (п ^ {4})}$

Таблица 2. Фактор экспериментальной аппроксимации по экземплярам из TSP-Lib
Алгоритм	${\ displaystyle \ mu}$	${\ displaystyle \ sigma}$	Алгоритм
Гон	1,396	0,091	${\ displaystyle O (kn)}$
HS	1,318	0,108	${\ Displaystyle О (п ^ {2} \ журнал п)}$
CDSh	1,124	0,065	${\ Displaystyle О (п ^ {2} \ журнал п)}$
CDS	1.042	0,038	${\ Displaystyle О (п ^ {4})}$

Полиномиальная эвристика

Жадный чистый алгоритм

Жадный чистый алгоритм (или Gr) следует основной идее жадных алгоритмов : принимать оптимальные локальные решения. В случае задачи вершинного k -центра оптимальное локальное решение состоит в выборе каждого центра таким образом, чтобы размер решения (радиус покрытия) был минимальным на каждой итерации. Другими словами, первый выбранный центр - это тот, который решает проблему с одним центром. Второй выбранный центр - это тот, который вместе с предыдущим центром создает решение с минимальным радиусом покрытия. Остальные центры выбираются таким же образом. Сложность алгоритма Gr составляет ${\ displaystyle O (kn ^ {2})}$ . ^[12] Эмпирическая производительность алгоритма Gr в большинстве тестовых примеров оставляет желать лучшего.

Алгоритм подсчета очков

Алгоритм подсчета очков (или Scr) был введен Юрием Михеличем и Борутом Робичем в 2005 году. ^[13] Этот алгоритм использует преимущество редукции от задачи k -центра вершины до задачи минимального доминирующего множества. Проблема решается путем отсечения входного графа до всех возможных значений оптимального размера решения и последующего эвристического решения задачи с минимальным доминирующим набором. Эта эвристика следует ленивому принципу, который принимает каждое решение как можно медленнее (в отличие от жадной стратегии). Сложность алгоритма Scr составляет ${\ Displaystyle О (п ^ {4})}$ . Эмпирическая производительность алгоритма Scr очень хорошая на большинстве тестовых примеров. Однако его время работы быстро становится непрактичным по мере роста входных данных. Так что, похоже, это хороший алгоритм только для небольших случаев.

Ссылки

^ Пачеко, Хоакин А .; Касадо, Сильвия (декабрь 2005 г.). «Решение двух моделей местоположения с небольшим количеством средств обслуживания с использованием гибридной эвристики: реальный случай ресурсов здравоохранения». Компьютеры и исследования операций . 32 (12): 3075–3091. DOI : 10.1016 / j.cor.2004.04.009 . ISSN 0305-0548 .
^ Kaveh, A .; Наср, Х. (август 2011 г.). «Решение проблемы условного и безусловного центра с помощью модифицированного поиска гармонии: реальный пример» . Scientia Iranica . 18 (4): 867–877. DOI : 10.1016 / j.scient.2011.07.010 . ISSN 1026-3098 .
^ Хакими, SL (1964). «Оптимальные положения центров коммутации и абсолютных центров и медиан графа». Исследование операций . 12 (3): 450–459. DOI : 10.1287 / opre.12.3.450 . JSTOR 168125 .
^ Карив, O .; Хакими, SL (декабрь 1979 г.). «Алгоритмический подход к проблемам сетевого размещения. I: p-центры». Журнал SIAM по прикладной математике . 37 (3): 513–538. DOI : 10.1137 / 0137040 . ISSN 0036-1399 .
^ a b c Гонсалес, Теофило Ф. (1985). «Кластеризация для минимизации максимального межкластерного расстояния» . Теоретическая информатика . 38 : 293–306. DOI : 10.1016 / 0304-3975 (85) 90224-5 . ISSN 0304-3975 .
^ a b c Дайер, Мэн; Frieze, AM (февраль 1985 г.). «Простая эвристика для проблемы p-центра». Письма об исследовании операций . 3 (6): 285–288. DOI : 10.1016 / 0167-6377 (85) 90002-1 . ISSN 0167-6377 .
^ a b c Hochbaum, Dorit S .; Шмойс, Дэвид Б. (май 1985 г.). «Лучшая возможная эвристика для проблемы k- центра». Математика исследования операций . 10 (2): 180–184. DOI : 10.1287 / moor.10.2.180 . ISSN 0364-765X .
^ a b Шмойс, Дэвид Б. (1995). Вычисление почти оптимальных решений комбинаторных задач оптимизации . В области комбинаторной оптимизации, рядов Димака в дискретной математике и теоретической информатике . Серия DIMACS по дискретной математике и теоретической информатике. 20 . С. 355––397. CiteSeerX 10.1.1.33.1719 . DOI : 10.1090 / dimacs / 020/07 . ISBN 9780821802397.
^ a b c Гарсиа-Диас, Иисус; Санчес-Эрнандес, Хайро; Менчака-Мендес, Рикардо; Менчака-Мендес, Роландо (01.07.2017). «Когда худший коэффициент аппроксимации дает лучшую производительность: алгоритм с 3 приближениями для задачи k- центра вершины ». Журнал эвристики . 23 (5): 349–366. DOI : 10.1007 / s10732-017-9345-х . ISSN 1381-1231 .
Перейти ↑ Beasley, JE (1990). «OR-Library: рассылка тестовых заданий по электронной почте». Журнал Общества оперативных исследований . 41 (11): 1069–1072. DOI : 10.2307 / 2582903 . JSTOR 2582903 .
^ Райнельт, Герхард (ноябрь 1991). «TSPLIB - Библиотека задач коммивояжера». ORSA Journal on Computing . 3 (4): 376–384. DOI : 10.1287 / ijoc.3.4.376 . ISSN 0899-1499 .
^ Рана, Ротанг; Гарг, Дипак (март 2009 г.). Эвристические подходы к проблеме k- центра . 2009 Международная конференция по передовым вычислениям IEEE . IEEE. DOI : 10.1109 / iadcc.2009.4809031 . ISBN 9781424429271.
^ Михелич, Юрий; Робич, Борут (2005). « Эффективное решение задачи k- центра с помощью алгоритма доминирующего множества» . Журнал вычислительной техники и информационных технологий . 13 (3): 225. DOI : 10,2498 / cit.2005.03.05 . ISSN 1330-1136 .

[1] Пачеко, Хоакин А .; Касадо, Сильвия (декабрь 2005 г.). «Решение двух моделей местоположения с небольшим количеством средств обслуживания с использованием гибридной эвристики: реальный случай ресурсов здравоохранения». Компьютеры и исследования операций . 32 (12): 3075–3091. DOI : 10.1016 / j.cor.2004.04.009 . ISSN 0305-0548 .

[2] Kaveh, A .; Наср, Х. (август 2011 г.). «Решение проблемы условного и безусловного центра с помощью модифицированного поиска гармонии: реальный пример» . Scientia Iranica . 18 (4): 867–877. DOI : 10.1016 / j.scient.2011.07.010 . ISSN 1026-3098 .

[3] Хакими, SL (1964). «Оптимальные положения центров коммутации и абсолютных центров и медиан графа». Исследование операций . 12 (3): 450–459. DOI : 10.1287 / opre.12.3.450 . JSTOR 168125 .

[4] Карив, O .; Хакими, SL (декабрь 1979 г.). «Алгоритмический подход к проблемам сетевого размещения. I: p-центры». Журнал SIAM по прикладной математике . 37 (3): 513–538. DOI : 10.1137 / 0137040 . ISSN 0036-1399 .

[Gonzalez_1985-5] Гонсалес, Теофило Ф. (1985). «Кластеризация для минимизации максимального межкластерного расстояния» . Теоретическая информатика . 38 : 293–306. DOI : 10.1016 / 0304-3975 (85) 90224-5 . ISSN 0304-3975 .

[Dyer_1985-6] Дайер, Мэн; Frieze, AM (февраль 1985 г.). «Простая эвристика для проблемы p-центра». Письма об исследовании операций . 3 (6): 285–288. DOI : 10.1016 / 0167-6377 (85) 90002-1 . ISSN 0167-6377 .

[Hochbaum_1985-7] Hochbaum, Dorit S .; Шмойс, Дэвид Б. (май 1985 г.). «Лучшая возможная эвристика для проблемы k- центра». Математика исследования операций . 10 (2): 180–184. DOI : 10.1287 / moor.10.2.180 . ISSN 0364-765X .

[Shmoys_1995-8] Шмойс, Дэвид Б. (1995). Вычисление почти оптимальных решений комбинаторных задач оптимизации . В области комбинаторной оптимизации, рядов Димака в дискретной математике и теоретической информатике . Серия DIMACS по дискретной математике и теоретической информатике. 20 . С. 355––397. CiteSeerX 10.1.1.33.1719 . DOI : 10.1090 / dimacs / 020/07 . ISBN 9780821802397.

[Garcia-Diaz_2017-9] Гарсиа-Диас, Иисус; Санчес-Эрнандес, Хайро; Менчака-Мендес, Рикардо; Менчака-Мендес, Роландо (01.07.2017). «Когда худший коэффициент аппроксимации дает лучшую производительность: алгоритм с 3 приближениями для задачи k- центра вершины ». Журнал эвристики . 23 (5): 349–366. DOI : 10.1007 / s10732-017-9345-х . ISSN 1381-1231 .

[10] Перейти ↑ Beasley, JE (1990). «OR-Library: рассылка тестовых заданий по электронной почте». Журнал Общества оперативных исследований . 41 (11): 1069–1072. DOI : 10.2307 / 2582903 . JSTOR 2582903 .

[11] Райнельт, Герхард (ноябрь 1991). «TSPLIB - Библиотека задач коммивояжера». ORSA Journal on Computing . 3 (4): 376–384. DOI : 10.1287 / ijoc.3.4.376 . ISSN 0899-1499 .

[12] Рана, Ротанг; Гарг, Дипак (март 2009 г.). Эвристические подходы к проблеме k- центра . 2009 Международная конференция по передовым вычислениям IEEE . IEEE. DOI : 10.1109 / iadcc.2009.4809031 . ISBN 9781424429271.

[13] Михелич, Юрий; Робич, Борут (2005). « Эффективное решение задачи k- центра с помощью алгоритма доминирующего множества» . Журнал вычислительной техники и информационных технологий . 13 (3): 225. DOI : 10,2498 / cit.2005.03.05 . ISSN 1330-1136 .

[1]