2

我有一系列关系，我想通过记录匹配来像图表一样遍历它们。例如，在支持以下库函数进行图形操作的系统中，我们有以下奇怪的情况：

image(raw).
image(png).
image(bitmap).
image(tiff).
conversion(tiff2bitmap, tiff, bitmap).
conversion(bitmap2png, bitmap, png).
conversion(png2raw, png, raw).
conversion(raw2bitmap, raw, bitmap).
conversion(png2tiff, png, tiff).

operation(crop, raw, raw).

因此，在上面的示例中，如果我们想要裁剪tiff，您必须执行以下操作：

  • 将 tiff 转换为位图
  • 将位图转换为 png
  • 将 png 转换为 raw
  • 使用裁剪操作
  • 将原始数据转换为位图
  • 将位图转换为 png
  • 将 png 转换为 tiff

例如，我可以坐在 Prolog REPL 上，首先询问将 tiff 转换为位图的操作：

?- conversion(OP1, tiff, F1).
OP1 = tiff2bitmap,
F1 = bitmap .
?- conversion(OP2, F1, F2).
OP2 = tiff2bitmap,
F1 = tiff,
F2 = bitmap ;
OP2 = bitmap2png,
F1 = bitmap,
F2 = png 
... and so on

我希望能够在 Prolog 中遵循以下逻辑，但我不知道如何处理。我想我需要使用递归规则和累加器。我们可以使用以下方法来解决如何裁剪 tiff。我可以像这样手动解决上述问题：

/* the op is op in operation(op, x, x) */
conversions(Op, In, Steps) :-
  operation(Op, In, Out); /* no conversions necessary */
  conversion(C1, O1, O2),/* switch the incoming/outgoing to */
  conversion(C2, O2, O3), /* match successive conversions */
  conversion(C3, O3, O4), /* A->B, B->C, C->D */

  /* adding the matches C1-C3 to steps */

我更喜欢使用累加器和递归规则自动处理这个问题，但我不知道如何处理这个问题。

4

2 回答 2

2

在larsmans提到“路径搜索”之后，我搜索并发现了一个“ TekTips问题”。由此看来，以下似乎有效：

image(raw).
image(png).
image(bitmap).
image(tiff).
conversion(tiff2bitmap, tiff, bitmap).
conversion(bitmap2png, bitmap, png).
conversion(png2raw, png, raw).
conversion(raw2bitmap, raw, bitmap).
conversion(png2tiff, png, tiff).

operation(crop, raw, raw).

sconversions(End, A, End, [Conv]) :-
    conversion(Conv, A, End).

sconversions(End, A, B, Ops) :-
    conversion(X, A, C),
    sconversions(End, C, B, TailOps),
    Ops = [X|TailOps].

convert(Op, A, Path) :-
    operation(Op, In, _),
    sconversions(In, A, In, Path).

convertKeep(Op, A, Path) :-
    operation(Op, In, Out),
    sconversions(In, A, In, CPath),
    sconversions(A, Out, A, RPath), /* backward */
    append(CPath, RPath, Path).

不考虑输出格式的转换：

?- convert(crop, tiff, Ops).
Ops = [tiff2bitmap, bitmap2png, png2raw, crop]

下面显示了转换： ?- convertKeep(crop, tiff, Ops)。操作 = [tiff2bitmap, bitmap2png, png2raw, 裁剪, raw2bitmap, bitmap2png, png2tiff]

我是 Prolog 的新手，访问者最好学习 larsmans 的答案。

于 2012-04-22T12:28:25.330 回答
1

在描述列表时，请始终考虑使用 DCG。在您的情况下，您只需要以下内容：

conversions(S, S) --> [].
conversions(S0, S) -->
        { conversion(Op, S0, S1) },
        [Op],
        conversions(S1, S).

您现在可以使用迭代深化来详尽地尝试越来越长的操作列表，直到达到所需的目标状态。例如，要从tiff到raw：

?- length(Ops, _), phrase(conversions(tiff, raw), Ops).
Ops = [tiff2bitmap, bitmap2png, png2raw] .
于 2014-10-21T21:26:25.377 回答