그래프에서 주어진 거리 (경로 길이) 내에 두 노드가 있는지 확인하십시오.

Question

주어진 두 노드 (start 및 goal)가 특정 거리 내에 있는지 확인하는 파이썬 함수를 구현하려고합니다 (예 : dist = 4) 그래프에서.

두 노드 사이에서 최단 경로 (Breadth First Algorithm 사용)를 찾은 다음 최단 경로 길이가 지정된 거리 (dist = 4)보다 작은 지 (또는 같은지) 확인하십시오. 그러나 이것은 분명히 최상의 솔루션이 아니며 오버 헤드가 많습니다. 이 두 가지 파이썬 함수를 시작으로, 이러한 함수가 이러한 함수를 갖도록 수정할 수있는 방법을 안내해 주시겠습니까?

내가 언급했듯이, 나는 그 자체로 발견 된 경로에 관심이 없다. 우리의 관심은 두 개의 노드가 내에 서로 규정 된 거리에 있는지 아닌지에 있습니다. YES 또는 NO 반환 플래그이면 충분합니다.

def bfs_paths(graph, start, goal): 
    queue = [(start, [start])] 
    while queue: 
     (vertex, path) = queue.pop(0) 
     for next in graph[vertex] - set(path): 
      if next == goal: 
       yield path + [next] 
      else: 
       queue.append((next, path + [next])) 

def shortest_path(graph, start, goal): 
    try: 
     return next(bfs_paths(graph, start, goal)) 
    except StopIteration: 
     return None 

Answer 1

사이의 최단 거리를 찾을 필요가 없습니다. 원하는 dist 다음에 bfs를 자르면됩니다. 컷오프 전에 목표 노드를 방문하지 않으면 시작과 목표 사이의 거리가 dist 이상입니다. 또한 비슷한 방식으로 dfs를 사용할 수 있습니다. 깊이가 dist보다 커지면 검색을 차단하십시오. 이 검색 방법을 Depth Limited Search라고합니다.