沃格尔方法

Question

我正在尝试创建一个在安卓中实现vogel方法的应用程序。任务是

1. 通过从同一行或列的下一个最低单元成本中减去该行或列的最低单元成本，确定每行和每列的惩罚成本

2. 选择惩罚成本最高的行或列（任意断开连接或选择成本最低的单元格）

3. 尽可能多地分配给具有最低成本的可行单元 惩罚最高的行或列中的运输成本 成本

4. 重复步骤2、3和4，直到满足所有要求

5. 计算可行分配的总运输成本

这是我的密码

public  class activityvogel extends ActionBarActivity {


private Button button;
    static int[] stock;
    static int[] required;
    static int[][] converted2;
          static int nRows,nCols;



    static boolean[] rowDone;
   static boolean[] colDone ;
   static int[][] result;
    static ExecutorService es = Executors.newFixedThreadPool(2);



    @Override
    public void onCreate(Bundle savedInstanceState){
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_activityvogel);
                Bundle extras = getIntent().getExtras();
         stock= extras.getIntArray("stock");
         required= extras.getIntArray("required");
        final String[][] cost = (String[][]) extras.getSerializable("converted");

\将数组成本字符串转换为int

        converted2=new int[stock.length][required.length];

       for (int index = 0; index <stock.length; index++)

        {

            for (int subIndex = 0; subIndex <required.length; subIndex++) {
                converted2[index][subIndex] = Integer.parseInt(cost[index][subIndex]);
                            }
        }
        System.out.println(Arrays.deepToString(converted2));
        System.out.println(Arrays.toString(stock));
        System.out.println(Arrays.toString(required));

\这里开始Vogel的方法

        nRows=stock.length;
        nCols = required.length;
        rowDone = new boolean[nRows];
        colDone = new boolean[nCols];
        result = new int[nRows][nCols];
        int supplyLeft = 0;
        for (int i = 0; i < stock.length; i++) {
            supplyLeft += stock[i];
        }
        int totalCost = 0;
        while (supplyLeft > 0) {
            int[] cell = new int[0];
            try {
                cell = nextCell();
            } catch (Exception e) {
                e.printStackTrace();
            }
            int r = cell[0];
            int c = cell[1];
            int quantity = Math.min(required[c], stock[r]);
            required[c] -= quantity;
            if (required[c] == 0)
                colDone[c] = true;
            stock[r] -= quantity;
            if (stock[r] == 0)
                rowDone[r] = true;
            result[r][c] = quantity;
            supplyLeft -= quantity;
            totalCost += quantity * converted2[r][c];
        }
System.out.println(Arrays.deepToString(result));

int[] nextCell() throws Exception{
        Future<int[]> f1 = es.submit(new Callable<int[]>() {
            @Override
            public int[] call() {
                return  maxPenalty(nRows, nCols, true);
            }
        });
        Future<int[]> f2 = es.submit(new Callable<int[]>() {
            @Override
            public int[] call() {
                return maxPenalty(nCols, nRows, false);
            }
        });
        int[] res1 = f1.get();
        int[] res2 = f2.get();

        if (res1[3] == res2[3])
            return res1[2] < res2[2] ? res1 : res2;

        return (res1[3] > res2[3]) ? res2 : res1;
    }

    int[] diff(int j, int len, boolean isRow) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int minP = -1;
        for (int i = 0; i < len; i++) {
            if (isRow ? colDone[i] : rowDone[i])
                continue;
            int c = isRow ? converted2[j][i] : converted2[i][j];
            if (c < min1) {
                min2 = min1;
                min1 = c;
                minP = i;
            } else if (c < min2)
                min2 = c;
        }
        return new int[]{min2 - min1, min1, minP};
    }

    int[] maxPenalty(int len1, int len2, boolean isRow) {
        int md = Integer.MIN_VALUE;
        int pc = -1, pm = -1, mc = -1;
        for (int i = 0; i < len1; i++) {
            if (isRow ? rowDone[i] : colDone[i])
                continue;
            int[] res = diff(i, len2, isRow);
            if (res[0] > md) {
                md = res[0];  // max diff
                pm = i;       // pos of max diff
                mc = res[1];  // min cost
                pc = res[2];  // pos of min cost
            }
        }
        return isRow ? new int[]{pm, pc, mc, md} : new int[]{pc, pm, mc, md};
    }

我的问题是，我没有总是得到我应该得到的正确结果，我也找不到原因。如果有人能帮助我，我将不胜感激。 Here就是这个算法的工作原理

Answer 1

您使用的算法的实现中似乎存在错误

当它执行检查以确定是否将使用惩罚最大的行或列时，它最终将使用惩罚最小的行或列，而不是惩罚最大的行或列

我指的是以下几行：

return (res1[3] > res2[3]) ? res2 : res1;

该行应改为：

return (res1[3] > res2[3]) ? res1 : res2;