1
현재 에있는 모든 노드를 찾는 효율적인 방법을 알아 내려고 노력 중입니다. 두 노드 (예 : X
및 Y
) 간의 경로는입니다. 그래프.유향 그래프에서 두 노드 사이에있는 모든 노드를 효율적으로 찾습니다
첫 번째 생각은 X에서 BFS를 실행하고, Y에서 BFS를 실행하고, 방문한 노드의 교차 부분을 가져 오는 것입니다. X와 Y 사이의 모든 경로를 열거 할 필요가 없습니다. X에서 Y까지의 경로에있는 모든 노드를 찾으십시오.
제 질문은 더 최적화 된 방법이 있습니까?
X부터 Y까지의 모든 경로에있는 모든 노드의 발견을 목표 상태로 프레임 화하는 방법을 잘 모르겠습니다. 목표 상태 (즉, X에서 Y까지의 최단 경로/최소 비용 경로)에 대한 최단/최적 경로를 찾는 맥락에서 A *만을 사용했습니다. – kk415kk
X와 Y 사이의 노드를 이해하면 해당 경로에서 통과 할 노드와 같을 것입니다. 그렇다면이 문제는 X와 Y 사이의 경로를 찾는 것과 동일 할 것이며 X에서 Y까지 가장 짧은 경로를 찾는 것입니까? 어쩌면 나는 당신의 질문을 이해하지 못했을 것입니다. – Joelmob
그래, 최단 경로 찾기 문제의 일부가 될 수 있지만 X에서 Y 모든 경로에있는 모든 노드를 찾을 필요가. X에서 Y까지 길이가 다른 여러 경로가있을 수 있습니다. * 검색을 현명하게 안내 할 것입니다 다른 경로의 일부 검색을 피하십시오. – kk415kk