36

私はプロローグの制約処理の問題を解決しようとしています。

5x5、4x4、3x3、2x2の4つの正方形を10x10のグリッドに詰める必要があります。それらは重複してはいけません。

私の変数は次のようになります。

Name: SqX(i), i=1..10, domain: 1..10

Xは5、4、3または2のいずれかです。インデックスiは行を表し、ドメインはグリッド内の列を表します。

私の最初の制約は、正方形の幅と高さを定義しようとします。私はそれをそのように定式化します:

Constraint: SqX(i) > SqX(j)-X /\ i>j-X, range: i>0 /\ j>0

そのため、可能なポイントは、互いにX行と列の範囲内に収まるように制限されます。ただし、Prologはこれらの制約で停止し、次の結果をもたらします。

Adding constraint "(Sq5_I > Sq5_J-5) /\ (I>J-5)" for values:
        I=1, J=1, 
        I=1, J=2, 
        I=1, J=3, 
        I=1, J=4, 
        I=1, J=5, 
        I=1, J=6, 
=======================[ End Solutions ]=======================

したがって、他の正方形をチェックすることさえせずに、そこで停止します。私の制約はおそらくきつすぎるでしょうが、その理由や方法がわかりません。助言がありますか?

4

5 に答える 5

20

正方形ごとに、左上隅を示す変数を定義Xします。Yこれらの変数にはドメインがあります1..10-L。ここLで、は正方形の長さです。ドメインをに設定する1..10と、正方形の一部が10x10の長方形の外側に配置される場合があります。

(X,Y)次に、長方形の各ペアに制約を投稿(X1,Y1)し、それらがx軸でオーバーラップする場合、y軸でオーバーラップしてはならない、またはその逆を示すことができます。

