8

所以我试图解决这里给出的展位安排问题。它基本上是一个滑动瓷砖拼图，其中一个（摊位）瓷砖必须到达目标点，最后所有其他（摊位）瓷砖应该在其原始位置。每个瓷砖/展位都有一个维度，以下是输入事实和关系描述：

  • room(W,H) 形式的一个事实，它指定
    房间的宽度 W 和高度 H (3 ≤ W, H ≤ 20)。
  • 一个事实展位（B），它
    指定展位的数量（1 ≤ B ≤ 20）。
  • 由形式维度（B，W，H）的事实组成的关系，它指定展位 B 的宽度 W 和高度 H。


  • 由position(B, W, H)形式的事实组成的关系，指定展位 B 的初始位置 (W, H)。

  • 一个事实 target(B, W, H)，指定
    目标展位 B的目的地 (W, H)。

  • 附加的事实水平（H）给出了要执行的移动次数的上限。

该程序应该从文件中读取输入事实，但我只是试图解决问题，所以我现在只是复制粘贴了一个可能的输入，并且我已经编写了一些基本条款：

room(3, 3).
booths(3).
dimension(1, 2, 1).
dimension(2, 2, 1).
dimension(3, 1, 1).
position(1, 0, 1).
position(2, 1, 2).
position(3, 0, 0).
target(3, 0, 2).
horizon(10).

xlim(X) :- room(X,_).
ylim(X) :- room(_,X).

sum(X,Y,Z) :- Z is X+Y .

do(position(B,X,Y),movedown,position(B,X,Z)) :- Y > 0 , sum(Y,-1,Z) .
do(position(B,X,Y),moveup,position(B,X,Z)) :- ylim(L), Y < L , sum(Y,1,Z) .
do(position(B,X,Y),moveleft,position(B,Z,Y)) :- X > 0 , sum(X,-1,Z) .
do(position(B,X,Y),moveright,position(B,Z,Y)) :- xlim(L), X < L, sum(X,1,Z) .

noverlap(B1,B2) :- 
    position(B1,X1,Y1), 
    position(B2,X2,Y2), 
    ends(Xe1,Ye1,B1), 
    ends(Xe2,Ye2,B2), 
    ( Xe1 < X2 ; 
      Xe2 < X1 ; 
      Ye1 < Y2 ; 
      Ye2 < Y1 ).

ends(Xe,Ye,B) :- 
    dimension(B,W,H), 
    position(B,X,Y), 
    Xe is X+W-1, 
    Ye is Y+H-1.

between(X,Y,Z) :- 
    X > Y , 
    X < Z .

validMove(M,B) :- do(position(B,X,Y),M,position(B,Xn,Yn)) .

我是 Prolog 的新手，我被困在如何从这里开始，我有 no_overlap 规则，所以我可以测试移动是否有效，但我不确定我拥有的当前条款如何。我当前的 move do/3 条款可能需要一些修改。任何指针？

4

1 回答 1

7

您需要根据拼图状态之间的关系来表达任务。您当前的子句确定单个移动的有效性，并且还可以生成可能的移动。

然而，这还不够：您需要表达的不仅仅是单个动作及其对单个图块的影响。您需要以某种方式对整个拼图的状态进行编码，还需要对单个动作如何改变整个任务的状态进行编码。

首先，我建议您考虑如下关系：

world0_move_world(W0, M, W) :- ...

并表达一个给定的“世界”  W0，一个可能的动作 M，和结果世界 之间的关系W。这种关系应该如此普遍，以便在回溯 时生成M中可能的 每个移动W0。理想情况下，如果它是一个自由变量，它甚至应该可以工作 W0，为此您可能会发现很有用：约束允许您以比当前使用的更通用的方式表达算术关系。

一旦你有了这样的关系，整个任务就是找到一系列 Ms移动，以便将任何初始世界 转换W0为所需的状态 。W

假设您已经实现world0_move_world/3为构建块，您可以轻松地将其提升到移动列表，如下所示（使用）：

移动（W0）-> {desired_world（W0）}。
移动（W0）-> [M]，{world0_move_world（W0，M，W）}，移动（W）。

然后，您可以使用迭代深化来找到解决难题的最短移动序列：

?- 长度（Ms，_），initial_world（W0），短语（moves（W0），Ms）。
于 2017-10-05T22:42:51.890 回答