페블 운동 문제

그래프의 조약돌 운동 문제, 즉 그래프의 조약돌 운동은 그래프에서 정점으로부터 정점으로의 여러 물체("페블스")의 이동을 다루는 그래프 이론의 관련 문제들의 집합으로, 정점을 언제든지 차지할 수 있는 조약돌의 수에 제약이 있다.페블 모션 문제는 멀티로봇 모션 계획(자갈이 로봇인 경우)과 네트워크 라우팅(자갈이 데이터의 패킷인 경우)과 같은 영역에서 발생한다.자갈모션 문제의 가장 잘 알려진 예는 한 번에 한 개의 타일을 미끄러뜨려 4x4 격자 내에서 15개의 타일 그룹을 재정렬해야 하는 유명한 15개의 퍼즐이다.

이론적 공식화

조약돌 운동 문제의 일반적인 형태는 다음과 같이 공식화된 그래프^[1] 상의 페블 운동이다.

$G{\displaystyle }$=${\displaystyle }$( ${\displaystyle V}$, ${\displaystyle E}$) ${\displaystyle G=(V,E)}$은(는) $정점$이 n$${\$displaystyle$ n$}$인 그래프가 되도록$$ 한다.$P{\displaystyle }$=${\displaystyle }${ ${\displaystyle 1}$,${\displaystyle }$… ,${\displaystyle k}$ ${\displaystyle \}}$ ${\displaystyle$ P$=\{1,\ldots,k\}}$은(는) < ${\displaystyle k<n}$이(가) 있는 조약돌의 집합이다 조약돌의 배열은 지도${\displaystyle }S{\displaystyle }$ :${\displaystyle P}$ → ${\displaystyle V}${\$displaystystyle S:$$P\rightarrow V}$ such that ${\displaystyle S(i)\neq S(j)}$ for ${\displaystyle i\neq j}$. A move ${\displaystyle m=(p,u,v)}$ consists of transferring pebble ${\displaystyle p}$ from vertex ${\displaystyle u}$ to adjacent unoccupied vertex ${\displaystyle v}$.그래프 상의 페블 모션 문제는 두 가지 ${\displaystyle {배열\mathrm{}}_{}}$ S ${\displaystyle {0\mathrm{}}_{}}$ ${\$과 S${\displaystyle {}_{}}$+ ${\$을 $S{\displaystyle {}_{}}$+ ${\$0}로$$ 변환하는 일련의 이동이 있는지 여부를 결정하는 것이다$.$

변형

문제에 대한 일반적인 변화는 그래프의 구조를 다음과 같이 제한한다.

• 나무^[2] 한 그루
• 사각 격자,^[3]
• 쌍방향 ^[4]그래프

또 다른 변형은 조약돌의 일부^[5][3] 또는 전체가 라벨이 부착되지 않은 경우와 상호 교환이 가능한 경우를 고려한다.

문제의 다른 버전들은 도달 가능성을 증명하는 것뿐만 아니라 변환을 수행하는 (잠재적으로 최적의) 일련의 움직임(즉, 계획)을 찾으려고 한다.

복잡성

그래프 상의 조약돌 운동(표시가 있는 조약돌 포함)에서 최단 경로를 찾는 것은 NP-하드^[6], APX-하드인 것으로 알려져 있다.^[3]라벨이 부착되지 않은 문제는 위에서 언급한 비용 메트릭을 사용할 때 다항식 시간에 해결할 수 있지만(주변 정점으로 이동하는 총 수를 최소화), 다른 자연 비용 메트릭에 대해서는 NP-hard이다.^[3]

참조