그래프에서주기 찾기 (반드시 해밀턴이나 모든 노드를 방문 할 필요는 없음)

Question

그림 1 (첫 번째 이미지)과 같은 그래프가 있고 빨간색 노드를 연결하여주기를 원하지만 순환은 해밀턴이 아니어야합니다 그림 2과 그림 3 (마지막 두 이미지)과 같습니다. 이 문제는 노드를 두 번 방문 할 수 있기 때문에 TSP보다 훨씬 큰 검색 공간을 가지고 있습니다. TSP와 마찬가지로 큰 그래프에서 모든 조합을 평가하는 것은 불가능하며 경험적으로 시도해야하지만 문제는 TSP와 달리주기 또는 둘러보기의 길이가 고정되어 있지 않다는 것입니다. 왜냐하면, 모든 청색 노드를 방문하는 것은 필수는 아니며, 이는 청색 노드 중 일부를 포함하는 가변 길이를 갖는 원인이되기 때문입니다. 평가를 위해 매회 "유효한"조합을 어떻게 생성 할 수 있습니까? 사이클은 {A, e, B, l, k, j, D, j, k, C, g, f, e} 또는 {A, e, B, l, k, j, D, {A, B, K, C, I, J, i, h, g} 디}.

업데이트 : 최종 목표는 길이와 위험을 고려하여 최적/최적에 가까운 사이클을 평가하는 것입니다 (아래 참조). 그래서 나는 길이를 최소화 할뿐만 아니라 위험을 최소화하려고합니다. 이것은 모든 노드 시퀀스를 알지 못하는 한주기의 위험을 평가할 수 없습니다. 희망이 왜 내가 생성 과정의 중간에 새로운주기를 평가할 수 없는지 명확하게. 다음과 같이 할 수 있습니다 :

• 가능한 사이클을 하나씩 생성하고 평가하십시오.
• 또는 가능한 모든 사이클을 생성 한 다음 평가를 수행하십시오. 위험의

정의 : 사이클을 가정은 다른 모든 빨간색 노드에 기본 노드 (빨간색 노드 중 하나)를 연결하는 고리입니다. 링의 일부 (에지)에서 장애가 발생할 경우 기본 노드에서 빨간색 노드를 연결 해제해야합니다 (원하는 경우). 그러나 우리는 두 번 통과해야만하는 몇 가지 모서리가 있습니다 (모든 적색 노드를 연결하는 해밀턴주기가 없기 때문에). 그리고 그 모서리에서 오류가 발생하면 일부 적색 노드가 완전히 끊어 질 수 있습니다. 그래서 사이클의 위험은 위험한 가장자리의 길이를 합한 것입니다 (우리는 링/투어에서 두 번씩) 각 위험한 가장자리를 잘라내는 경우 손실되는 빨간색 노드의 수를 곱합니다.

그리고 here 링크 Excel로이다 :

내가 5 개 빨간색 노드와 95 개 블루 노드를 포함 일하고 3D 그래프의 실제 예는 아래에있다 시트는 위의 그래프의 인접 행렬을 포함합니다 (처음 5 개의 노드는 빨간색이고 나머지는 파란색입니다).

Answer 1

조금 더 생각해 보면, 두 번째 빨간색 노드를 사용할 수 있기 때문에 내 솔루션을 다시 작성하는 것이 더 낫다고 판단했기 때문에 빨간색 노드 사이의 경로를 비효율적으로 매핑하는 독창적 인 아이디어를 만들 수 있습니다. 그러나 빨간색 노드 사이의 파란색 노드가 중요하기 때문에 완전히 낭비되지는 않습니다.

backtracking algorithm과 같이 BFS의 수정 된 버전을 사용하면 실제로이 문제를 해결할 수 있습니다. 각각의 고유 한 지점에 대한 다음 정보가있는 대부분은 단순히 더 많은 공간의 비용으로 빠른 거부를 허용, 저장, 첫 번째 두 항목이 실제로 필요합니다

