1

我遇到了一个令人惊讶的具有挑战性的问题，即安排受以下约束（或决定不可能）的值的类似矩阵（列表列表）：

一个由 m 个随机生成的行组成的矩阵，最多具有 n 个不同的值（行内没有重复），排列矩阵使得以下内容成立（如果可能）：

1）矩阵必须是“下三角”；行必须按升序排列，因此唯一的“间隙”位于右上角

2) 如果一个值出现在多行中，则它必须在同一列中（即允许重新排列一行中的值的顺序）。

用函数式语言（例如 Scala）表达问题/解决方案是可取的。

示例 1 - 有一个解决方案

AB
CED
驾驶室

变成（作为一种解决方案）

AB
EDC
ABC

因为 A、B 和 C 都分别出现在第 1、2 和 3 列中。

示例 2 - 没有解决方案

ABC
ABD
BCD

没有解决方案，因为约束要求第三行在第三列中有 C 和 D，这是不可能的。

4

2 回答 2

1

我认为这是一个有趣的问题，并在 MiniZinc（一个非常高级的约束编程系统）中建模了一个概念验证版本，这似乎是正确的。我不确定它是否有任何用处，老实说，我不确定它对于最大的问题实例是否强大。

根据这个模型，第一个问题实例有 4 个解决方案：

 B A _
 E D C
 B A C
 ----------
 B A _
 D E C
 B A C
 ----------
 A B _
 E D C
 A B C
 ----------
 A B _
 D E C
 A B C

第二个例子被认为是不可满足的（应该如此）。

完整的模型在这里：http ://www.hakank.org/minizinc/ordering_a_list_of_lists.mzn

基本方法是使用矩阵，其中较短的行填充空值（此处为 0，零）。问题实例是矩阵“矩阵”；得到的解决方案在矩阵“x”中（决策变量，作为整数，然后在输出中转换为字符串）。然后有一个辅助矩阵“perms”，用于确保“x”中的每一行都是“matrix”中相应行的排列，使用谓词“permutation3”完成。还有一些其他的辅助数组/集合可以简化约束。

主要的 MiniZinc 模型（无输出）如下所示。

以下是一些可能使模型无用的评论/假设：

  • 这只是一个概念验证模型，因为我认为这是一个有趣的问题。

  • 我假设矩阵中的行（问题数据）已经按大小排序（下三角形）。作为不需要约束编程的预处理步骤，这应该很容易做到。

  • 较短的列表用 0（零）填充，因此我们可以使用矩阵。

  • 由于 MiniZinc 是一种强类型语言并且不支持符号，我们只定义整数 1..5 来表示字母 A..E。在使用传统的约束编程系统时，使用整数也是有益的。

    % MiniZinc 模型（无输出）
    包括“globals.mzn”；
    诠释：行= 3；
    诠释：列= 3；

    整数：A = 1；
    诠释：B = 2；
    诠释：C = 3；
    诠释：D = 4；
    诠释：E = 5；
    诠释：max_int = E；

    字符串数组[0..max_int]：str = array1d(0..max_int, ["_", "A","B","C","D","E"]);

    % 问题 A（可满足）
    数组 [1..rows, 1..cols] of int: 矩阵 =
       array2d(1..rows, 1..cols,
       [
         A,B,0, % 用“0”填充这个较短的数组
         E,D,C,
         A,B,C,
       ]);

     % 有效值（我们跳过 0，零）
     一组int：值= {A，B，C，D，E}；

     % 确定特定值是哪些行。
     % 例如问题 A：
     % value_rows: [{1, 3}, {1, 3}, 2..3, 2..2, 2..2]
     int 集的数组 [1..max_int]：value_rows =
           [{我| i in 1..rows, j in 1..cols where matrix[i,j] = v} | v 值]；


     % 决策变量
     % 得到的矩阵
     数组[1..rows, 1..cols] of var 0..max_int: x;

     % 从矩阵到 x 的排列
     array[1..rows, 1..cols] of var 0..max_int: perms;


     %
     % 排列3(a,p,b)
     %
     % 使用排列 p 从 ab 获得排列。
     %  
     谓词 permutation3(array[int] of var int: a,
                            var int 的数组 [int]: p,
                            var int 的数组 [int]：b) =
         forall(i in index_set(a)) (
            b[i] = a[p[i]]
         )
     ;

     解决满足；

     约束
        forall(i in 1..rows) (
           % 确保 x 和 perms 中行中的值的唯一性（0 除外）
           alldifferent_except_0([x[i,j] | j in 1..cols]) /\
           alldifferent_except_0([perms[i,j] | j in 1..cols]) /\          
           permutation3([matrix[i,j] | j in 1..cols], [perms[i,j] | j in 1..cols], [x[i,j] | j in 1..cols])
        )
        /\ % x 中的零是矩阵中的零
        forall(i in 1..rows, j in 1..cols) (
           如果矩阵[i,j] = 0 那么
              x[i,j] = 0
           别的
              真的
           万一
        )

        /\ % 确保相同的值在同一列中：
           % - 对于每个值
           % - 确保它位于一列 c
           forall(k in 1..max_int where k in values) (
              存在（j in 1..cols）（
                 forall(i in value_rows[k]) (
                   x[i,j] = k
                 )
              )
           )
       ;

       ％ 输出
       % ...
于 2013-09-04T19:26:40.720 回答
0

我需要一个函数式语言 (XQuery) 的解决方案，所以我首先在 Scala 中实现了它，因为它的表现力，我在下面发布了代码。它使用蛮力、广度优先的方式搜索解决方案。我只对单个解决方案（如果存在）感兴趣，因此该算法会丢弃额外的解决方案。

def order[T](listOfLists: List[List[T]]): List[List[T]] = {

def isConsistent(list: List[T], listOfLists: List[List[T]]) = {
  def isSafe(list1: List[T], list2: List[T]) =
    (for (i <- list1.indices; j <- list2.indices) yield
      if (list1(i) == list2(j)) i == j else true
      ).forall(_ == true)

  (for (row <- listOfLists) yield isSafe(list, row)).forall(_ == true)
}


def solve(fixed: List[List[T]], remaining: List[List[T]]): List[List[T]] =
  if (remaining.isEmpty)
    fixed        // Solution found so return it
  else
    (for {
      permutation <- remaining.head.permutations.toList
      if isConsistent(permutation, fixed)
      ordered = solve(permutation :: fixed, remaining.tail)
      if !ordered.isEmpty
    } yield ordered) match {
      case solution1 :: otherSolutions =>       // There are one or more solutions so just return one
        solution1

      case Nil =>   // There are no solutions
        Nil
    }


// Ensure each list has unique items (i.e. no dups within the list)
  require (listOfLists.forall(list => list == list.distinct))

  /* 
   * The only optimisations applied to an otherwise full walk through all solutions is to sort the list of list so that the lengths 
   * of the lists are increasing in length and then starting the ordering with the first row fixed i.e. there is one degree of freedom
   * in selecting the first row; by having the shortest row first and fixing it we both guarantee that we aren't disabling a solution from being
   * found (i.e. by violating the "lower triangular" requirement) and can also avoid searching through the permutations of the first row since
   * these would just result in additional (essentially duplicate except for ordering differences) solutions.
   */
    //solve(Nil, listOfLists).reverse           // This is the unoptimised version
    val sorted = listOfLists.sortWith((a, b) => a.length < b.length)
    solve(List(sorted.head), sorted.tail).reverse
}
于 2013-09-29T23:51:27.690 回答