在erlang中生成幻方时内存消耗过多-需要帮助进行优化

Question

对于大学，我必须实现一种算法，为给定的边长和特定的和创建所有可能的幻方。对于n＝3，算法按预期工作。但是过了一段时间，当生成n=4的所有幻方时，我的内存用完了。任务描述中已经提到了这个问题。我已经尝试过优化一个代码，但它仍然不能正常工作。所以我希望有人能给我一些建议。

我的基本想法是：首先，我生成所有可能的行，这些行可以与给定的数字一起使用，然后我试图以一种充满幻方限制的方式将它们组合起来。这是通过回溯实现的。我认为问题在于函数makeRows，它在一段时间后消耗了太多内存来存储所有行。

如果你需要更多的代码解释，我可以给你！

magicSquare(N, Value) ->
Squares = buildSquare(N, makeRows(N, N*N, Value, N)),
io:fwrite("Squares ready"), io:fwrite("~n"),
Result = lists:filter(fun(X) -> testsquare(X, N, Value) end, Squares),
io:write(length(Result)),
Result.
buildSquare(0, _) -> [[]];
buildSquare(Rows, AvailableRows) ->
[ [X|L] || L <- buildSquare(Rows-1, AvailableRows), X <- AvailableRows, onlyUniqueNumbers(lists:flatten([X|L]))].
onlyUniqueNumbers(List) -> erlang:length(List) == sets:size(sets:from_list(List)).
%produces all possible rows with a dimension of Fields and the Numbers from 1 to Numbers and the right sum for each row
makeRows(0,_,_,_) -> [[]];
makeRows(Fields, Numbers, Value, TargetLength) ->
[ [X|L] || X <- makeRows(Fields-1, Numbers, Value, TargetLength), L <- lists:seq(1,Numbers), checkRow([X|L], TargetLength, Value)].
checkRow(Row, Length, Value) when length(Row) < Length -> true;
checkRow(Row, Length, Value) ->
Sum = lists:sum(Row),
if Sum == Value -> true;
true -> false
end.
testsquare(Square, N, Value) -> checkAllDiagonal(Square, Value) andalso checkAllHorizontal(Square, Value) andalso checkAllVertical(Square, N, Value).
checkAllHorizontal([H|T], Value) ->
case checkHorizontal(H, Value, 0) of
true -> checkHorizontal(lists:nth(1, T), Value, 0);
false -> false
end;
checkAllHorizontal([], Value) -> true.
checkHorizontal([H|T], Value, Summe) -> checkHorizontal(T, Value, Summe + H);
checkHorizontal([], Value, Summe) when Summe == Value -> true;
checkHorizontal([], Value, Summe) -> false.
checkAllVertical(Square, N, Value) -> checkAllVertical(Square, N, Value, 1).
checkAllVertical(Square, N, Value, Column) ->
if
Column > N -> true;
true ->
case checkVertical(Square, Value, 0, Column) of
true -> checkAllVertical(Square, N, Value, Column + 1);
false -> false
end
end.
checkVertical([], Value, Summe, Column) when Summe == Value -> true;
checkVertical([], Value, Summe, Column) -> false;
checkVertical([H|T], Value, Summe, Column) -> checkVertical(T, Value, Summe + lists:nth(Column, H), Column).
checkAllDiagonal(Square, Value) ->
case checkDiagonal(Square, Value, 0, 1,1) of
true -> case checkDiagonal(Square, Value, 0, length(lists:nth(1, Square)),-1) of
true -> true;
false -> false
end;
false -> false
end.
checkDiagonal([H|T], Value, Summe, Position, Richtung) -> checkDiagonal(T, Value, Summe + lists:nth(Position, H), Position + Richtung, Richtung);
checkDiagonal([], Value, Summe, Position, Richtung) when Summe == Value -> true;
checkDiagonal([], Value, Summe, Position, Richtung) -> false.

好的，我已经尝试在计算过程的早些时候添加行和正方形的检查。以下是修改后的函数。

