在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调用时,尝试构建所有3121348608个可能的四行组合的列表,每个行总和为34,使用它们之间的所有数字从1到16(包括).

即使每个方块只占用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方格,它们不是太多],你可以找到所有的小方块内存,如果你以一种好的方式处理约束,甚至相对较快.