Prolog中的配方

4 回答

• 1

  您的问题可以表示为配置之间的一系列转换 . 首先考虑一下如何表示单个配置 . 您可以使用列表来执行此操作，例如[ - >，< - ， - >，< - ， - >，< - ]来表示初始配置 . 可以使用用作步骤（State0，State）的关系步骤/ 2来描述单个移动，并且描述通过翻转两个相邻箭头而彼此“可达”的两个配置之间的关系 . 它通常是不确定的 . 然后，您的主谓词描述了一系列状态转换，这些转换从初始状态导致所需的目标状态 . 由于您要描述（配置）列表，DCG非常适合：

  solution(State0, Target) -->
      (    { State0 == Target } -> []
      ;    { step(State0, State1) },
           [State1],
           solution(State1, Target)
      ).
  

  然后使用迭代深化来找到解决方案（如果存在），如：

  ?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).
  

  好消息是，一旦尝试了给定长度的所有序列并且还无法达到目标状态，Prolog会自动回溯 . 您现在只需执行步骤/ 2即可完成 .

  回复于 2024-04-26T09:38:34+08:00
• 0

  由于已经发布了完整的解决方案，这是我的：

  solution(State0, Target) -->
      (    { State0 == Target } -> []
      ;    { step(State0, State1) },
           [State1],
           solution(State1, Target)
      ).
  
  flip(->, <-).
  flip(<-, ->).
  
  step([], []).
  step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
  step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).
  

  示例查询：

  ?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).
  Solution = [[->, <-, ->, <-, <-, ->],
              [->, <-, ->, ->, ->, ->],
              [->, ->, <-, ->, ->, ->],
              [<-, <-, <-, ->, ->, ->]].
  

  由于使用了迭代深化，我们知道不可能有更短的解决方案（少于4个步骤） .

  我对你所说的内容也有一般性评论：

  这是一个简单的例子，在Java / C /中可以很容易地解决 . 我的问题是，我认为过于依赖Java的思维来实际以一种利用Prolog逻辑能力的方式来表达问题 .

  就个人而言，我认为这个例子已经远远超过了一开始就可以预料的，比如Java程序员 . 请尝试用Java / C /解决这个问题，看看你能得到多少 . 根据我的经验，当学生说他们是"too tied to Java's thinking"等时，他们也无法解决Java中的问题 . Prolog是不同的，但没有那么不同，如果你清楚地知道如何用Java解决它，就不能直接将它翻译成Prolog . 我的解决方案使用Prolog的内置搜索机制，但您不必：您可以像在Java中一样自己实现搜索 .

  回复于 2024-04-26T09:38:34+08:00
• 7

  这是我的解决方案：

  solution(Begin, End, PrevSteps, [Step | Steps]) :-
      Step = step(Begin, State1),
      Step,
      forall(member(step(S, _), PrevSteps),
             State1 \= S
            ), % prevent loops
      (   State1 == End
      ->  Steps = []
      ;   solution(State1, End, [Step | PrevSteps], Steps)
      ).
  
  rev(->,<-).
  rev(<-,->).
  
  step([X,Y|T], [XX,YY|T]) :- rev(X,XX), rev(Y, YY).
  step([A,X,Y|T], [A,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
  step([A,B,X,Y|T], [A,B,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
  step([A,B,C,X,Y|T], [A,B,C,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
  step([A,B,C,D,X,Y], [A,B,C,D,XX,YY]) :- rev(X,XX), rev(Y, YY).
  
  
  run :-
      solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->],[],Steps),
      !,
      forall(member(Step,Steps),writeln(Step)).
  

  它只找到所有可能的第一个解决方案，尽管我认为找到的解决方案不是最优的，而是首先使用的解决方案 .

  回复于 2024-04-26T09:38:34+08:00
• 5

  管理将mat的代码转换为汞：

  :- module arrows.
  
  :- interface.
  
  :- import_module io.
  
  :- pred main(io, io).
  :- mode main(di, uo) is cc_multi.
  
  :- implementation.
  
  :- import_module list, io, int.
  
  :- type arrow ---> (->); (<-).
  
  :- mode solution(in, in, in, in, out, in) is cc_nondet.
  solution(State0, Target, MaxDepth, CurrentDepth) -->
      {CurrentDepth =< MaxDepth},
      (    { State0 = Target } -> []
      ;    { step(State0, State1) },
           [State1],
           solution(State1, Target, MaxDepth, CurrentDepth + 1)
      ).
  
  flip(->, <-).
  flip(<-, ->).
  
  step([], []).
  step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
  step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).
  
  main -->
      (({
      member(N, 1..10),
          solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->], N, 0, Solution, [])
      }) 
      -> print(Solution)
      ; print("No solutions")
      ).
  

  使用mmc --infer-all arrows.m进行编译以推断签名和确定性

  回复于 2024-04-26T09:38:34+08:00