정점 k-중심 문제

이 글은 고아로, 다른 어떤 기사도 그것에 연결되지 않는다.관련 문서에서 이 페이지에 대한 링크를 소개하고, 제안사항을 보려면 링크 찾기 도구를 사용하십시오.(2018년 11월)

정점 k-center 문제는 컴퓨터 과학의 고전적인 NP-hard 문제다.설비 위치와 클러스터링에 응용이 가능하다.^[1][2]기본적으로 꼭지점 k-center 문제는 다음과 같은 실제 문제를 모델링한다: $n{\displaystyle }$ ${\displaystyle n}$개의$$ 시설을 갖춘 도시를 주어진다면 소방서를 건설할 수 있는 최상의 k ${\displaystyle$ k$} 시설$을 $찾아라$.소방관들은 가능한 한 빨리 어떤 비상사태에 참가해야 하기 때문에, 가장 멀리 있는 시설에서 가장 가까운 소방서까지의 거리는 가능한 한 작아야 한다.소방서의 위치가 가능한 모든 화재가 가능한 한 빨리 참여하도록 해야 한다는 얘기다.

형식 정의

정점 k-중심 문제는 컴퓨터 과학의 고전적인 NP-하드 문제다.1964년 하키미가 처음 제안한 것이다.^[3]Formally, the vertex k-center problem consists in: given a complete undirected graph ${\displaystyle G=(V,E)}$ in a metric space, and a positive integer ${\displaystyle k}$, find a subset ${\displaystyle C\subseteq V}$ such that ${\displaystyle C \leq k}$ and the objective function $$${\displaystyle r}$( ${\displaystyle C}$)${\displaystyle }$= ${\displaystyle \underset{}{최대}}$ ${\displaystyle \underset{}{v}}$∈ ${\displaystyle \underset{}{V}}${ ${\displaystyle d(v}$, C${\displaystyle }$) ${\displaystyle \}}$ ${\displaystyle$r($C)=\max_{v\in$ V$}\{d(v,C)\}}}$은(는) 최소화된다$$.$d{\displaystyle (v}$, ${\displaystyle C}$) ${\displaystyle d(v,C)}$ 거리는 꼭지점 $v{\displaystyle }$ ${\displaystyle v}$에서 $C{\displaystyle }$ ${\displaystyle C}$의 가장 가까운 중심까지의$$ 거리로 정의된다$.$

근사 알고리즘