(((X  #=< X1) and (X+L   #> X1)) => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((X1 #=< X)  and (X1+L1 #> X))  => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((Y  #=< Y1) and (Y+L   #> Y1)) => ((X+L #=< X1) or (X1+L1 #=< X))),
(((Y1 #=< Y)  and (Y1+L1 #> Y))  => ((X+L #=< X1) or (X1+L1 #=< X)))

(特定の制約構文は異なる場合があります)

于 2012-11-29T15:32:08.050 に答える
20

バージョン 3.8.3 以降、SICStus Prolog は、パッキングの問題に適切に対応する多数の専用の配置制約を提供します。特に、パッキングの問題は 2 次元であるため、disjoint2/1制約の使用を検討する必要があります。

次のコード スニペットはdisjoint2/1、四角形が重なっていないことを表現するために使用します。主な関係はarea_boxes_positions_/4.

:- use_module(library(clpfd)).
:- use_module(library(lists)).

area_box_pos_combined(W_total*H_total,W*H,X+Y,f(X,W,Y,H)) :-
    X #>= 1,
    X #=< W_total-W+1,
    Y #>= 1,
    Y #=< H_total-H+1.

positions_vars([],[]).
positions_vars([X+Y|XYs],[X,Y|Zs]) :-
    positions_vars(XYs,Zs).

area_boxes_positions_(Area,Bs,Ps,Zs) :-
    maplist(area_box_pos_combined(Area),Bs,Ps,Cs),
    disjoint2(Cs),
    positions_vars(Ps,Zs).

いくつかのクエリに進みます!まず、最初のパッキングの問題:

?- area_boxes_positions_(10*10,[5*5,4*4,3*3,2*2],Positions,Zs),
   labeling([],Zs).
Positions = [1+1,1+6,5+6,5+9],
Zs        = [1,1,1,6,5,6,5,9] ? ...

次に、すべての正方形を配置するために必要な総面積を最小化しましょう。

?- domain([W,H],1,10),
   area_boxes_positions_(W*H,[5*5,4*4,3*3,2*2],Positions,Zs),
   WH #= W*H,
   minimize(labeling([ff],[H,W|Zs]),WH).
W         = 9,
H         = 7,
Positions = [1+1,6+1,6+5,1+6],
Zs        = [1,1,6,1,6,5,1,6],
WH        = 63 ? ...

ソリューションの視覚化

個々のソリューションは実際にはどのように見えますか? ImageMagickは素敵な小さなビットマップを生成できます...

適切な ImageMagick コマンドをダンプするための簡単なコードを次に示します。

:- use_module(library(between)).
:- use_module(library(codesio)).

drawWithIM_at_area_name_label(Sizes,Positions,W*H,Name,Label) :-
    Pix = 20,

    % let the ImageMagick command string begin
    format('convert -size ~dx~d xc:skyblue', [(W+2)*Pix, (H+2)*Pix]),

    % fill canvas 
    format(' -stroke none -draw "fill darkgrey rectangle ~d,~d ~d,~d"', 
           [Pix,Pix, (W+1)*Pix-1,(H+1)*Pix-1]),

    % draw grid
    drawGridWithIM_area_pix("stroke-dasharray 1 1",W*H,Pix),

    % draw boxes
    drawBoxesWithIM_at_pix(Sizes,Positions,Pix),

    % print label
    write( ' -stroke none -fill black'),
    write( ' -gravity southwest -pointsize 16 -annotate +4+0'),
    format(' "~s"',[Label]),

    % specify filename
    format(' ~s~n',[Name]).

上記のコードdrawWithIM_at_area_name_label/5は、2 つの小さなヘルパーに依存しています。

drawGridWithIM_area_pix(Stroke,W*H,P) :-   % vertical lines
    write(' -strokewidth 1 -fill none -stroke gray'),
    between(2,W,X),
    format(' -draw "~s path \'M ~d,~d L ~d,~d\'"', [Stroke,X*P,P, X*P,(H+1)*P-1]),
    false.
drawGridWithIM_area_pix(Stroke,W*H,P) :-   % horizontal lines
    between(2,H,Y),
    format(' -draw "~s path \'M ~d,~d L ~d,~d\'"', [Stroke,P,Y*P, (W+1)*P-1,Y*P]),
    false.
drawGridWithIM_area_pix(_,_,_).

drawBoxesWithIM_at_pix(Sizes,Positions,P) :-
    Colors = ["#ff0000","#00ff00","#0000ff","#ffff00","#ff00ff","#00ffff"],
    write(' -strokewidth 2 -stroke white'),
    nth1(N,Positions,Xb+Yb),
    nth1(N,Sizes,    Wb*Hb),
    nth1(N,Colors,   Color),
    format(' -draw "fill ~sb0 roundrectangle ~d,~d ~d,~d ~d,~d"',
           [Color, Xb*P+3,Yb*P+3, (Xb+Wb)*P-3,(Yb+Hb)*P-3, P/2,P/2]),
    false.
drawBoxesWithIM_at_pix(_,_,_).

ビジュアライザーの使用

次の 2 つのクエリを使用して、静止画像を生成してみましょう。

?- drawWithIM_at_area_name_label([5*5,4*4,3*3,2*2],[1+1,6+1,6+5,1+6],9*7,
                                 'dj2_9x7.gif','9x7').

?- drawWithIM_at_area_name_label([5*5,4*4,3*3,2*2],[1+1,1+6,5+6,5+9],10*10,
                                 'dj2_10x10.gif','10x10').

次のハック クエリを使用して、サイズ のボード上に上記の長方形を配置するソリューションごとに画像を生成しましょう9*7

?- retractall(nSols(_)), 
   assert(nSols(1)), 
   W=9,H=7,
   Boxes = [5*5,4*4,3*3,2*2],
   area_boxes_positions_(W*H,Boxes,Positions,Zs),
   labeling([],Zs), 
   nSols(N), 
   retract(nSols(_)), 
   format_to_codes('dj2_~5d.gif',[N],Name),
   format_to_codes('~dx~d: solution #~d',[W,H,N],Label),
   drawWithIM_at_area_name_label(Boxes,Positions,W*H,Name,Label),
   N1 is N+1,
   assert(nSols(N1)),
   false.

次に、上記のクエリによって出力されたすべての ImageMagick コマンドを実行します。

最後に、ImageMagick を使用して 3 番目のクエリのソリューション セットのアニメーションを作成します。

$ convert -delay 15  dj2_0.*.gif   dj2_9x7_allSolutions_1way.gif 
$ convert dj2_9x7_allSolutions_1way.gif -coalesce -duplicate 1,-2-1 \
          -quiet -layers OptimizePlus -loop 0 dj2_9x7_allSolutions.gif

結果

まず、ボード サイズ 10*10 の 1 つのソリューション:10x10: 1 つのソリューション

次に、最小サイズ (9*7) のボードの 1 つのソリューション:9x7: 1 つのソリューション

最後に、最小サイズ (9*7) のボードのすべてのソリューション:9x7: すべてのソリューション


編集 2015-04-14

バージョン 7.1.36 以降、SWI-Prolog clpfd ライブラリは制約をサポートしていますdisjoint2/1

編集 2015-04-22

tuples_in/2制約に基づく代替実装のスケッチを次に示します。

  1. ボックスの各ペアについて、これら 2 つが重ならないすべての位置を決定します。
  2. 有効な組み合わせをタプルのリストとしてエンコードします。
  3. tuples_in/2ボックスのペアごとに、1 つの制約を投稿します。

私的な概念実証として、そのアイデアに従っていくつかのコードを実装しました。彼の答えの@CapelliCのように169480、OPが述べたボックスとボードサイズに対して明確な解決策が得られます。

ランタイムは、他の clp(FD) ベースの回答に匹敵します。実際、小さなボード (10*10 以下) では非常に競争力がありますが、ボードのサイズが大きくなるとさらに悪化します。

良識のために、コードの投稿を控えることをご了承ください:)

于 2015-04-01T11:08:20.770 に答える
5

CLP(FD) 制約を使用して、ここに投稿されたいくつかの優れたソリューションが既にあります (すべて +1!)。

さらに、CLP( B ) 制約を使用して、このような配置とカバーのタスクを解決するための概念的に異なる方法を 1 つ示したいと思います。

アイデアは、タイルの各可能な配置をグリッド上の特定の要素での一連のTRUE値と見なすことです。ここで、各グリッド要素はマトリックスの 1 つの列に対応し、タイルの各可能な配置は 1 つの行に対応します。次に、各グリッド要素が最大 1 回カバーされるように、つまり、選択された行で構成されるサブマトリックスの各列に最大で 1 つのTRUE値が存在するように、マトリックスの行のセットを選択します。 .

この定式化では、行の選択、つまり特定の位置でのタイルの配置は、行列の行ごとに 1 つのブール変数によって示されます。

これが私が共有したいコードです。これは、SICStus Prolog と SWI で動作し、多くても小さな変更が必要です。

:- use_module(library(clpb)).
:- use_module(library(clpfd)).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   The tiles we have available for placement.

   For example, a 2x2 tile is represented in matrix form as:

       [[1,1],
        [1,1]]

   1 indicates which grid elements are covered when placing the tile.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

tile(5*5).
tile(4*4).
tile(3*3).
tile(2*2).

tile_matrix(Rows) :-
        tile(M*N),
        length(Rows, M),
        maplist(length_list(N), Rows),
        append(Rows, Ls),
        maplist(=(1), Ls).

length_list(L, Ls) :- length(Ls, L).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Describe placement of tiles as SAT constraints.

   Notice the use of Cards1 to make sure that each tile is used
   exactly once. Remove or change this constraint if a shape can be
   used multiple times, or can even be omitted.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

placement(M, N, Vs, *(Cs) * *(Cards1)) :-
        matrix(M, N, TilesRows),
        pairs_keys_values(TilesRows, Tiles, Rows),
        same_length(Rows, Vs),
        pairs_keys_values(TilesVs0, Tiles, Vs),
        keysort(TilesVs0, TilesVs),
        group_pairs_by_key(TilesVs, Groups),
        pairs_values(Groups, SameTiles),
        maplist(card1, SameTiles, Cards1),
        Rows = [First|_],
        phrase(all_cardinalities(First, Vs, Rows), Cs).

card1(Vs, card([1], Vs)).

all_cardinalities([], _, _) --> [].
all_cardinalities([_|Rest], Vs, Rows0) -->
        { maplist(list_first_rest, Rows0, Fs, Rows),
          pairs_keys_values(Pairs0, Fs, Vs),
          include(key_one, Pairs0, Pairs),
          pairs_values(Pairs, Cs) },
        [card([0,1], Cs)],
        all_cardinalities(Rest, Vs, Rows).

key_one(1-_).

list_first_rest([L|Ls], L, Ls).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   We build a matrix M_ij, where each row i describes what placing a
   tile at a specific position looks like: Each cell of the grid
   corresponds to a unique column of the matrix, and the matrix
   entries that are 1 indicate the grid positions that are covered by
   placing one of the tiles at the described position. Therefore,
   placing all tiles corresponds to selecting specific rows of the
   matrix such that, for the selected rows, at most one "1" occurs in
   each column.

   We represent each row of the matrix as Ts-Ls, where Ts is the tile
   that is used in each case.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

matrix(M, N, Ms) :-
        Squares #= M*N,
        length(Ls, Squares),
        findall(Ts-Ls, line(N, Ts, Ls), Ms).

line(N, Ts, Ls) :-
        tile_matrix(Ts),
        length(Ls, Max),
        phrase((zeros(0,P0),tile_(Ts,N,Max,P0,P1),zeros(P1,_)), Ls).

tile_([], _, _, P, P) --> [].
tile_([T|Ts], N, Max, P0, P) -->
        tile_part(T, N, P0, P1),
        { (P1 - 1) mod N >= P0 mod N,
          P2 #= min(P0 + N, Max) },
        zeros(P1, P2),
        tile_(Ts, N, Max, P2, P).

tile_part([], _, P, P) --> [].
tile_part([L|Ls], N, P0, P) --> [L],
        { P1 #= P0 + 1 },
        tile_part(Ls, N, P1, P).

zeros(P, P)  --> [].
zeros(P0, P) --> [0], { P1 #= P0 + 1 }, zeros(P1, P).

次のクエリは、どのグリッド要素がカバーされているか ( 1) を示しています。ここで、各行は長方形の 1 つの配置に対応しています。

?- M = 7, N = 9, placement(M, N, Vs, Sat), sat(Sat),
  labeling(Vs), matrix(M, N, Ms), pairs_values(Ms, Rows),
  pairs_keys_values(Pairs0, Vs, Rows),
  include(key_one, Pairs0, Pairs1), pairs_values(Pairs1, Covers),
  maplist(writeln, Covers).
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1]
[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
M = 7,
N = 9,
etc.

ソリューションに対応:

元の問題の解決策

このような CLP(B) の定式化は通常、CLP(FD) バージョンよりもスケーラブルではありません。これは、より多くの変数が含まれるためです。ただし、いくつかの利点もあります。

重要な利点の 1 つは、形状の一部またはすべてを複数回使用できるタスクのバージョンに容易に一般化できることです。たとえば、上記のバージョンでは、単純に次のように変更できますcard1/2

custom_cardinality(Vs, card([0,1,2,3,4,5,6,7], Vs)).

各タイルを最大 7 回使用できるバージョンを取得し、完全に省略することもできます (が含まれているため0)。

次に、これを正確なカバーの問題の解決策に簡単に変えることができます。つまり、グリッド要素が形状の 1 つによって覆われていることを意味します。card([0,1], Cs)card([1], Cs)all_cardinalities//3

他の変更と合わせて、4 つの 2x2 長方形を使用した 4x4 グリッドのカバーを次に示します。

[1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0]
[0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0]
[0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1]

CLP(B) 式の 3 つ目の利点は、解を明示的に列挙しなくても解の数を計算できることです。たとえば、元のタスクの場合:

?- placement(7, 9, Vs, Sat), sat_count(Sat, Count).
Count = 68.

これらの 68 のソリューションは、@repeat によってすでに美しく説明されています。

比較のために、各形状を 0 ~ 7 回使用できるソリューションの数を次に示します。

?- placement(7, 9, Vs, Sat), time(sat_count(Sat, Count)).
% 157,970,727 inferences, 19.165 CPU in 19.571 seconds
...
Count = 17548478.

10x10 グリッドでも同じで、約 6 分 (~ 20 億回の推論) で計算されます。

?- placement(10, 10, Vs, Sat), sat_count(Sat, Count).
Count = 140547294509.

11x11 のグリッドでは、約 30 分 (~ 90 億回の推論) で計算されます。

?- placement(11, 11, Vs, Sat), sat_count(Sat, Count).
Count = 15339263199580.

最後に、おそらく最も重要なことですが、このアプローチはあらゆる形状のタイルで機能し、正方形や長方形に限定されません。たとえば、1x1 の正方形と三角形、およびその垂直方向と水平方向の反射を処理するには、次の の定義を使用しますtile_matrix/1

tile_matrix([[1]]).
tile_matrix(T) :-
        T0 = [[1,1,1,1],
              [1,1,1,0],
              [1,1,0,0],
              [1,0,0,0]],
        (   T = T0
        ;   maplist(reverse, T0, T)
        ;   reverse(T0, T)
        ).

これらの形状のそれぞれを 9x7 ボードで 0 回から 7 回使用できるようにすると、1 分ほどでCount = 58665048314解決策が得られます。

そのうちの 1 つをランダムに選んで以下に示します。

三角形の例

解の数が多すぎて明示的に列挙できない場合でも、CLP(B) を使用すると、それぞれの可能性が等しくなるように解を選択することも非常に簡単です。

于 2015-05-17T09:20:38.823 に答える
3

SWI-Prologでコーディングしました

/*  File:    pack_squares.lp
    Author:  Carlo,,,
    Created: Nov 29 2012
    Purpose: http://stackoverflow.com/questions/13623775/prolog-constraint-processing-packing-squares
*/

:- module(pack_squares, [pack_squares/0]).
:- [library(clpfd)].

pack_squares :-
    maplist(square, [5,4,3,2], Squares),
    flatten(Squares, Coords),
    not_overlap(Squares),
    Coords ins 1..10,
    label(Coords),
    maplist(writeln, Squares),
    draw_squares(Squares).

draw_squares(Squares) :-
    forall(between(1, 10, Y),
           (   forall(between(1, 10, X),
              sumpts(X, Y, Squares, 0)),
           nl
           )).

sumpts(_, _, [], S) :- write(S).
sumpts(X, Y, [[X1,Y1, X2,Y2]|Qs], A) :-
    ( ( X >= X1, X =< X2, Y >= Y1, Y =< Y2 )
    ->  B is A+X2-X1+1
    ;   B is A
    ),
    sumpts(X, Y, Qs, B).

square(D, [X1,Y1, X2,Y2]) :-
    X1 + D - 1 #= X2,
    Y1 + D - 1 #= Y2.

not_overlap([_]).
not_overlap([A,B|L]) :-
    not_overlap(A, [B|L]),
    !, not_overlap([B|L]).

not_overlap(_, []).
not_overlap(Q, [R|Rs]) :-
    not_overlap_c(Q, R),
    not_overlap_c(R, Q),
    not_overlap(Q, Rs).

not_overlap_c([X1,Y1, X2,Y2], Q) :-
    not_inside(X1,Y1, Q),
    not_inside(X1,Y2, Q),
    not_inside(X2,Y1, Q),
    not_inside(X2,Y2, Q).

not_inside(X,Y, [X1,Y1, X2,Y2]) :-
    X #< X1 #\/ X #> X2 #\/ Y #< Y1 #\/ Y #> Y2.

これは、実行時に表示される最後の行です?- aggregate_all(count,pack_squares,C).。特に、C は合計配置数を数えます

...
0002255555
0002255555
[6,6,10,10]
[7,2,10,5]
[4,3,6,5]
[5,1,6,2]
0000220000
0000224444
0003334444
0003334444
0003334444
0000055555
0000055555
0000055555
0000055555
0000055555
C = 169480.
于 2012-11-29T17:13:56.263 に答える