1

给定 9 个变量 x1 x2 x3 x4 x5 x6 x7 x8 x9，我想给它们分配实数，这样：

exactly 1 pair among them sums to 2
exactly 2 pairs among them sum to 3
exactly 3 pairs among them sum to 4
exactly 4 pairs among them sum to 5
exactly 5 pairs among them sum to 6
exactly 6 pairs among them sum to 7
exactly 5 pairs among them sum to 8
exactly 4 pairs among them sum to 9
exactly 3 pairs among them sum to 10
exactly 2 pairs among them sum to 11
and exactly 1 pair among them sums to 12

这是否可以以某种方式建模为约束满足问题？或者如何解决这个问题？

谢谢，

4

1 回答 1

2

由于您要求 1 对具有一定的总和，因此必须计算无序的变量对。此外，由于指定了 36 个总和，我们排除（我假设）向自身添加一个变量（因此不需要 36 个不一定不同的总和）。

您正在问一个表面上的编程问题，即它是否可以通过约束编程来解决。约束编程可以产生有限域的答案。在实数域上，如果没有进一步的了解，将有无数种可能性进行检查。

在搜索中，可以假设变量是按升序排列的，这会使这些变量的“加法表”的行和列也按升序排列。现在我们至少有一个有限的问题要探索。这张表的上下三角形是对称的，所以我们只需要找出其中一半或另一半是否可以填写即可。

这足够暗示吗？我注意到表中 2 和 12 条目的位置是确定的（作为两个最小和两个最大的总和）变量。我们可以像这样可视化加法表的上半部分：

  _  2  ?  ?  ?  ?  ?  ?  ?
     _  ?  ?  ?  ?  ?  ?  ?
        _  ?  ?  ?  ?  ?  ?
           _  ?  ?  ?  ?  ?
              _  ?  ?  ?  ?
                 _  ?  ?  ?
                    _  ?  ?
                       _ 12
                          _

我们可以给出一个相当简单的 Prolog 程序，它逐行选择条目，使用的事实是每行中第一个打开的条目必须是可用的最小条目（因为以后不会出现使用该条目的机会，如果一个大一个用于那里）以及连续行但相应列中的条目之间的差异在该行中是一个常数（包括对角线和下半部分条目）。

要看到这一点，请考虑第 i 行和第 j 列减去第 i 行和第 j 列：

(x_i + x_j) - (x_i' + x_j)  =  x_i - x_i'

差异不取决于列！我们在这些行之间的每一列中得到相同的差异，例如，如果将 j 列更改为 j' 列（例如）。

将这些想法推得足够远，可以让人们手动解决问题。

于 2012-10-29T14:10:57.807 回答