我对搜索算法和回溯编程非常感兴趣。现在,我已经实现了算法X(参见我的另一篇文章:确定无冲突集?)来解决一个精确的掩体问题。这非常有效,但我现在有兴趣用更基本的回溯变体来解决这个问题。我只是不知道该怎么做。问题描述和前面一样:
假设你有一堆集合,而每个集合都有几个子集。
Set1 ={(香蕉、菠萝、橘子)、(苹果、甘蓝、黄瓜)、(洋葱、大蒜)}
Set2 ={(香蕉、黄瓜、大蒜)、(鳄梨、番茄)}
…
SetN ={…}
现在的目标是从每个集合中选择一个子集,而每个子集必须与任何其他选择的子集没有冲突(一个元素不包含在任何其他选择的子集中)。
作为一个例子,我编写了两个Java类。集合由单个字符标识,元素为纯数字。我特别有两个问题:
- 如何在所有集合/子集上迭代,使启发式的使用成为可能(选择具有最小元素,最小成本,…的子集)
- 如何维护选中的集合+子集及其包含的元素。
我能找到的所有其他例子都是数独或n-Queens,并且都使用固定的for循环。除此之外,我正在考虑一种相当通用的方法,其中一个函数"isPossiblePartialSolution"可以用来检查,如果选择的路径/集可能与先前选择的子集/元素冲突。
下面是两个Java类:
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Set> allSets = buildRandomTest();
for(Set r : allSets) {
System.out.print("Set with id: " + r.id + " is subset in collection: " + r.name + " and contains: ");
for(Integer n : r.listOfElements) {
System.out.print(" " + n + " ");
}
System.out.println();
}
}
public static int myRandomRange(int low, int high) {
return (int) (Math.random() * (++high - low) + low);
}
public static ArrayList<Set> buildRandomTest() {
ArrayList<Set> mySet = new ArrayList<Set>();
int numberOfSets = myRandomRange(10, 12);
for(int i=0; i<numberOfSets; i++) {
String nameOfSet = Character.toString((char) myRandomRange(65, 67));
Set tmp = new Set(nameOfSet, i);
ArrayList<Integer> listOfElements = new ArrayList<Integer>();
int elementsInList = myRandomRange(2, 4);
for(int j=0; j<elementsInList; j++) {
listOfElements.add(myRandomRange(1,30));
}
tmp.listOfElements = listOfElements;
mySet.add(tmp);
}
return mySet;
}
}
和
import java.util.ArrayList;
public class Set {
public String name;
public int id;
public ArrayList<Integer> listOfElements;
public Set(String name, int id) {
this.name = name;
this.id = id;
listOfElements = new ArrayList<Integer>();
}
}
EDIT:实际上这听起来像是你已经实现了跳舞链接(使用名称"算法X"),所以我不确定你在要求什么。你说的"更基本的回溯变体"是指"更慢的变体"吗?跳舞链接是最基本的,你可以得到....
原始答案:如果我这样做,我会试着把它减少到一个精确覆盖的问题,这可以用跳舞链接来解决。也就是说,构造一个0和1的矩阵,找到它的行子集,使得每列都有一个1,然后将该行集转换回原始问题的答案。
下面的答案是用c++(11)写的,但希望你能看到如何将其翻译成Java。在Java中实现跳舞链接留给读者和/或您选择的搜索引擎作为练习。
enum Element {
apple, avocado, banana, cucumber, garlic,
kale, onion, orange, pineapple, NUM_ELEMENTS
};
std::vector<std::vector<std::set<Element>>> sets = {
{ {banana, pineapple, orange}, {apple, kale, cucumber}, {onion, garlic} },
{ {banana, cucumber, garlic}, {avocado, tomato} },
...
};
int rows, columns;
// One row per subset, obviously...
rows = 0;
for (auto &vs : sets) {
rows += vs.size();
}
// ...plus N more rows for "vegetable X is not in any selected subset".
rows += NUM_ELEMENTS;
// One column per vegetable, obviously...
columns = NUM_ELEMENTS;
// ...plus N more columns for "we've chosen a subset from set X".
columns += sets.size();
Matrix M(rows, columns);
M.initialize_to_all_zeros();
int r = 0;
for (int i=0; i < sets.size(); ++i) {
for (int j=0; j < sets[i].size(); ++j) {
auto &subset = sets[i][j];
M[r][NUM_ELEMENTS + i] = 1; // the subset is a member of set i
for (Element veg : subset) {
M[r][veg] = 1; // the subset contains this element
}
++r;
}
}
for (Element veg = apple; veg < NUM_ELEMENTS; ++veg) {
M[r][veg] = 1;
++r;
}
// Now perform Dancing Links on the matrix to compute an exact cover.
std::set<int> row_indices = dancing_links(M);
// Now print out the subsets.
r = 0;
for (int i=0; i < sets.size(); ++i) {
for (int j=0; j < sets[i].size(); ++j) {
if (row_indices.find(r) != row_indices.end()) {
print_set(sets[i][j]);
}
++r;
}
}
// And print the unused vegetables, just for kicks.
for (Element veg = apple; veg < NUM_ELEMENTS; ++veg) {
if (row_indices.find(r) != row_indices.end()) {
std::cout << "Vegetable " << veg << " was not mentioned above.n";
}
++r;
}