C # A * Алгоритм с расширенным объектом состояния - PullRequest
Новая
       79

C # A * Алгоритм с расширенным объектом состояния

0 голосов
/ 07 декабря 2018

Я пытаюсь реализовать алгоритм A *, чтобы решить следующее:

  1. У меня есть начальное состояние
  2. Я могу применить «Действие», чтобы перейти от одногосостояние в другое состояние
  3. Я хочу достичь конечного состояния за наименьшее количество действий
  4. Применение действия к данному состоянию просто (= быстро)
  5. все состояние представляет собой сложный объект (= огромный в памяти и медленно клонируется)

Проблема возникает из пункта 5 /.

Действительно, при поиске возможных потомков из текущего состояния я не могу каждый раз создавать совершенно новое состояние, потому что это будет слишком дорого (как с точки зрения памяти, так и скорости).В результате я работаю с одним состоянием, которое меняю, чтобы отразить результирующее состояние при применении действия к прежнему состоянию.(Я могу откатить действие).Я думал о реализации A * с чем-то, как показано ниже: 

    //_state; //represent the "singleton" states that I can apply and rollback actions instead of cloning it
    while (openNodes.Any())
    {
        var currentNode = openNodes.DeQueue();
        currentNode.AdvanceFromStart(_state); //make _state such as all action on the path from the root to currentNode are played

        if (IsFinal(_state))
            return;

        AddToVisitedStates(_state);
        foreach(var transition in currentNode.GetPossibleActions())
        {
            var childNode = new Node(initialState:_state,action:transition.Action);
            //here _state is still reflecting the situation from the currentNode point of view
            childNode.ApplyAction(_state);
            //now _state reflect the situation from childNode point of view
            if (WasVisited(_state))
            {
                childNode.RollbackAction(_state);                
                continue;
            }

            if (childNode.CostToReachNode == 0 ||
                currentNode.CostToReachNode + transition.Cost < childNode.CostToReachNode)
            {
                childNode.CostToReachNode = node.CostToReachNode + transition.CostToReachNode;
                childNode.CostToReachFinal = childNode.CostToReachNode + HeuristicToReachFinalFromState(_state);
                openNodes.ReOrder(childNode);
            }
            if (!openNodes.Contains(childNode))
                openNodes.Add(childNode);

            childNode.RollbackAction(_state);
        }
        currentNode.RollbackToInitialState(_state);//make _state as initially setup
    }

Я не фанат этого решения.Есть ли в алгоритме A * что-то, чего мне не хватает, что помогло бы?Я еще не закончил имплантацию. Видите ли вы какие-то возникающие проблемы / некоторые моменты, которые нужно поднять?

Может быть, A * не правильный алгоритм, я открыт для любого повода к чему-то другому.

PD: если уместно, это для реализации C #

1 Ответ

0 голосов
/ 07 декабря 2018

Вы можете сделать его более похожим на обычный A *, сохранив в каждом объекте не состояние, а последовательность решений, принятых начиная с начального состояния, которое привело к нему.Если вы хотите иметь дело с состоянием, посмотрите на последовательность принятых решений, которые привели к текущему состоянию, вернитесь к общему предку с состоянием, к которому вам нужно перейти, и затем перейдите к этому набору записанных решений.Стоимость такого изменения составляет не более одного постоянного фактора, умноженного на глубину дерева решений.Если он сильно разветвлен и сбалансирован, он может быть не таким глубоким.

Другим вариантом может быть какая-то версия https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search или поиск с ограниченным расхождением с использованием лучшего ответа, найденного до сих пор (из предыдущих итераций) вместе с эвристикой A *, чтобы избежать узлов, которые не могут привести к возможному ответу.Когда вы завершаете проход, когда (после усечения) текущий предел несоответствия или глубины фактически не мешает вам исследовать каждый узел, который вы хотели, вы знаете, что нашли лучший ответ.

...