Задача поиска AI: кратчайший путь между двумя точками на плоскости с препятствиями

Question

Я пытаюсь решить проблему в ИИ, используя неинформированные стратегии поиска. Вот проблема, буду признателен за ваши советы по этому вопросу.

цель состоит в том, чтобы найти кратчайший путь между двумя точками на плоскости с выпуклыми многоугольными препятствиями. Предположим, что пространство состояний состоит из всех позиций в плоскости (x, y), сколько там состояний? Сколько путей к цели?

Я верю, что есть x * y состояния, но я не уверен, сколько путей к цели?

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

обновление 1: относительно «хорошего пространства состояний» - я должен объяснить, почему кратчайший путь от одной вершины многоугольника к любой другой в сцене должен состоять из отрезков прямых, соединяющих некоторые из вершин многоугольников, и затем определите хорошее пространство состояний, сообщив, насколько велико это пространство состояний.

Спасибо!

Answer 1

Предполагая дискретные позиции на плоскости - то есть целые числа - тогда на этой плоскости, как вы говорите, существуют x * y позиции. Предполагая отсутствие циклов, число различных путей экспоненциально больше, но оно не бесконечно. Например, в худшем случае, если начальное состояние равно 0,0, а конечное состояние равно w, h, и на поверхности нет препятствий, тогда вы можете представить построение минимального остовного дерева от начала до конца, которое будет содержать все пути. Для плоскости 2х2 будет 2 пути; для плоскости 2х3 будет 4 пути и так далее. Если вы разрешите циклы, то у вас может быть бесконечное количество путей.

Обратите внимание, что "препятствия" на самом деле не являются проблемой для алгоритма поиска. У них просто не было бы достижимых позиций из соседнего государства. Например, A * не будет генерировать «препятствие» в качестве достижимого узла, поэтому оно не добавит его в открытый список. (На самом деле, он также не будет добавлен в закрытый список; это вообще не узел.)

Я не уверен, что вы подразумеваете под "определить хорошее пространство состояний". Вы можете уточнить?

Редактировать: Как я могу получить максимум 2 пути для плоскости 2x2? Легко. Сначала разместите начальную и конечную позиции где угодно. Они будут либо рядом, либо на противоположных углах. В случае, когда они находятся рядом друг с другом, первый путь тривиален. Второй путь получается путем обхода всех остальных квадратов первым. В ситуации с противоположным углом вы получаете один путь, используя один из других квадратов в качестве первого шага, а другой путь - оставшийся пустой квадрат в качестве первого шага. В любом случае, если вы не разрешаете циклы, это единственные пути.