노드 하위 집합을 가져 오는 경로

Question

오늘 꽤 재미있는 인터뷰 질문을했습니다.

한 칩 칩 (예 : 노란색)과 한 칩에서 두 칩 (노란색 -> 녹색, 파란색) 중 하나가 제공됩니다. 결과를 얻기 위해해야하는 최소한의 거래 건수는 얼마입니까?

그래서

A 
A -> B, C 
B -> D, E 
C -> F, G 

내가 B, C에 무역 수의 내가 컬러 A로 시작, 나는 색상 D, E, F, G 얻을 필요가 가정 해 봅시다, 그리고 D, E, F를 얻기 위해 두 무역 , G.

이 문제를 해결하는 데 필요한 알고리즘은 무엇입니까? 결과 집합에서 거꾸로 작업하는 것이었지만 거래가 반복 될 수 있으므로 매우 까다로워 (A 칩 2 개에 대해 하나의 A 칩). 그것은 그래프 문제처럼 보입니다. MST는 매우 유사하게 보이지만, 그것은 내 방향이 틀려서, 나는 (비 고유 경로) 거래를 반복 할 수있다.

Answer 1

간단한 논리로 충분하지만 프로그램/알고리즘은 필요하지 않습니다.

chipsIn = 1 
chipsOut = 2 
changePerTrade = chipsOut - chipsIn 
numTrades = (goalSet.size - startSet.size)/changePerTrade 

: 각 무역은 당신이 (하나) 같은 양으로이 칩의 수를 변경하기 때문에

, 당신은 당신의 세트와 세트 크기의 변화에 ​​의해 설정된 목표 사이 칩의 차이를 나눌 수 있습니다

몇 가지주의 사항 :

주 그 모든 거래는 동일한 입력 및 출력 크기를 가지고 있고, (예를 들어, 모든 칩은 목표 설정을 향한 카운트를 가지고 있다는 가정하에 작동하기 때문에 제한이 유일한 작품 당신이 AB를 얻으려고한다면 ABC를 갖는 것은 실패입니다.)

이렇게하면 목표 세트를 달성 할 수 있는지 여부가 아니라 거래의 최소 수 (최대 거래 수이기도 함) 만 알려줍니다.

---

이 문제를 해결하는보다 일반적인 목적은 가능성의 나무를 탐구하는 것입니다.

이것은 단순히 트리를 탐색하는 것으로, 트리에서 탐색 할 때 노드를 생성합니다. 칩의 나무가 계속 (중복이 허용되는 경우 또는 목록) 모든 노드가 세트입니다

  A 
      | 
      B,C 
     / \ 
    D,E,C  B,F,G 
     |   | 
    D,E,F,G  D,E,F,G 

: 당신의 나무 (귀하의 예를 들어)과 같이 보일 것입니다. 나무의 개념을 설명하는 데 도움이되는 몇 가지 아이디어 :

1. 트리를 아래로 이동하는 것은 작업 진행을 나타냅니다.
2. 하나의 분기를 아래로 이동하면 단일 거래가 나타납니다.
3. 가장 적은 수의 거래를 찾고 모든 거래가 세트의 크기를 1 씩 늘리므로 goalSet.size 개의 트리 수준 만 탐색하면됩니다.

노드 A에서 시작하여 모든 칩을 반복하고 매번 가능한 한 한 단계 씩 각 단계별로 수행하십시오.

Here은 트리 탐색을 수행하는 방법을 설명하는 위키 백과 문서로, 노드를 탐색 할 때 노드를 만들 수 있습니다.한 번에 하나의 노드 만 추적하면되므로 깊이 우선 검색이 가장 쉽지만 구현이 더 어려울지라도 첫 번째 검색은 더 빠를 가능성이 높습니다.