5
나는 경로 찾기 라이브러리를 수행한다. QuickGraph, 열린 그래프 라이브러리, 내 모든 요구 사항을 충족하지만 한 가지 문제를 만났습니다. 현재 움직이는 에이전트가 통과 할 수없는 가장자리를 건너 뛰려면 최단 경로 알고리즘이 필요합니다. 내가 원하는 것은이 같은 것입니다 : 나는 그래프의 복사본을 생성하고 지나갈 가장자리를 삭제하여이 문제를 해결 상상할 수QuickGraph - 특정 가장자리를 건너 뛰려면 A *를 어떻게 만들 수 있습니까?
Func<SEquatableEdge<VectorD3>, double> cityDistances = delegate(SEquatableEdge<VectorD3> edge)
{
if(edge.IsPassableBy(agent))
return edgeWeight; // Edge is passable, return its weight
else
return -1; // Edge is impassable, return -1, which means, that path finder should skip it
};
Func<VectorD3, double> heuristic = ...;
TryFunc<VectorD3, IEnumerable<SEquatableEdge<VectorD3>>> tryGetPath = graph2.ShortestPathsAStar(cityDistances, heuristic, sourceCity);
하지만, 컴퓨터의 자원의 불필요한 낭비이다. 하나, 제발,이 문제를 해결하는 방법에 대한 힌트를 주시겠습니까? 아니면 해결책이 없으며 소스를 업데이트해야합니까?
빠른 해킹은 실제 가장 짧은 경로의 총중량보다 큰 가중치를 갖는 것입니다. A * 알고리즘은 항상 "무시할 수있는"가장자리를 포함하는 경로를 우선 순위 대기열의 끝으로 이동시켜 실제 최단 경로를 찾습니다. 이 접근법의 단점은 * 목표까지의 모든 경로가 "통과 할 수없는"경계를 지나면 해킹 된 알고리즘이 올바른 것을 수행하고 실패하는 대신 경로를 선택한다는 것입니다. –
@EricLippert 해결 방법은 해결 방법은 결과 경로 길이를 확인할 수 있으며 "통과 할 수없는"가장자리 무게보다 큰 경우 경로를 찾지 못했을 것으로 예상됩니다. – Luaan
사용자 정의 방법 거리 검색 방법을 지정하려면 'DelegateIncidenceGraph'와 같이 필요한 작업을 수행하지 않아도됩니까? – Superbest