Проблемы с пониманием алгоритма оптимального размещения обеденного стола

Question

Я читал проблему и пытался ее решить.

Вы пригласили N человек на обед.Скажем, 4.

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

Вы составили карту дружбы и ненависти каждого в матрице размера NxN и представляли дружбу с целым числом 1, ненавистью с -1 и абсолютным безразличием с 0.

[[ 0, 1, 1, 1, 1],    ← yes you like all your friends
 [-1, 0, 1,-1, 0],
 [-1, 1, 0, 1, 0],
 [ 1, 1, 1, 0,-1],
 [ 1, 0, 0,-1, 0]]

Вопрос:

-> Напишите метод Javascript, который вычисляет оптимальное расположение сидений в виде массива, например, [0,4,2,1,3], для данноговходная матрица.(при условии, что индексы 0 и N-1 расположены рядом).Какова сложность времени для решения?Добавьте мысли о возможной оптимизации.

Я пытался решить эту проблему вручную, однако не понял пример вопроса [0,4,2,1,3] для данной входной матрицы.

Может ли кто-нибудь просветить меня?

Как он / она придумали [0,4,2,1,3]?

Спасибо иочень ценю ваше время.

Answer 1

Проверка всех возможных порядков является классической задачей перестановки, даже если для этой конкретной задачи может быть более эффективный алгоритм.

Одна оптимизация может быть выполнена путем уменьшения перестановки до длины-1 массива, поскольку в круговых порядкахнапример, 0,1,2,3,4 и 4,0,1,2,3 (и все последующие вращения) одинаковы.Вы можете просматривать заказ со своего места, всегда начиная с позиции 0.

(function ()
{
  'use strict';

  let popularity =
  [
    [ 0, 1, 1, 1, 1],   // ← yes you like all your friends
    [-1, 0, 1,-1, 0],
    [-1, 1, 0, 1, 0],
    [ 1, 1, 1, 0,-1],
    [ 1, 0, 0,-1, 0],
  ];

  function permutation(arr)
  {
    let
      l = arr.length,
      perms = []
    ;

    if(l<2)
      return [arr];

    for(let i=0; i<l; i++)
    {
      let
        cpy    = Array.from(arr),
        [perm] = cpy.splice(i, 1)
      ;
      perms.push(...permutation(cpy).map(v => [perm, ...v]));
    }

    return perms;
  }


  let
    keys = Array.from(popularity.keys()).slice(1),
    permutations = permutation(keys),
    rating = permutations.map(v =>
    {
      let
        last = v.length -1,

        // start with our own relationships to the left and right neighbour
        // (each: we like him, he likes us)
        rate =
            popularity [0]       [v[0]]
          + popularity [v[0]]    [0]
          + popularity [0]       [v[last]]
          + popularity [v[last]] [0]
      ;

      for(let i = 0; i<last; i++)
        rate += popularity[v[i]][v[i+1]] + popularity[v[i+1]][v[i]];

      return [rate, [0, ...v]];
    }
  ).sort( (v1, v2) => ( v1[0] === v2[0] ? 0 : (v1[0] > v2[0] ? -1 : 1))  );

  console.log(rating);

})();

выход:

[ [ 8, [ 0, 4, 1, 2, 3 ] ],
  [ 8, [ 0, 3, 2, 1, 4 ] ],
  [ 6, [ 0, 3, 1, 2, 4 ] ],
  [ 6, [ 0, 4, 2, 1, 3 ] ],
  [ 4, [ 0, 1, 4, 2, 3 ] ],
  [ 4, [ 0, 1, 2, 3, 4 ] ],
  [ 4, [ 0, 4, 1, 3, 2 ] ],
  [ 4, [ 0, 1, 3, 2, 4 ] ],
  [ 4, [ 0, 2, 3, 1, 4 ] ],
  [ 4, [ 0, 3, 2, 4, 1 ] ],
  [ 4, [ 0, 4, 2, 3, 1 ] ],
  [ 4, [ 0, 4, 3, 2, 1 ] ],
  [ 2, [ 0, 3, 4, 2, 1 ] ],
  [ 2, [ 0, 3, 1, 4, 2 ] ],
  [ 2, [ 0, 2, 4, 1, 3 ] ],
  [ 2, [ 0, 4, 3, 1, 2 ] ],
  [ 2, [ 0, 3, 4, 1, 2 ] ],
  [ 2, [ 0, 1, 2, 4, 3 ] ],
  [ 2, [ 0, 2, 1, 4, 3 ] ],
  [ 2, [ 0, 2, 1, 3, 4 ] ],
  [ 0, [ 0, 1, 4, 3, 2 ] ],
  [ 0, [ 0, 2, 3, 4, 1 ] ],
  [ -2, [ 0, 1, 3, 4, 2 ] ],
  [ -2, [ 0, 2, 4, 3, 1 ] ] ]

Как мы видим, все еще в обратном порядкеПерестановки в сочетании с вами (0) с одинаковым рейтингом конечноИсключение зеркальных порядков, т. Е. Обращенных перестановок, было бы еще одной оптимизацией.

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

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

Answer 2

Как он / она придумали [0,4,2,1,3]?

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

---

Что касается того, почему я говорю, что [0,4,2,1,3] определенно неправильный ответ для примера, который вы дали.,,Я не совсем понимаю, как мы решаем, лучше ли одна перестановка, чем другая, но ясно, что [0,4,1,2,3] лучше по любым показателям.И для [0,4,2,1,3], и [0,4,1,2,3] первый человек (0) любит обоих соседей;второй человек (4) нейтрален по отношению к обоим соседям;и третий и пятый люди (2 и 3 в первом, 1 и 3 в последнем) каждый как один сосед и нейтрален по отношению к другому.Единственное различие между этими двумя перестановками состоит в том, что в [0,4,2,1,3] четвертый человек (1) нейтрален по отношению к одному соседу и не любит другого, тогда как в [0,4, 1,2,3], четвертый человек (2) нейтрален по отношению к одному соседу и любит другого.Таким образом, последний, очевидно, превосходит, независимо от того, считаем ли мы более важным увеличить количество симпатий или уменьшить их.