了解餐桌最佳座位算法的问题

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

他/她是如何想出[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)对一个邻居是中立的,喜欢另一个.所以后者显然是优越的,无论我们是否认为增加喜欢或减少不喜欢更重要.

Answer 2

检查所有可能的订单是经典的排列任务,即使可能存在针对此特定问题的更有效的算法.

可以通过将置换减少到阵列长度-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)相结合,当然具有相同的评级.重新映射镜像订单,即反向排列,将是另一种优化.

我这样做是为了演示,只需要一步一步地解决单个问题的可读代码.您可以将评级计算直接重构为置换算法.

正确计算时间复杂度似乎并不那么容易.请阅读以下评论中的讨论.