IDA * (Итеративное углубление звезды) решает поиск пути в C #

Question

Я создал универсальную версию IDA * для решения проблемы поиска пути.Я использовал дорожную карту Румынии, и у меня есть некоторые проблемы.

Румынская карта, которую я использую: https://dzone.com/storage/temp/11185033-romanianmap-astar.jpg

Например, для дороги Арад в Бухарест конечный результат - Тимишоара-Лугож-Мехадия-Дробета-Крайова-Рымнику-Вылча-Сибиу-Фэгэраш-Бухарест.Также для дороги Бухарест-Арад конечный результат - Питешти-Рымнику-Вылча-Сибиу-Арад (что является правильным результатом).Нормально ли иметь разные результаты для одной и той же дороги?Есть метод, который может оптимизировать алгоритм для более быстрого отображения результата?

Изначально я начал реализовывать A *, вдохновленный Leniel Maccaferri: https://github.com/leniel/AStar и использовать классы для IDA *.

Для эвристики я использовал манхэттенское расстояние и формулу Хаверсайна для оценки в км.

Вот что я попробовал:

public async Task<List<string>> ResolveIDAStarAlgorithm(string startCity, string destinationCity)
{
            /* Creating the graph. */
            Graph graph = new Graph();
            await CreateGraph(graph);

            /* Store the start Node */
            Node start = graph.Nodes[startCity];
            /* Store the destination Node */
            Node destination = graph.Nodes[destinationCity];

            /* Sets the cost of the start node. */
            start.GCost = 0;

            /* Sets the heuristic cost. */
            start.HCost = Haversine.Distance(start, destination);

            /* Sets the f cost limit. */
            double fCostLimit = start.GCost + start.HCost;

            List<string> path = new List<string>();

            while (true)
            {
                /* Start IDA Star pathfinding search. */
                Node foundTemp = await SearchPath(start, destination, start.GCost, fCostLimit);

                switch (foundTemp.Status)
                {
                    /* A new cost limit has been found. */
                    case SEARCHRETURN.BOUND:

                        fCostLimit = foundTemp.HCost;
                        break;

                    /* The path was found. */
                    case SEARCHRETURN.FOUND:

                        path = RetracePath(start, destination);
                        return path;

                    /* No path has been found. */
                    case SEARCHRETURN.NOT_FOUND:
                        return null;
                }
            }

        }


        public async Task<Node> SearchPath(Node currentNode, Node targetNode, double gCost, double fCostLimit)
        {
            Node retNode = new Node();
            Path<Node> path = new Path<Node>(currentNode);

            double distance(Node node1, Node node2) =>
                                                   node1.Neighbors.Cast<EdgeToNeighbor>().Single(
                                                       etn => etn.Neighbor.Key == node2.Key).Cost;

            /* If the current node is the target, the search process will finish. */
            if (currentNode == targetNode)
            {
                retNode.Status = SEARCHRETURN.FOUND;
                return retNode;
            }

            double newFCostLimit = gCost + Haversine.Distance(currentNode, targetNode);


            if (newFCostLimit > fCostLimit)
            {
                retNode.Status = SEARCHRETURN.BOUND;
                retNode.HCost = newFCostLimit;
                return retNode;
            }


            if (!_visitedNodes.Contains(currentNode.Key))
            {
                _visitedNodes.Add(currentNode.Key);
            }


            foreach (Node neighbor in path.LastStep.Neighbours)
            {

                if (_visitedNodes.Contains(neighbor.Key))
                {
                    continue;
                }


                if (!_visitedNodes.Contains(neighbor.Key))
                {
                    double newCostNeighbor =  distance(currentNode, neighbor) + Haversine.Distance(currentNode, neighbor);
                    if (newCostNeighbor < neighbor.GCost || !_visitedNodes.Contains(neighbor.Key))
                    {
                        neighbor.GCost = gCost + newCostNeighbor;
                        neighbor.HCost = Haversine.Distance(neighbor, targetNode);
                        neighbor.PathParent = currentNode;
                    }

                    Node t = await SearchPath(neighbor, targetNode, newCostNeighbor, fCostLimit);
                    switch (t.Status)
                    {
                        case SEARCHRETURN.BOUND:
                            if (t.HCost < _costLimit)
                            {
                                _costLimit = t.HCost;
                            }
                            break;
                        case SEARCHRETURN.FOUND:
                            return t;
                        case SEARCHRETURN.NOT_FOUND:
                            continue;
                    }
                }

            }

            if (_costLimit == _minValue)
            {
                retNode.Status = SEARCHRETURN.NOT_FOUND;
            }
            else
            {
                retNode.HCost = _costLimit;
                retNode.Status = SEARCHRETURN.BOUND;
            }

            _visitedNodes.Remove(currentNode.Key);
            return retNode;

        }


        public List<string> RetracePath(Node start, Node destination)
        {
            List<string> path = new List<string>();
            Node currentNode = destination;

            double totalCost = 0;
            double distance(Node node1, Node node2) =>
                                                  node1.Neighbors.Cast<EdgeToNeighbor>().Single(
                                                      etn => etn.Neighbor.Key == node2.Key).Cost;

            while (currentNode != start)
            {
                path.Add(currentNode.Key);

                totalCost += distance(currentNode, currentNode.PathParent);

                currentNode = currentNode.PathParent;

            }

            path.Add((totalCost * 0.99).ToString());

            path.Reverse();

            return path;

        }