$P{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle N}$ ${\displaystyle P}$ ${\displaystyle P\neq NP}$인 경우$,$ 정점 k-center 문제는 다항 시간 내에 (최적적으로) 해결될 수 없다.그러나 최적 솔루션에 근접하는 일부 다항식 시간 알고리즘이 있다.구체적으로는 2개 정도의 시효용액.실제로 $P{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle N}$ P ${\displaystyle P\neq NP}$이(가) 다항 시간 알고리즘을 통해 달성할 수 있는 최선의 해결책은$$ 2-추정 솔루션이다.^[4][5][6][7]정점 k-center 문제와 같은 최소화 문제의 맥락에서, 2-추정 솔루션은 $r{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle \prime }$ ) ${\displaystyle \le }$ 2${\displaystyle x}$ r${\displaystyle }$(${\displaystyle \text{OPT}}$ )${\displaystyle r(C')\leq 2\time$ r$({\text${\text$})$과 같은 솔루션 $C{\displaystyle {}^{}}$′ ${\$이다.$OPT$ $여기$서 r${\displaystyle (\text{OPT}}$) ${\displaystyle$ r$({\text}){$$OPT})}$은(는) 최적의 솔루션 크기 입니다.2-추정 솔루션 생성을 보장하는 알고리즘은 2-추정 알고리즘으로 알려져 있다.문헌에 보고된 정점 k-center 문제에 대한 주요 2-추정 알고리즘은 Sh 알고리즘,^[8] HS 알고리즘,^[7] Gon 알고리즘이다.^[5][6]이러한 알고리즘이 (다항식) 최선의 알고리즘이지만 대부분의 벤치마크 데이터셋에서 성능이 매우 부족하다.이 때문에 많은 휴리스틱스, 메타휴리스틱스 등이 시대를 거치면서 발전해 왔다.상식과 달리 정점 k-center 문제에 대한 가장 실용적인(폴리노멀) 휴리스틱스 중 하나는 3-추정 알고리즘인^[9] CDS 알고리즘을 기반으로 한다.

슈 알고리즘

1995년 David Shmoys에 의해 공식적으로 특징지어지는 Sh 알고리즘은 $완전$한 비방향 그래프 G${\displaystyle }$= ${\displaystyle (V}$, E${\displaystyle }$) ${\displaystyle G=(V,E$ 양수 $k{\displaystyle }$ ${\displaystyle$ k$\},$ 최적 솔루션 크기가 무엇인지에 대한$$ $가정{\displaystyle }$ r ${\displaystyle r}$을 입력으로 한다.^[8]Sh 알고리즘은 다음과 같이 동작한다: 첫 번째 중심 $c{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}를 임의로$$ 선택한다.So far, the solution consists of only one vertex, ${\displaystyle C=\{c_{1}\}}$. Next, selects center ${\displaystyle c_{2}}$ at random from the set containing all the vertices whose distance from ${\displaystyle C}$ is greater than ${\displaystyle 2\times r}$. At this point, ${\displaystyle C=\{c_{}}$${\displaystyle 1_{}}$,${\displaystyle {}_{}}$c ${\displaystyle {2\mathrm{}}_{}}$} ${\displaystyle$ C$=\{c_{1},$${\displaystyle \mathrm{c\_}}$${2$ 마지막으로 c ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle k-2}$ 중심을$$ c 2 ${\$2}}$개가$ 선택된$$ 것과 동일하게 $선택$한다${\displaystyle .}$Sh 알고리즘의 복잡성은 $O{\displaystyle }$ (${\displaystyle k}$ ${\displaystyle n}$ )${\displaystyle O(kn)}$이며$,$ 여기서 $n{\displaystyle }$ ${\displaystyle n}$은 정점의 수입니다.

HS 알고리즘

1985년 도릿 ^[7]호치바움과 데이비드 슈모이스가 제안한 HS 알고리즘은 Sh 알고리즘을 기본으로 한다.$r{\displaystyle (\text{OPT}}$) ${\displaystyle$ r$({\text${\text$})$의 값을 알아냄으로써$OPT})}$은(는) $E{\displaystyle }$ ${\displaystyle E}$의 일부 에지 비용과 같아야 하며$$$,$ $E{\displaystyle }$ ${\displaystyle E}$에 $O{\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle O(n^{2})$ 에지가$$ 있기 때문에 HS 알고리즘은 기본적으로 모든 에지 비용으로 Sh 알고리즘을 반복한다$.$HS 알고리즘의 복잡성은 $O{\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle$ O $(n^{4$ 그러나 순서화된 에지 비용 집합에 대해 바이너리 검색을 실행함으로써 복잡성은 $O{\displaystyle }$ ${\displaystyle ({n\mathrm{}}^{}}$ 2 ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle$O ($n^{$2}\$log n)}$로 감소한다$.$

곤 알고리즘

테오필로 곤잘레스가 독자적으로 제안하고 ^[5]마틴 다이어와 앨런 프리제가^[6] 1985년에 제안한 곤 알고리즘은 기본적으로 슈 알고리즘의 보다 강력한 버전이다.Sh $알고리즘$에 $r{\displaystyle (\text{OPT})}$${\$$displaystyle r({\text{)$의 추측 r {\$displaystyle r}$이 필요한 반면$OPT}}},$Gon 알고리즘은 $2{\displaystyle \mathrm{}}$×${\displaystyle r}$ ($){\displaystyle$2\$time$ r$({\$text{\$text})$보다 큰 거리에 정점 집합이 있는 경우 그러한 추측으로부터 지시한다.$OPT})}$이(가) 존재하며$$, 그러면 가장 먼 꼭지점이 그러한 집합 안에 있어야 한다.따라서 각 반복에서 ${\displaystyle 2}$ ${\displaystyle \times }$ r$[\displaystyle 2\time r}$보다 큰 거리의 정점 집합을 계산한 다음$$ 무작위 정점을 선택하는 대신에 Gon 알고리즘은 모든 부분 $솔루션{\displaystyle {}^{}}$ C ${\displaystyle {\prime }^{}}$ ${\$ C$'}$에서 가장 먼 정점을 선택한다$.$ Gon 알고리즘의 복잡성은 O${\displaystyle }$( ${\displaystyle k}$ ${\displaystyle n}$ )${\displa$.$ystyle O(kn$ 여기서 $n{\displaystyle }$ ${\displaystyle n}$은 정점의 수입니다.

CDS 알고리즘

2017년 Garcia Diaz 등이 제안한 CDS 알고리즘은 Gon 알고리즘(가장 빠른 지점 휴리스틱), HS 알고리즘(모수 프루닝), 정점 k-center 문제와 Leaking Set 문제의 관계에서 아이디어를 얻는 3-대략 알고리즘이다.^[9]CDS 알고리즘은 $O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {4\mathrm{}}^{}}$) ${\displaystyle O(n^{4})$의 복잡성을 가지고 있지만$,$ 순서화된 에지 비용 집합에 대해 바이너리 검색을 수행함으로써 CDSh라는 보다 효율적인 휴리스틱스를 제안한다.CDSh 알고리즘의 복잡성은 $O{\displaystyle ({n\mathrm{}}^{}}$ 2 ${\displaystyle \log }$ $){\displaystyle O(n^{2}\logn)}$이다$.$ CDSh 알고리즘의 차최적 성능 및 CDSh의 경험적 성능에도 불구하고, 둘 다 Sh, HS, Gon 알고리즘보다 훨씬 나은 성능을 나타낸다.

실험비교

정점 k-center 문제에 대해 가장 널리 사용되는 벤치마크 데이터셋 중 일부는 OR-Lib의 ped 인스턴스,^[10] 일부는 TSP-Lib의 인스턴스들이다.^[11]표 1은 OR-Lib에서^[9] 40개의 ped 인스턴스(instance)에 걸쳐 각 알고리즘에 의해 생성된 솔루션의 실험 근사치 인자의 평균 및 표준 편차를 보여준다.

표 1.

알고리즘.	$\displaystyle \mu }$	$\displaystyle \sigma }$	복잡성
HS	1.532	0.175	${\displaystyle O(n^{2}\log n)}$
곤	1.503	0.122	$O(kn)}$
CDSh	1.035	0.031	${\displaystyle O(n^{2}\log n)}$
CDS	1.020	0.027	${\displaystyle O(n^{4})}$

표 2.

알고리즘.	$\displaystyle \mu }$	$\displaystyle \sigma }$	알고리즘.
곤	1.396	0.091	$O(kn)}$
HS	1.318	0.108	${\displaystyle O(n^{2}\log n)}$
CDSh	1.124	0.065	${\displaystyle O(n^{2}\log n)}$
CDS	1.042	0.038	${\displaystyle O(n^{4})}$

다항식 휴리스틱스

탐욕스러운 순수 알고리즘

탐욕스러운 순수 알고리즘(또는 Gr)은 탐욕스러운 알고리즘의 핵심 아이디어를 따른다. 즉, 최적의 지역적 의사결정을 하는 것이다.정점 k-center 문제의 경우 최적의 국소적 결정은 각 반복에서 용액의 크기(덮는 반지름)가 최소가 되도록 각 중심을 선택하는 데 있다.즉, 첫 번째로 선정된 센터가 1-센터 문제를 해결하는 센터라는 것이다.선택된 두 번째 센터는 이전 센터와 함께 최소 커버 반경의 용액을 생성하는 센터다.나머지 센터도 같은 방식으로 선택된다.Gr 알고리즘의 복잡성은 $O{\displaystyle }$( ${\displaystyle k}$ ${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(kn^{2})$ 입니다$.$^[12]Gr 알고리즘의 경험적 성능은 대부분의 벤치마크 사례에서 좋지 않다.

스코어링 알고리즘

스코어링 알고리즘(또는 Scr)은 쥬리 미헬리치와 보루트 로비치가 2005년에 도입했다.^[13]이 알고리즘은 정점 k-center 문제에서 최소 지배적 집합 문제로의 축소를 활용한다.최적 솔루션 크기의 가능한 모든 값으로 입력 그래프를 가지런히 치운 다음 최소 지배적인 세트 문제를 경험적으로 해결함으로써 문제를 해결한다.이 휴리스틱은 모든 결정을 가능한 한 느리게(욕심 많은 전략에 편승)하는 게으른 원칙을 따른다.Scr 알고리즘의 복잡성은 $O{\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$ 4${\displaystyle {}^{}}$) ${\displaystyle O(n^{4})}$ 입니다$.$Scr 알고리즘의 경험적 성능은 대부분의 벤치마크 사례에서 매우 우수하다.그러나, 그것의 가동 시간은 입력의 증가에 따라 빠르게 비현실적이 된다.그래서, 그것은 작은 경우에 대해서만 좋은 알고리즘인 것 같다.

참조