그래프 검색 알고리즘

Question

저는 몇 가지 특이한 속성을 가진 그래프 알고리즘을 찾고 있습니다.

그래프의 각 가장자리는 "위쪽" 가장자리이거나 "아래쪽" 가장자리입니다.

유효한 경로는 무한한 수의 "위"로 이동한 다음 무한한 수의 "아래로"로 이동할 수 있으며 그 반대의 경우도 마찬가지입니다.그러나 방향을 두 번 이상 변경할 수는 없습니다.

예를 들어, 유효한 경로는 "up"b "up"c "e"e "e"down "f"up "b"down c "up"d 일 수 있습니다.

두 노드 사이의 최단 유효 경로를 찾는 좋은 알고리즘은 무엇입니까?동일한 길이의 최단 경로를 모두 찾는 것은 어떻습니까?

Answer 1

경험적 방법이 없다고 가정하면 다익스트라의 알고리즘 꽤 괜찮을 겁니다.새로운 엣지를 고려할 때마다 해당 엣지의 "선조"에 대한 정보를 저장하세요.그런 다음 불변성(한 방향만 변경)을 확인하고 위반되면 되돌립니다.

여기의 조상은 최단 경로를 따라 현재 노드에 도달하기 위해 통과한 모든 가장자리입니다.조상 정보를 저장하는 좋은 방법 중 하나는 숫자 쌍으로 저장하는 것입니다.U가 위이고 D가 아래인 경우 특정 가장자리의 조상은 다음과 같을 수 있습니다. UUUDDDD, 이는 쌍이 될 것입니다 3, 4.불변성 때문에 세 번째 숫자는 필요하지 않습니다.

우리는 dijkstra의 알고리즘을 사용했기 때문에 여러 최단 경로를 찾는 것이 이미 처리되었습니다.

Answer 2

어쩌면 그래프를 일반 방향 그래프로 변환한 다음 기존 알고리즘을 사용할 수도 있습니다.

한 가지 방법은 그래프를 두 개의 그래프로 분할하는 것입니다. 하나는 모든 위쪽 가장자리가 있고 다른 하나는 모든 아래쪽 가장자리가 있고 그래프 1의 모든 노드와 그래프 2의 해당 노드 사이에 방향이 지정된 가장자리가 있습니다.

먼저 그래프 1에서 시작하여 그래프 2에서 끝나고 그 반대 방향으로 해결한 다음 가장 짧은 솔루션을 확인합니다.

Answer 3

누군가는 당신의 기준을 생각할 것입니다 BFS 여기서 일해야 해.열린 목록에 노드를 추가할 때마다 사용 중인 방향(위 또는 아래)을 보유하는 구조체와 방향이 아직 전환되었는지 여부를 나타내는 부울 플래그로 이를 래핑할 수 있습니다.이는 해당 노드에서 나가는 가장자리가 유효한지 결정하는 데 사용될 수 있습니다.

동일한 길이의 모든 최단 경로를 찾으려면 지금까지 구조체에 통과한 가장자리 수를 포함하십시오.첫 번째 최단 경로를 찾으면 경로 길이를 기록하고 열린 목록에 노드 추가를 중지하세요.현재 길이의 모든 경로를 확인할 때까지 목록의 나머지 노드를 계속 진행한 다음 중지합니다.

Answer 4

ㅏ* 특별히 제작된 비용(G 점수)과 휴리스틱(H 점수) 기능으로 처리할 수 있습니다.

비용의 경우 경로의 방향 변경 횟수를 추적하고 두 번째 변경에 무한한 비용을 추가할 수 있습니다(예:해당 지점에 대한 검색을 중단합니다.)

휴리스틱은 특히 휴리스틱을 허용 가능하고(목표까지의 최소 거리를 과대평가하지 않음) 단조롭게 유지하려는 경우 좀 더 생각해야 합니다.(A*가 최적의 솔루션을 찾도록 보장하는 유일한 방법입니다.)

휴리스틱을 생성하는 데 사용할 수 있는 도메인에 대한 추가 정보가 있을까요?(즉.그래프 노드의 x,y 좌표는 무엇입니까?)

물론 풀려는 그래프의 크기에 따라 먼저 너비 우선 검색이나 Dijkstra 알고리즘과 같은 더 간단한 알고리즘을 시도해 볼 수 있습니다.기본적으로 모든 검색 알고리즘이 가능하며 모든 검색 알고리즘에 대해 어쨌든 비용 함수(또는 이와 유사한)가 필요합니다.

Answer 5

표준 그래프 검색 기능이 있는 경우 다음과 같이 말하세요. Graph.shortest(from, to) 라이브러리에서는 C#/의사 코드로 반복하고 최소화할 수 있습니다.

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

최소 경로를 기억해야 하고 표준 함수가 데이터를 반환하는 경우 다음과 같이 발음할 수도 있습니다.

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

어디 myMin 두 가지를 비교해야합니다 [fst, nxt, C, AC, BD] 튜플을 만들고 거리가 더 낮은 것을 떠나거나 둘 다 가정하고 reduce 스마트한 기능입니다.

그래프가 크고 메모리를 전혀 사용하지 않는 경우(동적으로 생성된 경우 가능함) 약간의 메모리 오버헤드가 있지만 실제로는 속도 오버헤드가 없습니다.