第一搜索算法

Question

我需要使用第一个搜索算法

在我如何使用第一搜索算法方面，有人能帮助我吗？

提前感谢

Answer 1

根据节点A的字母顺序展开状态，下面是为深度优先搜索而维护的打开/关闭列表，用于上面的图。答案：

​

​

Answer 2

在这个问题的背景下，开放和封闭究竟意味着什么？

在Prolog中，关闭的列表是由原子[]终止的列表，表示空列表。

在括号内的列表表示法中，应该是这样的列表：

[a,b,c]

在正式的./2表示法中，该列表由以下Prolog结构表示：

.( a , .( b , .( c , [] ) ) )

与打开的列表相同的列表是：

[ a , b , c | Some_Unbound_Variable ]

或者用./2符号表示：

.( a , .( b , .( c , Some_Unbound_Variable ) ) )

我不相信这就是你要找的。请解释一下。

您的图看起来是一个有向循环图，也就是说，边只能在一个方向上遍历(一个人可以从A到G，但不能从G到A)，而且它包含循环，这意味着从图中的一个节点开始并遍历该图，您最终会回到原点(一个循环)。这会导致无止境的循环，除非你跟踪你去过的地方。

您可以这样表示您的图形：

edge( a , f ).
edge( a , g ).
edge( c , a ).
edge( c , d ).
edge( d , c ).
edge( d , f ).
edge( e , c ).
edge( e , d ).
edge( e , g ).
edge( f , e ).

遍历一个图是非常简单的：

traverse( Origin, Destination, Path ) :-
  edge(Origin,_),
  traverse( Origin, Destination, [Origin] , Path )
  .

traverse( A, B , Vs , [B|Vs] ) :- % we can get from A to B
  edge(A,B)                       % - if A and B are directly connected.
  .                               % otherwise...
traverse( A, B , Vs , P      ) :- % we can get from A to B
  edge(A,X) ,                     % - if we can get from A to some X
  X \== B   ,                     % - such that X is not B
  \+memberchk(X,Vs) ,             % - and that we have not yet visited X
  traverse(X,B,[X|Vs],P)          % - and see if we can get from X to B
  .                               %

成功后，Path应该与通过图的路径以相反的顺序统一，因此，以您的图形为例，Path = [G,E,F,A]说您遍历了G <- E <- F <- A。

Answer 3

要获得@J013R给出的答案，您可以使用以下程序：

dfs_traversal(Root) :-
   format('Open    Closed        Visited\n'),
   dfs_traversal([Root], [], -).

dfs_traversal(Open, Closed, Visited) :-
   format('~|~w~t~7+ ~|~w~t~13+ ~w\n', [Open, Closed, Visited]),
   (   Open = [Node|Rest]
   ->  findall(Successor, successor(Node, Open, Closed, Successor), Successors),
       append(Successors, Rest, NewOpen),
       dfs_traversal(NewOpen, [Node|Closed], Node)
   ;   true ).

successor(Node, Open, Closed, Successor) :-
   arc(Node, Successor),
   not(member(Successor, Open)),
   not(member(Successor, Closed)).

arc(a, f).
arc(a, g).
arc(c, a).
arc(c, d).
arc(d, c).
arc(d, f).
arc(e, c).
arc(e, d).
arc(e, g).
arc(f, e).

示例：

?- dfs_traversal(a)
Open    Closed        Visited
[a]     []            -
[f,g]   [a]           a
[e,g]   [f,a]         f
[c,d,g] [e,f,a]       e
[d,g]   [c,e,f,a]     c
[g]     [d,c,e,f,a]   d
[]      [g,d,c,e,f,a] g
true.