0

考虑以下难题：

数仓

一个单元格被标记或未标记。谜题右侧和底部的数字表示特定行或列的总和。单元格对其行和列的总和有贡献（如果标记）：位置 (i,j) 的单元格对列总和贡献 i，对行总和贡献 j。比如上图的第一行，标记了第 1、2、5 个单元格。这些对行总和贡献 1 + 2 + 5（因此总计 8），对它们的列总和贡献 1。

我在 ECLiPSe CLP 中有一个求解器来解决这个难题，我很想为它编写一个自定义启发式算法。

我认为最容易开始的单元格是那些列和行提示尽可能低的单元格。一般来说，值越低，写为 1 和 之间的自然数之和的N可能性就越小。在这个谜题的上下文中，这意味着具有最低的单元格出错的可能性最低，因此回溯更少。NNcolumn hint + row hint

在实现中，我有一个NxN代表棋盘的数组，以及两个代表提示的大小为 N 的列表。（侧面和底部的数字。）

我看到两个选项：

  • 为search/6编写一个自定义选择谓词。但是，如果我理解正确的话，我只能给它2个参数。没有办法计算给定变量的行+列总和，因为我需要能够将它传递给谓词。我需要4个参数。

  • 忽略 search/6 并编写自己的标记方法。这就是我现在的方式，请参见下面的代码。

它采用棋盘（NxN包含所有决策变量的数组）、提示列表并返回包含所有变量的列表，现在根据它们的行 + 列总和进行排序。但是，如您所见，这可能不会变得更麻烦。为了能够排序，我需要将总和附加到每个变量，但为了做到这一点，我首先需要将其转换为还包含所述变量坐标的术语，以便我转换回变量为排序完成后...

lowest_hints_first(Board,RowArr,ColArr,Out) :-
    dim(Board,[N,N]),
    dim(OutBoard,[N,N]),
    ( multifor([I,J],[1,1],[N,N]), foreach(Term,Terms), param(RowArr,ColArr) do
        RowHint is ColArr[I],
        ColHint is RowArr[J],
        TotalSum is RowHint + ColHint,
        Term = field(I,J,TotalSum)
    ),
    sort(3,<,Terms,SortedTerms), % Sort based on TotalSum
    terms_to_vars(SortedTerms,Board,Out), % Convert fields back to vars...
    ( foreach(Var,Out) do
         indomain(Var,max)
    ).

terms_to_vars([],_,[]).
terms_to_vars([field(I,J,TotalSum)|RestTerms],Vars,[Out|RestOut]) :-
    terms_to_vars(RestTerms,Vars,RestOut),
    Out is Vars[I,J].

最后，这种启发式方法几乎不比 input_order 快。我怀疑这是因为它的实施方式很糟糕。关于如何做得更好的任何想法？或者我认为这种启发式应该是一个巨大的改进是不正确的？

4

1 回答 1

2

我看到您已经对 Joachim 提出的改进感到满意；但是，当您要求进一步改进启发式算法时，请考虑只有一种方法可以得到 0 作为总和，也只有一种方法可以得到 15。只有一种方法可以得到 1 和 14, 2和 13；得到 3 和 12 的两种方法。一般来说，如果你有 K 种方法得到总和 N，你也有 K 种方法得到 15-N。

所以困难的金额不是大的，而是中等的。

于 2016-07-17T09:12:39.590 回答