yield를 사용하여 변수를 재귀 함수에 전달하여 최소값을 찾습니다.

Question

space = [0, 100]이라고합시다.

나는 공간의 일부분을 제공 받았고 아마도 중복 될 수있다. 예를 들어

,

[0, 30], [0, 20], [10, 40], [30, 50], [50, 90], [70, 100] 

은 단편들의 집합이다.

상기 세트로부터 선택된 전체 공간에 걸쳐있는 단편들의 세트의 예는 다음은 [0, 100]

모든 요소를 ​​갖고 있기 때문에

가

[0, 30], [10, 40], [30, 50], [50, 90], [70, 100] 

프래그먼트의 세트가 전체 공간에 걸쳐

다른 예 [10, 40] 않고 ​​이전의 예에서의 집합이다

[0, 30], [30, 50], [50, 90], [70, 100] 

이다.

각 조각 세트에 대해 비용을 계산할 수 있습니다.

집합 비용은 조각 추가의 한계 비용 합계입니다.

def get_marginal_cost(fragment): 
    return RTT + (fragment[1] - fragment[0])/bandwidth 

여기서 RTT 및 bandwidth 상수이다 :

세트에 단편을 첨가하는 한계 비용 함수

가 주어진다.

최소한의 비용을 가진 조각 집합에서 하위 집합을 찾으려고합니다.

이것은 욕심 많은 알고리즘으로 해결할 수 없기 때문에 모든 가능한 조각 세트를 고려하고 싶습니다.

난 node 각 단편을 고려하고 edgeu[0] < v[0] <= u[1] <= v[1] 경우 vu 단편 사이가 존재한다고 정의하여 모든 가능한 경우를 고려 Depth First Search 알고리즘을 사용 하였다.

잎 노드 내가 (아마도) 대표 아래의 기능에 의해, 전체 space를 구성하는 조각의 집합의 모든 가능한 경우 발전기 개체를 얻을 수 있었다 (100)

로 끝나는 조각입니다.

def dfs(a, start, path=None): 
    if path is None: 
     path = [start, ] 
    if start[1] == space: 
     yield path 
    for frgmt in a - set(path): 
     l = frgmt[0] 
     r = frgmt[1] 
     if start[0] < l <= start[1] <= r: 
      yield dfs(a, frgmt, path + [frgmt, ]) 

그러나, 나는 내가에 최소의 비용을 찾을 수 있도록 내가 내 dfs 함수 내에서 위에서 언급 한 get_marginal_cost 기능을 사용할 수있는 방법을 내가 통과 할 수있는 방법과 minimum 변수 dfs에 기능을 업데이트 확실하지 않다 프로그램 종료.

한계 값을 최소값에 계속 추가하고 if start[1] == space: (공간은 100)에서만 최소값을 확인하고 업데이트해야합니다.

테스트 케이스와 코드는 내가 당신이 잘못 어디로 가는지 정확히 볼 수 충분히 기존의 코드를 이해하지 못했다 두려워 (이 a, 또는 start이 무엇인지 분명하지 않다 http://ideone.com/oN4jWa

Answer 1

에 예를 들어, dfs). 그러나 나는 당신이 해결하려고하는 문제를 파악하고 있다고 생각합니다. 여기에 당신이 설명 된 기본 알고리즘을 사용하여, 그것을 자신을 해결할 줄 방법은 다음과 같습니다 내가 재귀 깊이 우선 탐색을 사용하여 모든 유효한 경로를 찾는 사이의 일을 (최대 분할하여 최소 비용 경로를 찾는 문제를 해결

from operator import itemgetter 

def dfs(space, fragments, path=None, cost=0): 
    if path == None: 
     path = [] 
     path_end = space[0] 
    else: 
     path_end = path[-1][1] 

    for i, fragment in enumerate(fragments): 
     if fragment[0] > path_end: # this fragment would leave a gap (as 
      break     # will all the rest) so we can stop 
     elif path_end < fragment[1]: # useless fragments are skipped 
      new_path = path + [fragment] 
      new_cost = cost + get_marginal_cost(fragment) 
      if fragment[1] == space[1]: # this fragment reaches the end, 
       yield new_path, new_cost # so this is a base case 
      else:  # recursive case 
       for result in dfs(space, fragments[i+1:], # slice frag list 
            new_path, new_cost): 
        yield result # in Python 3.3 and later, you can skip the 
           # loop and just use "yield from dfs(...)" 

def find_minimum_cost_path(space, fragments): 
    fragments.sort(key=itemgetter(0)) # sort by start of the fragments 
    path, cost = min(dfs(space, fragments), key=itemgetter(1)) 
    return path 

)을 선택하고 최소 비용 경로를 선택하십시오 ( min을 호출). dfs을 찾은 경로의 최저 비용 만 반환하도록 변경할 수는 있지만 좀 더 복잡합니다. 단순화를 위해 부품을 분리하여 보관했습니다.

내 dfs 기능의 핵심은 정렬 된 부분의 조각에서만 작동한다는 것입니다. 어떤 데이터 구조를 사용하고 있는지 명확하지 않으므로 find_minimum_cost_path 함수에 sorted이 필요합니다. 조각이 이미 정렬되어 (시작 요소에 의해) 해당 데이터 구조가 슬라이스 될 수 있으면 해당 단계를 제거 할 수 있습니다.