Простейшая реализация

Пример реализации A* алгоритма на C++ приведен здесь. В качестве функции веса w(u,v), функция EdgeCost, определенная в 3.2.2 используется. Эвристика A* реализована таким образом:

DWORD SearchGraph::CostNorm(CellRef crSrc, CellRef crDst)

// Возвращает недооценку стоимости пути от crSrc до crDst

// в массиве dwMinEdgeCost сохранены стоимости всевозможных граней

{

int iDX = abs(crSrc.X()-crDst.X());

int iDY = abs(crSrc.Y()-crDst.Y());

return dwMinEdgeCost[edDiagMod]*min(iDX,iDY) +

dwMinEdgeCost[edAxisMod]*abs(iDX-iDY);

}

Класс FibHeap стандартная куча Фибоначчи из узлов FibHeapNode.

cr для сохранения ссылки на ячейку узла

g стоимость на данный момент самого лучшего пути к cr

h мин. оценка стоимости пути от cr до адресата

Массив Nodes[]- справочная таблица, используемая, чтобы найти либо указатель в FibHeapNode для вершины, которая находится на данный момент в PQ, или специальные значения обозначающие, что вершина уволена или не посещена. Когда найдено, что вершина не посещена, то она находится в U, когда найдено что она уволена, то она находится в R (см. 4.2.1), иначе она находится в PQ. Память для FibHeapNode выделена вначале, когда вершина помещена в PQ и освобождается, когда она увольняется. Каждый узел FibHeapNode требует намного больше памяти, чем вход в Nodes[] (34 байта против 4 в нашей реализации). Число вершин в PQ в любое время в среднем намного меньше, чем общее число вершин (наши тесты показывают почти логарифмическую зависимость, хотя при самом плохом случае зависимость будет линейной, это вряд ли произойдет).

DWORD SearchGraph::AStarPath(

EdgeDir *&pedEdges, // Выход: список направлений грани

int &iNumEdges, // Выход: число граней в pedEdges

CellRef crBeg, // Вход: исходная ячейка

CellRef crEnd // Вход: ячейка адресат

)

{

PFibHeapNode *Nodes = new PFibHeapNode[dwTotalCells];

EdgeDir *ed = new EdgeDir[dwTotalCells];

PFibHeapNode pU, pV, pReuse = NULL;

FibHeap PQ;

CellRef crU, crV;

DWORD dwCost;

int iV, i;

// Установим, что все узлы не посещены

for (i = 0; i < dwTotalCells; i++)

Nodes[i] = notvisited;

// Вставка исходного узла

Nodes[IndexOf(crBeg)] = pU = new FibHeapNode;

pU->cr = crBeg;

pU->g = 0;

pU->h = CostNorm(crBeg, crEnd);

PQ.Insert(pU);

// Пока можно посещаем все

while ((pU = PQ.ExtractMin()) != NULL) {

// Если достигли адресата выйдем

crU = pU->cr;

if (crU == crEnd) {

dwCost = pU->g; // Окончательная стоимость

delete pU;

break;

}

// Проверка возможных путей от U к его соседям

for (EdgeDir edp = 0; edp < NUMEDGEDIRECTIONS; edp++) {

// Вычисление кандидата с новой наименьшей стоимостью

dwCost = pU->g + EdgeCost(crV, crU, edp);

// Если значение больше ограничения

// ( т.е. вне карты), то пропустим его

if (dwCost >= infinity) continue;

iV = IndexOf(crV);

pV = Nodes[iV];

if (pV == retired) continue; // не можем улучшить

if (pV == notvisited) { // Вставка в очередь первый раз

if (pReuse != NULL) {

pV = pReuse;

pReuse = NULL;

} else pV = new FibHeapNode;

Nodes[iV] = pV;

ed[iV] = edp;

pV->cr = crV;

pV->g = dwCost;

pV->h = CostNorm(crV, crEnd);

PQ.Insert(pV);

} else if (dwCost g) { // Может улучшим !?

if (dwCost == pV->g) {

if (rand() g = dwCost;

PQ.DecreaseKey(pV);

}

}

}

if (crU == crEnd) { // Мы нашли путь

// Подсчет числа граней возврата пути

for (iNumEdges = 0; crU != crBeg; iNumEdges++)

WalkEdge(crU, crU, OppositeEdge(ed[IndexOf(crU)]));

// Реконструирование пути по граням при помощи

// перебора по возвратам & в обратном направлении ...

pedEdges = new EdgeDir[iNumEdges];

EdgeDir *ped = pedEdges + iNumEdges;

for (crU = crEnd; crU != crBeg; )

WalkEdge(crU, crU,

OppositeEdge(*(--ped) = ed[IndexOf(crU)]));

} else { // Путь не найден

return 0

delete[] ed;

pedEdges = NULL;

dwCost = 0;

}

// Освобождение памяти (PQ, освобождает узлы поставленные

// в очередь самостоятельно)

if (pReuse != NULL) delete pReuse;

delete[] Nodes;

delete[] ed;

return dwCost;

}

7.3