Может кто-нибудь помочь мне понять, верны ли мои реализации и предположения? К сожалению, у меня нет средств воспроизвести это.
Я пытаюсь реализовать эвристическую функцию hmax для направленного развертывания сетей Петри из статьи здесь. TLDR; он оценивает значение оставшегося расстояния от одной отметки (аргумент a в моей функции) до другой отметки (b) на основе определения, данного в ссылке. Вам не нужно знать, что такое Марк или Конфигурация, достаточно знать, как работают сети Петри.
Документ использует в своем определении 1 + min(), но поскольку я использую направленное развертывание на основе стоимости, я также использую функцию Cost_function. Кроме того, поскольку вычисления являются циклическими, во время рекурсии они могут оказаться в цикле, поэтому я использую in_stack для отслеживания вызовов. Всякий раз, когда обнаруживается цикл, функция возвращает inf, и поскольку я использую min для всех путей, расстояние должно вычисляться по путям без цикла. Еще одно дополнение с моей стороны:
if len(possible_candidates) == 0:
return 0
Не уверен, что это правильное предположение. Я не могу объяснить, почему возможные_кандидаты иногда равны 0.
def compute_hmax(
self,
mark: frozenset[PetriNet.Place],
target: Set[PetriNet.Place],
cost_function,
):
if len(mark) == 0:
self.local_configuration.hmax = 0
else:
in_stack = (
dict()
) # stack to detect visited nodes in the search to detect cycles
d = self.hmax(mark, frozenset(target), in_stack, cost_function)
self.local_configuration.hmax = d
@cached(
cache={},
key=lambda self, a, b, in_stack, cost_function: hashkey((a, b)),
)
def hmax(
self,
a: frozenset[PetriNet.Place],
b: frozenset[PetriNet.Place],
in_stack,
cost_function,
):
if b.issubset(a):
return 0
elif len(b) == 1:
q = list(b)[0]
if q in in_stack:
return float("inf") # cycle detected
in_stack[q] = True
pre_trans = set(map(lambda arc: arc.source, q.in_arcs))
possible_candidates = list(
map(
lambda t: (
t,
self.hmax(
a, frozenset(t.preset), in_stack, cost_function
),
),
pre_trans,
)
)
in_stack.pop(q)
if len(possible_candidates) == 0:
return 0
min_d_tup = min(possible_candidates, key=lambda t: t[1] + cost_function[t[0]])
return cost_function[min_d_tup[0]] + min_d_tup[1]
else:
return max(
list(
map(
lambda t: self.hmax(
a, frozenset({t}), in_stack, cost_function
),
b,
)
)
)
Подробнее здесь: https://stackoverflow.com/questions/790 ... petri-nets
