Implementing backtrack search with heuristics?

Question

I am very interested in search algorithms and return path programming. At the moment, I have performed Algorithm X (see My other post here: Define sets without conflicts? ) To solve the problem with the exact shell. This works very well, but now I'm interested in solving this problem with a more basic retreat option. I just can't figure out how to do this. The problem description is the same as before:

Suppose you have many sets, while each set has several subsets.

Set1 = {(banana, pineapple, orange), (apple, cabbage, cucumber), (onion, garlic)}

Set2 = {(banana, cucumber, garlic), (avocado, tomato)}

...

SetN = {...}

Now you need to select one subset from each set, while each subset must be in conflict with any other selected subset (one element is not contained in any of the other selected subsets).

As an example, I wrote two Java classes. Sets are identified by a single character, and elements are prime numbers.

I have two problems:

• How to iterate over all sets / subsets in such a way that heuristics can be used (select a subset with minimal elements, minimum cost, ...)
• How to save selected sets + subsets and their contained elements.

All other examples I can find are Sudoku or n-Queens, and they all use fixed for-loops. In addition to this, I was thinking of a fairly general approach where the "isPossiblePartialSolution" function can be used to check if the selected path / set may contradict a previously selected subset / element.

Here are two Java classes:

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; } } 

and

 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>(); } } 

Answer 1

EDIT: Actually, it sounds like you already implemented Dancing Links (using the name "Algorithm X"), so I'm not sure what you are asking. By “more basic backtracking option” do you mean “slower option”? "Dance links" are about as important as you can get ....

ORIGINAL ANSWER: If I did this, I would try to reduce it to a problem with the exact shell, which can be solved using Dancing Links . Ie, we will build a matrix of 0s and 1s, we will find a subset of our rows, so that in each column there will be exactly one 1, and then we will transform this set of rows back in response to your original problem.

The following answer is written in C ++ (11), but hopefully you can see how to translate it into Java. Implementing Dancing Links in Java remains an exercise for the reader and / or your search engine.

 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; }