All geek questions in one place

Uncertainty in the logical engine (creation of plausible relative positions based on local geography)

I know that there is a high probability that I encountered the XY problem, so the first fragment of this question concerns a more general situation.

Problem

I have a set of data points containing abstract geographic information, but not actual locations (absolute or relative). For example, let’s call it the following list of cities, which describes the local landscape, but without coordinates or relative positioning:

  • City A is on an island and on a hill.
  • City B is on the coast and by the river.
  • City C is on a mountain and near a river.
  • City D is on an island and on a hill.
  • City E is on the island and on the plains.

From this, I want to write a program that can provide relative positions for these locations. In the above list, you can get that A and D are next to each other, E can be next to them, but less likely, and B and C can be next to each other. You can think of it as a graph with all the edges trimmed, and the program tries to write them back depending on the properties of the nodes. Given this, he could come up with some arbitrary coordinates for each city from which a map could be drawn.

I do not need a unique solution - my ultimate goal is plausible maps of unpublished, but described fictional places.

, , , , Prolog , . , . , , , , , , . " - " " ". ( , , ), ( , , , ).

( ) , , Prolog /?

+4
2

MiniZinc ( ).

, , . , , .. ( , . . .)

, ( A..H)  - (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).

Constraint , , . MIP- / SAT.

: - , . : http://hakank.org/minizinc/place_cities.mzn , , , ..

+1

placement , .

satisfiability, . 2D-, - , , . (Mt. Foobar). - node, . .

. . , node - :

IF node node

node , A

IF node B

, :

a node THEN

, . , , .

, SAT (, Glucose)

, AllSAT, .

, SMT

, , , .

, .

SAT solver , .

+1

Source: https://habr.com/ru/post/1675813/

More articles:


All Articles