Звездный алгоритм, не выбирающий визуально идеальный маршрут
Я реализовал алгоритм "звезда", чтобы найти маршрут между двумя узлами в простой сетке. В настоящее время я тестирую сетку без каких-либо препятствий, и кажется, что она находит кратчайший путь, но это не "идеальный" кратчайший путь, я имею в виду тот, который не сохраняет случайно меняющиеся направления. В идеале я бы хотел, чтобы он продолжал двигаться в одном направлении, то есть он менял направление только один раз.
Как я могу обеспечить это? Я смотрю на ту часть кода, где я рассматриваю, какой узел развернуть в открытом списке, и я мог бы кое-что взломать, сохранив примечание предыдущего направления и выбрав то же направление, если следующий фрагмент имеет то же самое значение f, но это не очень элегантно.
2 ответа
Учитывая ваш график G=(V,E) где каждый v в V обозначает клетку, и каждый край (u,v) Возможно перемещение, вы можете создать новый (взвешенный) график G'=(V',E') следующее:
V' = V_u U V_d U V_l U V_r - каждая группа обозначает тип хода, который вы сделали последним, и V_u = { v_u | for each v in V }аналогично для V_d,V_l,V_r
Теперь для каждого края (u,v) в E:
- Если (u,v) означает "левый" ход, добавьте
(u_l,v_l,1)а также(u_r,v_l,1+eps),(u_u,v_l,1+eps),(u_d,v_l,1+eps), Интуитивно понятно - вы назначаете небольшое наказание ("eps") за "изменение направления" и не получаете наказания, если придерживаетесь того же направления. - Если (u,v) означает движение "вверх", добавьте
(u_u,v_u,1)а также(u_r,v_u,1+eps),(u_l,v_u,1+eps),(u_d,v_u,1+eps), (так же) - Повторите для "правых" и "нисходящих" ходов.
Удостовериться eps достаточно мал, чтобы влиять только на пути одинаковой длины. 1/(|V|+1) должен сделать это.
Также убедитесь, что у вас есть 4 цели сейчас (t_u,t_d,t_l,t_r, где t это оригинальная цель).
Это дает вам график с 4*|V| вершины, которые теперь предпочитают сохранять то же направление, чем менять его. Вы можете придерживаться той эвристики, которая была у вас ранее - если она допустима, она останется такой.
Вы не должны ничего принуждать. Просто глядя на ваш путь, я могу сказать, что у вас есть проблема с алгоритмом. Хотя без вашего кода я не могу сказать вам, где он. Кратчайший путь на открытой сетке всегда будет прямой из-за (a^2+b^2=c^2). A* всегда вернет это. Если вы опубликуете свой код, я могу дать вам несколько советов о том, что вам нужно делать. но сейчас ваши расчеты стоимости по какой-то причине отключены, иначе вы бы пошли прямо от начала до конца. также помните, что A * находит один из самых коротких путей, когда / если есть связь. В вашем случае не будет, но когда вы добавляете препятствия, визуальная оценка графика не всегда является хорошим показателем.
длинный ответ короткий. проверьте ваши функции стоимости и способ определения предыдущего узла узла пути. если вы не используете предыдущий узел для своего пути, когда вы обнаружите, что перенос его на текущий узел выгоден, это произойдет. это также произойдет, если ваши функции стоимости неверны (обычно эвристика как-то испорчена).