Определение того, какой номер рядом соответствует какому входу - PullRequest
Новая
       11

Определение того, какой номер рядом соответствует какому входу

0 голосов
/ 01 апреля 2019

Контекст: У меня немного странная проблема: давайте рассмотрим 2 кортежа, один из которых является подмножеством другого размера N-1. 

node = (40, 50, 60, 80)
adj_node = (40, 50, 60)

КакВы можете видеть, я называю эти комбинации как узлы сетевого графа.Префикс adj_ означает adjacent.Алгоритм раскрашивает график, то есть находит альтернативное значение для каждого узла.Суффикс alt_ будет означать alternative.

И для node, и для adj_node предусмотрена 1 альтернатива в пределах допустимого диапазона.Цель этой функции - вычислить отклонение между обеими альтернативами. 

def compute_deviation_between_node_alternative_and_adj_node_alternative(node,
                                            node_alt, adj_node, adj_node_alt):
"""
4 tuples in input, the node, the node alternative, the adjacent node, and 
the adjacent node alternatives.
"""
# Compute
return deviation

Рассмотрим следующий вход: 

node = (40, 50, 60, 80)
node_alt = (39, 48, 59, 87)
adj_node = (40, 50, 60)
adj_node_alt = (42, 55, 59)

Каждое значение из узла или из adj_node заменяется наальтернативное значение в пределах диапазона допуска +/- 10%.Таким образом, 40 становится 39 в альтернативном узле и 42 в соседнем альтернативном узле.Альтернативы не могут быть заказаны.то есть node_alt могло бы быть (48, 39, 87, 59).Диапазон допуска может перекрываться, например, для 60, оба значения 55 и 59 находятся в пределах диапазона допуска.

Проблемная часть кода: Шаг, который я пытаюсь выполнитьреализовать - это то, что я назвал этапом идентификации: выяснить, какое альтернативное значение соответствует какому входному значению.Для этого я вычисляю расстояние между значениями и возвращаю id (или idx), на котором находится альтернативное значение. 

tolerances = [0.1 if x <= 100 else 0.2 for x in node]
distance = dict()
alt_identification = dict()
for k, x in enumerate(node):
    distance[k] = [abs(elt-1) for elt in [alt_x/x for alt_x in node_alt]]
    alt_identification[x] = list(np.where([elt <= tolerances[k]+0.00001 for elt in distance[k]])[0])

В приведенном выше примере выводом является: 

alt_identification
Out[67]: {40: [0], 50: [1], 60: [2], 80: [3]}

То же самое делается для альтернативы смежного узла. 

distance = dict()
adj_alt_identification = dict()
for k, x in enumerate(node):
    distance[k] = [abs(elt-1) for elt in [alt_x/x for alt_x in adj_node_alt]]
    adj_alt_identification[x] = list(np.where([elt <= tolerances[k]+0.00001 for elt in distance[k]])[0])

Вывод: 

adj_alt_identification
Out[66]: {40: [0], 50: [1], 60: [1, 2], 80: []}

Проблема: У меня есть разные сценарии, которые могут возникнуть.

Сценарий 1: каждому значению присвоено одно альтернативное значение.Например, это относится к node, где вывод равен {40: [0], 50: [1], 60: [2], 80: [3]}.

Сценарий 2: Некоторые из входных значений идентифицируются как 2 или более различных возможных альтернативных значений.Это может произойти из-за перекрытия диапазона допуска.Например, 

adj_node = (40, 50, 60)
adj_node_alt = (42, 55, 54)

Оба 55 и 54 включены в диапазон допуска от 50 и 60.Вывод будет (если узел (40, 50, 60, 80)):

adj_alt_identification Out [66]: {40: [0], 50: [1, 2], 60: [1, 2], 80: []}

Сценарий 3: Это имеет место в предыдущем примере для adj_alt: 

adj_node = (40, 50, 60)
adj_node_alt = (42, 55, 59)

55 и 59 включены в диапазон допуска 60.Только 55 входит в диапазон допуска 50.

Токовый выход: 

adj_alt_identification
Out[66]: {40: [0], 50: [1], 60: [1, 2], 80: []}

Корректный выход будет означать, что 60 не может принять значение55, поскольку оно уже занято 50.Таким образом, выходные данные должны быть: 

adj_alt_identification
Out[66]: {40: [0], 50: [1], 60: [2], 80: []}

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

1 Ответ

0 голосов
/ 01 апреля 2019

Текущий код, приводящий к правильному выводу: это беспорядок и явно неэффективный ... 

def traceback(tuple_node, tuple_node_alt):
    """
    Compute which value from tuple_node_alt comes from which value from tuple_node.
    tuple_node is the input
    tuple_node_alt is the "output"
    """
    # Compute the tolerances based on the node
    tolerances = [0.1 if f <= 100 else 0.2 for f in tuple_node]

    # Traceback
    distance = dict()
    alt_identification = dict()
    for k, x in enumerate(tuple_node):
        distance[k] = [abs(elt-1) for elt in [alt_x/x for alt_x in tuple_node_alt]]
        alt_identification[x] = list(np.where([elt <= tolerances[k]+0.00001 for elt in distance[k]])[0])

    len_values = {key: len(val) for key, val in alt_identification.items()}

    if all([x <= 1 for x in len_values.values()]):
        return alt_identification
    else:
        for key, value in alt_identification.items():
            if len(value) <= 1:
                continue
            else:
                other_values = [val for k, val in alt_identification.items() if k != key]
                if value in other_values:
                   continue
                else:
                    for val in other_values:
                        set1 = set(value)
                        intersec = set1.intersection(set(val))
                        if len(intersec) == 0:
                            continue
                        else:
                            alt_identification[key] = [v for v in value if v not in intersec]

    return alt_identification
...