arrays - 所有非重叠组

Question

我正在尝试从嵌套数组中提取所有可能的非重叠组以生成最少数量的组

{
  0:  4, 5, 6
  1:  4, 5
  2:  3, 4 ,9
  3:  8, 9
  4:  8,10,11
  5:  8,10,11
}

从 0 到 5，这是最好的结果:

1. [ [4,4,4],[8,8,8] ]
2. [ [5,5],[9,9],[10,10] ]
3. [ [5,5],[9,9],[11,11] ]

1 是更好的组，因为它只有两组。

我知道如何在多个循环中执行此操作，但有什么方法可以一次完成此操作吗？感觉可能是寻路问题，但不确定如何将其转化为寻路问题。

---

解决方案

我只用了 19 个周期就根据下面 libik 的答案(使用 JS)设计了一个方法!

function bestPath(){
    var array = [[4,5,6],[4,5],[3,4,9],[8,9],[8,10,11],[8,10,11]],
        arrayOfIndexes = (function (){
            var arr = [];
            for (var k=0; k < array.length; k++){
                arr.push({
                    index: array[k].length-1,
                    last_split: 0
                })
            }
            //dummy index, needed for jumping back
            arr.push({index:0, last_split:0});  

            return arr;
        })();


    // This function clones the current working path
    // up to a specific index (which we then use to 
    // rebuild upon by taking another route)
    var cloneTill = function(array, till){
        var new_arr = [];
        for (var l=0; l < till; l++)
            new_arr.push( array[l] );
        return new_arr;
    };

    var numset = 0,             // running counter of num. sets in working path
        bestset = 99999;

    var path_list = [],       // array of all paths
        best_path = null,     //
        temppath = [];        // current working path

    var row = 0,
        min_stretch_len = 2; // minimum length heuristic

    while (true){
        var color_index = arrayOfIndexes[row];
        console.log("path="+temppath);

var jumpBack = false;

        if (row === 0){
            if (color_index.index < 0) break;                   //No more paths to explore after jumping back.
            numset = 0;
        }

        if (row === array.length){

            if (numset < bestset){
                bestset = numset;
                best_path = temppath;
            }
            path_list.push ( temppath );

            jumpBack = true;
        }

        if (color_index.index < 0) jumpBack = true;


        if (jumpBack){
//          console.log( ">>jumprow:"+row+"-->"+color_index.last_split
//                        +", index to:"+(arrayOfIndexes[color_index.last_split].index - 1)+'\n');

            // jump back to last split  
            row = color_index.last_split;
            temppath = cloneTill(temppath, row);

            arrayOfIndexes[row].index--;        
            continue;
        }

        //We have an unexplored color
        var color = array[row][color_index.index];
//          console.log("    trying color='"+color+"'");


        //Perform lookahead
        var stretch = row;
        while ( stretch < array.length  && array[stretch].indexOf(color)!== -1){
            temppath.push(color);
            stretch ++;
        }
        stretch -= row;

        // Unsuccessful
        if (stretch < min_stretch_len){
//          console.log("    failed (too short)");
            while(stretch --> 0) temppath.pop();    // clear changes

            arrayOfIndexes[row].index--;            // next attempt at this row will try a different index          
            continue;
        }

        // Successfully found a new color. Splitting
//      console.log("    worked, arrayOfIndexes["+(row+stretch)+"].last_split = "+row);
        arrayOfIndexes[row+stretch].last_split = row; // this row is where we split

        row += stretch;
        numset ++;
    }   
    console.log("sols", path_list);
    console.log("best path=", best_path);
}

Answer 1

我认为在 O(n) 时间内是不可能的(见评论)。

但是，您可以通过回溯解决此问题、记住最佳解决方案并“剪切”您知道无法比找到的最佳解决方案更好的解决方案来节省一些时间。

---

这是带切割的回溯解决方案

import java.util.LinkedList;

public class JavaApplication12 {

    public static void main(String[] args) {
        int[][] array = {{4, 5, 6}, {4, 5}, {3, 4, 9}, {8, 9}, {8, 10, 11}, {8, 10, 11}};
        int[] arrayOfIndexes = new int[array.length];

        LinkedList<Integer> solution = new LinkedList<>();
        boolean end = false;

        int valueOfSolution = 1;
        int bestValueOfSolution = Integer.MAX_VALUE;
        LinkedList<Integer> bestSolution = new LinkedList<>();

        int row = 1;        

        while (end == false) {
            if (row == array.length) {
                if (bestValueOfSolution > valueOfSolution) {
                    bestValueOfSolution = valueOfSolution;
                    bestSolution = (LinkedList<Integer>) solution.clone();
                }
                row++;
            } else {
                if (row > array.length) {
                    row = array.length - 1;
                }

                if (arrayOfIndexes[0] == array[0].length) {
                    end = true;
                } else if (array[row].length == arrayOfIndexes[row] || solution.size() > row || valueOfSolution >= bestValueOfSolution ) {
                    if (valueOfSolution >= bestValueOfSolution && !(array[row].length == arrayOfIndexes[row] || solution.size() > row)){
                        System.out.println("Cutting");
                    }

                    boolean decreaseRow = true;
                    if (solution.size() > row) {
                        decreaseRow = false;
                    }

                    int lastNumber = solution.removeLast();

                    if (solution.isEmpty() || solution.getLast().equals(lastNumber) == false) {
                        valueOfSolution--;
                    }

                    if (decreaseRow) {
                        arrayOfIndexes[row] = -0;
                        row--;
                    }
                } else {
                    if (!solution.isEmpty() && array[row][arrayOfIndexes[row]] != solution.getLast()) {
                        valueOfSolution++;
                    }

                    if (solution.isEmpty()){
                        valueOfSolution = 1;
                    }

                    solution.add(array[row][arrayOfIndexes[row]]);
                    arrayOfIndexes[row]++;
                    row++;
                }
            }
        }

        System.out.println("Best solution is: " + bestSolution);
        System.out.println("It has value of: " + bestValueOfSolution);
    }
}

这个例子的输出是

Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Cutting
Best solution is: [4, 4, 4, 8, 8, 8]
It has value of: 2

---

我添加了一个“numberOfSteps”变量来计算 whyle 循环被调用的次数。

通过切割我得到了

Number of steps:62

没有切割!!

Number of steps:1314

---

切割由条件 valueOfSolution >= bestValueOfSolution 提供。我们正在寻找最小的数字，对吗？因此，当我们通过添加每一行的数字来构建解决方案时，如果我们已经有了相同或更高的分数，无论我们添加什么数字，我们都不能做得更好，所以我们可以跳过这个。

---

如果您不知道回溯是什么，这是一个很好的 gif 动图，展示了数独是如何完成的:http://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Sudoku_solved_by_bactracking。 gif/220px-Sudoku_solved_by_bactracking.gif

它只是尝试添加数字，当它无法继续时(因为添加任何数字都会违反数独规则)它会返回并尝试另一个数字。