逻辑引擎中的不确定性（根据当地地理位置产生合理的相对位置）

Question

我知道我很有可能在这里遇到 XY 问题，所以第一部分是关于更一般的情况。

问题

我有一组包含抽象地理特征信息但没有实际位置（绝对或相对）的数据点。为了举例，我们将其称为以下描述当地地形的城市列表，但没有坐标或相对定位：

A市在一座小岛上，在一座小山上。
B市在海边，靠近河流。
C市依山傍水
D市在一座小岛上，在一座小山上。
E城在岛上，在平原上。

据此，我想编写一个程序，可以为这些位置提供相对位置。对于上面的列表，可能推导出A和D彼此靠近，E可能靠近但不太可能，B和C可能彼此靠近。你可以把它想象成一个所有边都被擦掉的图，程序会尝试根据节点的属性将它们写回。鉴于此，它可以为每个城市提供一些任意坐标，可以从中绘制地图。

我不需要独特的解决方案 – 我的最终目标是为未映射但已描述的虚构地点绘制合理的地图。

在我看来，这似乎是一种非常适合的问题，例如Prolog 或类似的逻辑引擎，因为它基本上只是约束解析。但是，我自己无法完全解决。我目前遇到的问题与这样的方式有关，例如，两个城市可能具有相似的局部特征，而无需靠近较大特征的同一实例。这就是“这座城市靠近某座未指明的山”和“这座城市靠近福巴尔山”之间的区别。后者提供了一个很强的约束条件（两个都在福巴山附近的城市彼此靠近），但后者只是提供了一个指导（两个都在山上的城市比一个城市靠近一个山和另一个城市更可能彼此靠近）不靠近山）。

问题

如何在 Prolog 或其他 logic/rules 引擎中定义（并根据其提供解决方案）概率而不是绝对值？

Answer 1

这对我来说听起来像是 placement 问题，因此您应该尝试研究解决问题的方法。

我将使用 satisfiability 框架来讨论不确定性和相关内容。你可以定义一个2D网格，每个节点可以容纳特征——一座山，一条河，一座山。功能可以是通用的或特殊的（Mt. Foobar）。可以预定义某些功能 - 您可以在指定节点放置一座山，但这取决于您。城市也被定义为特征。

现在，有趣的部分。您可以定义一组约束 over 这样的网格。因此，对于网格中的每个节点，您可以定义如下内容：

IF city A takes place at node THEN a mountain must be at an adjacent node

IF given node contains a mountain THEN city A must be at any of adjacent nodes

IF city A is present at given node THEN city B can't be at any of adjacent nodes

你可以用这种方式引入很多不同的约束，甚至是计数对象：

IF a node has a river THEN no more than 2 cities could be at adjacent nodes

要做到这一点，可以依靠pseudo-boolean constraints。您甚至可以通过为特定配置引入计数器来将其用于优化解决方案，并要求此处必须多于或小于。

要解决由此产生的问题，您可以使用任何 SAT 求解器（例如 Glucose）

您可以使用 AllSAT 生成多个 不同的 解决方案，也有解决方案。

如果纯布尔公式太复杂，可以试试SMT

如何实施此类系统的详细信息超出了问题的范围，它太宽泛了，需要大量的初步研究。

希望我的回答对您有所帮助。

编辑

SAT 求解器 returns 第一个 正确的解决方案，从这个意义上讲它是随机的。

Answer 2

这是一种使用 MiniZinc（一种非常好的约束建模语言）的方法。

模型的假设是有一张固定地点的地图，例如山，丘陵，河流等所在的地方。（我不确定这是否符合您的假设。对于不同的模型，请参见下文。）

然后 objective 使用这些约束放置多个城市（在此模型中的城市 A..H） - near(P1,P2)：P1 和 P2 必须在一定距离内（由 "near_distance" 定义） - on(P1,P2)：城市 P1 必须位于或非常靠近固定地点 - not_near(P1,P2): P1和P2不能靠近

我更改了一个原始约束并添加了更多城市和约束。

这个模型也在这里：http://hakank.org/minizinc/place_cities2.mzn。解决方案在模型

