Объедините два списка индексов, чтобы создать сопоставление 1-1 между двумя другими списками.

Мы начнем с примера.

У меня есть два списка:

segments = [16, 19, 22, 26]
labels = [horse, cow, mule]

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

       | Preferred Label                 | Preferred Segment
       | (in order, L -> R)              | (in order, L -> R)
    ---+-------------------        ------+-------------------
    16 | horse, cow, mule          horse | 26, 19, 22, 16
    19 | horse, mule               cow   | 16, 22, 19
    22 | mule, cow, horse          mule  | 26, 22, 19
    26 | mule

который может быть выражен в виде двух индексных списков:

// We have 4 segments, each have a ranked list (length 0-3) of preferred label
labelIndicesForSegments = [[0, 1, 2], [0, 2], [2, 1, 0], [2]] 

// We have 3 labels, each have a ranked list (length 0-4) of preferred segment
segmentIndicesForLabels = [[3, 1, 2, 0], [0, 2, 1], [3, 2, 1]]

Теперь, как мне создать «оптимальное сопоставление 1 к 1» между сегментами и метками? То есть сегмент получает метку как можно левее в своей таблице, и наоборот. Алгоритм должен создавать пары, даже если сегмент и метка не имеют друг друга в списке предпочтений (однако этого следует избегать, насколько это возможно).

Я не знаю, что было бы лучшим ответом на пример выше. Некоторые ответы могут быть

1: [(16, horse), (19, mule), (22, cow)]
2: [(16, cow), (19, horse), (26, mule)]
3: [(19, horse), (22, cow), (26, mule)]

Но как мне выбрать, какой сегмент будет без соответствующей метки? И как мне вычислить, какой из них наиболее оптимален?

Как видите, практически все может варьироваться. Сегменты и метки не обязательно должны быть одинаковой длины, а список индексов не обязательно должен быть одинаковой длины. Хотя скорость алгоритма всегда имеет значение, могу сказать, что в этом случае я не буду работать с более чем 10-20 элементами ни в сегментах, ни в метках.

Моя проблема в том, что у меня нет точки входа, как решить эту проблему. Скорее всего, есть алгоритм для решения этой проблемы, но я не знаю его названия. Я также реализую это на Java, если вы хотите сделать конкретный пример без псевдокода;)


java indices algorithm combinations
person Snail    schedule 10.12.2013    source источник
comment
Не понятно, что вам нужно сделать. Пожалуйста, опубликуйте ожидаемый ответ для вашего образца с объяснением.   -  person PM 77-1    schedule 11.12.2013
comment
Я бы создал таблицу, содержащую сумму предпочтений, а затем выбрал бы для каждой строки элемент с более высокой доступной суммой предпочтений. Надеюсь, это поможет!   -  person Gustavo    schedule 11.12.2013
comment
Если между сегментами и метками существует однозначное соответствие, то можете ли вы объяснить, как первый элемент segmentIndicesForLabels будет включать сегмент 3? Элемент 3 в labelIndicesForSegments содержит только индекс 2. Итак, не должен ли элемент 2 в segmentIndicesForLabels содержать только 2 и 1? Аналогично, элемент 1 в segmentIndicesForLabels не должен содержать элемент 1, так как 1 не появляется в labelIndicesForSegments для этого элемента. Если это не так, не могли бы вы отредактировать вопрос и лучше объяснить проблему.   -  person Bob Bryan    schedule 12.12.2013
comment
Я обновил вопрос, чтобы прояснить многое. Надеюсь, теперь это должно быть более понятно. @BobBryan Переписка 1-1 не обязательно должна существовать с самого начала, но ее можно обеспечить, если до этого дойдет.   -  person Snail    schedule 13.12.2013
comment
Ok. Это помогает прояснить некоторые вещи. Мне было интересно, как выглядит ваш вклад. Возможно, это список сегментов со списком меток для каждого из этих сегментов, а также список сегментов со списком меток для этих сегментов? Что касается выходных контейнеров, как вы хотите обрабатывать эти данные позже? Все сразу или произвольный доступ? Когда вы говорите, как мне вычислить, какой из них наиболее оптимален? - что ты имеешь в виду? Вы имеете в виду сегмент с наименьшим количеством меток в нем?   -  person Bob Bryan    schedule 13.12.2013

Ответы (1)


arrow_upward
-1
arrow_downward

Эта проблема называется проблемой стабильного брака.

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

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

Вот пример java (я его особо не тестировал, используйте на свой страх и риск;))

class SMP {
  static int[] segments = {16, 19, 22, 26};
  static String[] labels = {"horse", "cow", "mule"};

  static int[][] labelIndicesForSegments = {{0, 1, 2}, {0, 2}, {2, 1, 0}, {2}};
  static int[][] segmentIndicesForLabels = {{3, 1, 2, 0}, {0, 2, 1}, {3, 2, 1}};

  static int[] matching = new int[segments.length];
  static int[] nextLabel = new int[segments.length]; // A simple pointer to the next label to test for each segment (the current position in its own preference list) 

  public static void main(String[] args) {
    // initialize all matchings
    for (int i=0; i<matching.length; i++) {  
      matching[i] = -1;
      nextLabel[i] = 0;
    }

    // While there is at least one free label and one free segment  
    while (canEnhance()) {
      int unmatched = findUnmatchedSegment(); // Pick an unmatched segment
      int label = labelIndicesForSegments[unmatched][nextLabel[unmatched]];

      nextLabel[unmatched]++;

      int matchedSegment = getMatchedSegment(label);

      if (matchedSegment == -1) { // The label is not matched
        matching[unmatched] = label;
      } else {
        if (labelPrefersSegment(label, matchedSegment, unmatched)) {
          matching[unmatched] = label;
          matching[matchedSegment] = -1;
        }
      }
      for (int i = 0; i < matching.length; i++) {
                if (matching[i] != -1)
                  System.out.println("Segment "+segments[i]+" matched with label "+labels[matching[i]]);
              }
      System.out.println("-----");
    }

    for (int i = 0; i < matching.length; i++) {
      if (matching[i] != -1)
        System.out.println("Segment "+segments[i]+" matched with label "+labels[matching[i]]);
    }
  }

  public static boolean labelPrefersSegment(int label, int currentSegment, int newSegment) {
    int[] preferenceList = segmentIndicesForLabels[label];

    for (int i = 0; i < preferenceList.length; i++) {
      if (preferenceList[i] == currentSegment) return false;
      if (preferenceList[i] == newSegment) return true;
    }
    return false;
  }

  public static int getMatchedSegment(int label) {
    for (int i=0; i<matching.length; i++) {
      if (matching[i] == label) return i;
    }
    return -1;
  }

  public static int findUnmatchedSegment() {
    for (int i=0; i<matching.length; i++) {
      // The segment need to be free and to still have labels to test
      if (matching[i] == -1 && nextLabel[i] < labelIndicesForSegments[i].length) {
        return i;
      }
    }
    return -1;
  }

  public static boolean canEnhance() {
    return findUnmatchedSegment() != -1;
  }
}

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

Основная часть находится в цикле while, мелкие функции после основной не так интересны :)

Вы можете найти дополнительную информацию здесь: https://en.wikipedia.org/wiki/Stable_marriage_problem

Ваше здоровье

person Tamere    schedule 10.12.2013