拼圖搜索過程的樹形圖

Question

我應該在貨架上放置1個大箱子和3個小箱子，如下圖所示，使用最小能量的。

大框具有一個小的兩倍的長度和重量。貨架的長度是一個小盒子長度的三倍。上層擱架的位置是下層高度的兩倍。

我如何表示搜索過程的樹（例如，使用Uinform-cost搜索）？

Answer 1

你可以使用Constraint Logic Programming（這裏是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