캐나다 여행자 문제

컴퓨터 과학 및 그래프 이론에서 캐나다 여행자 문제(CTP)는 부분적으로 관측 가능한 그래프에 최단 경로 문제를 일반화시킨 것입니다.즉, 그래프는 탐색 중에 공개되며 탐색 에지는 최종 경로에 기여하지 않더라도 충전된다.

이 최적화 문제는 Christos Papadimitriou와 Mihalis Yannakakis에 의해 1989년에 도입되었으며, 그 이후로 이 문제의 많은 변형들이 연구되었다.이 이름은 캐나다 운전자들의 어려움을 알게 된 저자들의 대화에서 유래한 것으로 추측된다: 눈이 내리는 도시들의 네트워크를 무작위로 봉쇄하는 것.각 가장자리가 그래프에 독립적으로 존재할 확률과 연관된 확률적 버전은 "Resourtive Straight Path Problem"(SSPPR)이라는 이름으로 운영 연구에서 상당한 주의를 기울였다.

문제 설명

특정 인스턴스에서는 숨겨진 그래프가 어떻게 표시되는지 여러 가지 가능성 또는 실현 가능성이 있습니다.인스턴스를 지정하면 인스턴스를 가장 잘 따르는 방법을 정책이라고 합니다.CTP 태스크는 최적의 정책의 예상 비용을 계산하는 것입니다.최적의 정책에 대한 실제 설명을 계산하는 것은 더 어려운 문제일 수 있습니다.

인스턴스와 인스턴스의 정책을 지정하면 모든 실현이 그래프에 자체(결정론적) 워크를 생성합니다.예를 들어, 사이클의 모든 정점을 방문하고 시작점으로 돌아가는 것이 최선의 전략이 될 수 있기 때문에 걷기가 반드시 경로는 아니라는 점에 유의하십시오.이는 보행에서의 반복이 더 나은 해결책이 존재함을 의미하는 최단 경로 문제(엄밀하게 양의 가중치)와는 다르다.

변종

캐나다 여행자 문제의 변종 수를 구분하는 5가지 매개변수가 있습니다.첫 번째 파라미터는 특정 인스턴스와 실현에 대해 정책에 의해 생성된 워크의 가치를 어떻게 평가하는가이다.Resourget을 사용한 확률적 최단 경로 문제에서 목표는 단순히 보행 비용을 최소화하는 것이다(에지 비용의 모든 모서리에 대한 합계에 해당 모서리를 취한 횟수를 곱한 값으로 정의됨).캐나다 여행자 문제의 경우, 과제는 보행의 경쟁률을 최소화하는 것이다. 즉, 실현 가능한 최단 경로까지 더 긴 보행 횟수를 최소화하는 것이다.

두 번째 파라미터는 검토 중인 인스턴스와 일치하는 다양한 실현에 대해 정책을 평가하는 방법입니다.캐나다 여행자 문제에서는 최악의 경우를, SSPPR에서는 평균적인 경우를 연구하고자 한다.평균 사례 분석의 경우 실현에 대한 사전 분포를 추가로 지정해야 합니다.

세 번째 매개변수는 확률적 버전으로 제한되며 실현의 분포에 대해 우리가 어떤 가정을 할 수 있는지 그리고 그 분포가 입력에서 어떻게 표현되는지에 관한 것이다.확률적 캐나다 여행자 문제와 에지 독립적 확률적 최단 경로 문제(i-SSPPR)에서, 각 불확실한 에지(또는 비용)는 실현될 확률을 가지며, 그래프에 에지가 있는 경우는 실현에 있는 다른 에지와는 독립적이다.이는 상당히 단순하지만 문제는 여전히 #P-hard입니다.또 다른 변형은 분포를 가정하지 않고 0이 아닌 확률을 갖는 각 실현을 명시적으로 기술하는 것이다(예: "엣지 집합 {3,4}, {1,2} }, ...의 확률 0.2).이것은 Distribution Stochastic Shortest Path Problem(d-SSPPR 또는 R-SSPPR)이라고 불리며 NP-complete입니다.첫 번째 변종은 두 번째 변종보다 어렵다. 왜냐하면 전자는 로그 공간에서 후자가 선형 공간에서 나타내는 분포를 나타낼 수 있기 때문이다.

