У меня есть следующий рабочий A * код в C #:
static bool AStar(
IGraphNode start,
Func<IGraphNode, bool> check,
out List<IGraphNode> path)
{
// Closed list. Hashset because O(1).
var closed =
new HashSet<IGraphNode>();
// Binary heap which accepts multiple equivalent items.
var frontier =
new MultiHeap<IGraphNode>(
(a, b) =>
{ return Math.Sign(a.TotalDistance - b.TotalDistance); }
);
// Some way to know how many multiple equivalent items there are.
var references =
new Dictionary<IGraphNode, int>();
// Some way to know which parent a graph node has.
var parents =
new Dictionary<IGraphNode, IGraphNode>();
// One new graph node in the frontier,
frontier.Insert(start);
// Count the reference.
references[start] = 1;
IGraphNode current = start;
do
{
do
{
frontier.Get(out current);
// If it's in the closed list or
// there's other instances of it in the frontier,
// and there's still nodes left in the frontier,
// then that's not the best node.
} while (
(closed.Contains(current) ||
(--references[current]) > 0) &&
frontier.Count > 0
);
// If we have run out of options,
if (closed.Contains(current) && frontier.Count == 0)
{
// then there's no path.
path = null;
return false;
}
closed.Add(current);
foreach (var edge in current.Edges)
{
// If there's a chance of a better path
// to this node,
if (!closed.Contains(edge.End))
{
int count;
// If the frontier doesn't contain this node,
if (!references.TryGetValue(edge.End, out count) ||
count == 0)
{
// Initialize it and insert it.
edge.End.PathDistance =
current.PathDistance + edge.Distance;
edge.End.EstimatedDistance = CalcDistance(edge.End);
parents[edge.End] = current;
frontier.Insert(edge.End);
references[edge.End] = 1;
}
else
{
// If this path is better than the existing path,
if (current.PathDistance + edge.Distance <
edge.End.PathDistance)
{
// Use this path.
edge.End.PathDistance = current.PathDistance +
edge.Distance;
parents[edge.End] = current;
frontier.Insert(edge.End);
// Keeping track of multiples equivalent items.
++references[edge.End];
}
}
}
}
} while (!check(current) && frontier.Count > 0);
if (check(current))
{
path = new List<IGraphNode>();
path.Add(current);
while (current.PathDistance != 0)
{
current = parents[current];
path.Add(current);
}
path.Reverse();
return true;
}
// Yep, no path.
path = null;
return false;
}
Как мне сделать это быстрее? Нет примеров кода, пожалуйста; это вызов, который я поставил перед собой.
Изменить: Чтобы уточнить, я ищу любые советы, предложения, ссылки и т. Д., Которые относятся к A * в целом. Код является лишь примером. Я не просил никаких примеров кода, потому что они слишком облегчают реализацию описываемой методики.
Спасибо.