Проблема в здесь, в этом фрагменте кода :
{ 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
Я не знаю, почему Clin go не протестует? Я не пытался выполнить это.
цикл "Гамильтониан" или цикл "Проблема китайского почтальона"?
Обратите внимание, что вы пишете;
Вышеуказанная проблема можно смоделировать, представив карту города с помощью ориентированного графика, и задача состоит в том, чтобы посетить все края (ie дороги) хотя бы один раз
Это совершенно верно: края являются дороги / улицы, поэтому концептуально (хотя и синтаксически эквивалентно) относительные узлы называются 1..6 как street1 .. street6.
Программа, как указано далее, приступает к решению Гамильтонова задача (каждый узел просматривался ровно один раз), в то время как он должен решить (с точки зрения сложности) Проверка маршрута / Китайский почтальон (каждое ребро посещено хотя бы один раз, оптимально ровно один раз).
Ограничение исходной программы
{ 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
И это выглядит следующим образом:
Ницца.