#c #search #graph #a-star #heuristics
#c #Поиск #График #a-star #эвристика
Вопрос:
Я столкнулся с проблемой, в которой мне предоставляется введенная пользователем матрица (строки и столбцы). Пользователь также предоставит начальное состояние (строка и столбец) и целевое состояние. Задача состоит в том, чтобы использовать * search для поиска пути от начального узла до целевого узла.
Пример матрицы приведен ниже,
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 G
0 0 0 1 1 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 0 0 0
0 1 0 1 0 1 1 0 0 0
0 1 0 1 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
S 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 0 0 0
где «S» — начальное состояние, а «G» — целевое состояние. 0 — это состояния, в которые вы можете перейти, а 1 — препятствия в сетке, вы не можете перейти к ним.
Разрешено 3 действия.
- Вверх на одну ячейку (стоимость равна 1)
- исправьте одну ячейку (стоимость равна 3)
- по диагонали вверх вправо (стоимость равна 2)
Чтобы решить эту проблему, я использовал расстояние Манхэттена в качестве своей эвристической функции и вычислил эвристические значения для всех моих состояний…. Они выглядели примерно так (для указанной выше сетки)
10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 0
10 9 8 7 6 5 4 3 2 1
11 10 9 8 7 6 5 4 3 2
12 11 10 9 8 7 6 5 4 3
13 12 11 10 9 8 7 6 5 4
14 13 12 11 10 9 8 7 6 5
15 14 13 12 11 10 9 8 7 6
16 15 14 13 12 11 10 9 8 7
17 16 15 14 13 12 11 10 9 8
18 17 16 15 14 13 12 11 10 9
19 18 17 16 15 14 13 12 11 10
20 19 18 17 16 15 14 13 12 11
21 20 19 18 17 16 15 14 13 12
Теперь, это мой код для * search
void A_search()
{
priority_queue<node, vector<node>, CompareCost>q; // Priority Queue is used.
// node contains 4 elements... 1. "Heuristic" value, 2. Index row, 3. Index Col, 4. Actual Cost until this point
q.push(node(heuristic[srow][scol], srow, scol, 0)); // srow, scol is start state. 0 is Actual Cost
while (!q.empty())
{
node temp = q.top();
path_cost = temp.cost; // path_cost is global variable, which stores actual cost until this point
path[temp.i][temp.j] = true; // Boolean array, which tells the path followed so far.
q.pop();
if (temp.i == grow amp;amp; temp.j == gcol) // If goal state is found, we break out of the loop
break;
if (temp.i > 0) // Checking for rows above the current state.
{
if (arr[temp.i - 1][temp.j] != 1) // Checking if index above current state is obstacle or not
{
q.push(node(heuristic[temp.i - 1][temp.j] (temp.cost 1), temp.i - 1, temp.j, temp.cost 1)); // pushing the above index into queue
}
if (temp.j - 1 < cols)
{
if (arr[temp.i - 1][temp.j 1] != 1) // Diagonal Index checking
{
q.push(node(heuristic[temp.i - 1][temp.j 1] (temp.cost 2), temp.i - 1, temp.j 1, temp.cost 2));
}
}
}
if (temp.j - 1 < cols) // Horizontal Index... Checking if column has exceeded the total cols or not
{
if (arr[temp.i][temp.j 1] != 1) // Obstacle check for horizontal index
{
q.push(node(heuristic[temp.i][temp.j 1] (temp.cost 3), temp.i, temp.j 1, temp.cost 3));
}
}
}
}
И это результат, который я получаю после запуска этого алгоритма (обратите внимание, что # представляет путь, пройденный программой… Я просто использую логический 2D-массив, чтобы проверить, какие узлы посещаются приоритетной очередью. Только для этих индексов я печатаю #, а остальная часть сетки остается прежней)
0 0 0 0 0 # # # # #
# # # 1 1 # # # # G
# # # 1 1 # # # 1 1
# # 0 # # # # # 0 0
# 1 1 # # # # 0 0 1
# # # # # # # 0 1 0
# # # # # 1 1 0 0 0
# # # # 0 1 1 0 0 0
# 1 # 1 0 1 1 0 0 0
# 1 # 1 0 1 1 0 0 0
# # 0 0 0 0 0 0 0 0
S 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 0 0 0
Path Cost: 21
Теперь проблема, как видно из выходных данных, заключается в том, что он хранит каждый посещаемый индекс (потому что эвристические значения имеют очень низкую разницу для всех индексов, поэтому посещается почти каждый узел.. Однако, в конечном счете, поиск * находит наилучший путь, и это видно из «Стоимости пути: 21», которая является фактической стоимостью оптимального пути)
Я считаю, что мой алгоритм верен, учитывая стоимость пути, но сейчас я хочу сохранить также путь оптимального пути. Для этого я хочу вести учет всех индексов (строк и столбцов), посещаемых одним путем.
Например, мой путь начинается со строки 11, Col 0
Затем «оптимальные пути» переходят в строку 10, столбец 1 -> Когда я помещаю эти узлы в очередь, я также хочу сохранить «11, 0». Таким образом, я могу знать, какой путь этот узел прошел ранее, чтобы достичь этого состояния.
Следуя тому же, затем он перейдет в строку 9, Col 2 -> Итак, этот узел также должен хранить в нем как «11, 0», так и «10, 1», следовательно, сохраняя запись о пути, который он прошел до сих пор.
И так продолжается до тех пор, пока не появится узел «цель». Но, похоже, я не могу найти способ реализовать эту вещь, что-то, что отслеживает весь путь, пройденный каждым узлом. Таким образом, я могу легко избежать проблемы, с которой я сталкиваюсь (я просто напечатаю путь, по которому «целевой узел» достиг этой точки, игнорируя все остальные узлы, которые были посещены без необходимости)
Кто-нибудь может мне помочь в попытке найти логику для этого?
Кроме того, просто для ясности, мой класс node и CompareCost имеют эту реализацию,
class node
{
public:
int i, j, heuristic, cost;
node() { i = j = heuristic = cost = 0; }
node(int heuristic, int i, int j, int cost) :i(i), j(j), heuristic(heuristic), cost(cost) {}
};
struct CompareCost {
bool operator()(node constamp; p1, node constamp; p2)
{
return p1.heuristic > p2.heuristic;
}
};
Я предполагаю, что мне нужно сохранить что-то дополнительное в моем «узле класса», но, похоже, я не могу понять, что именно.
Комментарии:
1. Что, если существует более одного пути с одинаковым значением? Вы хотите вывести их все?
2. @KennethMcKanders Нет, достаточно одного оптимального пути. Поскольку оба пути будут оптимальными, поэтому выбор любого из них даст правильный результат.
Ответ №1:
Создайте свой node подобный связанный список:
class node
{
public:
int i, j, cost;
node* next;
}
Добавьте метод в класс для отображения полного пути:
void ShowPath()
{
Node* temp = this;
do
{
if (temp != NULL)
{
std::cout << "(" << temp->i << ", " << temp->j << ")";
temp = temp->next;
}
} while (temp != NULL);
}
Наконец, измените A_search() , чтобы оно возвращало новое node определение. Затем вы можете вызвать ShowPath() возвращаемое значение.