비순환 그래프에서 두 노드 사이에 길이 L의 경로가 있는지 여부를 확인하려고합니다. 내 질문은,이 경우에 사용하는 가장 좋은 알고리즘과 가장 간단한 알고리즘입니다.특정 길이의 경로가 비순환 그래프에 있는지 알아보기
그래프의 최대 노드 수는 50 개이고 가장자리 수는 100 개입니다.
DFS를 사용하는 모든 경로를 찾은 다음 두 경로 사이에 경로가 있는지 확인하려고했지만 온라인 판사가 "제한 시간 초과"라는 대답을 받았습니다.
나는 또한 비용 검색 알고리즘을 사용했으나 부정적인 반응을 보였다.
나는 이러한 문제를 해결하는보다 효율적인 방법이 필요합니다. 고맙습니다.
가 빠르게 DFS 접근 한 후이 될 것입니다 나도 몰라 -하지만 실현 가능한 솔루션을 제공합니다 :
매트릭스A로 그래프를 표현, 그리고 계산
A^L - 길이 L의 경로 나는 사이 j는 경우에만 DFS 솔루션에 관한 또한
A[i][j] != 0
, 경우에 존재 : 당신은 DFS에서을 모든 경로를 찾을 필요가 없습니다 - 당신은 길이 < = L의 경로에 자신을 제한하고로한다 이 트림 일부 바다 일단 길이가 필요한 길이를 초과하면 길이가 L 인 경로가 목표에 도달하면 검색에서 탈출 할 수 있습니다.
다른 가능한 최적화는 bi-directional search 일 수 있습니다.
다음 알고리즘을 사용하여 트리에서 가장 긴 경로를 찾을 수 있다고 생각합니다.
분명히 다음 그래프는 topologicaly 정점을 주문할 수 있습니다 비순환 때문에 길이 L.
알고리즘에 따라 B에서 다른 노드로 갈 수 있다면 2 단계에서 B에서 멈춘 이유는 무엇입니까? 우리는 가장 먼 곳으로 계속 가려고하지 않습니까? "가장 먼 노드"에 대한 정의는 무엇입니까? 여기서 제안하는 알고리즘의 이름은 무엇입니까? –
우리는해야하기 때문에 B에서 멈춰야합니다. 잎 노드이고 다른 곳은 없습니다. 그런 다음 B에서 시작하여 다른 검색을 수행하면 A에 도달하지만 추가로 C로 이동합니다. 노드 X는 X와 거리가 같은 노드 Z가없는 경우 노드 Y에서 가장 멀리 떨어져 있습니다. Z까지는 X에서 Y까지입니다. –
이 알고리즘에 이름이 있는지는 잘 모르겠습니다. 학교에 갔을 때 다시 생각해 냈습니다. 그 당시 그것을 증명해야했지만, 나는 약간 지루하다는 증거를 기억하므로 여기서 다시 시도하려고하지 않았습니다. –
의 경로를 찾을 수를 줄일 수 있습니다. 정점 A를 시작하고 정점 B를 끝내자.
이제 핵심 알고리즘이 시작됩니다. 각 정점에 대해 A에서이 정점까지의 모든 가능한 거리를 계산합니다. 처음에는 길이가 0 인 A에서 A까지 하나의 경로 인 이 있습니다. 그런 다음 토폴로지 순서로 정점을 가져옵니다. 정점 x를 선택할 때 : 각 선행자를보고 여기에서 가능한 거리를 업데이트하십시오.
O (N^3) 시간으로 실행해야합니다.
시작 및 끝 노드가 문제에 지정되어 있습니다. –
수정 된 Dijkstra 알고리즘을 사용하여 모든 정점에 대해 원점까지의 최소 거리를 저장하는 대신 가능한 모든 거리를 원하는 거리보다 작거나 같게 저장합니다.
그래프에 가중치가 있습니까? – kilotaras
아니요, 가중치가 적용되지 않습니다. –