用启发式实现回溯搜索？
我对搜索算法和回溯编程非常感兴趣。 现在，我已经实现了算法X（请参阅我的其他post： 确定无冲突集？ ）来解决确切的覆盖问题。 这非常有效，但我现在有兴趣用更基本的回溯变体来解决这个问题。 我无法弄清楚如何做到这一点。 问题描述与以前相同：
假设你有一堆集合，而每个集合都有几个子集。
Set1 = {（香蕉，菠萝，橙子），（苹果，羽衣甘蓝，黄瓜），（洋葱，大蒜）}
Set2 = {（香蕉，黄瓜，大蒜），（鳄梨，番茄）}
…
SetN = {…}
现在的目标是从每个集合中选择一个子集，而每个子集必须与任何其他所选子集无冲突（一个元素不包含在任何其他所选子集中）。
作为一个例子，我写了两个Java类。 集合由单个字符标识，元素是普通数字。
我特别有两个问题：
- 如何迭代所有集合/子集，以便可以使用启发式（选择具有最小元素，最低成本的子集……）
- 如何维护选定的集+子集及其包含的元素。
我能找到的所有其他例子都是Sudoku或n-Queens，并且都使用固定的for循环。 除此之外，我正在考虑一种相当普遍的方法，其中如果所选择的路径/集合可能与先前选择的子集/元素冲突，则可以使用函数“isPossiblePartialSolution”来检查。
以下是两个Java类：
import java.util.ArrayList; public class Main { public static void main(String[] args) { ArrayList 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 buildRandomTest() { ArrayList mySet = new ArrayList(); 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 listOfElements = new ArrayList(); 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 listOfElements; public Set(String name, int id) { this.name = name; this.id = id; listOfElements = new ArrayList(); } }
编辑：实际上听起来你已经实现了Dancing Links（使用名称“算法X”），所以我不确定你要求的是什么。 通过“回溯的一个更基本的变体”，你的意思是“一个较慢的变种”？ Dancing Links就像你能得到的一样基本……
原始答案：如果我这样做，我会尝试将其缩小为精确覆盖问题，可以通过Dancing Links解决。 即，构造一个0和1的矩阵，找到其行的子集，使每列中只有一个1，然后将该行集转换回原始问题的答案。
以下答案是用C ++（11）编写的，但希望您能看到如何将其转换为Java。 在Java中实现Dancing Links可以作为读者和/或您选择的搜索引擎的练习。
enum Element { apple, avocado, banana, cucumber, garlic, kale, onion, orange, pineapple, NUM_ELEMENTS }; std::vector>> 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 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; }