buildSquare(0, _, _, _) -> [[]];
buildSquare(Rows, AvailableRows, RowLength, Value) ->
[ [X|L] || L <- buildSquare(Rows-1, AvailableRows, RowLength, Value), X <- AvailableRows, validateSquare([X|L], RowLength, Value)].
checkOnlyUniqueNumbers(List) -> erlang:length(lists:flatten(List)) == sets:size(sets:from_list(lists:flatten(List))).
validateSquare(List, RowLength, Value) when length(List) == RowLength -> testsquare(List, RowLength, Value) andalso checkOnlyUniqueNumbers(List);
validateSquare(List, _,_) -> checkOnlyUniqueNumbers(List).
%produces all possible rows with a dimension of Fields and the Numbers from 1 to Numbers
makeRows(0,_,_,_) -> [[]];
makeRows(Fields, Numbers, Value, TargetLength) ->
[ [X|L] || L <- makeRows(Fields-1, Numbers, Value, TargetLength), X <- lists:seq(1,Numbers), checkRow([X|L], TargetLength, Value)].
%Checks if the sum of the row is Value when the row has the needed length Length
checkRow(Row, Length, _) when length(Row) < Length -> checkOnlyUniqueNumbers(Row);
checkRow(Row, _, Value) ->
Sum = lists:sum(Row),
Sum == Value andalso checkOnlyUniqueNumbers(Row).

Answer 1

嗯，erlang并不懒惰，所以

magicSquare(N, Value) ->
Squares = buildSquare(N, makeRows(N, N*N, Value, N)),

当使用自变量4和34调用时，尝试使用四行之间从1到16(包括1到16)的所有数字来构建四行的所有3121348608可能组合的列表，每行求和为34。

即使每个正方形只占用16个字节(每个单元一个)，也需要大约48GB的内存，这还不包括列表开销。

你的算法会在一种懒惰的语言中工作，尽管速度很慢。但在非懒惰语言中，需要更早地进行修剪，或者选择完全不同的算法。

您可以测试垂直线和对角线是否有机会求和到buildSquare中已经存在的目标值，这可能会将内存需求降低到足够低的程度，使其适合4×4幻方的内存(但我不太相信)。如果只构建(N-1)×N网格，并根据垂直和计算最后一行，那么Squares的大小将减少N!的另一个因子，这与早期修剪一起有更好的机会适应内存(对于N == 4，而不是更大的N)。

但是，您应该重组您的算法，以便尽早使用约束。假设您检查了第一行1 2 15 16。然后你知道左列1下面的三个数字，以及主对角线上剩下的三个号码，每个数字的总和必须为33。所以你需要一组从{ 3,4,5,6,7,8,9,10,11,12,13,14}和66中选出的六个数字。这六个数字的选择不多，因为其中最大的六个数字加起来只有69，所以你有

6, 10, 11, 12, 13, 14
7,  9, 11, 12, 13, 14
8,  9, 10, 12, 13, 14

只有三种可能性。底角的两个数字也受到右列和主东北对角线的约束。将这些约束结合在一起进一步限制了搜索空间。

如果你按顺序考虑可能的正方形，一排接一排，并且不存储候选正方形[你可以存储魔术4×4的正方形，它们不太多]，你可以在小内存中找到所有的魔术正方形，如果你能很好地处理约束，甚至相对较快。

Answer 2

我有一个可能会有所帮助的方向。我几乎让它工作，但在接下来的几天里无法花任何时间。

首先，我认为这个问题是NP完全问题，这表明当输入大小线性增加时，你将使用指数内存或时间。

无论如何，这就是我的方法：

1. 如果你的幻方涉及数字1..N，你将为这N个数字创建所有排列。毕竟，magicSquare(3,15)将是1..15所有可能排列的子集

2. 诀窍是，如果它所代表的所有行的总和不等于幻数，则在生成时删除每个排列。通过这种方式，您不存储所有的排列，只存储那些非常有希望的排列，从而避免指数记忆(但不存储指数时间)。换句话说，在生成每个排列的过程中，只有当它可能是一个幻方时才保存它。我使用列表理解在生成器上创建了带有限定符的排列，该生成器进行了测试以确保所有行的总和正确

3. 我的测试函数采用了一个指示行长度的参数(在这种情况下为3)，并且能够检查[8，1，6，5，7，4，9，2]的排列，并确定每一行(每个子列表1-3，4-6，7-9加起来为15
4. 在得到至少每一行都与幻数求和的排列后，然后过滤MN标准的其余部分

顺便说一句，确保创建排列的算法是尾部递归的。

同样，这似乎对我有效(除非它不是；)，但我离开电脑几天了。

希望这能有所帮助。