네 번째이자 마지막 매개 변수는 시간이 지남에 따라 그래프가 어떻게 변하는지입니다.CTP 및 SSPPR에서는 실현은 고정되어 있지만 알 수 없습니다.Resource and Resets에 의한 확률적 최단 경로 문제 또는 Expected Shortest Path 문제에서는 정책에 의해 실행되는 각 단계 후에 배포에서 새로운 실현이 선택됩니다.이 문제는 다항식 지평선을 가진 마르코프 결정 과정으로 줄임으로써 다항식 시간에 해결될 수 있다.그래프의 실현이 다음 실현에 영향을 미칠 수 있는 마르코프 일반화는 훨씬 더 어려운 것으로 알려져 있다.

또 하나의 파라미터는 실현에 관한 새로운 지식의 발견 방법입니다.기존의 CTP 바리안트에서는 에이전트는 인접한 정점에 도달하면 엣지의 정확한 무게(또는 상태)를 검출합니다.에이전트가 실현의 어느 장소에서나 리모트센싱을 실행할 수 있는 새로운 배리언트가 최근 제안되었습니다.이 변형에서는 이동 비용과 감지 작업 비용을 최소화하는 것이 과제입니다.

형식적 정의

우리는 1989년부터 연구된 변형을 정의한다.즉, 최악의 경우 경쟁률을 최소화하는 것이 목표입니다.먼저 특정 용어를 도입할 필요가 있습니다.

