Алгоритм «звезда»: использование эвристического значения в качестве выключателя связи, где узлы имеют одинаковые F-значения

Question

Предыстория: в настоящее время я работаю над реализацией 8 задач оригинального алгоритма A Star и сравниваю его с немного измененным алгоритмом, который намеревается улучшить расширение узла (используя дополнительную информацию, конечно, звезда в одинаково информированном однонаправленном поиске имеетбыло доказано оптимальным).Открытый список узлов в настоящее время упорядочен по их значениям F (G-Cost + H-Cost).

Поэтому при реализации этого в Java я настроил компаратор, который упорядочивает список по их F-значениям по возрастаниюorder.

       @Override
    public int compare(PNode o1, PNode o2) {
        return Integer.compare(o1.costF, o2.costF);
    }

Вопрос: У меня вопрос:

1. Разрешено ли под A-star внедрить еще один Tie-breaker в A-Star, используя стоимость эвристики (H-значение) для устранения любой тупиковой ситуации с F-значением среди многих узлов (если узлы существуют с одинаковым F-значением в открытом списке, они будут упорядочены по эвристическому значению (H-стоимости) в порядке возрастания).Причина, по которой меня это смущает, так как фактический псевдокод алгоритма «звезда» сортирует открытый список только по значению F.

Расширение того же кода выше, реализация будет:

        @Override
    public int compare(PNode o1, PNode o2) {
        if (o1.costF == o2.costF) {
            return Integer.compare(o1.costH, o2.costH);
        }
        return Integer.compare(o1.costF, o2.costF);
    }

Если это разрешено, есть ли причины, по которым я должен опасаться этого?Логично, что я ценю, что заказ Открытого списка будет более дорогостоящим.Но из моих экспериментов разница не кажется достаточно значительной, чтобы помешать мне использовать это.

Большое спасибо всем ~

Answer 1

Да, это разрешено, в значительной степени по причинам, указанным в ответе mcdowella .

Однако я хотел бы добавить, что зачастую это очень хорошая идея, и оченьболее выгодно, чем подразумевается в этом ответе.Этот тип тай-брейка может привести к гораздо более значительному увеличению производительности , чем только нахождение цели чуть раньше.См., Например, эту страницу , на которой визуализируется, как A * все еще исследует довольно массивную область без прерывателя связей и только очень узкую полосу вдоль оптимального пути с прерывателем связей.

Интуитивно, вы можете понять, что он настолько эффективен, если подумать о различных уровнях «надежности» затрат G по сравнению с H.G затраты очень надежны, они являются истинной правдой, это именно те затраты, которые вы действительно должны были заплатить, чтобы добраться до узла.H затраты гораздо менее надежны, они эвристические, они могут быть совершенно неверными.Реализуя предложенный вами прерыватель связей, вы, по сути, говорите "всякий раз, когда два узла имеют одинаковое значение для F = G + H, я предпочитаю те, которые имеют больший G и меньший H, чем узлы с меньшим G ибольше H ".Это разумно, потому что, когда более надежный G компонент F доминирует над менее надежным H компонентом, сам F также будет более надежным.

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

Answer 2

Я думаю, что это нормально по двум причинам

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

2) Вы сохраняете свойство, что, если вы извлекаете целевой узел из открытого списка, все остальные открытые узлы имеют G-Cost + H-Cost, по крайней мере, такие же дорогие, как итот из узла, который вы только что извлекли, и, следовательно, должен привести к пути к целевому узлу, по крайней мере, столь же дорогому, как и узел, который вы только что извлекли., вы предпочитаете любые целевые узлы в случае связей, так что я думаю, вы могли бы получить целевой узел немного раньше и закончить немного раньше.