10

大学では、特定の辺の長さと特定の合計に対して可能なすべての魔方陣を作成するアルゴリズムを実装する必要があります。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).
4

2 に答える 2

0

役立つかもしれない方向性があります。ほとんど機能していますが、今後数日間は時間を費やすことができません。

まず、この問題は NP-Complete であると考えています。これは、入力サイズが直線的に増加するにつれて、指数メモリまたは時間を使用することを示しています。

いずれにせよ、これが私のアプローチでした：

  1. 魔方陣に数字 1..N が含まれる場合、それらの N の数字のすべての順列を作成します。結局、magicSquare(3,15) は 1..15 のすべての可能な順列のサブセットになります。

  2. 秘訣は、各順列が表すすべての行の合計がマジック ナンバーに達しない場合に生成される各順列を削除することです。このようにして、すべての順列を保存するのではなく、非常に有望な順列のみを保存することで、指数記憶を回避します (ただし、指数時間は回避します)。つまり、各順列の生成に合わせて、魔方陣である可能性がある場合にのみ保存します。リスト内包表記を使用して、すべての行が正しく合計されることを確認するテストを行ったジェネレーターで修飾子を使用して順列を作成しました

  3. 私のテスト関数は、行の長さ (この場合は 3) を示すパラメーターを取り、[8,1,6,3,5,7,4,9,2] の順列を調べて、各行 (各サブリスト 1 ～ 3、4 ～ 6、7 ～ 9 の合計は 15 です。
  4. 少なくともすべての行の合計がマジック ナンバーになる順列を取得した後、残りの MN 基準をフィルター処理します。

ちなみに、順列を作成するアルゴリズムが末尾再帰であることを確認してください。

繰り返しますが、これは私にとってはうまくいっているように見えました (そうでない場合を除いて ;)) が、私は数日間自分のコンピューターから離れています。

うまくいけば、これが役に立ちます。

于 2012-12-23T18:17:35.970 に答える