• 전체 전류 경로를.(시작 빨간색 노드가있는 목록)
• 나머지 빨간색 노드. (처음에는 모두 빨간색 노드 임)
• 마지막 빨간색 노드입니다. (처음에는 빨간색 노드 시작)
• 마지막 빨간색 노드 이후 청색 노드 세트입니다. (처음에 비어)
• 1의 수와 노드의 세트 (처음에 비어)
• 2의 카운트 노드 세트 (처음에 비어)

알고리즘은 하나의 시작 노드가 BFS 또는 DFS를 사용하여 인접한 노드를 확장하면 결과가 유효한 둘러보기이거나 확장 될 노드가 거부 될 때까지 반복됩니다. 그래서 기본적인 푸 라우 도시 코드 (현재 경로와 나머지 붉은 점)는 다음과 같습니다. 여기서 rn은 적색 노드 집합, t는 유효한 둘러보기 목록, p/p2는 노드 경로, r/r2는 적색 노드 집합, v는 확장 노드, a는 가능한 노드 확장합니다.

function PATHS2HOME(G,rn) 
    create a queue Q 
    create a list t 
    p = empty list 
    v ← rn.pop() 
    r ← rn 
    add v to p 
    Q.enqueue((p,r)) 
    while Q is not empty 
     p, r ← Q.dequeue() 
     if r is empty and the first and last elements of p are the same: 
      add p to t 
     else 
      v ← last element of p 
      for all vertices a in G.adjacentVertices(v) do 
       if canExpand(p,a) 
        p2 ← copy(p) 
        r2 ← copy(r) 
        add a to the end of p2 
        if isRedNode(a) and a in r2 
         remove a from r2 
        Q.enqueue((p2,r2)) 
    return t 

다음 조건은 노드의 확장을 방지합니다. 전체 목록이 아닐 수도 있습니다.

• 레드 노드 :
  • 는 빨간색 노드가 두 번 이상 사용 된 것 때문이다 (2)의 수를 가지고 노드 세트에있는 경우.
  • 마지막 빨간색 노드와 동일한 경우. 이렇게하면 빨간색 노드가 다른 세 개의 파란색 노드에 인접 해있을 때 "이상한"투어를 방지 할 수 있습니다. 따라서 빨간색 노드 A가 파란색 노드 b, c 및 d에 인접했다고 가정 해보십시오. 그런 다음 둘러보기의 일부가 b-A-c-A-d처럼 보이는 둘러보기를 종료합니다.
• 블루 노드 :
  • 는 빨간색 노드가 두 번 이상 사용 된 것 때문이다 (2)의 수를 가지고 노드 세트에있는 경우.
  • 마지막 빨간색 노드 이후 청색 노드 집합에있는 경우. 이것은 빨간색 노드 사이에 파란색 노드의 순환을 유발하기 때문입니다.

가능한 최적화 :

는
• 접미어 트리의 무언가를 구축하는 것을 사용, 빨간색 노드 사이의 경로를 매핑 할 수 있습니다, 그 다음 경로를 제공 도달 할 수있는 빨간색 노드를 보여줍니다 처럼. 여기서 이점은 확장 경로가 이미 두 번 방문한 빨간색 노드로 연결되는 경우 노드를 확장하지 않는 것입니다. 따라서 최소한 한 번 빨간색 노드가 두 번 방문하면 유용한 검사 일뿐입니다.
• 알고리즘의 병렬 버전을 사용하십시오. 단일 스레드가 큐에 액세스 할 수 있으며 큐의 요소간에 상호 작용이 없습니다. 아마 더 좋은 방법이 있을지도 모르지만. 런타임을 수백 초가 아닌 초 단위로 줄이는 것이 가능할 수 있습니다. 그것은 병렬화 수준과 효율성에 달려 있지만. 이전 알고리즘에도 적용 할 수 있습니다. 실제로이 알고리즘을 사용하여 전환 한 이유는 거의 무효입니다.
• 대기열 대신 스택을 사용할 수 있습니다. 여기에서 가장 큰 이점은 깊이 우선 접근법을 사용하는 것입니다. 대기열의 크기는 상당히 작아야합니다.