prolog - 逻辑引擎中的不确定性(根据本地地理产生合理的相对位置)

Question

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

问题
我有一组包含抽象地理特征信息的数据点，但没有实际位置(绝对或相对)。例如，我们将其称为以下描述本地地形但没有坐标或相对定位的城市列表:

城市A在一个岛上和一个小山上。

B 市位于海岸边，靠近河流。

C市依山傍水

D 市在一个岛上和一个小山上。

城市 E 位于岛屿和平原上。

由此，我想编写一个程序，可以提供这些位置的相对位置。对于上面的列表，可以推导出 A 和 D 彼此靠近，E 可能靠近它们但可能性较小，而 B 和 C 可能彼此靠近。你可以把它想象成一个所有边都被磨掉的图，程序试图根据节点的属性把它们写回。鉴于此，它可以为每个城市提供一些任意坐标，从中可以绘制 map 。
我不需要一个独特的解决方案——我在这里的最终目标是未映射但描述的虚构地点的似是而非的 map 。
在我看来，这是一种非常适合的问题，例如Prolog 或类似的逻辑引擎，因为它基本上只是约束解析。但是，我自己无法完全解决。我目前遇到的问题与这样一种方式有关，例如，两个城市可以具有相似的本地特征，而不会靠近该更大特征的同一实例。这是“这座城市靠近某个未指定的山”和“这座城市靠近富巴山”之间的区别。后者提供了很强的约束(都在富巴山附近的两个城市彼此靠近)，但后者仅提供了一个指南(两个靠近山脉的城市比一个靠近山的城市和另一个城市更靠近彼此)不在山附近)。

问题
在 Prolog 或其他逻辑/规则引擎中，如何定义(并提供基于)概率而不是绝对概率？

Answer 1

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

该模型的假设是有一张固定地点的 map ，例如山、丘陵、河流等所在的地方。 (我不确定这是否在您的假设中。对于不同的模型，请参见下文。)

然后目标是使用这些约束放置一些城市(在这个模型中的城市 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,
 ]);

数据基于此(虚构的)带有缩写的 map 。

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 求解器和大多数/许多 SAT 求解器相比。

补充两点意见:
- 我首先解释了现在根本存在已知位置的问题。型号在此: http://hakank.org/minizinc/place_cities.mzn
请注意，它假设只有一座山、一条河流等。

此外，在构建这些模型后，我意识到这个问题让人想起 Rina Dechter “约束处理”，第 5 页中引用的“经典”纳德尔构造问题。目标是将某些东西放在靠近或不靠近某些地方的地方。我已经在一些 CP 系统中实现了这个问题:

MiniZinc:http://hakank.org/minizinc/nadel.mzn

皮卡:http://hakank.org/picat/nadel.pi

B-Prolog: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