Обязан использовать ограничения в прологе - PullRequest
Новая
       29

Обязан использовать ограничения в прологе

0 голосов
/ 22 декабря 2018

Я сейчас пытаюсь решить эту загадку дома , используя только ограничения, предоставляемые библиотекой пролога clpfd, а это значит, что я не могу использовать возвратный путь!

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

Мой ввод - это список координат, подобный этому [[0,0],[0,3],[2,0],[3,0],[2,1],[3,1],[2,2],[3,3]] И решение для этого будет: 

[
   [[0,0],[0,3]],
   [[2,0],[3,1]],
   [[2,1],[3,0]],
   [[2,2],[3,3]]
]

Мой текущий прогресс такой: 

connect(Houses):-
    %There are only 2 distances and they're different
    length(Distances, 2),
    all_distinct(Distances),

    %One connection per 2 houses (pairs) means half the number of houses as connections
    length(Houses, NHouses),
    NConnections #= NHouses // 2,
    length(Connections, NConnections),

    restrictDistances(Connections, Distances), %restrict every connection to have one of the two distances


    %All the houses must be connected
    append(Connections, ConnectedHouses),
    ensureAllConnected(Houses, ConnectedHouses), %table

    removeSymmetries(Connections), %avoid symmetries

    %flatten list and labeling
    append(ConnectedHouses, HousesCoordinates),
    labeling([], HousesCoordinates),
    write(Connections).

/*
    All distances of all connections are one of the two distances
    Distance is kept squared to keep it an integer i.e. dist(connection) = dist([[x1, y1], [x2, y2]]) = (x2-x1)^2 + (y2-y1)^2
*/
restrictDistances([], _).
restrictDistances([[[X1, Y1], [X2, Y2]]|Connections], Distances):-
    DiffX #= X2 - X1,
    DiffY #= Y2 - Y1,
    Dis #= DiffX * DiffX + DiffY * DiffY,
    % element(Idx, Distances, Dis), %element
    member(Dis, Distances), %element
    restrictDistances(Connections, Distances).

/*
    Ensures all houses are connected
*/
ensureAllConnected([], _).
ensureAllConnected([H|Houses], ConnectedHouses):-
    member(H, ConnectedHouses),
    % element(_, ConnectedHouses, H),
    ensureAllConnected(Houses, ConnectedHouses).

/*
    Remove symmetries and connection permutations in final result
*/
removeSymmetries([_]).
removeSymmetries([[[X1, _], [X2, _]], [[X3, Y3], [X4, Y4]]|Connections]):-
    X1 #=< X2,
    X1 #=< X3,
    X3 #=< X4,
    removeSymmetries([[[X3, Y3], [X4, Y4]]|Connections]).

Хуже всего то, что этот код работает , однако предикат member не может быть использован, потому что он использует возвратный путь ... И да, предикат element существует, но я не могу заменить егопотому что, если я заменю первый, вывод будет другим, и если я заменю второй, я получу ошибку создания экземпляра.

1 Ответ

0 голосов
/ 24 декабря 2018

Строго говоря, проблема недостаточно конкретизирована, поскольку существует более одного вида расстояния, например, евклидово расстояние и гамильтоново расстояние.По-видимому, подразумеваются евклидовы расстояния, в противном случае вы получите несколько решений для этого экземпляра.

Для этой головоломки полезно подумать о том, какие подзадачи могут быть закодированы с глобальными ограничениями.Вот несколько советов:

  • Вам нужно найти соответствие - которое можно закодировать с помощью assignment(Xs,Xs).
  • Вы можете использовать table/2 для кодирования отношения (дом, дом, расстояние) .
  • Вы можете использовать nvalue/2 для ограничения количества различных расстояний.

Это глобальные ограничения в SICStus Prolog.

...