퍼즐 검색 과정의 트리 표현

Question

그림에서와 같이 최소한의 에너지를 사용하여큰 상자 1 개와 작은 상자 3 개를 선반 위에 놓아야합니다.

큰 상자가 작은 하나의 길이의 두 배와 무게를 갖는다. 선반의 길이는 작은 상자의 길이의 3 배입니다. 상단 선반은 하단 선반 높이의 두 배에 위치합니다.

검색 프로세스의 트리를 어떻게 나타낼 수 있습니까 (예 : Uinform-cost 검색 사용)?

Answer 1

제약 논리 프로그래밍 (여기 ECLiPSe)을 사용하여이를 해결할 수 있습니다. 숫자 도메인에 이르는 변수로 문제점을 모델링하고 내장 검색 루틴을 호출합니다. 간단히하기 위해 나는 길이 = 체중을 가정했습니다.

:- lib(ic). 
:- lib(branch_and_bound). 

solve(Vars, Energy) :- 

    Vars = [TopSmall, TopLarge, BotSmall, BotLarge], 

    TopSmall :: 0..3,      % how many small boxes on top 
    BotSmall :: 0..3,      % how many small boxes on bottom 
    TopLarge :: 0..1,      % how many large boxes on top 
    BotLarge :: 0..1,      % how many large boxes on bottom 

    TopSmall + BotSmall #= 3,    % total small boxes 
    TopLarge + BotLarge #= 1,    % total large boxes 

    TopWeight #= TopSmall*1 + TopLarge*2, % total on top 
    BotWeight #= BotSmall*1 + BotLarge*2, % total on bottom 

    TopWeight #=< 3,      % shelf capacities 
    BotWeight #=< 3, 

    Energy #= 2*TopWeight + 1*BotWeight, % Top shelf at double height 

    minimize(labeling(Vars), Energy).  % find a minimal solution 
    % labeling(Vars).      % alternatively, find all solutions