편도 비행 문제
수십억 개의
알 수없는 매우 많은 수 의 환승 을 포함하는 편도 간접 비행 여행을 가고
있습니다.
- 같은 공항에서 두 번 멈추지 않습니다.
- 여행의 각 부분에 대해 1 장의 티켓이 있습니다.
- 각 티켓에는 src 및 dst 공항이 있습니다.
- 보유한 모든 티켓은 무작위로 정렬됩니다.
- 원래 출발 공항 (첫 번째 src)과 목적지 (마지막 dst)를 잊어 버렸습니다.
최소한의 big- O 복잡성으로 여행을 재구성하는 알고리즘을 설계하십시오 .
이 문제를 해결하기 위해 Srcs와 Dsts라는 두 세트 의 대칭 차이 를 사용하기 시작했습니다 .
1) 배열 Srcs의 모든 src 키
정렬 2) 배열 Dsts의 모든 dst 키 정렬
3) 두 배열의 합집합 집합을 만들어 중복되지 않는 항목을 찾습니다-첫 번째 src 및 마지막 dst
4) 이제 시작점을 가지고, 이진 검색을 사용하여 두 배열을 모두 탐색합니다.
하지만 더 효과적인 방법이 또있을 것 같습니다.
해시 테이블을 생성하고 각 공항을 해시 테이블에 추가합니다.
<key,value> = <airport, count>
공항이 출발지 또는 목적지 인 경우 공항 수는 증가합니다. 따라서 모든 공항에 대해 카운트는 1이 될 여행의 출발지와 목적지를 제외하고는 2 (src의 경우 1, dst의 경우 1)가됩니다.
각 티켓을 한 번 이상 확인해야합니다. 따라서 복잡성은 O (n)입니다.
요약 : 아래에 단일 패스 알고리즘이 제공 됩니다. (즉, 선형적인 것이 아니라 각 티켓을 정확히 한 번만 보며 , 이는 물론 티켓 당 최적의 방문 횟수입니다). 겉보기에 동등한 솔루션이 많고 다른 솔루션을 추가 한 이유를 찾기가 어렵 기 때문에 요약을 넣었습니다. :)
인터뷰에서 실제로이 질문을 받았습니다. 개념은 매우 간단합니다. 각 티켓은 개념적으로 src와 dst의 두 가지 요소가있는 단일 목록입니다.
첫 번째와 마지막 요소를 키로 사용하여 해시 테이블에서 이러한 각 목록을 인덱싱하므로 목록이 특정 요소 (공항)에서 시작하거나 끝나는 경우 O (1)에서 찾을 수 있습니다. 각 티켓에 대해 다른 목록이 끝나는 곳에서 시작되는 것을 볼 때 목록을 연결하기 만하면됩니다 (O (1)). 마찬가지로 다른 목록이 시작되는 곳에서 끝나는 경우 다른 목록이 결합됩니다. 물론 두 목록을 연결하면 기본적으로 두 목록을 파괴하고 하나를 얻습니다. (N 티켓 체인은 이러한 링크 N-1 이후에 구성됩니다.)
해시 테이블 키가 나머지 목록의 첫 번째 요소와 마지막 요소라는 불변성을 유지하려면주의가 필요합니다.
전체적으로 O (N).
그리고 네, 그 자리에서 대답했습니다 :)
편집 중요한 점을 추가하는 것을 잊었습니다. 모든 사람이 두 개의 해시 테이블을 언급 하지만 하나도 트릭을 수행합니다. 알고리즘 불변에는 최대 하나의 티켓 목록이 단일 도시에서 시작되거나 시작 된다는 것이 포함되기 때문 입니다 (두 개가있는 경우 즉시 해당 도시의 목록에 가입하고 해당 도시를 제거합니다). 해시 테이블에서). 점근 적으로 차이가 없으며이 방법이 더 간단합니다.
편집 2 또한 흥미로운 점은 각각 N 개의 항목이있는 2 개의 해시 테이블을 사용하는 솔루션과 비교 하여이 솔루션은 최대 N / 2 개의 항목 이 있는 하나의 해시 테이블을 사용 한다는 것입니다 (예를 들어 1st, 3rd, 5 일 등). 따라서 이것은 더 빠르다는 것 외에는 약 절반의 메모리를 사용합니다.
두 개의 해시 테이블 (또는 시도)을 생성합니다. 하나는 src에, 다른 하나는 dst에 입력합니다. 무작위로 하나의 티켓을 선택하고 src-hash 테이블에서 dst를 찾으십시오. 끝 (최종 목적지)에 도달 할 때까지 결과에 대해이 과정을 반복합니다. 이제 dst-keyed 해시 테이블에서 src를 찾으십시오. 처음에 도달 할 때까지 결과에 대해 프로세스를 반복하십시오.
해시 테이블을 구성하려면 O (n)이 필요하고 목록을 구성하는 데는 O (n)이 필요하므로 전체 알고리즘은 O (n)입니다.
편집 : 실제로 하나의 해시 테이블 만 구성하면됩니다. src-keyed 해시 테이블을 구성한다고 가정 해 보겠습니다. 무작위로 하나의 티켓을 선택하고 이전과 마찬가지로 최종 목적지로 연결되는 목록을 작성하십시오. 그런 다음 목록에 아직 추가되지 않은 티켓에서 다른 무작위 티켓을 선택합니다. 처음에 시작한 티켓을 찾을 때까지 목적지를 따르십시오. 전체 목록을 구성 할 때까지이 프로세스를 반복하십시오. 최악의 경우 티켓을 역순으로 선택하기 때문에 여전히 O (n)입니다.
편집 : 내 알고리즘에서 테이블 이름이 바뀌 었습니다.
기본적으로 모든 티켓이 노드를 나타내고 src 및 dst 공항이 방향 링크를 나타내는 종속성 그래프 이므로 토폴로지 정렬을 사용하여 비행 순서를 결정합니다.
편집 : 이것은 항공권이고 실제로 수행 할 수있는 여정을 실제로 만들었 기 때문에 UTC로 출발 날짜 및 시간별로 정렬하십시오.
EDIT2 : 각 공항에 3 개의 문자 코드를 사용하는 티켓이 있다고 가정하면 여기에 설명 된 알고리즘 ( 세 개의 숫자가 한 번만 나타남 )을 사용하여 모든 공항을 함께 xoring하여 두 개의 고유 한 공항을 결정할 수 있습니다.
EDIT3 : xor 메서드를 사용하여 실제로이 문제를 해결하는 몇 가지 C ++가 있습니다. 전체 알고리즘은 다음과 같이 공항에서 정수로 고유 한 인코딩을 가정합니다 (3 자로 된 공항 코드를 가정하거나 위도와 경도를 사용하여 공항 위치를 정수로 인코딩).
먼저 모든 공항 코드를 함께 XOR합니다. 이것은 초기 출발지 공항 XOR 최종 목적지 공항과 같아야합니다. 초기 공항과 최종 공항이 고유하다는 것을 알고 있으므로이 값은 0이 아니어야합니다. 0이 아니기 때문에 해당 값에 적어도 하나의 비트가 설정됩니다. 이 비트는 공항 중 하나에 설정되고 다른 공항에는 설정되지 않은 비트에 해당합니다. 그것을 지정자 비트라고 부릅니다.
다음으로, 각각 첫 번째 단계에서 XOR 된 값을 가진 두 개의 버킷을 설정합니다. 이제 모든 티켓에 대해 지정자 비트가 설정되었는지 여부에 따라 각 공항을 버킷 화하고 버킷의 값으로 공항 코드를 xor합니다. 또한 각 버킷에 대해 해당 버킷으로 이동 한 소스 공항 및 목적지 공항 수를 추적합니다.
모든 티켓을 처리 한 후 버킷 중 하나를 선택합니다. 해당 버킷으로 전송 된 소스 공항의 수는 해당 버킷으로 전송 된 목적지 공항의 수보다 하나 크거나 작아야합니다. 출발지 공항의 수가 도착지 공항의 수보다 적 으면 초기 출발지 공항 (유일한 유일한 출발지 공항)이 다른 버킷으로 전송되었음을 의미합니다. 즉, 현재 버킷의 값이 초기 소스 공항의 식별자입니다! 반대로 목적지 공항의 수가 소스 공항의 수보다 적 으면 최종 목적지 공항이 다른 버킷으로 전송되었으므로 현재 버킷은 최종 목적지 공항의 식별자입니다!
struct ticket
{
int src;
int dst;
};
int get_airport_bucket_index(
int airport_code,
int discriminating_bit)
{
return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0;
}
void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst)
{
int xor_residual= 0;
for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
{
xor_residual^= current_ticket->src;
xor_residual^= current_ticket->dst;
}
// now xor_residual will be equal to the starting airport xor ending airport
// since starting airport!=ending airport, they have at least one bit that is not in common
//
int discriminating_bit= xor_residual & (-xor_residual);
assert(discriminating_bit!=0);
int airport_codes[2]= { xor_residual, xor_residual };
int src_count[2]= { 0, 0 };
int dst_count[2]= { 0, 0 };
for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
{
int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit);
airport_codes[src_index]^= current_ticket->src;
src_count[src_index]+= 1;
int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit);
airport_codes[dst_index]^= current_ticket->dst;
dst_count[dst_index]+= 1;
}
assert((airport_codes[0]^airport_codes[1])==xor_residual);
assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination
assert(abs(src_count[1]-dst_count[1])==1);
assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1]));
int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1;
// if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket!
assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index);
*out_src= airport_codes[src_index];
*out_dst= airport_codes[!src_index];
return;
}
int main()
{
ticket test0[]= { { 1, 2 } };
ticket test1[]= { { 1, 2 }, { 2, 3 } };
ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } };
ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } };
ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } };
ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } };
int initial_src, final_dst;
find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst);
assert(initial_src==1);
assert(final_dst==2);
find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst);
assert(initial_src==1);
assert(final_dst==3);
find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst);
assert(initial_src==1);
assert(final_dst==4);
find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst);
assert(initial_src==1);
assert(final_dst==4);
find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst);
assert(initial_src==4);
assert(final_dst==1);
find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst);
assert(initial_src==1);
assert(final_dst==2);
return 0;
}
두 개의 데이터 구조를 만듭니다.
Route
{
start
end
list of flights where flight[n].dest = flight[n+1].src
}
List of Routes
그리고:
foreach (flight in random set)
{
added to route = false;
foreach (route in list of routes)
{
if (flight.src = route.end)
{
if (!added_to_route)
{
add flight to end of route
added to route = true
}
else
{
merge routes
next flight
}
}
if (flight.dest = route.start)
{
if (!added_to_route)
{
add flight to start of route
added to route = true
}
else
{
merge routes
next flight
}
}
}
if (!added to route)
{
create route
}
}
두 개의 해시를 넣으십시오 : to_end = src-> des; to_beg = des-> src
공항을 출발점으로 선택 S.
while(to_end[S] != null)
S = to_end[S];
S는 이제 최종 목적지입니다. 시작 지점을 찾으려면 다른지도에서도 반복하세요.
제대로 확인하지 않으면 적절한 해시 테이블 구현이 있으면 O (N) 느낌이 듭니다.
해시 테이블은 큰 크기 (예 : 원래 질문의 수십억 개)에서는 작동하지 않습니다. 그들과 함께 일한 사람은 그들이 작은 세트에만 좋다는 것을 알고 있습니다. 대신 복잡성 O (n log n)를 제공하는 이진 검색 트리를 사용할 수 있습니다.
가장 간단한 방법은 두 개의 패스를 사용하는 것입니다. 첫 번째는 src에 의해 색인 된 트리에 모두 추가합니다. 두 번째는 트리를 걷고 노드를 배열로 수집합니다.
더 잘할 수 있습니까? 우리가 정말로 원한다면 우리는 한 번에 할 수 있습니다. 각 티켓을 좋아요 목록의 노드로 나타냅니다. 처음에 각 노드는 다음 포인터에 대해 null 값을 갖습니다 . 각 티켓에 대해 색인에 src와 dest를 모두 입력합니다. 충돌이 발생하면 이미 인접한 티켓이 있음을 의미합니다. 노드를 연결하고 색인에서 일치를 삭제하십시오. 완료되면 패스를 한 번만 만들었고 빈 색인과 순서대로 모든 티켓의 연결 목록을 갖게됩니다.
이 방법은 훨씬 더 빠릅니다. 두 번이 아니라 한 번만 통과하면됩니다. 그리고 저장소는 상당히 작아서 (최악의 경우 : n / 2, 최상의 경우 : 1, 일반적인 경우 : sqrt (n)) 이진 검색 트리 대신 해시를 실제로 사용할 수있을만큼 충분합니다.
각 공항은 node. 각 티켓은 edge. 그래프를 나타내는 인접 행렬을 만듭니다. 이것은 가장자리를 압축하는 비트 필드로 수행 할 수 있습니다. 시작점은 경로가없는 노드가됩니다 (열이 비어 있음). 이것을 알면 존재하는 경로를 따르십시오.
또는 공항별로 색인을 생성 할 수있는 구조를 만들 수 있습니다. 각 티켓에 대해 src및 dst입니다. 둘 중 하나가 없으면 목록에 새 공항을 추가해야합니다. 각각이 발견되면 출발 공항의 출구 포인터를 목적지를 가리키고 목적지의 도착 포인터를 출발 공항을 가리 키도록 설정합니다. 티켓이 없으면 전체 목록을 탐색하여 경로가없는 사람을 확인해야합니다.
또 다른 방법은 각 티켓을 만날 때 함께 연결하는 가변 길이의 미니 여행 목록을 만드는 것입니다. 티켓을 추가 할 때마다 기존 미니 여행의 끝이 티켓의 src 또는 dest와 일치하는지 확인합니다. 그렇지 않은 경우 현재 티켓이 자체 미니 트립이되어 목록에 추가됩니다. 그렇다면 새 티켓은 일치하는 기존 여행의 끝에 부착되어 기존의 미니 여행 두 개를 함께 연결하여 미니 여행 목록을 하나씩 줄입니다.
이것은 단일 경로 상태 머신 매트릭스의 간단한 경우입니다. 의사 코드가 C # 스타일로되어있어서 미안하지만 객체로 아이디어를 표현하는 것이 더 쉬웠습니다.
먼저 턴 파이크 행렬을 만듭니다. 대형 상태 머신을 테스트하기위한 몇 가지 전략 은 무엇입니까 ?에서 턴 파이크 매트릭스가 무엇인지에 대한 설명을 읽으십시오 (FSM 답변은 신경 쓰지 말고, 턴 파이크 매트릭스에 대한 설명 만) . .
그러나 설명하는 제한 사항으로 인해 사례가 단순한 단일 경로 상태 시스템이됩니다. 완전한 커버리지로 가능한 가장 단순한 상태 머신입니다.
5 개 공항의 간단한 경우,
vert nodes = src / entry points,
horiz nodes = dst / exit points.
A1 A2 A3 A4 A5
A1 x
A2 x
A3 x
A4 x
A5 x
각 행과 각 열에 대해 하나 이상의 전환이 없어야합니다.
기계의 경로를 얻으려면 매트릭스를 다음과 같이 정렬합니다.
A1 A2 A3 A4 A5
A2 x
A1 x
A3 x
A4 x
A5 x
또는 정렬 된 쌍의 고유 벡터 인 대각선 정사각형 행렬로 정렬합니다.
A1 A2 A3 A4 A5
A2 x
A5 x
A1 x
A3 x
A4 x
주문 된 쌍은 티켓 목록입니다.
a2 : a1, a5 : a2, a1 : a3, a3 : a4, a4 : a5.
또는 좀 더 공식적인 표기법으로
<a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>.
음 .. 주문한 쌍 응? Lisp에서 재귀의 힌트를 냄새 맡고 있습니까?
<a2,<a1,<a3,<a4,a5>>>>
기계에는 두 가지 모드가 있습니다.
- 여행 계획-공항이 몇 개 있는지 모르고 지정되지 않은 공항 수에 대한 일반적인 여행 계획이 필요합니다.
- 여행 재건-과거 여행의 모든 통행 금 티켓을 가지고 있지만 모두 작은 상자 / 수하물 가방에 하나의 큰 스택입니다.
귀하의 질문이 여행 재건에 관한 것이라고 생각합니다. 따라서 티켓 더미에서 무작위로 티켓을 하나씩 선택합니다.
우리는 티켓 더미의 크기가 무한하다고 가정합니다.
tak mnx cda
bom 0
daj 0
phi 0
여기서 0 값은 주문되지 않은 티켓을 나타냅니다. 순서가 지정되지 않은 티켓을 dst가 다른 티켓의 src와 일치하지 않는 티켓으로 정의하겠습니다.
다음 티켓은 mnx (dst) = kul (src) 일치를 찾습니다.
tak mnx cda kul
bom 0
daj 1
phi 0
mnx 0
언제든지 다음 티켓을 선택하면 두 개의 순차적 인 공항을 연결할 가능성이 있습니다. 이 경우 두 노드에서 클러스터 노드를 만듭니다.
<bom,tak>, <daj,<mnx,kul>>
행렬이 줄어들고
tak cda kul
bom 0
daj L1
phi 0
어디
L1 = <daj,<mnx,kul>>
메인 목록의 하위 목록입니다.
다음 무작위 티켓을 계속 선택하십시오.
tak cda kul svn xml phi
bom 0
daj L1
phi 0
olm 0
jdk 0
klm 0
existent.dst를 new.src에 일치 시키거나 existent.src를 new.dst에 일치
시킵니다.
tak cda kul svn xml
bom 0
daj L1
olm 0
jdk 0
klm L2
<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>
위의 토폴로지 연습은 시각적 이해를위한 것입니다. 다음은 알고리즘 솔루션입니다.
개념은 순서가 지정된 쌍을 하위 목록으로 클러스터링하여 티켓을 보관하는 데 사용할 해시 구조의 부담을 줄이는 것입니다. 점차적으로 점점 더 많은 의사 티켓 (병합 된 일치 티켓에서 형성됨)이 있으며, 각각은 주문 된 대상의 하위 목록을 포함합니다. 마지막으로 하위 목록에 전체 여정 벡터를 포함하는 단일 의사 티켓이 남습니다.
보시다시피 아마도 이것은 Lisp로 가장 잘 수행됩니다.
그러나 연결된 목록 및지도의 연습으로 ...
다음 구조를 만듭니다.
class Ticket:MapEntry<src, Vector<dst> >{
src, dst
Vector<dst> dstVec; // sublist of mergers
//constructor
Ticket(src,dst){
this.src=src;
this.dst=dst;
this.dstVec.append(dst);
}
}
class TicketHash<x>{
x -> TicketMapEntry;
void add(Ticket t){
super.put(t.x, t);
}
}
그래서 효과적으로
TicketHash<src>{
src -> TicketMapEntry;
void add(Ticket t){
super.put(t.src, t);
}
}
TicketHash<dst>{
dst -> TicketMapEntry;
void add(Ticket t){
super.put(t.dst, t);
}
}
TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst
TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src
더미에서 티켓을 무작위로 뽑으면
void pickTicket(Ticket t){
// does t.dst exist in mapbyDst?
// i.e. attempt to match src of next ticket to dst of an existent ticket.
Ticket zt = dstExists(t);
// check if the merged ticket also matches the other end.
if(zt!=null)
t = zt;
// attempt to match dst of next ticket to src of an existent ticket.
if (srcExists(t)!=null) return;
// otherwise if unmatched either way, add the new ticket
else {
// Add t.dst to list of existing dst
mapbyDst.add(t);
mapbySrc.add(t);
}
}
기존 dst 확인 :
Ticket dstExists(Ticket t){
// find existing ticket whose dst matches t.src
Ticket zt = mapbyDst.getEntry(t.src);
if (zt==null) return false; //no match
// an ordered pair is matched...
//Merge new ticket into existent ticket
//retain existent ticket and discard new ticket.
Ticket xt = mapbySrc.getEntry(t.src);
//append sublist of new ticket to sublist of existent ticket
xt.srcVec.join(t.srcVec); // join the two linked lists.
// remove the matched dst ticket from mapbyDst
mapbyDst.remove(zt);
// replace it with the merged ticket from mapbySrc
mapbyDst.add(zt);
return zt;
}
Ticket srcExists(Ticket t){
// find existing ticket whose dst matches t.src
Ticket zt = mapbySrc.getEntry(t.dst);
if (zt==null) return false; //no match
// an ordered pair is matched...
//Merge new ticket into existent ticket
//retain existent ticket and discard new ticket.
Ticket xt = mapbyDst.getEntry(t.dst);
//append sublist of new ticket to sublist of existent ticket
xt.srcVec.join(t.srcVec); // join the two linked lists.
// remove the matched dst ticket from mapbyDst
mapbySrc.remove(zt);
// replace it with the merged ticket from mapbySrc
mapbySrc.add(zt);
return zt;
}
존재하는 src 확인 :
Ticket srcExists(Ticket t){
// find existing ticket whose src matches t.dst
Ticket zt = mapbySrc.getEntry(t.dst);
if (zt == null) return null;
// if an ordered pair is matched
// remove the dst from mapbyDst
mapbySrc.remove(zt);
//Merge new ticket into existent ticket
//reinsert existent ticket and discard new ticket.
mapbySrc.getEntry(zt);
//append sublist of new ticket to sublist of existent ticket
zt.srcVec.append(t.srcVec);
return zt;
}
위의 내용에 약간의 오타가있는 것 같지만 개념이 옳 아야합니다. 오타가 발견되면 누군가가이를 수정할 수 있습니다. plsss.
가장 쉬운 방법은 해시 테이블을 사용하는 것이지만 최악의 경우 복잡성이 가장 좋지는 않습니다 ( O (n 2 ) )
대신 :
- (src, dst) O (n)을 포함하는 노드 묶음 만들기
- 목록에 노드를 추가하고 src O (n log n)로 정렬
- 각 (대상) 노드에 대해 해당 (소스) 노드 O (n log n)에 대한 목록을 검색합니다.
- 시작 노드 찾기 (예 : 토폴로지 정렬 사용 또는 3 단계에서 노드 표시) O (n)
전체 : O (n log n)
(두 알고리즘 모두 문자열의 길이가 무시할 만하다고 가정합니다. 즉, 비교는 O (1)입니다)
해시 나 비슷한 것이 필요 없습니다. 여기서 실제 입력 크기는 티켓 수 (예 : n )가 아니라 티켓 의 총 '크기'(예 : N ), char코드화 에 필요한 총 수입니다 .
k 문자 의 알파벳이있는 경우 (여기서 k 는 대략 42 임) bucketsort 기술을 사용 하여 O (n + N + k) 에서 k 문자 의 알파벳으로 인코딩 된 총 크기 N 의 n 문자열 배열을 정렬 할 수 있습니다. 시각. 다음은 n <= N (사소한)이고 k <= N (잘 N 은 수십억, 그렇지 않은 경우)
- 티켓이 제공되는 순서대로 티켓에서 모든 공항 코드를 추출
struct하여 코드를 문자열로, 티켓 인덱스를 숫자로 갖는에 저장합니다. struct코드에 따라 해당 배열을 버킷 정렬 합니다.- 정렬 된 배열을 실행하고 새로 발견 된 각 항공사 코드에 서수 ( 0 부터 시작 )를 할당합니다 . 동일한 코드 (연속 된)를 가진 모든 요소에 대해 티켓으로 이동하여 (코드와 함께 번호를 저장했습니다 ) 티켓 의 코드 를 서수로 변경합니다 (오른쪽
src또는dst). - 어레이를 통해 실행하는 동안 원본 소스를 식별 할 수 있습니다
src0. - 이제 모든 티켓이
src와dst서수로 다시 작성, 하나의 목록에서 시작으로 티켓 해석 할 수있다src0. src0티켓에 대해 목록 순위를 지정합니다 (=로부터의 거리를 추적하는 토폴로지 정렬 ).
모든 것을 (아마도 디스크에) 저장할 수있는 결합 가능한 목록 구조를 가정하는 경우 :
- 2 개의 빈 해시 테이블 S 및 D 만들기
- 첫 번째 요소를 잡아
- D에서 src를 찾으십시오.
- 발견되면 D에서 연관된 노드를 제거하고 현재 노드에 연결합니다.
- 찾을 수 없으면 src에 S 키가 지정된 노드를 삽입하십시오.
- 다른 방법으로 src <-> des, S <-> D 3에서 반복
- 다음 노드로 2부터 반복하십시오.
O(n)시각. 공간의 경우 생일 패러독스 (또는 이와 유사한 것)로 인해 데이터 세트가 전체 세트보다 훨씬 작게 유지됩니다. 여전히 커지는 불운의 경우 (최악의 경우는 O(n)) 해시 테이블에서 임의 실행을 제거하고 처리 대기열의 끝에 삽입 할 수 있습니다. 속도는 팟으로 갈 수 있지만 충돌을 예상하는 임계 값 (~ O(sqrt(n)))을 훨씬 초과 할 수있는 한 데이터 세트 (테이블과 입력 대기열 결합)가 정기적으로 줄어들 것으로 예상해야합니다.
그래프 기반 접근 방식이 여기에 기반한 것 같습니다.
각 공항은 노드이고 각 티켓은 에지입니다. 지금은 모든 가장자리를 무 방향으로 만들어 보겠습니다.
첫 번째 단계에서는 그래프를 작성합니다. 각 티켓에 대해 소스와 대상을 조회하고 그 사이에 에지를 구축합니다.
이제 그래프가 구성되었으므로 그래프가 비순환 적이며이를 통과하는 단일 경로가 있음을 알 수 있습니다. 결국, 당신은 여행에 대한 티켓 만 가지고 있고 같은 공항을 한 번도 방문한 적이 없습니다.
두 번째 단계에서는 그래프를 검색합니다. 노드를 선택하고 계속할 수 없을 때까지 양방향으로 검색을 시작합니다. 이것이 당신의 출발지와 목적지입니다.
소스와 대상을 구체적으로 말해야하는 경우 각 에지에 디렉토리 속성을 추가합니다 (하지만 방향이없는 그래프로 유지). 후보 소스와 대상이 있으면 연결된 에지를 기반으로 어느 것이 어느 것인지 알 수 있습니다.
이 알고리즘의 복잡성은 특정 노드를 조회하는 데 걸리는 시간에 따라 달라집니다. O (1)을 얻을 수 있다면 시간은 선형이어야합니다. n 개의 티켓이 있으므로 그래프를 작성하는 데 O (N) 단계가 필요하고 검색하려면 O (N), 경로를 재구성하려면 O (N)이 필요합니다. 여전히). 인접 행렬이이를 제공합니다.
공간을 절약 할 수 없다면 노드에 대해 해시를 수행 할 수 있습니다. 그러면 최적의 해싱과 그 모든 쓰레기에서 O (1)을 얻을 수 있습니다.
작업이 (전체 여행을 재구성하는 대신) 출발지와 목적지 공항을 결정하는 것 뿐 이라면 퍼즐이 더 흥미로워 질 것입니다.
즉, 공항 코드가 정수로 주어 졌다고 가정하면 데이터의 O (1) 패스와 O (1) 추가 메모리 (즉, 해시 테이블, 정렬, 이진 검색 등에 의존하지 않고)를 사용하여 출발지 및 목적지 공항을 결정할 수 있습니다. ).
물론 소스를 찾으면 전체 경로를 인덱싱하고 순회하는 것도 사소한 문제가되지만, 그 시점부터는 어쨌든 최소한 O (n) 개의 추가 메모리가 필요합니다 (데이터를 정렬 할 수없는 경우). 그건 그렇고, O (1) 추가 메모리로 O (n log n) 시간에 원래 작업을 해결할 수 있습니다)
잠시 데이터 구조와 그래프는 잊어 버리자.
먼저 모든 사람들이 루프가 없다고 가정했다는 점을 지적해야합니다. 경로가 한 공항을 두 번 통과하면 훨씬 더 큰 문제입니다.
그러나 지금은 가정을 유지합시다.
입력 데이터는 실제로 이미 정렬 된 세트입니다. 모든 티켓은 일련의 공항에 주문을 도입하는 관계의 요소입니다. (영어는 제 모국어가 아니므로 정확한 수학 용어가 아닐 수 있습니다.)
모든 티켓에는 다음과 같은 정보가 포함 airportX < airportY되어 있으므로 티켓을 한 번 통과하는 동안 알고리즘은 모든 공항에서 시작하는 순서 목록을 다시 만들 수 있습니다.
이제 "선형 가정"을 삭제하겠습니다. 그런 종류의 물건으로는 주문 관계를 정의 할 수 없습니다. 입력 데이터는 형식 문법에 대한 생산 규칙으로 취급되어야합니다. 여기서 문법의 어휘 집합은 ariport 이름 집합입니다. 다음과 같은 티켓 :
src: A
dst: B
사실 한 쌍의 제작물입니다.
A->AB
B->AB
하나만 유지할 수 있습니다.
이제 가능한 모든 문장을 생성해야하지만 모든 생산 규칙을 한 번 사용할 수 있습니다. 모든 프로덕션을 한 번만 사용하는 가장 긴 문장이 올바른 솔루션입니다.
전제 조건
우선, 경로의 일부를 포함하는 일종의 하위 여행 구조를 만듭니다.
예를 들어 전체 여정이 a-b-c-d-e-f-g인 경우 하위 여정은 b-c-d, 즉 여정의 연결된 하위 경로 가 될 수 있습니다 .
이제 도시를 도시가 포함 된 하위 여행 구조에 매핑하는 두 개의 해시 테이블을 만듭니다. 따라서 하나의 Hashtable은 하위 여행이 시작되는 도시를 나타내고 다른 하나는 하위 여행이 끝나는 도시를 나타냅니다. 즉, 해시 테이블 중 하나에서 한 도시가 최대 한 번 발생할 수 있습니다.
나중에 살펴 보 겠지만 모든 도시를 저장할 필요는 없지만 각 하위 여행의 시작과 끝만 저장해야합니다.
서브 트립 구성
이제 티켓을 차례대로 가져 가십시오. 우리는에서 갈 수있는 티켓 가정 x에를 y(로 표시 (x,y)). x일부 하위 여행의 끝인지 확인하십시오 s(모든 도시는 한 번만 방문하므로 다른 하위 여행의 끝일 수 없습니다). 경우 x시작은, 그냥 현재의 티켓을 추가 (x,y)subtrip의 끝에서 s. 로 끝나는 서브 트립이없는 경우로 시작 x하는 서브 트립이 있는지 확인하십시오 . 이 경우, 추가 의 시작 부분에 . 또한 그러한 subtrip이 없다면 , 그냥 포함하는 새로운 subtrip를 작성 .ty(x,y)tt(x,y)
서브 트립을 다루는 것은 특별한 "트릭"을 사용하여 이루어져야합니다.
- 새로운 subtrip 만들기
s포함(x,y)추가해야합니다x"subtrip 시작 도시"의 해시 테이블에 추가합니다y"subtrip 끝나는 도시"에 대한 해시 테이블에 있습니다. (x,y)subtrip 시작 부분에 새 티켓 을 추가하면 시작 도시의 해시 테이블에서s=(y,...)제거y하고 대신 시작 도시x의 해시 테이블에 추가 해야합니다.(x,y)서브 트립 끝에 새 티켓 을 추가하면 종료 도시의 해시 테이블에서s=(...,x)제거x하고 대신 종료 도시y의 해시 테이블에 추가 해야합니다.
이 구조를 사용하면 도시에 해당하는 서브 트립이 상각 된 O (1)에서 수행 될 수 있습니다.
모든 티켓에 대해이 작업이 완료된 후 일부 하위 여행이 있습니다. (n-1)/2 = O(n)절차 후에 이러한 하위 여행이 많아야 한다는 사실에 유의하십시오 .
서브 트립 연결
이제 우리는 서브 트립을 차례로 고려합니다. 우리가 subtrip이있는 경우 s=(x,...,y)subtrip이 있다면, 우리는 그냥 끝나는 도시의 우리 해시 테이블에서 볼 t=(...,x)로 끝나는이 x. 그렇다면, 우리는 연결할 t및 s새로운 subtrip합니다. 그렇지 않다면, 이것이 우리 s의 첫 번째 서브 트립입니다. 으로 u=(y,...)시작하는 다른 서브 트립이 있는지 확인 y합니다. 그렇다면 s및 u. 서브 트립이 하나만 남을 때까지이 작업을 수행합니다 (이 서브 트립은 원래의 전체 여행입니다).
내가 somtehing을 간과하지 않았 으면 좋겠지 만이 알고리즘은 다음에서 실행되어야합니다.
- 에서 서브 트립에 티켓 추가를 구현하면 에서 모든 서브 트립 (최대
O(n))을 구성 할 수 있습니다 . 좋은 포인터 구조 나 그와 비슷한 것이 있다면 문제가되지 않을 것입니다 (서브 트립을 연결 목록으로 구현). 또한 해시 테이블에서 두 값을 변경하는 것은 (상각) 입니다. 따라서이 단계는 시간을 소비 합니다.O(n)O(1)O(1)O(n) - 하나만 남을 때까지 서브 트립을 연결하는 것도에서 수행 할 수 있습니다
O(n). 너무 보니 두 번째 단계에서 수행되는 작업 인 해시 테이블 조회, 포인터 연결 등O(1)으로 수행 할 수있는 분할 및 서브 트립 연결이 필요O(1)합니다.
따라서 전체 알고리즘에는 시간이 걸리며 O(n), 이는 최소한 모든 티켓 을 확인 해야 할 수 있으므로 최적의 O바운드 일 수 있습니다 .
나는 작은 파이썬 프로그램을 작성했고, 하나는 count에, 다른 하나는 src와 dst 매핑을 위해 두 개의 해시 테이블을 사용합니다. 복잡성은 사전 구현에 따라 다릅니다. 사전에 O (1)이 있으면 복잡성은 O (n)이고 사전에 STL 맵과 같이 O (lg (n))이 있으면 복잡성은 O (n lg (n))입니다.
import random
# actual journey: a-> b -> c -> ... g -> h
journey = [('a','b'), ('b','c'), ('c','d'), ('d','e'), ('e','f'), ('f','g'), ('g','h')]
#shuffle the journey.
random.shuffle(journey)
print("shffled journey : ", journey )
# Hashmap to get the count of each place
map_count = {}
# Hashmap to find the route, contains src to dst mapping
map_route = {}
# fill the hashtable
for j in journey:
source = j[0]; dest = j[1]
map_route[source] = dest
i = map_count.get(source, 0)
map_count[ source ] = i+1
i = map_count.get(dest, 0)
map_count[ dest ] = i+1
start = ''
# find the start point: the map entry with count = 1 and
# key exists in map_route.
for (key,val) in map_count.items():
if map_count[key] == 1 and map_route.has_key(key):
start = key
break
print("journey started at : %s" % start)
route = [] # the route
n = len(journey) # number of cities.
while n:
route.append( (start, map_route[start]) )
start = map_route[start]
n -= 1
print(" Route : " , route )
여기에 문제에 대한보다 일반적인 해결책을 제공합니다.
같은 공항에서 여러 번 정차 할 수 있지만 모든 티켓을 정확히 1 번 사용해야합니다.
여행의 각 부분에 대해 하나 이상의 티켓을 가질 수 있습니다.
각 티켓에는 src 및 dst 공항이 포함됩니다.
보유한 모든 티켓은 무작위로 정렬됩니다.
원래 출발 공항 (첫 번째 src)과 목적지 (마지막 dst)를 잊어 버렸습니다.
내 메서드는 지정된 모든 도시를 포함하는 도시 목록 (벡터)을 반환하고, 그렇지 않으면 빈 목록을 반환합니다. 도시를 여행하는 여러 가지 방법이있는 경우이 메서드는 사전 순으로 가장 작은 목록을 반환합니다.
#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<map>
using namespace std;
struct StringPairHash
{
size_t operator()(const pair<string, string> &p) const {
return hash<string>()(p.first) ^ hash<string>()(p.second);
}
};
void calcItineraryRec(const multimap<string, string> &cities, string start,
vector<string> &itinerary, vector<string> &res,
unordered_set<pair<string, string>, StringPairHash> &visited, bool &found)
{
if (visited.size() == cities.size()) {
found = true;
res = itinerary;
return;
}
if (!found) {
auto pos = cities.equal_range(start);
for (auto p = pos.first; p != pos.second; ++p) {
if (visited.find({ *p }) == visited.end()) {
visited.insert({ *p });
itinerary.push_back(p->second);
calcItineraryRec(cities, p->second, itinerary, res, visited, found);
itinerary.pop_back();
visited.erase({ *p });
}
}
}
}
vector<string> calcItinerary(vector<pair<string, string>> &citiesPairs)
{
if (citiesPairs.size() < 1)
return {};
multimap<string, string> cities;
set<string> uniqueCities;
for (auto entry : citiesPairs) {
cities.insert({ entry });
uniqueCities.insert(entry.first);
uniqueCities.insert(entry.second);
}
for (const auto &startCity : uniqueCities) {
vector<string> itinerary;
itinerary.push_back(startCity);
unordered_set<pair<string, string>, StringPairHash> visited;
bool found = false;
vector<string> res;
calcItineraryRec(cities, startCity, itinerary, res, visited, found);
if (res.size() - 1 == cities.size())
return res;
}
return {};
}
다음은 사용 예입니다.
int main()
{
vector<pair<string, string>> cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"Y", "W"}, {"W", "Y"}};
vector<string> itinerary = calcItinerary(cities); // { "W", "X", "Y", "W", "Y", "Z" }
// another route is possible {W Y W X Y Z}, but the route above is lexicographically smaller.
cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"W", "Y"} };
itinerary = calcItinerary(cities); // empty, no way to travel all cities using each ticket exactly one time
}
참조 URL : https://stackoverflow.com/questions/2991950/one-way-flight-trip-problem
'programing' 카테고리의 다른 글
| 동적 크기 UICollectionView 셀 (0) | 2021.01.15 |
|---|---|
| std :: fstream에서 FILE * 가져 오기 (0) | 2021.01.15 |
| 파이썬 하위 프로세스 Popen 환경 경로? (0) | 2021.01.15 |
| 화면에 PIL 이미지를 표시하는 방법은 무엇입니까? (0) | 2021.01.14 |
| 특정 줄에 공백이있는 sed 삽입 줄 (0) | 2021.01.14 |