启发式函数序言

Question

我有一个问题是 [1,2,3,0,4,5,6]，目标是 [4,5,6,0,1,2,3] 和启发式函数是计算 4、5、6 块在 1、2、3 块位置的错位，所以当我尝试为 head >3 添加条件时，它总是 false

getHeuristic([], 0, []):-!.
% here it is calculated as number of misplaced numbers for 4,5,6 only
% ( so if Head = Head and value greater than 3 its correct so
% don't count it)
getHeuristic([H|T1],V,[H|T2]):-!,
    H>3,
    getHeuristic(T1,V, T2).
getHeuristic([_|T1],H,[_|T2]):-
    getHeuristic(T1,TH, T2),
    H is TH + 1.

Answer 1

如果您想通过计算不匹配位置的数量来计算从“当前状态”到“目标状态”的“距离”：

% nmpcount(+CurrentState,+TargetState,?Count)

nmpcount(CurrentState,TargetState,Count) :-
   nmpcount2(CurrentState,TargetState,0,Count).

% nmpcount2(+CurrentState,+TargetState,+CountSoFar,?CountFinal)

nmpcount2([],[],Count,Count).
nmpcount2([X|MoreCS],[X|MoreTS],CountIn,FinalCount) :-
   nmpcount2(MoreCS,MoreTS,CountIn,FinalCount).
nmpcount2([X|MoreCS],[Y|MoreTS],CountIn,FinalCount) :-
   dif(X,Y),
   CountNext is CountIn+1,
   nmpcount2(MoreCS,MoreTS,CountNext,FinalCount).

Answer 2

A heuristic 是一种快速估计当前状态与目标状态（在状态 space 中）有多接近的方法。

设 h*(S) 为从当前状态 S 到目标状态 G 的最优路径的成本。然后，启发式函数 h(S) 为 可接受 当且仅当：

0 ≤ h(S) ≤ h*(S)，并且

h(G) = 0.

换句话说，可接受的启发式函数必须始终乐观！

例如，从以下当前状态，您需要至少两次“移动”才能达到目标状态：

当前状态=[6,4,5,0,1,2,3]

交换 6 和 4 : [4,6,5,0,1,2,3]

交换 5 和 6：[4,5,6,0,1,2,3] = 目标状态

请注意，例如，启发式函数估计从当前状态 [5,4,6,0,1,2,3] 到达目标状态 [4,5,6,0,1,2,3] 的最佳路径的成本至少为 2 不可接受（因为独特的移动 - 交换 5 和 4 - 足以纠正两个位置）。

因此，我认为你可以这样做：

heuristic(State, Goal, Value) :- heuristic(State, Goal, 0, Value). heuristic([], [], A, A). heuristic([X|Xs], [Y|Ys], A, V) :- ( X < Y -> A1 is A + 1 ; A1 is A ), heuristic(Xs, Ys, A1, V).

示例：

?- heuristic([1,2,3,0,4,5,6], [4,5,6,0,1,2,3], V). V = 3. ?- heuristic([6,4,5,0,1,2,3], [4,5,6,0,1,2,3], V). V = 2. ?- heuristic([5,4,6,0,1,2,3], [4,5,6,0,1,2,3], V). V = 1. ?- heuristic([4,5,6,0,1,2,3], [4,5,6,0,1,2,3], V). V = 0.

备注：启发式函数计算的“移动”不一定对应于导致状态从状态转移到其后继状态的实际移动space （即，它们是 放松的动作 ）。

启发式函数序言

Heuristic function prolog

prolog