हेरिस्टिक के साथ बैकट्रैक खोज को कार्यान्वित करना?

Question

मुझे खोज एल्गोरिदम और बैकट्रैक प्रोग्रामिंग में काफी रुचि हो रही है। अभी के लिए, मैंने एक सटीक कवर समस्या को हल करने के लिए एल्गोरिदम एक्स लागू किया है (मेरी अन्य पोस्ट यहां देखें: Determine conflict-free sets?)। यह बहुत अच्छी तरह से काम करता है लेकिन अब मैं बैकट्रैकिंग के एक और बुनियादी संस्करण के साथ इसे हल करने में रुचि रखता हूं। मैं सिर्फ यह नहीं समझ सकता कि यह कैसे किया जा सकता है। समस्या का वर्णन पहले जैसा ही है:

मान लें कि आपके पास सेट का एक गुच्छा है, जबकि प्रत्येक सेट में कुछ सबसेट हैं।

SET1 = {(केला, अनानास, नारंगी), (सेब, गोभी, खीरा), (प्याज, लहसुन)}

SET2 = {(केला, ककड़ी, लहसुन), (एवोकैडो, टमाटर)}

...

SetN = {...}

लक्ष्य अब, प्रत्येक सेट से एक उपसमूह चुनने के लिए है, जबकि प्रत्येक सबसेट किसी अन्य चयनित सबसेट के साथ संघर्ष मुक्त होना चाहिए (एक तत्व है किसी अन्य चुने हुए सबसेट में शामिल नहीं है)।

उदाहरण के तौर पर, मैंने दो जावा कक्षाएं लिखीं। सेट एक वर्ण द्वारा पहचाने जाते हैं और तत्व सादे संख्याएं हैं।

मैं विशेष रूप से दो समस्याएं हैं:

• सभी सेट पर पुनरावृति कैसे/इस तरह से है कि एक अनुमानी के उपयोग संभव है में सबसेट (न्यूनतम तत्वों, कम से कम लागत के साथ सबसेट चुनें, ...)
• चयनित सेट + सबसेट और उनके निहित तत्वों को कैसे बनाए रखें।

अन्य सभी उदाहरण जो मैं पा सकते हैं वे हैं सुडोकू या एन-क्वींस और सभी फिक्स्ड फॉर-लूप का उपयोग कर रहे हैं। इसके अलावा, मैं एक सामान्य दृष्टिकोण के बारे में सोच रहा था जहां एक चुना गया पथ/सेट पहले चुने गए सबसेट/तत्व के साथ संघर्ष में हो सकता है, तो एक कार्य "isPossiblePartialSolution" का उपयोग करने के लिए किया जा सकता है।

यहाँ दो जावा वर्गों हैं:

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

संपादित करें: असल में यह लग रहा है आप पहले से ही नृत्य लिंक को क्रियान्वित किया है की तरह (नाम "एल्गोरिथ्म एक्स" का प्रयोग करके) , इसलिए मुझे यकीन नहीं है कि आप क्या पूछ रहे हैं। "बैकट्रैकिंग का एक और मूल संस्करण" से, क्या आपका मतलब "धीमा संस्करण" है? नृत्य लिंक के बारे में के रूप में बुनियादी रूप में आप प्राप्त कर सकते हैं ....

मूल जवाब: यदि मैं यह कर रहे थे, मैं एक सटीक कवर समस्या है, जो Dancing Links साथ हल किया जा सकता करने के लिए इसे कम करने की कोशिश होगी। यानी, 0s और 1s के मैट्रिक्स का निर्माण करें, इसकी पंक्तियों का एक सबसेट ढूंढें जैसे कि प्रत्येक कॉलम में बिल्कुल एक 1 है, और उसके बाद उस पंक्ति-सेट को अपनी मूल समस्या के उत्तर में परिवर्तित करें।

निम्नलिखित उत्तर C++ (11) में लिखा गया है, लेकिन उम्मीद है कि आप जावा में इसका अनुवाद कैसे कर सकते हैं। जावा में नृत्य लिंक लागू करना पाठक और/या पसंद के आपके खोज इंजन के लिए एक अभ्यास के रूप में छोड़ा गया है।

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