Блог

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

У меня есть графики/деревья, подобные тезисам :

У меня есть ограничения, специфические для каждого графика, такие как «UUB ?» для A). Ограничение спрашивает, есть ли в графике путь, проходящий через каждую из букв, указанных в ограничении.

Для ограничения «UUB ?» нам нужен путь, проходящий по крайней мере через два U и один B. Для первого графика «UUB ?» возможно с путем U-gt;B-gt;gt;U. «RBB ?» невозможно, потому что один из B находится на том же слое, что и R, и вы не можете иметь оба одновременно. Я не нашел никакого эффективного метода проверки того, может ли быть выполнено ограничение..

Точность ограничения : Ограничение не может содержать больше букв, чем количество слоев. Порядок ограничения не имеет значения (UBB совпадает с BUB и BBU).

Точность графика : Эти графики ориентированы, и каждый слой (столбец) полностью связан со следующим. Они могут иметь максимум 5 слоев (столбцов) и 5 строк (U,B,R,G,W).

Они могут быть представлены в виде векторов (соответственно):

A)
U 1 0 1
B 1 1 0
R 1 0 0

Б)
U 1 0 1 0
B 1 1 0 1
R 1 0 1 0
G 1 1 0 0

C)
U 1 0 1 0 0
B 1 1 0 1 0
R 1 0 1 0 0
G 1 1 0 0 0
W 0 0 1 0 1

Точность алгоритма : Эта проверка будет происходить на каждом шаге моделирования Монте-Карло из миллионов шагов, она должна быть как можно быстрее (это означает, что я не могу извлечь все пути и проверить, включают ли они нужные узлы..)

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

Спасибо вам за чтение и за вашу помощь !

Вы можете использовать рекурсивную функцию генератора, выстраивая возможные пути при каждом вызове, сверяя частоты букв выполняемой комбинации с частотами возможных путей:

 from collections import Counter def check_paths(d, p, c=[], f={}):  if not d and any(all(j in i and i[j] == k for j, k in f.items()) for i in p):  yield c #produce a path if all the layers have been examined and all the letter frequencies from the path match a possible path  elif d:  for x in d[0]:  _c = Counter(c [x])  #check if the current path, with the addition of a new letter, is below or equals the frequency threshold of any of the target paths  if any(all(j in i and i[j] gt;= k for j, k in _c.items()) for i in p):  yield from check_paths(d[1:], p, c=c [x], f=_c)  

 l = ['U', 'B', 'R', 'G', 'W'] def path_exists(m, p):  v = [[j for j, k in zip(l, i) if k] for i in zip(*m)]  return next(check_paths(v, [Counter(i) for i in p]), None) is not None  print(path_exists([[1, 0, 1], [1, 1, 0], [1, 0, 0]], ['UUB', 'RBB', 'UBR'])) print(path_exists([[1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0]], ['UBBB', 'RGRR', 'UBRG'])) print(path_exists([[1, 0, 1, 0, 0], [1, 1, 0, 1, 0], [1, 0, 1, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 1]], ['UBRGW', 'RGRGG', 'WWRUB']))  

Выход:

 True True True