Thực hiện tìm kiếm quay lại bằng heuristic?

Question

Tôi nhận được khá quan tâm đến các thuật toán tìm kiếm và lập trình quay vòng. Bây giờ, tôi đã thực hiện thuật toán X (xem bài viết khác của tôi ở đây: Determine conflict-free sets?) để giải quyết một vấn đề chính xác bao gồm. Điều này hoạt động rất tốt nhưng bây giờ tôi quan tâm đến việc giải quyết vấn đề này với một biến thể cơ bản hơn của tính năng backtracking. Tôi chỉ không thể hiểu được làm thế nào điều này có thể được thực hiện. Mô tả sự cố giống như trước:

Giả sử bạn có một nhóm bộ, trong khi mỗi bộ có một vài tập con.

set1 = {(chuối, dứa, cam), (táo, cải xoăn, dưa chuột), (hành tây, tỏi)}

set2 = {(chuối, dưa chuột, tỏi), (bơ, cà chua)}

...

SetN = {...}

mục tiêu bây giờ là chọn một tập hợp con từ mỗi bộ, trong khi mỗi tập con phải mâu thuẫn miễn phí với bất kỳ tập con chọn khác (một phần tử là không chứa trong bất kỳ tập con nào đã chọn).

Ví dụ, tôi đã viết hai lớp Java. Các bộ được xác định bởi một ký tự đơn và các phần tử là số đơn giản.

Tôi đặc biệt có hai vấn đề:

• Làm thế nào để lặp qua tất cả các bộ/tập con theo cách như vậy mà việc sử dụng một heuristic là có thể (chọn tập con với các yếu tố tối thiểu, chi phí tối thiểu, ...)
• Cách duy trì các tập hợp con đã chọn + tập hợp con và các phần tử được chứa của chúng.

Tất cả các ví dụ khác tôi có thể tìm thấy là Sudoku hoặc n-Queens và tất cả đều sử dụng các vòng lặp cố định. Thêm vào đó, tôi đã suy nghĩ về một cách tiếp cận khá chung chung, trong đó một hàm "isPossiblePartialSolution" có thể được sử dụng để kiểm tra, nếu một path/set đã chọn có thể xung đột với một tập con/phần tử đã được chọn trước đó.

Dưới đây là hai lớp 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; 
} 

} 

và

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: Trên thực tế nó có vẻ như bạn đã thực hiện Liên kết Dancing (sử dụng cái tên "Algorithm X") , vì vậy tôi không chắc chắn những gì bạn đang yêu cầu. Bởi "một biến thể cơ bản hơn của backtracking", bạn có nghĩa là "một biến thể chậm hơn"? Liên kết khiêu vũ về cơ bản như bạn có thể nhận được ....

ORIGINAL TRẢ LỜI: Nếu tôi làm điều này, tôi sẽ cố gắng giảm nó thành vấn đề chính xác, có thể được giải quyết với Dancing Links. Tức là, xây dựng một ma trận 0 và 1, tìm một tập con của các hàng của nó sao cho có chính xác 1 trong mỗi cột và sau đó chuyển đổi hàng đó thành câu trả lời cho vấn đề ban đầu của bạn.

Câu trả lời sau được viết bằng C++ (11), nhưng hy vọng bạn có thể xem cách dịch nó sang Java. Thực hiện các liên kết Dancing trong Java được để lại như một bài tập cho người đọc và/hoặc công cụ tìm kiếm bạn chọn.

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