之后

include "globals.mzn"; 

% The places
enum places       = {island,hill,coast,river,mountain,plains,
                   city_a,city_b,city_c,city_d,city_e,city_f,city_g,city_h
                 };

int: empty  = 0;

set of int: fixed_places = {island,hill,coast,river,mountain,plains};
set of int: to_place = places diff fixed_places; % {city_a,city_b,city_c,city_d,city_e,city_f,city_g,city_h};

int: num_places = length(places);
int: max_x;
int: max_y;
int: near_distance;

array[1..max_x, 1..max_y] of int: data;
array[0..num_places] of string: places_s = array1d(0..num_places, 
                            ["-","i","h","c","r","m","p",
                             "A","B","C","D","E","F","G","H",
                             ]);


 % decision variables
 % position of a city
 array[to_place] of var 1..max_x: x;
 array[to_place] of var 1..max_y: y;

 % the grid (0 is an empty spot)
 array[1..max_x, 1..max_y] of var 0..num_places: grid;


 % on: must be really near.
 % Assumption: p2 is a fixed_place
 predicate on(var 1..num_places: p1, var 1..num_places: p2) =
    exists(I in 1..max_x, J in 1..max_y) (
     data[I,J] = p2 /\
     pow(abs(x[p1]-I),2) + pow(abs(y[p1]-J),2) <= 1
  )
;

% define the concept of near: atmost d distance apart
predicate near(var 1..num_places: p1, var 1..num_places: p2) =
   exists(I in 1..max_x, J in 1..max_y) (
     grid[I,J] = p2 /\
     pow(abs(x[p1]-I),2) + pow(abs(y[p1]-J),2) <= near_distance
  )
;

% not near: > d distance apart
predicate not_near(var int: p1, var int: p2) =
  exists(I in 1..max_x, J in 1..max_y) (
     grid[I,J] = p2 /\
     pow(abs(x[p1]-I),2) + pow(abs(y[p1]-J),2) > near_distance
  )
;



solve satisfy;
% solve :: int_search(x ++ y ++ array1d(grid), input_order, indomain_split, complete) satisfy;

% general constraints
constraint
 % Here we ensure that:
 %   - a fixed place can only be positioned by the fixed place or a city
 %   - if an empty spot (in data[I,J]) then it can only be positioned by a city
 forall(I in 1..max_x, J in 1..max_y) (
    if data[I,J] != empty then 
        (grid[I,J] in {data[I,J]} union to_place)
        /\ grid[I,J] != empty
    else 
     grid[I,J] in to_place union {empty}
    endif
 ) 
;

% city constraints
constraint
 % City A is on an island and on a hill.
  on(city_a,island)  /\
  on(city_a, hill) /\

 % City B is on the coast and near a river.
   on(city_b,coast) /\
   near(city_b,river) /\

 % City C is on a mountain and near a river
   on(city_c,mountain) /\
   near(city_c,river) /\

 % City D is on an island and on a hill.
  on(city_d,island) /\
  on(city_d,hill) /\

%%%City E is on an island and on plains.
%   % on(city_e,island) /\
% Changed it to:
% City E is near the mountains and on plains
near(city_e, mountain) /\
on(city_e,plains) 


% ADDED: 
%  City F is on mountains and near a river
/\
 on(city_f, mountain) /\
 near(city_f,river) 

/\
near(city_g, mountain) /\
near(city_g, hill) 

/\
on(city_h,plains) /\ 
% near(city_h,hill) % /\
% not_near(city_h,city_c) /\
not_near(city_h,city_f)

;

