通过 MiniZinc 求解并显示最短路径问题中的有序边

Question

我在http://www.hakank.org/minizinc

中使用MiniZinc计算了一个基于hakank模型的最短路径优化问题

我将距离矩阵输入到一个对称的矩阵中，这样图形就是双向的。

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，但我无法将所有边排序为 2->5、5->8 和 8 ->1.

我想找到起始节点所在的索引（这里是 2,5）并搜索矩阵直到 x[i,j]>0 和 x[j,k]>0，其中 inFlow [j]=outFlow[j]=1，但它不起作用，因为可能有不止一个 k 满足问题（输出图是无方向的）。我想知道是否有任何想法如何在解决方案中保存边的顺序。谢谢

Answer 1

一种方法是通过表示路径的变量：

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" ++

通过 MiniZinc 求解并显示最短路径问题中的有序边

Solve and show the ordered edges in shortest path problem by MiniZinc

sorting

shortest-path

minizinc