使用啓發式實現回溯搜索？

Question

我對搜索算法和回溯編程頗感興趣。現在，我已經實現了算法X（請參閱我的其他帖子：Determine conflict-free sets?）來解決精確的覆蓋問題。這工作得很好，但我現在有興趣用一個更基本的回溯方法來解決這個問題。我無法弄清楚如何做到這一點。問題描述與以前相同：

假設您有一堆集合，而每個集合都有幾個子集。

SET1 = {（香蕉，菠蘿，橙），（蘋果，羽衣甘藍，黃瓜），（洋蔥，大蒜）}

SET2 = {（香蕉，黃瓜，大蒜），（鱷梨，番茄）}

...

SETN = {...}

現在的目標是選擇來自每個組的一個子集，而每一子集必須無衝突與任何其他選擇的子集（一種元素是不包含在任何其他選擇的子集中）。

作爲一個例子，我寫了兩個Java類。這些集合由單個字符標識，元素是純數字。

我專門有兩個問題：

• 如何遍歷所有集合/以這樣的方式，使用啓發式是可能的子集（選擇以最小的元素，最低的成本集，...）
• 如何維護選定的集合+子集及其包含的元素。

我可以找到的所有其他示例是Sudoku或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>(); 
} 

} 

Answer 1

編輯：其實這聽起來像你已經實現舞蹈鏈（使用名稱 「算法X」） ，所以我不確定你在問什麼。通過「回溯的一個更基本的變體」，你的意思是「一個更慢的變體」？舞蹈鏈大約是基本的，你可以得到....

原來的答案：如果我這樣做，我會嘗試將其降低到一個確切的覆蓋問題，這可能與Dancing Links來解決。即，構造一個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; 
}