주어진 그래프와 주어진 세트에서 하나 이상의 모서리를 추가하여 구성할 수 있는 무방향 그래프 패밀리를 고려합니다. ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ 으로 ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ G ( ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ , ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ , ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ F ) ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ { ( ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ , ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ + ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ ) F ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ , $E$ F ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ ${\$ \ $displaystyle$ \ $mathcal$ { $G$ } ( $V , E$ , F ) = \ { ( $V$ , $E$ + $F$ ' ) 、 \ $SUB Q 、$ G $G\in {\mathcal {G}}(V,E,F)$ G ( V $G\in {\mathcal {G}}(V,E,F)$ , $G\in {\mathcal {G}}(V,E,F)$ , $G\in {\mathcal {G}}(V,E,F)$ ) { $displaystyle$ G \ $in$ \ $mathcal$ { $G$ } （ $V$ , $E$ , $F$ ） }는 그래프 $G\in {\mathcal {G}}(V,E,F)$ 패밀리의 실현이라고 합니다.또한 W를 관련 비용행렬로 합니다. $w_{ij}$ 서 $w_{ij}$ j\ $displaystyle w_{$ ij}는 $w_{ij}$ 정점i에서 정점j로 이동하는 비용입니다.이 엣지가 실현되고 있다고 가정합니다.

V의 모든 정점 V에 대해 V의 에지 집합 B에 대한 $E_{B}(v,V)$ B $E_{B}(v,V)$ ( $E_{B}(v,V)$ , $E_{B}(v,V)$ ) { $displaystyle E_{B}(v,V)}$ 의 $E_B(v,V)$ 입사 에지라고 $E_{B}(v,V)$ . $G\in {\mathcal {G}}(V,E,F)$ 실현 Gization $G\in {\mathcal {G}}(V,E,F)$ ( $G\in {\mathcal {G}}(V,E,F)$ , $G\in {\mathcal {G}}(V,E,F)$ , $G\in {\mathcal {G}}(V,E,F)$ ) $G\in {\mathcal {G}}(V,E,F)$ { $displaystyle$ G \ $in$ \ $mathcal$ { $G$ } （ $V$ , $E$ , $F$ ） $G\in {\mathcal {G}}(V,E,F)$ } 에서는 $d_B(s,t)$ d $d_{B}(s,t)$ ( $d_{B}(s,t)$ , $d_{B}(s,t)$ ) { $displaystyle d$ _ { $B （ s$ , $t$ ） $G\in {\mathcal {G}}(V,E,F)$ 이러한 문제에 대한 알고리즘은 그래프에 대한 완전한 정보를 가지고 있기 때문에 이를 오프라인 문제라고 합니다.

이러한 그래프를 탐색하는 전략 ${\(\displaystyle \pi)$ 은 $\pi$ ( $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ P $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ ${\mathcal {P}}(X)$ $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ V $(\mathcal {P}}(E),$ {\ $mathcal {P}}(F),$ V(\ $displaystyle$ { $P$ $V$ 에서 $(\mathcal{P}(E),\mathcal{P}(F),V)$ $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ V $(\$ displaystyle V $},$ P $mathcal$ { $P})$ 로의 매핑이라고 합니다.특정 $G=(V,B)$ G $G=(V,B)$ ( $G=(V,B)$ , $G=(V,B)$ ) \ $displaystyle$ $\pi$ G = ( V , B ) \ displaystyle G = ( $V$ , $B$ ) $c(\pi ,B)$ $display$ display display we we strategy we strategy strategy $strategy$ strategy $\pi$ $c(\pi ,B)$ （ \ $displaystyle$ c ( \ $pi$ , $B$ )의 $c(\pi ,B)$ c ( $c(\pi ,B)$ 。

$v_{0}=s,E_{0}=E$ 0 $v_{0}=s,E_{0}=E$ $v_{0}=s,E_{0}=E$ $v_{0}=s,E_{0}=E$ 0 $=$ {\ $displaystyle v_{0$ }= $s,$ $E_{0}=E}$ $F_{0}=F$ $F_{0}=F$ 0 $F_{0}=F$ {\ $displaystyle F_{0$ }= $F$
i $i=0,1,2,...$ $i=0,1,2,...$ , $i=0,1,2,...$ 2, $...({displaystyle$ i $=0,1,2$ 의 $i=0,1,2,...$ ,
- $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$ i + $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$ $=$ i $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$ B $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$ ( $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$ , $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$ $){$ $displaystyle E_{i+1$ }= $E_{i}\cup$ E_ ${B}(v_{i$ },V $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$
- $F_{i+1}=F_{i}-E_{F}(v_{i},V)$ + $F_{i+1}=F_{i}-E_{F}(v_{i},V)$ $=$ $F_{i+1}=F_{i}-E_{F}(v_{i},V)$ $F_{i+1}=F_{i}-E_{F}(v_{i},V)$ $F_{i+1}=F_{i}-E_{F}(v_{i},V)$ F ( $F_{i+1}=F_{i}-E_{F}(v_{i},V)$ , $F_{i+1}=F_{i}-E_{F}(v_{i},V)$ $){displaystyle F_{i+1$ }= $F_{i}-E_{F}(v_{$ i}, $V$ 및
- $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ i + $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ （ $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ + 1 $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ 、 $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ i + $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ 、 $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ $）$ { $displaystyle$ v $_$ { $i$ + 1 } = \ $pi$ ( $E$ _ { $i$ + $1$ } , $F _$ { i + $1$ , $v$ _ { i $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ } $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$ 。
$v_{T}=t$ 가 v $=$ t { $displaystyle v$ _ { T } $v_{T}=t$ $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ ( $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ , $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ ) $=$ i = $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ - $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ , $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ + $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ ( \ $displaystyle$ c ( \ $pi$ , B ) $=$ \ $sum$ _ { i $v_{T}=t$ 0 }^{ $T-1} w$ _ { v ; $i$ } $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$ } 。

즉, 현재 그래프에 표시되어 있는 $E_{i}$ ( $E_{i}$ \ $displaystyle E_$ i})와 그래프에 표시되어 있을 가능성이 있는 엣지( $\$ 를 바탕으로 정책을 평가합니다.그래프에서 한 단계 진행하면 새 위치의 가장자리를 알 수 있습니다.그래프에 표시되는 에지는 $(\$ ${$ $i$ 에 추가되며, 에지가 그래프에 있는지 여부에 관계없이 알 수 없는 에지의 $F_{i}$ $(\$ i $F_{i}$ 에서 삭제됩니다.목표에 도달하지 않으면 비용이 무한하다고 할 수 있습니다.목표에 도달한 경우 워크 비용은 카디널리티와 함께 횡단된 모든 에지의 비용 합계로 정의한다.

마지막으로, 우리는 캐나다 여행자 문제를 정의한다.

CTP 인스턴스

(V,E,F,s,t,r)

,

(V,E,F,s,t,r)

,

(V,E,F,s,t,r)

,

(V,E,F,s,t,r)

,

(V,E,F,s,t,r)

,

(V,E,F,s,t,r)

r

){

displaystyle ( V

,

(V,B)\in {\mathcal {G}}(V,E,F)

, F

, t ,

r

displaystyle (

(V,B)\in {\mathcal {G}}(V,E,F)

, B

(V,B)\in {\mathcal {G}}(V,E,F)

(

(V,B)\in {\mathcal {G}}(V,E,F)

,

(V,B)\in {\mathcal {G}}(V,E,F)

,

(V,B)\in {\mathcal {G}}(V,E,F)

){ displaystyle

(

B

){

displaystyle

\

pi

}

가

\pi

존재하는지

확인합니다.

또는 r 곱하기

d_{B}(s,t)

최적

d_{B}(s,t)

( s ,

d_{B}(s,t)

){

displaystyle

d_

{B}(s,

t

d_{B}(s,t)

보다 커집니다.

파파디미트리우와 얀나카키스는 이것이 두 사람이 함께 하는 게임을 정의한다고 언급했다.여기서 선수들은 각각의 경로의 비용을 놓고 경쟁하고 엣지 세트는 두 번째 선수(자연)에 의해 선택된다.

복잡성

원래 논문은 문제의 복잡성을 분석하여 PSPACE-완전하다고 보고했습니다.또한 각 에지가 그래프에 포함될 확률(i-SSPPR)을 갖는 경우 최적의 경로를 찾는 것은 PSPACE-쉽지만 P-하드 ^[1]문제인 것으로 나타났다.이 갭을 메우는 것은 미해결 문제였지만, 그 이후 다이렉트 버전과 비다이렉트 버전 모두 PSPACE ^[2]하드인 것으로 나타났습니다.

확률적 문제의 지향적 버전은 운영 연구에서 리소지를 사용한 확률적 최단 경로 문제로 알려져 있다.

적용들

이 문제는 운영 연구, 교통 계획, 인공지능, 기계 학습, 통신 네트워크, 라우팅 분야에서 응용되고 있는 것으로 알려져 있다.확률론적 랜드마크 ^[3]인식으로 로봇 항법에 대한 문제의 변종이 연구되었다.

미해결 문제

문제의 나이와 많은 잠재적인 적용에도 불구하고, 많은 자연스런 질문들은 여전히 미해결 상태로 남아 있습니다.상수계수 근사치가 존재합니까, 아니면 APX-hard 문제가 존재합니까?i-SSPPR #P-완성 여부보다 근본적인 질문은 답변되지 않은 채 남아 있습니다: ^[4]최적 정책에 대한 다항식 크기의 설명이 잠시나마 설명 계산에 필요한 시간을 남겨두고 있습니까?

「」를 참조해 주세요.

메모들

^ 파파디미트리오와 얀나카키스, 1989, 148페이지
^ 프라이드, 시모니, 벤바사트, 웨너 2013
^ Briggs, Amy J.; Detweiler, Carrick; Scharstein, Daniel (2004). "Expected shortest paths for landmark-based robot navigation". International Journal of Robotics Research. 23 (7–8): 717–718. CiteSeerX 10.1.1.648.3358. doi:10.1177/0278364904045467. S2CID 15681481.
^ Karger and Nicolova, 2008,

레퍼런스

C.H. Papadimitriou; M. Yannakakis (1989). "Shortest paths without a map". Lecture Notes in Computer Science. Proc. 16th ICALP. Vol. 372. Springer-Verlag. pp. 610–620.
Dror Fried; Solomon Eyal Shimony; Amit Benbassat; Cenny Wenner (2013). "Complexity of Canadian traveler problem variants". Theoretical Computer Science. 487: 1–16. doi:10.1016/j.tcs.2013.03.016. S2CID 17810202.
David Karger; Evdokia Nikolova (2008). "Exact Algorithms for the Canadian Traveller Problem on Paths and Trees". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
Zahy Bnaya; Ariel Felner; Solomon Eyal Shimony (2009). Canadian Traveller Problem with remote sensing. International Joint Conference On Artificial Intelligence (IJCAI).

[1] 파파디미트리오와 얀나카키스, 1989, 148페이지

[2] 프라이드, 시모니, 벤바사트, 웨너 2013

[briggs04-3] Briggs, Amy J.; Detweiler, Carrick; Scharstein, Daniel (2004). "Expected shortest paths for landmark-based robot navigation". International Journal of Robotics Research. 23 (7–8): 717–718. CiteSeerX 10.1.1.648.3358. doi:10.1177/0278364904045467. S2CID 15681481.

[4] Karger and Nicolova, 2008,

[1]

[2]

[3]

[4]

Search

캐나다 여행자 문제

네임스페이스

더

목차

문제 설명

변종

형식적 정의

복잡성

적용들

미해결 문제

「」를 참조해 주세요.

메모들

레퍼런스

Search

캐나다 여행자 문제

문제 설명

변종

형식적 정의

복잡성

적용들

미해결 문제

「 」를 참조해 주세요.

메모들

레퍼런스

「」를 참조해 주세요.