Решите и покажите упорядоченные ребра в задаче кратчайшего пути от MiniZinc - PullRequest
Новая
       12

Решите и покажите упорядоченные ребра в задаче кратчайшего пути от MiniZinc

0 голосов
/ 10 января 2020

Я использую MiniZin c вычисляю задачу оптимизации задачи кратчайшего пути на основе модели Хаканка в http://www.hakank.org/minizinc

Я вводю матрицу расстояний в симметрию c единицу такой, что график является двунаправленным. 

int: start = 2; % start node
int: end = 1;   % end node
int: M = 999;   % large number

array[1..n, 1..n] of 0..M: d = array2d(1..n,1..n, 
                                [  M, 11, 8,  3,  8, 10,  2,  4, % 1-X
                                  11,  M, 3,  5,  1,  4,  8,  3, % 2-X
                                   8,  3, M,  5,  7,  7, 11,  4, % 3-X
                                   3,  5, 5,  M,  9,  3, 10, 15, % 4-X
                                   8,  6, 7,  9,  M,  7, 12,  1, % 5-X
                                  10,  4, 7,  3,  7,  M,  6,  9, % 6-X
                                   2,  8, 8, 10, 12,  9,  M, 14, % 7-X
                                   4,  3, 4, 15,  1,  9, 14,  M  % 8-X
                                  ]
                               );

% objective to minimize
var int: total_cost = sum(i in 1..n, j in 1..n where d[i,j] < M) ( d[i,j]*x[i,j] );

array[1..n] of var -1..1: rhs;  % indicating start/end nodes
array[1..n, 1..n] of var 0..1: x; % the resulting connection matrix
array[1..n, 1..n] of var 0..n*n: y; % output node matrix
array[1..n] of var 0..1: outFlow; % out flow array
array[1..n] of var 0..1: inFlow;  % in flow array

constraint 
     % set rhs for start/end nodes
     forall(i in 1..n) ( 
       if i = start then 
         rhs[i] = 1
       elseif i = end then 
         rhs[i] = -1
       else  
         rhs[i] = 0
       endif
    )
    /\ % assert that all x values is >= 0
   forall(i in 1..n, j in 1..n where d[i,j] < M) (
         x[i,j] >= 0 /\ y[i,j] >= 0
   ) 
   /\ % calculate out flow
   forall(i in 1..n) (
      outFlow[i] = sum(j in 1..n where d[i,j] < M) (x[i,j])
   )
   /\ % calculate in flow
  forall(j in 1..n) (
    inFlow[j]  = sum(i in 1..n where d[i,j] < M) (x[i,j])
  )
  /\ % outflow = inflow
  forall(i in 1..n) (outFlow[i] - inFlow[i] = rhs[i])
  /\ % do not loops
  forall(i in 1..n) (
     x[i,i] = 0
  )
  /\ % sanity: there can be no connection in x if there is not
     % connection in d
  forall(i,j in 1..n) (
     if d[i,j] = M then
        x[i,j] = 0
     else 
        true
     endif
  )

;

solve minimize total_cost;

output [
       if i = 1 /\ j = 1 then
         "total_cost: " ++ show(total_cost) ++ "\n" ++
         "inFlow:  " ++ show(inFlow) ++ "\n" ++ "outFlow: " ++ show(outFlow) ++ "\n" ++
         "       1    2    3    4    5    6    7    8\n" 
       else "" endif ++
       if j = 1 then show(i) ++ " : " else "" endif ++
       show_int(4,x[i,j]) ++ if j = n then "\n" else " " endif
       | i in 1..n, j in 1..n
];

Решение дает выходную матрицу, которая указывает, какое ребро графа участвует в решении; Однако решение не имеет направления. Я не могу сказать порядок края, чтобы принять конкретное решение. В вышеприведенном примере кратчайший путь от узла 2 к узлу 1 дает следующее решение 

total_cost: 6
inFlow:  [1, 0, 0, 0, 1, 0, 0, 1]
outFlow: [0, 1, 0, 0, 1, 0, 0, 1]
       1    2    3    4    5    6    7    8
1 :    0    0    0    0    0    0    0    0
2 :    0    0    0    0    1    0    0    0
3 :    0    0    0    0    0    0    0    0
4 :    0    0    0    0    0    0    0    0
5 :    0    0    0    0    0    0    0    1
6 :    0    0    0    0    0    0    0    0
7 :    0    0    0    0    0    0    0    0
8 :    1    0    0    0    0    0    0    0

, которое предлагает к краю 8-> 1, 2-> 5, 5-> 8, но I Я не смогу упорядочить все ребра как 2-> 5, 5-> 8 и 8-> 1.

Я думал найти индекс в том месте, где находится начальный узел (здесь это 2 , 5) и искать в матрице до тех пор, пока x [i, j]> 0 и x [j, k]> 0, где inFlow [j] = outFlow [j] = 1, но не работает, так как может иметь более одного k удовлетворяет задаче (выходной граф не имеет направления). Интересно, есть ли идея, как сохранить порядок ребер в решении. Спасибо.

1 Ответ

1 голос
/ 13 января 2020

Один путь был бы над переменной, представляющей путь: 

array[1..n] of var 0..n: path;

Определите путь через ограничения: 

constraint
    % start point
    path[1] = start 
    /\ % end point
    path[sum(inFlow) + 1] = end
    /\ % interior points
    forall(p in 2..sum(inFlow))
        (path[p] = sum(i in 1..n)(i * x[path[p-1], i]));

Затем отобразите путь как часть выходного оператора: 

     "path:  " ++ show([path[i] | i in 1..sum(inFlow) + 1]) ++ "\n" ++
...