Проблема здесь, в этом фрагменте кода:

{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).

Вы заменили 1 на атом street1.

Но 1 в исходной программе не является идентификатором "улицы" (больше похоже на перекресток: узлы – это перекрестки, ребра – улицы, потому что концептуально трудно добраться до одной улицы с другой улицы в одностороннем порядке с фиксированной стоимостью, не так ли?), но значение: это ограничение кардинальности. Правильное выражение:

{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).

который выражает, что:

Для любого основного факта cycle(X,Y) в наборе ответов:

• должен быть соответствующий edge(X,Y)
• должно быть ровно 1 из cycle(X,Y) для любого X
• должно быть ровно 1 из cycle(X,Y) для любого Y

Я не знаю, почему клинго не протестует? Я не пробовал это запускать.

«Гамильтоновский» цикл или цикл «Задача китайского почтальона»?

Обратите внимание, что вы пишете;

Вышеупомянутая проблема может быть смоделирована путем представления карты города в виде ориентированного графа, и задача состоит в том, чтобы посетить все ребра (т.е. дороги) хотя бы один раз.

Это совершенно верно: ребра — это дороги/улицы, поэтому концептуально неправильно (хотя синтаксически эквивалентно) перемаркировать узлы с именами 1..6 как street1..street6.

Программа, как указано, затем приступает к решению проблемы Гамильтоновского пути (каждый узел посещается ровно один раз), тогда как он должен решить (по сложности проще) Route Inspection/Chinese Postman (каждое посещенное ребро хотя бы один раз, оптимально ровно один раз).

Ограничение исходной программы

{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).

выражает ограничение для гамильтонова пути (еще не гамильтонов цикл, начинающийся и заканчивающийся в одном и том же узле, просто путь). Для любого узла существует ровно одно входящее ребро, принадлежащее циклу, и ровно одно исходящее ребро, принадлежащее циклу. Следовательно, каждый узел посещается ровно один раз => Гамильтонов путь.

(Интересно, reached лишнее? Если нет, то почему?)

График исходной задачи

• Узлы - синие круги.
• Стоимости - белые овалы.
• Начальный узел для цикла равен 1.
• Стрелки указывают, как можно обойти край (как это принято)
• Указано одно решение.

Обновление: моя попытка ASP

Этот материал ASP сложен. Не знаю, как правильно сформулировать проблему. Большая проблема заключается в том, что мы не знаем, как глубоко искать, и единственный способ, который я нашел для атаки, заключается в запуске программы с последовательно увеличивающимися значениями max_time, пока не будет выведено SATISFIABLE. Проблема в том, что мы генерируем возможные пути с «ровно одним литералом в каждый момент времени T» через

1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).

эти наборы path/2 литералов затем проверяются на соответствие ограничениям. Таким образом, в отличие от Пролога, мы не можем "завершить выполнение, когда мы достигнем узла 1 и все ребра были посещены". Как это делается правильно? Я думал о «парковке пути» на edge(1,1) со стоимостью 0 в конце, но это делает программу беспорядочной, и мне не удалось указать глобальное ограничение на структуру пути, которая затем состоит из «хорошей части», «в последний раз ударить по узлу 1» и «хвостовую часть игнорировать».

% ===
% Attempt at the "Chinese Postman Problem" / "Route Inspection Problem"
% ===
% https://en.wikipedia.org/wiki/Route_inspection_problem

% Original statement:
%
% "Find a shortest closed path or circuit that visits every edge of an
% (connected) undirected graph."
%
% Here:
%
% "Find a closed path (cycle) starting from node 1 that visits every pair
% (X,Y) of nodes of a directed graph where that pair is connected by an edge
% (X->Y) or (Y->X) or both. Every edge has an associated
% cost. Find the cycle with the minimum cost."
%
% "max_time" is the length of the resulting path. Sadly, one has to manually
% reduce "max_time" in a stepwise fashion until the shortest path is found.
% How can that be done programmatically?

#const max_time=13.

time(1..max_time).

% ---
% Generating part
% ---

% For every time "T", there is exactly one path/2 literal indicating that
% the path element for time T goes via edge(X,Y).

1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).

% ---
% Defining part
% ---

% "Start at node 1", alias:
% "The path/2 literal for time=1 cannot be based on an edge/2 literal that
% does not start at node 1"

:- path(e(X,Y),t(1)), edge(X,Y), X!=1.

% "Path literals must be connected", alias
% "The path/2 literals for time=T and time=T+1 cannot have edges ending and
% starting at different nodes"

:- path(e(X,N1),t(T)), path(e(N2,Y),t(TT)), TT=T+1, N1!=N2.

% "Every street must have been visited at least once before time T", alias:
% "It is not possible for edge/2 to exist between node pair (X,Y) and
% visited(X,Y) not to be true"
% and 
% "visited(X,Y) is true if edge(X,Y) or the edge(Y,X) (or both) are the path"

visited(X,Y,T) :- time(T),path(e(X,Y),t(Tx)), Tx <= T.
visited(X,Y,T) :- time(T),path(e(Y,X),t(Tx)), Tx <= T.

