Wdrażanie przeszukiwania wstecznego z heurystyką?

Question

Zaczynam interesować się algorytmami wyszukiwania i programowaniem wstecznym. Na razie zaimplementowałem Algorithm X (zobacz mój drugi post tutaj: Determine conflict-free sets?), aby rozwiązać dokładny problem z okładką. Działa to bardzo dobrze, ale teraz jestem zainteresowany rozwiązaniem tego problemu z bardziej podstawowym wariantem backtrackingu. Po prostu nie mogę zrozumieć, jak można to zrobić. Opis problemu jest taki sam jak wcześniej:

Załóżmy, że masz kilka zestawów, podczas gdy każdy zestaw ma kilka podzbiorów.

Set1 = {(bananów, ananasów, pomarańczy), (jabłka, kapusta, ogórek) (cebula, czosnek)}

zestaw2 = {(banan, ogórek, czosnek), (awokado, pomidor)}

...

SetN = {...}

celem jest teraz wybrać jeden podzbiór z każdego zestawu, natomiast każdy podzbiór muszą być konflikt darmo z dowolnego innego wybranego podzbioru (jeden element jest nie zawarte w żadnym z pozostałych wybranych podzbiorów).

Jako przykład napisałem dwie klasy Javy, które. Zestawy są oznaczone pojedynczym znakiem, a elementy są zwykłymi liczbami.

I konkretnie mają dwa problemy:

• Jak iteracyjne nad wszystkie zbiory/podzbiory w taki sposób, że zastosowanie heurystyki jest możliwe (wyboru podzbioru z elementów obowiązkowych, minimalny koszt, ...)
• Jak konserwować wybrane zestawy + podzbiory i ich zawarte elementy.

Wszystkie inne przykłady, które mogę znaleźć, to Sudoku lub n-Queens i wszystkie używają stałych pętli for. Oprócz tego myślałem o raczej ogólnym podejściu, w którym funkcja "isPossiblePartialSolution" może być używana do sprawdzenia, czy wybrana ścieżka/zestaw może być w konflikcie z wcześniej wybranym podzbiorem/elementem.

Oto dwie klasy 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; 
} 

} 

i

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: Faktycznie brzmi to jak już wdrożone Dancing Links (używając nazwy "Algorytm X") , więc nie jestem pewien, o co prosisz. Przez "bardziej podstawowy wariant cofania" masz na myśli "wolniejszy wariant"? Taniec Links jest o tak podstawowe jak można dostać ....

ORIGINAL ODPOWIEDŹ: Gdybym robił to, bym spróbować zmniejszyć go do problemu dokładny pokrywy, które mogą być rozwiązane z Dancing Links. Np. Skonstruuj macierz zer i jedynek, znajdź podzbiór wierszy, tak aby w każdej kolumnie był dokładnie jeden 1, a następnie przekonwertuj ten zestaw wierszy z powrotem na odpowiedź na pierwotny problem.

Poniższa odpowiedź jest napisana w języku C++ (11), ale mam nadzieję, że możesz zobaczyć, jak przetłumaczyć ją na język Java. Implementacja Dancing Links w Javie jest pozostawiona jako ćwiczenie dla czytelnika i/lub wybranej przez ciebie wyszukiwarki.

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