작은 세계 그래프를 통해 길을 찾는 가장 효율적인 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/221311

문제

노드 클러스터를 연결하는 가장자리가있는 가중 노드 바다가 있습니다. 이 그래프는 전형적인 작은 세계 레이아웃을 따릅니다.

프로세서 파워에 비용이 많이 드지 않는 경로 찾기 알고리즘을 찾고 싶습니다. 노드가 가장 호의적 인 가중치가 가장 좋은 경로를 따라 경로를 찾으려면 가장 빠른 경로가 가장 중요한 요소가 아닙니다. 이 알고리즘은 또한 부하 베어링 및 트래픽 리우팅을 고려합니다.

(Sidenote : 여기서 신경망을 사용할 수 있습니까?)

감사

보고 있어요 아코. 이런 종류의 문제에 대해 ACO보다 더 좋은 것이 있습니까?

맞아 ㅏ* 알고리즘은로드 밸런싱없이 비용이 가장 적거나 가장 빠른 경로를 찾습니다.

가장 빠르거나 가장 짧은 경로는 가장 중요한 경로가 아니라고 가정 해 봅시다. 더 중요한 것은 가중 노드에 특정 값이있는 경로를 따르는 것입니다. No1.

NO2. A*를 사용하면 해당 경로의 트래픽이 과부하가 걸리면 갑자기 그 경로가 중복됩니다. 따라서 a*만큼 시원하게도, 고유 한로드 밸런싱을위한 특정 기능이 없습니다.

- 내가 착각하고 오해하지 않는 한*

그렇다면 ACO를 능가하는 것은 무엇입니까?

그것은 정말로 ACO와 A* 사이의 쇼처럼 보입니다. A*에 대한 긍정적 인 이야기가 너무 많았습니다.

먼저 다윗에 대한 응답으로; 뒷면 접지에서 ACO 시뮬레이션을 실행하고 최고의 경로를 만들 수 있습니다. 예, 초기 시작 비용이 있지만 시작은 운 좋게도 필수는 아닙니다. 그래서 나는 시뮬레이션을 여러 번 실행할 여유가 있습니다. 진정한 문제는 연결된 소스와 대상 노드를 찾는 것입니다. 반면에*는 이것을 아주 쉽게 할 수있을 것 같습니다. 이제이 네트워크가 수백만 개의 노드에서처럼 두려운 커지면 어떻게 되는가. A*가 쉽게 확장 할 수 있습니까?

나는 더 이상 연구 할 것이다. 그러나 나는 당신에게 마지막 질문을 남깁니다!

A*는 Antnet (ACO)뿐만 아니라 확장 할 수 있습니까?

도움이 되었습니까?

해결책

일반 노트

Dijkstra의 알고리즘 및 IT 변형 A* "그래프를 통한 최소 비용으로 경로를 찾으십시오. 중요한 것은 a) 그래프를 올바르게 정의하고 b) 적절한 비용 기능을 정의하는 것입니다.

변화하는 비용 기능에 직면하여 Dijksta는 솔루션을 다시 계산해야합니다.

하중 밸런싱의 경우 최적 경로를 계산할뿐만 아니라 홍수 충전 동작을 사용하여 대안을 찾기 위해 가능한 경로 세트 (비용별로 정렬)를 만듭니다. 특정 문제와 비용 기능에 대한 지식만이 이것이 작동하는지 여부와 방법에 대답 할 수 있습니다.

개미 식민지 최적화 반면에 비용 함수가 변경되는 동안/후 반복을 계속함으로써 변화하는 비용 기능에 적응하는 데 훨씬 유연한 것으로 보인다.

능률

이것은 문제 영역에 크게 의존합니다. 좋은 휴리스틱이 있다면 (참조 A* 기사의 복잡성 섹션) 및 거의 비용 변경과*의 다항식 런타임은 반복적 인 재 계산을 선호 할 수 있습니다. 반면에 ACO는 대략적인 솔루션을 수렴하기 전에 반복적으로 반복해야합니다. 비용 변경이 매우 자주 발생하면 정보가 알고리즘 상태 내에 정보가 유지되기 때문에 A*-Solution을 업데이트하는 것보다 일정한 속도로 반복을 계속하는 것이 더 효율적 일 수 있습니다. ACO는 약속하지 않습니다 그만큼 그래도 최적의 솔루션 및 아마 "좋은"솔루션으로 수렴하기 전에 시작 비용이 더 높습니다. 다시 한 번 그것은 특정 도메인, 그래프 및 비용 기능과 최적성에 대한 요구 사항에 달려 있습니다.

다른 팁

A*를 사용하면 경로 비용이 일정 할 필요가 없으므로 다음 그래프로 시작할 수 있습니다.

