所有非重叠组
All non-overlapping groups
我正在尝试从嵌套数组中提取所有可能的非重叠组以生成最少数量的组
{
0: 4, 5, 6
1: 4, 5
2: 3, 4 ,9
3: 8, 9
4: 8,10,11
5: 8,10,11
}
从 0 到 5,以下是可能的最佳结果:
- [[4,4,4],[8,8,8]]
- [[5,5],[9,9],[10,10]]
- [[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);
}
我认为在 O(n) 时间内是不可能的(见评论)。
但是,您可以通过回溯解决此问题,记住最佳解决方案和 "cut" 您知道无法比找到的最佳解决方案更好的解决方案来节省一些时间。
这是带切割的回溯解法
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
它只是尝试添加数字,当它无法继续时(因为添加任何数字都会违反数独规则)它 returns 并尝试另一个数字。
我正在尝试从嵌套数组中提取所有可能的非重叠组以生成最少数量的组
{
0: 4, 5, 6
1: 4, 5
2: 3, 4 ,9
3: 8, 9
4: 8,10,11
5: 8,10,11
}
从 0 到 5,以下是可能的最佳结果:
- [[4,4,4],[8,8,8]]
- [[5,5],[9,9],[10,10]]
- [[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);
}
我认为在 O(n) 时间内是不可能的(见评论)。
但是,您可以通过回溯解决此问题,记住最佳解决方案和 "cut" 您知道无法比找到的最佳解决方案更好的解决方案来节省一些时间。
这是带切割的回溯解法
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
它只是尝试添加数字,当它无法继续时(因为添加任何数字都会违反数独规则)它 returns 并尝试另一个数字。