Я предполагаю, что график представляет собой правильную прямоугольную сетку с узлами препятствий, через которые не должно пройти ни одно из решений. Более того, я предполагаю, что путешествие от узла к соседнему узлу равно 1. Также я понял, что Манхэттенское расстояние используется в качестве эвристического.
Учитывая это, я боюсь, что твое является неправильной реализацией.
Прежде всего, вместо рекурсивного вы должны использовать итеративный подход. Учитывая размер вашего графика, вы наверняка получите Stackoverflows, если это будет правильная реализация.
Во-вторых, кажется, есть проблема с понятиями GValue, HValue, FValue и / или стоимостью. Я чувствую себя обязанным дать неофициальное описание этих терминов.
Простая формула, которую использует A *: F = G + H, где
G - это текущая стоимость проезда от начального узла к текущему узлу. Итак, для начального узла значение Gvalue должно быть 0, любой узел, достижимый из startNode, должен иметь значение G, равное 1 (моё предположение было таким: при переходе от узла к соседнему узлу) я хотел бы подчеркнуть термин «в настоящее время» здесь, потому что gValue узла может измениться во время выполнения алгоритма.
H - эвристическая часть стоимости, обозначающая стоимость от текущего узла до конечного узла. В отличие от части G, значение H узла не меняется вообще (у меня есть сомнения, может быть такая эвристика?, А у вас нет, давайте продолжим), его следует вычислять только один раз. Ваша реализация, похоже, использует Манхэттенское расстояние в качестве эвристики, которая, безусловно, является лучшей эвристикой для такого графа. Но будьте осторожны, мой друг, здесь тоже есть небольшая проблема: абсолютные значения разностей следует брать отдельно и затем суммировать.
А F - это сумма этих значений, обозначающая возможные затраты на решение, проходящее от текущего узла (с учетом вашего графика и эвристики любое вычисленное значение F должно быть равно или меньше фактической стоимости, что хорошо).
Имея это под рукой, я бы использовал SearchNode так:
public class SearchNode {
private int xCoordinate;
private int yCoordinate;
private double gScore;
private double hScore;
public double getfScore() {
return gScore + hScore;
}
public double getgScore() {
return gScore;
}
public void setgScore(int gScore) {
this.gScore = gScore;
}
public SearchNode(int xCoordinate,int yCoordinate, double gScore, SearchNode endNode) {
this.gScore=gScore;
this.hScore = //Manhattan distance from this node to end node
this.xCoordinate =xCoordinate;
this.yCoordinate = yCoordinate;
}
public int getxCoordinate() {
return xCoordinate;
}
public int getyCoordinate() {
return yCoordinate;
}
}
Тогда алгоритм может быть реализован так:
private ArrayList<SearchNode> closedNodes = new ArrayList<SearchNode>();
private ArrayList<SearchNode> openNodes = new ArrayList<SearchNode>();
//create the start and end nodes
SearchNode end = new SearchNode(380, 560, -1, null);
SearchNode start = new SearchNode(115,655, 0, end);
// add start node to the openSet
openNodes.Add(start);
while(openNodes.Count > 0) // while there still is a node to test
{
// I am afraid there is another severe problem here.
// OpenSet should be PriorityQueue like collection, not a regular Collection.
// I suggest you to take a look at a Minimum BinaryHeap implementation. It has a logN complexity
// of insertion and deletion and Constant Complexity access.
// take the Node with the smallest FValue from the openSet. (With BinHeap constant time!)
SearchNode current = openNodes.GetSmallestFvaluedNode(); // this should both retrieve and remove the node fromt he openset.
// if it is the endNode, then we are node. The FValue (or the Gvalue as well since h value is zero here) is equal to the cost.
if (current.EqualTo(end)) // not reference equality, you should check the x,y values
{
return current.getfScore();
}
//check the neighbourNodes, they may have been created in a previous iteration and already present in the OpenNodes collection. If it is the case, their G values should be compared with the currently calculated ones.
// dont forget to check the limit values, we probably do not need nodes with negative or greater than the grid size coordinate values, I am not writing it
// also here is the right place to check for the blocking nodes with a simple for loop I am not writing it either
double neighbourGValue = current.getgScore() + 1;
if (openNodes.Contains(current.getXCoordinate(), current.getYCoordinate() + 1))
{
// then compare the gValue of it with the current calculated value.
SearchNode neighbour = openNodess.getNode(current.getXCoordinate(), current.getYCoordinate() + 1);
if(neighbour.getgScore() > neighbourGValue)
neighbour.setgScore(neighbourGValue);
}
else if(!closedNodes.Contains(current.getXCoordinate(), current.getYCoordinate()))
{
// create and add a fresh Node
SearchNode n = new SearchNode(current.getXCoordinate(), current.getYCoordinate() + 1, neighbourGValue, endNode);
openNodes.Add(n);
}
// do the same for the other sides : [x+1,y - x-1,y - x, y-1]
// lastly add the currentNode to the CloseNodes.
closedNodes.Add(current);
}
// if the loop is terminated without finding a result, then there is no way from the given start node to the end node.
return -1;
Единственный вопрос, который возникает у меня в связи с приведенной выше реализацией, - это строка
if (openNodes.Contains(current.getXCoordinate(), current.getYCoordinate() + 1))
Даже если открытый набор реализован как Min Binary Heap, нет простого способа проверить неминимальные f-значные узлы. Я не могу вспомнить детали сейчас, но я помню реализацию этого со сложностью logN. Более того, моя реализация осуществляла доступ и изменение значения g этого узла (если это необходимо) за один вызов, поэтому вы не потратили время на его восстановление. Независимо от того, было ли изменено значение g, если есть узел с заданными координатами, он возвращал значение true, поэтому новый узел не создавался.
Последнее, что я понял, когда закончил писать все это. Вы сказали, что при любом вводе данных ваша реализация вычисляла тот же результат. Хорошо, если вход, о котором вы говорите, является узлами препятствий, то в большинстве случаев он найдет, независимо от того, что это за реализация, одинаковое расстояние, так как ищет минимально возможное расстояние. На изображении ниже я пытался это объяснить.
