최단 경로를 찾을 때 너비 우선 검색은 어떻게 작동합니까?
나는 약간의 연구를 해왔고이 알고리즘의 작은 부분이 빠져있는 것 같습니다. 너비 우선 검색의 작동 방식을 이해하지만 각 개별 노드가 어디로 갈 수 있는지 알려주는 것이 아니라 정확히 특정 경로로 이동하는 방법을 이해하지 못합니다. 혼란을 설명하는 가장 쉬운 방법은 예제를 제공하는 것입니다.
예를 들어 다음과 같은 그래프가 있다고 가정 해 봅시다.
그리고 내 목표는 A에서 E로 얻는 것입니다 (모든 가장자리는 가중되지 않습니다).
나는 A에서 시작합니다. 왜냐하면 그것이 나의 기원이기 때문입니다. A를 대기열에 넣은 다음 즉시 A를 대기열에서 빼고 탐색합니다. A가 B와 D에 연결되어 있기 때문에 B와 D가 생성됩니다. 따라서 B와 D를 모두 대기열에 넣습니다.
B를 대기열에서 빼서 탐색 한 후 A (이미 탐색) 및 C로 연결되는 것을 발견했습니다. 그래서 C를 대기열에 넣습니다. 그런 다음 D를 대기열에서 빼고 E로 연결됩니다. 그런 다음 C를 대기열에서 빼고 목표 인 E로 연결되는 것도 발견했습니다.
나는 가장 빠른 경로가 A-> D-> E라는 것을 논리적으로 알고 있지만 너비 우선 검색이 정확히 어떻게 도움이되는지 잘 모르겠습니다. 경로를 어떻게 기록하여 마무리해야 할 때 결과를 분석하고 볼 수 있는지 최단 경로는 A-> D-> E입니까?
또한 실제로 트리를 사용하고 있지 않으므로 "부모"노드가없고 자식 만 있습니다.
엄밀히 말하면 BFS (Breadth-First Search) 자체만으로는 BFS가 최단 경로를 찾지 않기 때문에 최단 경로를 찾을 수 없습니다. BFS는 그래프를 검색하기위한 전략을 설명하지만 반드시 검색해야한다고 말하는 것은 아닙니다. 특히 무엇이든.
Dijkstra의 알고리즘 은 BFS를 조정하여 단일 소스 최단 경로를 찾을 수 있습니다.
원점에서 노드까지의 최단 경로를 검색하려면 그래프의 각 노드에 대해 현재 최단 거리와 최단 경로에있는 선행 노드의 두 항목을 유지해야합니다. 처음에는 모든 거리가 무한대로 설정되고 모든 선행 작업은 비어 있습니다. 이 예에서는 A의 거리를 0으로 설정 한 다음 BFS를 진행합니다. 각 단계에서 하위 항목의 거리를 개선 할 수 있는지 확인합니다. 즉, 원점에서 선행 작업까지의 거리에 탐색중인 모서리의 길이에 해당 노드의 현재 최고 거리보다 작습니다. 거리를 개선 할 수있는 경우 새 최단 경로를 설정하고 해당 경로를 획득 한 선행 작업을 기억하십시오. BFS 대기열이 비어 있으면 노드 (예 : E)를 선택하고 이전 노드를 다시 원래 위치로 이동합니다.
약간 혼란스러워 보이는 경우, 위키 백과에는 주제에 대한 의사 코드 섹션이 있습니다.
위에서 지적한 것처럼 BFS는 다음과 같은 경우에만 그래프에서 최단 경로를 찾는 데만 사용할 수 있습니다 .
루프가 없습니다
모든 모서리의 무게는 동일하거나 무게가 없습니다.
가장 짧은 경로를 찾으려면 소스에서 시작하여 광범위한 첫 번째 검색을 수행하고 대상 노드를 찾을 때 중지하면됩니다. 추가로해야 할 일은 방문한 모든 노드에 대해 이전 노드를 저장할 배열 이전 [n]을 갖는 것입니다. 이전 소스는 null 일 수 있습니다.
경로를 인쇄하려면 대상에 도달하고 노드를 인쇄 할 때까지 소스에서 이전 [] 배열을 반복합니다. DFS를 사용하여 유사한 조건에서 그래프에서 최단 경로를 찾을 수도 있습니다.
그러나 가중치가 적용된 모서리와 루프를 포함하는 그래프가 더 복잡한 경우 더 복잡한 버전의 BFS 즉 Dijkstra 알고리즘이 필요합니다.
에서 여기 자습서
"그래프의 모든 모서리가 가중되지 않은 경우 (또는 동일한 가중치) 노드를 처음 방문 할 때 소스 노드에서 해당 노드까지의 최단 경로라는 매우 유용한 특성이 있습니다."
BFS를 사용하여 최단 거리 를 찾는 데 사용되는
그래프 질문을 궁극적으로 3 일 동안 낭비했습니다.
경험을 나누고 싶다.
When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges
#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)
#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path
#3
It does not matter what queue you use
deque/queue(c++) or
your own queue implementation (in c language)
A circular queue is unnecessary
#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.
#5
Wikipedia BFS will work, and is sufficient.
https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode
위의 대안을 모두 시도하여 3 일을 잃어 버렸습니다. 위에서 다시 확인하고 다시 확인하는
것은 문제가 아닙니다.
(위의 5 가지 문제가 발견되지 않으면 다른 문제를 찾는 데 시간을 투자하십시오).
아래 의견에서 더 많은 설명 :
A
/ \
B C
/\ /\
D E F G
위의 그래프
그래프가 아래로 내려 간다고 가정하면
A의 경우 인접 항목은 B & C이고
B의 경우 인접 항목은 D & E
이고 C의 경우 인접 요소는 F & G입니다
예를 들어 시작 노드는 A입니다.
A, B, C에 도달하면 A에서 B & C까지의 최단 거리는 1입니다.
B를 통해 D 또는 E에 도달하면 A 및 D까지의 최단 거리는 2 (A-> B-> D)입니다.
마찬가지로 A-> E는 2 (A-> B-> E)입니다.
또한 A-> F & A-> G는 2
이제 노드 사이의 1 거리 대신 6이면 대답에 6
예제를 곱하십시오.
각 거리가 1이면 A-> E는 2입니다 (A-> B-> E = 1 + 1 )
각각의 거리가 6 인 경우 A-> E는 12 (A-> B-> E = 6 + 6)입니다.
yes, bfs may take any path
but we are calculating for all paths
if you have to go from A to Z, then we travel all paths from A to an intermediate I, and since there will be many paths we discard all but shortest path till I, then continue with shortest path ahead to next node J
again if there are multiple paths from I to J, we only take shortest one
example,
assume,
A -> I we have distance 5
(STEP) assume, I -> J we have multiple paths, of distances 7 & 8, since 7 is shortest
we take A -> J as 5 (A->I shortest) + 8 (shortest now) = 13
so A->J is now 13
we repeat now above (STEP) for J -> K and so on, till we get to Z
Read this part, 2 or 3 times, and draw on paper, you will surely get what i am saying, best of luck
Based on acheron55 answer I posted a possible implementation here.
Here is a brief summery of it:
All you have to do, is to keep track of the path through which the target has been reached. A simple way to do it, is to push into the Queue the whole path used to reach a node, rather than the node itself.
The benefit of doing so is that when the target has been reached the queue holds the path used to reach it.
This is also applicable to cyclic graphs, where a node can have more than one parent.
The following solution works for all the test cases.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();
for (int i = 0; i < testCases; i++)
{
int totalNodes = sc.nextInt();
int totalEdges = sc.nextInt();
Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();
for (int j = 0; j < totalEdges; j++)
{
int src = sc.nextInt();
int dest = sc.nextInt();
if (adjacencyList.get(src) == null)
{
List<Integer> neighbours = new ArrayList<Integer>();
neighbours.add(dest);
adjacencyList.put(src, neighbours);
} else
{
List<Integer> neighbours = adjacencyList.get(src);
neighbours.add(dest);
adjacencyList.put(src, neighbours);
}
if (adjacencyList.get(dest) == null)
{
List<Integer> neighbours = new ArrayList<Integer>();
neighbours.add(src);
adjacencyList.put(dest, neighbours);
} else
{
List<Integer> neighbours = adjacencyList.get(dest);
neighbours.add(src);
adjacencyList.put(dest, neighbours);
}
}
int start = sc.nextInt();
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
int[] costs = new int[totalNodes + 1];
Arrays.fill(costs, 0);
costs[start] = 0;
Map<String, Integer> visited = new HashMap<String, Integer>();
while (!queue.isEmpty())
{
int node = queue.remove();
if(visited.get(node +"") != null)
{
continue;
}
visited.put(node + "", 1);
int nodeCost = costs[node];
List<Integer> children = adjacencyList.get(node);
if (children != null)
{
for (Integer child : children)
{
int total = nodeCost + 6;
String key = child + "";
if (visited.get(key) == null)
{
queue.add(child);
if (costs[child] == 0)
{
costs[child] = total;
} else if (costs[child] > total)
{
costs[child] = total;
}
}
}
}
}
for (int k = 1; k <= totalNodes; k++)
{
if (k == start)
{
continue;
}
System.out.print(costs[k] == 0 ? -1 : costs[k]);
System.out.print(" ");
}
System.out.println();
}
}
}
'Programing' 카테고리의 다른 글
| Rails 앱이 사용하는 gem 버전을 확인하는 방법 (0) | 2020.07.25 |
|---|---|
| html 웹 페이지에서 모든 요소의 글꼴 속성을 지정하는 방법은 무엇입니까? (0) | 2020.07.25 |
| WebRequest의 본문 데이터 설정 (0) | 2020.07.24 |
| 장고. (0) | 2020.07.24 |
| Rstudio에서 작업 디렉토리를 소스 파일 위치로 설정하기위한 R 명령 (0) | 2020.07.24 |