A---1---B---1---C
|               |
\-------1-------/

우리가 A에서 C로 가고 싶은 경우, 처음에는 ABC가 2이기 때문에 AC 경로를 선택합니다. AC는 1이기 때문에 AC 경로를 선택합니다. 경로에 추가 용어를 추가 할 수 있습니다.

A---r---B---r---C
|               |
\-------r-------/

~와 함께

r(NM) = k(NM) + users(NM) / 10

어디

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

사용자가 시스템에 추가되면 경로 AC는 20 명의 사용자 (1 + 20/10) = 3에서 ABC보다 비싸게됩니다. 다시.

A*의 실제 힘은 각 연결 비용을 계산하는 데 사용하는 휴리스틱입니다.

이 문제에 가장 일반적으로 사용되는 알고리즘은 다음과 같습니다 A* (별), 일반화 된 것입니다 Dijkstra의 알고리즘 추가 휴리스틱 검색 - 휴리스틱의 목적은 일반적인 검색이 더 빨리 완료되도록 검색 목표를 향해 검색을 지시하는 것입니다.

이 알고리즘에는 많은 변형, 파생 버전 및 개선 사항이 있으며 Google 검색 또는 Wikipedia 페이지는 좋은 출발점이어야합니다.

확실히*. A*는 경로가 없으면 최상의 경로를 찾거나 경로가 전혀 없습니다. 예를 들어이 보트의 경로는 a*를 사용하여 계산되었습니다.

A* Example on Game Map
(원천: cokeandcode.com)

여기에 있습니다 대화식 Java 데모 놀기 위해. 이 알고리즘은 수면으로 느려지므로 작동하는 것을 볼 수 있습니다. 이 속도가 느려지지 않으면 1 초 이내에 경로를 찾을 수 있습니다.

알고리즘은 간단하지만 강력합니다. 각 노드에는 3 값이 있으며 G는이 노드의 비용입니다. H는이 노드에서 대상으로 추정되는 비용이며 F는 둘 다의 합입니다 (전체 경로에 대한 추측). A*는 열린 목록과 폐쇄 목록의 두 목록을 유지합니다. 열린 목록에는 지금까지 탐색되지 않은 모든 노드가 포함되어 있습니다. 닫힌 목록 탐색 된 모든 노드. 알고리즘이 이미이 노드에 연결된 모든 노드를 이미 테스트 한 경우 노드가 탐색 된 것으로 카운트합니다 (연결된 것은 노드 간의 대각선 이동이 허용되는 경우 수평 및 수직으로 만 의미 할 수 있음).

알고리즘은 다음과 같이 설명 할 수 있습니다

  1. P를 시작점으로하자
  2. g, h 및 f 값을 p에 할당
  3. 열린 목록에 p를 추가하십시오 (이 시점에서 P는 해당 목록의 유일한 노드입니다).
  4. B를 열린 목록에서 가장 좋은 노드로 둡니다 (Best == 최저 F 값)
    • B가 목표 노드 인 경우 -> 종료하면 경로를 찾았습니다.
    • 열린 목록이 비어 있으면 -> 종료, 경로는 존재하지 않습니다.
  5. c를 b에 연결된 유효한 노드로합시다
    • g, h 및 f를 할당하십시오
    • C가 열린 또는 닫힌 목록에 있는지 확인
      • 그렇다면 새로운 경로가 가장 효율적인지 확인하십시오 (F- 값이 낮음)
        • 그렇다면 경로를 업데이트하십시오
      • 그렇지 않으면 열린 목록에 c를 추가합니다
    • b에 연결된 모든 노드에 대해 5 단계를 반복하십시오
  6. 닫힌 목록에 B 추가 (우리는 모든 이웃을 탐색했습니다)
  7. 4 단계에서 반복하십시오.

또한 살펴보십시오 위키 백과 구현 세부 사항.

이런 종류의 문제를 처리하기위한 NN 구현에 대해 들었습니다. 따라서 NNS를 사용하려면 결국 길을 찾을 수 있지만 "유전자 알고리즘"과 비교하여 열등해야합니다.

계산/시간 소비가 문제라면 유전자 알고리즘을 사용하는 것이 좋습니다. 이것은 그들이 예외적 인 문제의 유형입니다.

가스는 특정 솔루션에 대한 만족도를 설명하는 기능을 기반으로합니다. 귀하의 요구에 맞게이 기능을 수정할 수 있습니다 (예 : 경로 비용뿐만 아니라 원하는 요소를 포함 할 수 있습니다).

일반적인 dijkstra가 충분하지 않습니까?

http://improve.dk/generic-dijkstras-algorithm/

dijkstras 알고리즘, 작은 예

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top