constraint
  % connect the x[p] and y[p] arrays with grid[I,J]
  forall(p in to_place) ( 
     exists(I in 1..max_x, J in 1..max_y) (
       x[p] = I /\ y[p] = J  /\ grid[I,J] = p
     ) 
   )

   % unique place in grid  
   % all cities have unique positions
   /\ all_different([(x[p]*num_places-1)+ y[p]  | p in to_place])

   /\ % each city has just one place in the grid
   forall(p in to_place) (
      sum([grid[I,J] = p | I in 1..max_x, J  in 1..max_y]) <= 1
   )
 ;

 output [
    "x: \(x)\ny: \(y)\n"
 ]
 ++ 
 [
   join("", [places_s[fix(grid[I,J])] | J in 1..max_y]) ++ "\n"
   | I in 1..max_x % , J in 1..max_y
 ]
 ;


 %
 % data
 %  
 max_x = 15;
 max_y = 15;
 near_distance = 4;
 data = array2d(1..max_x,1..max_y,
 [
  empty,empty,empty,empty,empty,empty,river,empty,empty,coast,empty,island,hill,hill,empty,
   empty,empty,empty,empty,empty,empty,river,empty,empty,coast,empty,empty,island,island,empty,
   empty,empty,empty,empty,empty,empty,river,empty,empty,empty,coast,coast,coast,coast,coast,
  empty,empty,empty,empty,empty,empty,river,empty,empty,empty,empty,empty,empty,empty,empty,
     empty,empty,empty,empty,empty,empty,river,empty,empty,empty,empty,empty,empty,empty,empty,
   empty,empty,mountain,mountain,mountain,mountain,empty,empty,empty,empty,empty,empty,empty,empty,empty,
  empty,empty,mountain,mountain,mountain,mountain,mountain,empty,empty,empty,hill,hill,hill,empty,empty,
  empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,hill,hill,hill,empty,empty,
   empty,empty,empty,empty,plains,plains,plains,plains,empty,empty,empty,empty,empty,empty,empty,
  empty,empty,empty,empty,plains,plains,plains,empty,empty,empty,empty,empty,empty,empty,empty,
  empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,
  empty,empty,empty,empty,empty,empty,mountain,mountain,mountain,empty,empty,empty,empty,empty,empty,
  empty,empty,empty,empty,empty,empty,mountain,mountain,mountain,empty,empty,empty,empty,empty,empty,
   empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,
   empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,empty,
 ]);

数据基于这张（虚构的）地图并带有缩写。

i: island
h: hill
c: coast
r: river
m: mountain
p: plains

......r..c.ihh.
......r..c..ii.
......r...ccccc
......r........
......r........
..mmmm.........
..mmmmm...hhh..
..........hhh..
....pppp.......
....ppp........
...............
......mmm......

这是一种解决方案，其中大写字母是要放置的城市：

x: [1, 1, 5, 1, 9, 5, 7, 10]
y: [13, 9, 6, 12, 4, 5, 9, 4]
------r-Bc-DAh-
------r--c--ii-
------r---ccccc
------r--------
----FCr--------
--mmmm---------
--mmmmm-G-hhh--
----------hhh--
---Epppp-------
---Hppp--------
---------------
------mmm------
------mmm------
---------------
---------------

使用 Gecode FlatZinc 解算器在几秒钟内解决（大部分时间是转换为通用 FlatZinc 格式）。

约束规划求解器的一个优点是很容易生成许多解决方案，例如与大多数 MIP 求解器和 most/many SAT 求解器相比。

另外两条评论： - 我首先解释了现在已知位置的问题。模型在这里：http://hakank.org/minizinc/place_cities.mzn 注意这里假设只有一山一河等

此外，在建立这些模型后，我意识到这个问题让我想起了第 5 页 Rina Dechter "Constraint Processing" 中引用的 "classic" Nadel 的构造问题。objective 然后放置某些东西靠近或不靠近某些地方。我已经在一些 CP 系统中实现了这个问题：
- 迷你锌：http://hakank.org/minizinc/nadel.mzn
- 皮卡：http://hakank.org/picat/nadel.pi
- B-序言：http://hakank.org/bprolog/nadel.pl
- ECLiPSe CLP：http://hakank.org/eclipse/nadel.ecl
- SICStus 序言：http://hakank.org/sicstus/nadel.pl
- 地理编码：http://hakank.org/gecode/nadel.cpp

逻辑引擎中的不确定性（根据当地地理位置产生合理的相对位置）

Uncertainty in a logic engine (Produce plausible relative positions based on local geography)

prolog

logic-programming

constraint-programming

问题

问题