Я пытаюсь реализовать A* algorithm (с визуализацией в Qt).У меня есть этот метод:
result_path astar_algorithm::calculate(mapview* m_view)
{
map_view = m_view;
auto closed_set = std::vector<std::shared_ptr<node>>();
auto start_node = std::make_shared<node>(_start);
auto open_set = std::vector<std::shared_ptr<node>>{start_node};
std::map<node, node> came_from;
std::shared_ptr<node> current;
while (!open_set.empty())
{
current = *std::min_element(open_set.begin(), open_set.end());
if (*current == _end)
{
// TODO: Reconstruct a result path!!!
break;
}
open_set.erase(std::find(open_set.begin(), open_set.end(), current));
closed_set.push_back(current);
auto neighbors = get_neighbors(*current);
for (auto& neighbor : neighbors)
{
if (std::find_if(closed_set.begin(), closed_set.end(),
[&](std::shared_ptr<node> const& p) { return *p == neighbor; }) !=
closed_set.end())
continue;
auto tentative_g_score = current->G + 1;
if (std::find_if(open_set.begin(), open_set.end(), [&](std::shared_ptr<node> const& p) {
return *p == neighbor;
}) == open_set.end())
{
neighbor.G = tentative_g_score;
neighbor.H = heuristic_cost_estimate(neighbor.pos, _end);
neighbor.parent = current;
open_set.push_back(std::make_shared<node>(neighbor));
}
else if (tentative_g_score < neighbor.G)
{
neighbor.parent = current;
neighbor.G = tentative_g_score;
}
}
}
auto result = result_path();
while (*current != *start_node)
{
result.path.push_back(current->pos);
current = current->parent;
}
result.path.push_back(start_node.pos);
std::reverse(result.path.begin(), result.path.end());
return result;
}
Он работает, но у меня есть несколько проблем:
if (std::find_if(closed_set.begin(), closed_set.end(),
[&](std::shared_ptr<node> const& p) { return *p == neighbor; }) !=
closed_set.end())
continue;
Эта строка проверяет, присутствует ли node в std::vectorи если это так, он продолжает цикл (тогда есть вторая строка, подобная этой, он просто проверяет, действительно ли узел не присутствует в векторе).Я думаю, что лучшим способом было бы сохранить эти узлы в векторе, а затем поиск и дальнейшее добавление было бы проще (потому что мне просто нужно проверить, удалось ли insert).
Проблема заключается в том, afaik,чтобы сделать эту работу, я должен реализовать оператор <.И я так и сделал.Я также сделал == и !=:
class node
{
public:
node() {}
node(const QPoint& p) : pos(p) {}
bool operator == (const node& o ) const { return pos == o.pos; }
bool operator == (const QPoint& o ) const { return pos == o; }
bool operator != (const node& o) const {return pos != o.pos; }
bool operator <(const node& o ) const { return G + H < o.G + o.H; }
QPoint pos;
std::shared_ptr<node> parent;
int G = 0;
int H = 0;
};
Он отлично работает для более раннего поиска std::min_element (он ищет узел с самым низким значением F (F=G+H)), он использует < оператор.Но затем я попытался использовать набор, поэтому эти два вектора в начале метода были установлены, и когда я хотел просто insert или даже проверить, есть ли уже узел в наборе, а затем insert, у меня возникла проблема,Многие из этих nodes будут иметь то же значение G+H, что и лабиринт, который я использовал, был довольно простым (то есть лабиринт полностью без рельефа).Я проверил это в отладчике, и узлы с уникальными значениями .pos (QPoint) не были добавлены в набор точно так же, как они не были уникальными (но если узел имел значение G+H, отличное от любого узла вустановить, было бы добавлено).Для вектора работают те же самые узлы, конечно, потому что нет никаких проверок, я все тщательно проверил в отладчике.
Я не знаю, ошибаюсь ли я, но я думал, что он будет использовать== или != операторов, но, как видно из этого ответа: link , на самом деле используется оператор <, который в моем случае не будет различать два узла (потому что уникальная часть каждого узлаего положение в сетке (узел представляет собой блок в сетке, который может представлять лабиринт или что-то подобное))
Итак, что-то я делаю неправильно или я действительно правильно понимаю, и вставка(который проверяет, является ли элемент уникальным) или проверяет, существует ли элемент в наборе, использует оператор <, и я ничего не могу с этим поделать?(Потому что я хотел бы иметь мой оператор < со сравнением G+H, а затем я бы хотел, чтобы поиск / вставка использовал оператор == для сравнения)
Это пример, который я написал (Я забыл, что у меня есть компилятор Microsoft C ++ из командной строки - cl.exe)
#include <algorithm>
#include <iostream>
#include <memory>
#include <set>
class Point
{
public:
int _x, _y;
Point() : _x(0), _y(0) {}
Point(int x, int y) : _x(x), _y(y) {}
bool operator==(const Point& p) const { return _x == p._x && _y == p._y; }
bool operator!=(const Point& p) const { return _x != p._x && _y != p._y; }
};
class node
{
public:
node() {}
node(const Point& p) : pos(p) {}
bool operator==(const node& o) const { return pos == o.pos; }
bool operator==(const Point& o) const { return pos == o; }
bool operator!=(const node& o) const { return pos != o.pos; }
bool operator<(const node& o) const { return G + H < o.G + o.H; }
Point pos;
std::shared_ptr<node> parent;
int G = 0;
int H = 0;
};
int main()
{
node n1(Point(0, 0));
n1.G = 1;
n1.H = 1;
node n2(Point(1, 1));
n2.G = 2;
n2.H = 2;
node n3(Point(2, 2));
n3.G = 1;
n3.H = 1;
std::set<node> nodes;
nodes.insert(n1);
nodes.insert(n2);
nodes.insert(n3);
auto min = (*std::min_element(nodes.begin(), nodes.end())).pos;
std::cout << min._x << " " << min._y << '\n';
std::cout << nodes.size() << '\n';
}
>main.exe
0 0
2
std::min_element работает, но это 3 уникальных узла для меня (разные .pos значения), поэтому должно быть 3узлы в наборе.И это то, чего я хочу достичь