Путь функция поиска


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

// Searches for a path from [start] to [end].
// Predicate [passable] should take an std::pair<int,int> and return true if the node is passable.
// Nodes in path are stored in [out].
// Return value is a pair.  With first being a bool to indicate if a path was found,
// and second an iterator for the end of the path
template<typename OutputIterator, typename PassablePR>
std::pair<bool, OutputIterator> ShortestPath(std::pair<int,int> start, std::pair<int,int> end, PassablePR passable, OutputIterator out)
{
    typedef std::pair<int,int> node;

    std::pair<bool, OutputIterator> ret(false, out);

    // queue of nodes expanding out from the starting point
    std::queue<node> q;

    // keep track of visited nodes so we don't visit them twice
    std::vector<node> visited_nodes;
    auto visited = [&visited_nodes] (node n) {
        return std::find(visited_nodes.begin(), visited_nodes.end(), n) != visited_nodes.end();
    };

    // link child nodes to parents
    std::map<node,node> path_tree;

    q.push(start);
    while(q.empty() == false)
    {
        auto parent = q.front();
        if(passable(parent) && !visited(parent))
        {
            visited_nodes.push_back(parent);

            if(parent == end)
            {
                ret.first = true;
                std::vector<std::pair<int,int>> path;
                auto i = path_tree.find(parent);
                while(i != path_tree.end())
                {
                    path.push_back(i->first);
                    parent = i->second;
                    path_tree.erase(i);
                    i = path_tree.find(parent);
                }

                // path is currently from end to start, so reverse it
                std::copy(path.rbegin(), path.rend(), ret.second);

                return ret;
            }

            auto child(parent);

            // node to the left         
            --child.first;
            q.push(child);          
            if(path_tree.find(child) == path_tree.end())
                path_tree[child] = parent;

            // right
            child.first += 2;
            q.push(child);
            if(path_tree.find(child) == path_tree.end())
                path_tree[child] = parent;

            // above
            --child.first;
            --child.second;
            q.push(child);
            if(path_tree.find(child) == path_tree.end())
                path_tree[child] = parent;

            // and below
            child.second += 2;
            q.push(child);
            if(path_tree.find(child) == path_tree.end())
                path_tree[child] = parent;
        }
        q.pop();
    }
    return ret;
}

Тестируем его:

int main()
{
    int grid[5][5] =
    { { 0, 1, 0, 0, 0 },
      { 0, 0, 0, 1, 0 },
      { 0, 1, 0, 1, 0 },
      { 0, 1, 0, 1, 0 },
      { 0, 0, 0, 1, 0 } };

    std::vector<std::pair<int,int>> path;

    auto ret = ShortestPath(std::pair<int,int>(0,0), std::pair<int,int>(4,4),
        [&grid] (std::pair<int,int> n) -> bool {
            if(ben::WithinBoundsInclusive(std::pair<int,int>(0,0), std::pair<int,int>(4,4), n) == false)
                return false;
            return grid[n.first][n.second] == 0;
        },
        std::back_inserter(path));

    if(ret.first)
    {
        std::cout << "Path found\n";

        std::for_each(path.begin(), path.end(),
            [](std::pair<int,int> n) {
                std::cout << '(' << n.first << ',' << n.second << ")\n";
            });
    }
    else
        std::cout << "Path not found\n";
}


2288
13
задан 9 февраля 2011 в 09:02 Источник Поделиться
Комментарии
1 ответ

// keep track of visited nodes so we don't visit them twice
std::vector<node> visited_nodes;
auto visited = [&visited_nodes] (node n) {
return std::find(visited_nodes.begin(), visited_nodes.end(), n) != visited_nodes.end();
};

Каждый раз, когда вы должны проверить, находится ли точка посетили, это будет просканировать за весь список visited_nodes. Лучше сделать СТД::набор

// path is currently from end to start, so reverse it
std::copy(path.rbegin(), path.rend(), ret.second);

А затем строит путь и обращая его, вы могли бы построить путь назад.

Когда дело доходит до построения все дочерние узлы, я думаю, что ваш подход вызывает недоумение. Вы бы лучше построить новый узел, а затем повторно использовать узел. Как это, непонятно, что вы делаете. Этот раздел кода тоже повторяющиеся. Я бы сделал что-то вроде

int x_dir = {0, 0, 1, -1}
int y_dir = {1, -1, 0, 0}

for(int pos = 0; pos < 4; pos++)
{
node child = parent;
child.first += x_dir[pos];
child.second += y_dir[pos];
...
}

Другие заметки:

Использование карты будет o(зарегистрируйте), если вы используете многомерный массив для хранения данных для каждой точки вы можете сделать это в O(1) времени.

Используя пар, чтобы держать координат легко. Однако, я полагаю, что его лучше есть класс Point с X и y элементы. Я думаю, что это делает происходящее более ясным. Кроме того, класс может инкапсулировать точки в соседней ячейке логики.

9
ответ дан 11 февраля 2011 в 08:02 Источник Поделиться