:- edge(X,Y), not visited(X,Y,max_time).

% "The path must be a cycle, returning to node 1 at exactly max_time"

:- path(e(X,Y),t(max_time)), Y!=1.

% Compute cumulative cost of path

acc_cost(C,1) :- path(e(X,Y),t(1)),cost(edge(X,Y),C).
acc_cost(C,T) :- time(T),T>1,path(e(X,Y),t(T)),cost(edge(X,Y),Cx),Tp=T-1,acc_cost(Cp,Tp),C=Cp+Cx.

% ---
% Define the graph itself
% ---

% Nodes are street intersections, just labeled node(1) .. node(6).
% Note that this is different from using atoms as names as in 
% node_1, node_2, ....
% What we are saying here is that "certain integers 1 ... 6 can appear
% as labels of nodes" or "integer  1 ... 6 have the attribute 'node'"

node(1..6).

% Directed edges are streets, linking the nodes, i.e. the intersections.
% If there is an edge A->B and an edge B->A then it's a two-way-street.
% If there is an edge A->B but no edge B->A then it's a one-way street.
% What we are saying here is that "certain tuples of integers (X,Y) can
% appear as labels of edges".

edge(1,(2;3;4)).  edge(2,(4;5;6)).  edge(3,(1;4;5)).
edge(4,(1;2)).    edge(5,(3;4;6)).  edge(6,(2;3;5)).

% Not made explicit is the fact that X and Y in edge(X,Y) must be labels
% of nodes. For good measure, we add an integrity constraint. Also,
% disallow reflexivity.

:- edge(X,Y), not node(X).
:- edge(X,Y), not node(Y).
:- edge(X,X).

% Driving down a street has a cost, so associate a cost with each edge.
% Let's be explicit in naming and use the "edge/2" predicate inside of the
% cost/2 predicate.

cost(edge(1,2),2).  cost(edge(1,3),3).  cost(edge(1,4),1).
cost(edge(2,4),2).  cost(edge(2,5),2).  cost(edge(2,6),4).
cost(edge(3,1),3).  cost(edge(3,4),2).  cost(edge(3,5),2).
cost(edge(4,1),1).  cost(edge(4,2),2).
cost(edge(5,3),2).  cost(edge(5,4),2).  cost(edge(5,6),1).
cost(edge(6,2),4).  cost(edge(6,3),3).  cost(edge(6,5),1).

:- cost(edge(X,Y),C), not edge(X,Y).
:- edge(X,Y), not cost(edge(X,Y),_).
:- cost(edge(X,Y),C1), cost(edge(Y,X),C2), C1 != C2.

% ---
% Optimization
% ---

#minimize { C: acc_cost(C,max_time) }.

% ---
% Displaying part
% ---

#show path/2.
% #show acc_cost/2.

Таким образом, присвоив max_time значение 13, мы получим:

Solving...
Answer: 1
path(e(1,3),t(1)) path(e(3,1),t(2)) path(e(1,2),t(3))
path(e(2,5),t(4)) path(e(5,4),t(5)) path(e(4,2),t(6))
path(e(2,6),t(7)) path(e(6,3),t(8)) path(e(3,5),t(9))
path(e(5,6),t(10)) path(e(6,3),t(11)) path(e(3,4),t(12))
path(e(4,1),t(13))
Optimization: 30
OPTIMUM FOUND

И это выглядит следующим образом:

Ницца.

Вдохновленный изменением @David, я сделал это, у нас есть 2 ответа!

%hamilltonian cycles

% Generate
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
cleaned(Y) :- cycle(X,Y).
cleaned(Y) :- cycle(X,Y), cleaned(X).
% Test
:- node(Y), not cleaned(Y).

% Nodes
%node(1..6).
%node(street1..street6).

node(street1;street2;street3;street4;street5;street6).


% (Directed) Edges
edge(street1,(street2;street3;street4)).  
edge(street2,(street4;street5;street6)).  
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).    
edge(street5,(street3;street4;street6)).  
edge(street6,(street2;street3;street5)).

% Edge Costs
cost(street1,street2,2).  cost(street1,street3,3).  cost(street1,street4,1).
cost(street2,street4,2).  cost(street2,street5,2).  cost(street2,street6,4).
cost(street3,street1,3).  cost(street3,street4,2).  cost(street3,street5,2).
cost(street4,street1,1).  cost(street4,street2,2).
cost(street5,street3,2).  cost(street5,street4,2).  cost(street5,street6,1).
cost(street6,street2,4).  cost(street6,street3,3).  cost(street6,street5,1).


% Optimize minimum cost and cycle 
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.

% Display
#show cycle/2.

Запуск вышеуказанного

Solving...
Answer: 1
cycle(street1,street4) cycle(street2,street5) cycle(street3,street1) cycle(street4,street2) cycle(street5,street6) cycle(street6,street3)
Optimization: 12
Answer: 2
cycle(street1,street2) cycle(street2,street4) cycle(street3,street5) cycle(street4,street1) cycle(street5,street6) cycle(street6,street3)
Optimization: 11
OPTIMUM FOUND

График для второго ответа выше не связан: