Dyanmic 최단 경로

Question

친구는 캐나다 북쪽 다음 겨울 방학에 깊은 작은 마을에 여행을 계획하고 있습니다. 그들은 모든 여행 옵션을 연구했고 노드가 중개 목적지를 나타내는 지시 된 그래프를 작성했으며 가장자리는 사이의 재로드를 나타냅니다. 이 과정에서 극단적 인 날씨로 인해이 부분의 도로에서 도로가 발생하여 겨울이 매우 느려지고 큰 여행 지연이 발생할 수 있음을 알게되었습니다. 그들은 도로를 따라 얼마나 빨리 이동할 수 있는지 예측할 수있는 우수한 여행 웹 사이트를 발견했습니다. 그러나 여행의 속도는 연중 시간에 따라 다릅니다. 더 정확하게, 웹 사이트는 다음과 같은 형식의 질의 응답 : U를 = (유, v)를 이 두 사이트 U와 V를 연결하는 에지 전자 주어진 위치에서 제안 된 시작 시간 (T)를 주어진 사이트는 값을 반환합니다 FE (t), V의 예상 도착 시간. 웹 사이트는 보장이 FE (t)> 모든 에지 e와 모든 시간 t (당신이 시간에 뒤로 여행 할 수 없음), 그 철에 대한 t (t)는 t의 단조 증가 함수입니다 (즉, 나중에 을 시작하여 일찍 도착하지 않습니다). 그것 이외의 함수 fe는 임의적 일 수 있습니다. 예를 들어, 여행 시간은 계절에 따라 변화하지 않는 지역에서, 우리는 철 (t) =의 t + e, where 전자는 에지 전자의 처음부터 끝까지 여행하는 데 필요한 시간이있을 것입니다. 친구가 웹 사이트를 사용하여 방향성 그래프를 시작 지점에서 원하는 목적지까지 가장 빨리 이동하는 방법을 결정하려고합니다. (당신은 그들이 시간 0에서 시작 을 가정해야하고 웹 사이트에 의해 만들어진 모든 예측이 완전히 올바른 있음.) 우리가 에 웹 사이트를 하나의 쿼리를 치료하는이 작업을 수행하는 다항식 시간 알고리즘을 부여 (기반 특정 에지 e 및 시간 t)를 단일 계산 단계를 취하는 것으로 가정한다.

def updatepath(node): 
     randomvalue = random.randint(0,3) 
     print(node,"to other node:",randomvalue) 
     for i in range(0,n): 
      distance[node][i] = distance[node][i] + randomvalue 

    def minDistance(dist,flag_array,n): 
     min_value = math.inf 
     for i in range(0,n): 
      if dist[i] < min_value and flag_array[i] == False: 
       min_value = dist[i] 
       min_index = i 
     return min_index 

    def shortest_path(graph, src,n): 
     dist = [math.inf] * n 
     flag_array = [False] * n 
     dist[src] = 0 

     for cout in range(n): 
      #find the node index that have min cost 
      u = minDistance(dist,flag_array,n) 
      flag_array[u] = True 
      updatepath(u) 
      for i in range(n): 
       if graph[u][i] > 0 and flag_array[i]==False and dist[i] > dist[u] + graph[u][i]: 
        dist[i] = dist[u] + graph[u][i] 
        path[i] = u 
     return dist 

Dijkstra 알고리즘을 적용했지만 올바르지 않습니까? 동적 인 가장자리를 변경하기 위해 알고리즘을 변경하려면 어떻게해야합니까? 함수가 단조 증가 것을

Answer 1

음 요점이다. 이 속성을 악용하는 알고리즘이 있으며 A *이라고합니다.

누적 비용 : 교수님께서는 누적 비용 중 하나를 두 번 사용하길 원합니다 (이전 노드의 비용이 다음 노드로 이동하는 데 필요한 비용/시간에 간단 해졌습니다).

경험적 비용 : 이것은 예상 비용입니다. 당신이 휴리스틱 비용으로 작업하기 때문에

Disjkstra 접근 방식이 작동하지 않을 것입니다/ 및 비용을 축적 예측했다.

단조 수단을 H (A) < = h를 (A)을 증가 F (A..B) + .IT 단순히 노드 이동할 경우은 B 다음 노드 것을 말한다 선정 안 이전 노드 (이 경우 A)보다 작아야하며 이는 경험적 + 누적입니다.이 속성이있는 경우 A *이 선택하는 첫 번째 경로는 항상 목표 경로이며 되돌릴 필요가 없습니다.

참고 :이 알고리즘의 힘은 가치를 예측하는 방법에 기초합니다.

누적 값으로 보정 할 값을 과소 평가했지만 값을 과대 평가하면 잘못된 경로가 선택됩니다.

알고리즘 :

Create a Min Priority queue. 
insert initial city in q. 

while(!pq.isEmpty() && !Goalfound) Node min = pq.delMin() //this should return you a cities to which your distance(heuristic+accumulated is minial). put all succesors of min in pq // all cities which you can reach, you can better make a list of visited cities s that queue will be efficient by not placing same element twice. Keep doing this and at the end you will either reach goal or your queue will be empty

추가

여기

난 A *를 사용하여 8 퍼즐 - 해결 A는, 그것은 당신에게 비용이 방법에 대한 아이디어를 제공 할 수 있습니다 구현 정의되고 호 작동합니다.

`

private void solve(MinPQ<Node> pq, HashSet<Node> closedList) { 
     while(!(pq.min().getBoad().isGoal(pq.min().getBoad()))){ 
      Node e = pq.delMin(); 
      closedList.add(e); 
      for(Board boards: e.getBoad().neighbors()){ 
       Node nextNode = new Node(boards,e,e.getMoves()+1); 
       if(!equalToPreviousNode(nextNode,e.getPreviousNode())) 
         pq.insert(nextNode); 
       } 
      } 
     Node collection = pq.delMin(); 
      while(!(collection.getPreviousNode() == null)){ 
       this.getB().add(collection.getBoad()); 
       collection =collection.getPreviousNode(); 
     } 
      this.getB().add(collection.getBoad()); 
      System.out.println(pq.size()); 
    } 

는 full 코드에 대한 링크가 여기에있다.