Sezgisel bir backtrack araması mı uyguluyorsunuz?

Question

Arama algoritmaları ve backtrack programlama ile oldukça ilgileniyorum. Şimdilik, tam bir kapak problemini çözmek için Algorithm X'i (diğer yazıma bakın: Determine conflict-free sets?) uyguladım. Bu çok iyi çalışıyor, ancak şimdi bunun daha temel bir geri izleme çeşidi ile çözülmesini istiyorum. Bunun nasıl yapılacağını anlayamıyorum. Sorun açıklaması, öncekiyle aynıdır:

Bir grup kümeniz varsayalım, bununla birlikte her kümenin birkaç altkümesi vardır.

Ayar 1 = {(muz, ananas, portakal), (elma, lahana, salatalık), (soğan, sarımsak)}

Set 2 = {(muz, salatalık, sarımsak), (avokado, domates)}

...

SetN = {...}

her alt küme başka seçilmiş alt kümesiyle çatışma özgür olmalıdır oysa Şimdi hedef, her setten birer alt kümesini seçmektir (bir unsurdur

seçilen diğer alt kümelerin hiçbirinde bulunmaz). Örneğin, iki Java sınıfı yazdım. Setler tek bir karakterle tanımlanır ve öğeler düz sayılardır.

Ben özellikle iki sorun var:

• tüm setleri üzerinde yineleme nasıl/bulgulara dayalı bir yöntemle kullanılması mümkün olduğunu şekilde alt kümeleri (asgari unsurları, minimum maliyet ile alt küme seçin ...)
• Seçilen kümeler + alt kümeler ve içerdikleri öğeler nasıl korunur.

Bulabildiğim diğer örnekler ya Sudoku ya da n-Queens'tir ve hepsi sabit döngüler kullanmaktadır. Buna ek olarak, seçilen bir yol/setin önceden seçilmiş bir alt set/öğe ile çakışması halinde, kontrol etmek için "isPossiblePartialSolution" işlevinin kullanılabileceği oldukça genel bir yaklaşım düşünmekteydim. İşte

iki Java sınıfları şunlardır:

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

} 

ve

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

DÜZENLEME: Zaten (adı "Algoritma X" kullanarak) Dans Linkler uyguladık gibi Aslında bu sesler , o yüzden ne istediğini bilmiyorum. "Backtracking'in daha temel bir versiyonu" ile "daha yavaş bir varyant" mı demek istiyorsun? Bağlantılar Dans alabileceğiniz gibi yaklaşık olarak basit ....

ORİJİNAL CEVAP: bunu yaparken olsaydı, ben Dancing Links ile çözülebilir Bir Tam kapak sorunu, bunu azaltmak için çalışacaktı. Örneğin, 0 ve 1 sn'lik bir matris oluşturarak, her sütunda tam olarak 1 tane olacak şekilde satırlarının bir alt kümesini bulun ve sonra bu satır kümesini orijinal sorununuza bir yanıt olarak geri dönüştürün.

Aşağıdaki cevap C++ (11) ile yazılmıştır, ancak umarım bunu Java'ya nasıl çevireceğinizi görebilirsiniz. Java'daki Dans Linklerini uygulama, okuyucu ve/veya seçtiğiniz arama motorunuz için bir egzersiz olarak bırakılmıştır.

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