поиск. добавление стоимости движения от начальной позиции - PullRequest
Новая
       18

поиск. добавление стоимости движения от начальной позиции

0 голосов
/ 20 марта 2012

если f = g + h, то где в приведенном ниже коде я бы добавил g?

Кроме того, помимо добавления стоимости перемещения из моей начальной позиции, как еще я могу сделать этот код более эффективным? 

def a_star(initial_node):
    open_set, closed_set = dict(), list()
    open_set[initial_node] = heuristic(initial_node)
    while open_set:
        onode = get_next_best_node(open_set)
        if onode == GOAL_STATE:
            return reconstruct_path(onode)
        del open_set[onode]
        closed_set.append(onode)
        for snode in get_successor_nodes(onode):
            if snode in closed_set:
                continue
            if snode not in open_set:
                open_set[snode] = heuristic(snode)
                self.node_rel[snode] = onode
    return False

1 Ответ

0 голосов
/ 20 марта 2012

В последнем if, если snode не находится в open_set (не каламбур!), Вы не должны устанавливать только эвристику, но эвристику плюс стоимость текущего узла.И если snode равно в открытом наборе, вы должны проверить минимум между текущим значением и текущим (если есть два или более способов добраться до одного и того же узла, следует рассмотреть наименее дорогостоящий).

Это означает, что вам необходимо хранить как «фактическую» стоимость узла, так и «расчетную» стоимость.Фактическая стоимость начального узла равна нулю.Для каждого нового узла это минимум для каждой входящей дуги между стоимостью другой вершины плюс стоимость дуги (другими словами, стоимость последнего узла плюс стоимость перехода от этого к текущему).Ориентировочная стоимость должна была бы суммировать оба значения: фактическую стоимость на данный момент плюс эвристическую функцию.

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

...