java中的回溯优化

Question

我有一个优化问题，我试图安排一些名为“Assignatura”的任务。 我的表示是，如果我有 N 天，对于每一天我可以有两个任务，并且我使用单个数组来表示它。所以，在偶数位置上，这是当天的第一个任务，在奇数位置上，这是第二个任务。所以位置 0,1 代表第一天，2,3 代表第二天，依此类推。 限制是我每天至少需要一个Assignatura，尽量减少每天的一定数量，称为getPerjudicats。

这是我的代码：

package backtracking;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class SolucioCalendari {
    private int nDays, nAssignInADay;
    private boolean[] assignada;  // Track if an Assignatura has been assigned
    private Assignatura[] solucio;  // Current solution attempt
    private Assignatura[] millor_solucio;  // Best solution found so far
    private int millor_cost;  // Cost of the best solution
    private int assignades;  // Number of assigned Assignatura
    private int cost_actual;  // Current cost
    private Map<String, Integer> memoization;  // Cache for memoization

    public SolucioCalendari(int nDays, int nAssigInADay) {
        if (nDays * nAssigInADay < Assignatura.getPlaEstudis().length) {
            throw new IllegalArgumentException("El nombre d'assignatures es menor que nDays per nAssignInADay");
        }
        this.nDays = nDays;
        this.nAssignInADay = nAssigInADay;
        this.assignada = new boolean[Assignatura.getPlaEstudis().length];
        this.solucio = new Assignatura[nAssigInADay * nDays];
        this.millor_solucio = new Assignatura[nAssigInADay * nDays];
        this.millor_cost = Integer.MAX_VALUE;
        this.assignades = 0;
        this.cost_actual = 0;
        Arrays.fill(this.assignada, false);
    }

    public void start() {
        this.backMillorSolucio(0);
    }

    private void backMillorSolucio(int dia) {
        if (dia >= this.solucio.length) {
            if (assignades == Assignatura.getPlaEstudis().length && this.millor_cost > this.cost_actual) {
                this.millor_cost = this.cost_actual;
                this.millor_solucio = Arrays.copyOf(this.solucio, this.solucio.length);
            }
            return;
        }

        int remainingAssignatura = Assignatura.getPlaEstudis().length - assignades;
        int remainingSlots = this.solucio.length - dia;

        if (remainingAssignatura > remainingSlots) {
            return; //Cut off the recursion if impossible to assign all
        }

        //Try not assigning an Assignatura only if it does not leave insufficient slots
        if (remainingAssignatura < remainingSlots) {
            backMillorSolucio(dia + 1);
        }

        for (int i = 0; i < Assignatura.getPlaEstudis().length; i++) {
            if (!assignada[i]) {
                this.solucio[dia] = Assignatura.getPlaEstudis()[i];
                assignada[i] = true;
                assignades++;
                int previousCost = this.cost_actual;

                boolean validAssignment = true;
                int perjudicatsCost = 0;

                if (dia % 2 == 1 && this.solucio[dia - 1] != null) {
                    int codi_anterior = (this.solucio[dia - 1].getCodi() / 1000) % 10;
                    int codi_actual = (this.solucio[dia].getCodi() / 1000) % 10;
                    if (codi_anterior != codi_actual) {
                        perjudicatsCost = Assignatura.getPerjudicats(
                            Assignatura.assignatures.indexOf(this.solucio[dia - 1]),
                            Assignatura.assignatures.indexOf(this.solucio[dia])
                        );
                        this.cost_actual += perjudicatsCost;
                    } else {
                        validAssignment = false;
                    }
                }

                if (validAssignment) {
                    backMillorSolucio(dia + 1);
                }

                this.cost_actual = previousCost;
                assignada[i] = false;
                assignades--;
                this.solucio[dia] = null;
            }
        }
    }

    public int getMillorResultat() {
        return this.millor_cost;
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Assignatura assignatura : millor_solucio) {
            s.append(assignatura == null ? "null " : assignatura.toString()).append(" ");
        }
        return s.toString().trim();
    }

    public void printaSolActual() {
        for (Assignatura assignatura : solucio) {
            System.out.print(assignatura + " - ");
        }
        System.out.println();
    }
}

然而，对于实际情况来说，这时间太长了。有没有什么方法可以进一步优化这个？我尝试删除一些排列，仅在Assignatura中创建具有特定顺序的解决方案，删除坏分支......但这还不够。

谢谢

Answer 1

不确定我完全理解你的代码，因为它不是英文的，而且有些东西像

PlaEstudis

你没有解释。您的问题是一个称为约束编程的组合优化问题，它被称为 NP-Hard，因此输入越大，花费的时间就越长。

但是，考虑到您的限制（仅基于您的描述，因为代码太神秘），您可以执行以下操作：

假设您有天数

d

和任务数

n

，其中

2d >= n

。

1. 按成本（Perjudicats）对任务进行排序，成本最高的在前。

2. 从数组末尾开始，将每天的第一个任务（仅）分配给列表中的下一个任务。因此，第

   d-1

   日任务 1 获得成本最低的任务，第

   d-2

   日任务 1 获得次成本最低的任务，依此类推。在此步骤结束时，所有日子都将有 1 个任务，最后一天是成本最高的任务。

3. 剩余未分配的任务

   n-d

   ，从第 0 天开始分配每天的任务 2。最后，您将在最后几天只完成一项任务，但它们将是成本最高的任务。

除非我遗漏了什么，否则你应该在所有日子之间分配你的费用。