在 Prolog 数组中进行有序插入的意外行为

Question

我需要使用需要按升序排序的数组来实现队列。每个项目都是图的一个节点，我正在使用 A* 算法进行探索，即：

nodo(S, ListaAzioniPerS, C, S)

其中 S 是节点的标识符，ListaAzioniPerS 到达该节点的路径，C 是到这里的成本，S 是它的启发式。我需要按我称为 F

的 C+S 的总和来排序它们

为此，我尝试通过以下代码进行有序插入：

orderedInsert(X, [], [X]).
orderedInsert(nodo(S, ListaAzioniPerS, C, S),
              [nodo(S1, ListaAzioniPerS1, C1, S1)|Rest],
              [nodo(S, ListaAzioniPerS, C, S), nodo(S1, ListaAzioniPerS1, C1, S1)|Rest]) :-
  F is C + S,
  F1 is C1 + S1,
  F < F1,
  !.
%orderedInsert(nodo(S, ListaAzioniPerS, C, S),
%              [nodo(S1, ListaAzioniPerS1, C1, S1)|Rest],
%       [nodo(S, ListaAzioniPerS, C, S), nodo(S1, ListaAzioniPerS1, C1, S1)|Rest]) :-
%  F is C + S,
%  F1 is C1 + S1,
%  F == F1,
%  C < C1,
%  !.
orderedInsert(X, [Y|Rest0], [Y|Rest]) :-
  orderedInsert(X, Rest0, Rest).

（有一个评论部分在 F==F1 的情况下进行考试，所以他们会按 C 订购，但因为我已经搞砸了，所以我只是评论了它）

现在，出于某种原因，即使我用第二个参数调用 orderedInsert/3 一个非空列表，它也只与第一个函子匹配！但这还不是全部，结果总是在列表末尾追加... 这是这一行的一个简单示例 orderedInsert(nodo(nodo1, listaAzioniPerS, 1, 1), [nodo(nodo2, listaAzioniPerS1, 2, 1)], X).

[trace] 7 ?- orderedInsert(nodo(nodo1, listaAzioniPerS, 1, 1), [nodo(nodo2, listaAzioniPerS1, 2, 1)], X).
 * Call: (8) orderedInsert(nodo(nodo1, listaAzioniPerS, 1, 1), [nodo(nodo2, listaAzioniPerS1, 2, 1)], _2026) ? creep
   Call: (9) length([nodo(nodo2, listaAzioniPerS1, 2, 1)], 0) ? creep
   Fail: (9) length([nodo(nodo2, listaAzioniPerS1, 2, 1)], 0) ? creep
 * Redo: (8) orderedInsert(nodo(nodo1, listaAzioniPerS, 1, 1), [nodo(nodo2, listaAzioniPerS1, 2, 1)], _2026) ? creep
 * Call: (9) orderedInsert(nodo(nodo1, listaAzioniPerS, 1, 1), [], _2278) ? creep
   Call: (10) length([], 0) ? creep
   Exit: (10) length([], 0) ? creep
 * Exit: (9) orderedInsert(nodo(nodo1, listaAzioniPerS, 1, 1), [], [nodo(nodo1, listaAzioniPerS, 1, 1)]) ? creep
 * Exit: (8) orderedInsert(nodo(nodo1, listaAzioniPerS, 1, 1), [nodo(nodo2, listaAzioniPerS1, 2, 1)], [nodo(nodo2, listaAzioniPerS1, 2, 1), nodo(nodo1, listaAzioniPerS, 1, 1)]) ? creep
X = [nodo(nodo2, listaAzioniPerS1, 2, 1), nodo(nodo1, listaAzioniPerS, 1, 1)] .

跟踪虽然执行对我没有任何帮助（实际上它让我怀疑我是否完全理解序言）。知道我哪里错了吗？

使用 SWI Prolog。

Answer 1

您的问题是变量 S 和 S1 的重复使用。您可以将它们更改为 - 例如 -

orderedInsert(nodo(N, ListaAzioniPerS, C, S),
              [nodo(N1, ListaAzioniPerS1, C1, S1)|Rest],
              [nodo(N, ListaAzioniPerS, C, S), nodo(N1, ListaAzioniPerS1, C1, S1)|Rest]) :-
  F is C + S,
  F1 is C1 + S1,
  F < F1,
  !.

您的代码将起作用。顺便说一句，你可以减少一点混乱：

orderedInsert(nodo(N, ListaAzioniPerS, C, S),
              [nodo(N1, ListaAzioniPerS1, C1, S1)|Rest],
              [nodo(N, ListaAzioniPerS, C, S), nodo(N1, ListaAzioniPerS1, C1, S1)|Rest]) :-
  C + S < C1 + S1,
  !.

在 Prolog 数组中进行有序插入的意外行为

Unexpected behaviour doing ordered insertion in array in Prolog

arrays

graph-theory

prolog