5
Tôi tiến hành một thư viện tìm đường dẫn. QuickGraph, thư viện biểu đồ mở, phù hợp với tất cả các yêu cầu của tôi nhưng tôi đã gặp một vấn đề. Tôi cần các thuật toán đường đi ngắn nhất để bỏ qua các cạnh không thể vượt qua được bởi tác nhân chuyển động hiện tại. Những gì tôi muốn là một cái gì đó như thế này:QuickGraph - Làm thế nào tôi có thể tạo A * để bỏ qua các cạnh cụ thể?
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);
tôi có thể tưởng tượng được giải quyết vấn đề này bằng cách tạo một bản sao của đồ thị và xóa các cạnh không thể vượt qua, nhưng nó là sự lãng phí không cần thiết của các nguồn tài nguyên của máy tính. Có thể một, xin vui lòng, gợi ý cho tôi về cách giải quyết vấn đề này? Hoặc là không có giải pháp và tôi nên cập nhật nguồn?
Việc hack nhanh sẽ làm cho các cạnh không thể vượt qua có trọng lượng lớn hơn tổng trọng lượng của đường đi ngắn nhất thực. Thuật toán A * sẽ luôn di chuyển các đường dẫn chứa các cạnh "không thể vượt qua" của bạn đến cuối hàng đợi ưu tiên và sẽ tìm thấy đường đi ngắn nhất thực sự. Điểm bất lợi của phương pháp này là * nếu mọi đường dẫn tới mục tiêu đi qua một cạnh "không thể vượt qua" thì thuật toán bị tấn công sẽ chọn một đường dẫn, thay vì làm điều đúng và thất bại *. –
@EricLippert Cách giải quyết khác có thể là bạn sẽ kiểm tra chiều dài đường dẫn kết quả và nếu nó lớn hơn trọng số cạnh "không thể vượt qua" của bạn, bạn mong đợi nó không tìm được đường dẫn. – Luaan
Nếu bạn muốn chỉ định phương thức truy xuất khoảng cách phương thức tùy chỉnh, không phải là những thứ như 'DelegateIncidenceGraph' có nghĩa là để thực hiện những gì bạn cần? – Superbest