使用启发式算法实现回溯搜索？

Question

使用启发式算法实现回溯搜索？

7

我对搜索算法和回溯编程非常感兴趣。目前，我已经实现了Algorithm X（请参见我在此处的其他帖子：确定无冲突集合？），以解决精确覆盖问题。这很有效，但我现在更想用一种更基本的回溯变体来解决这个问题。我只是想不出如何实现。问题描述与之前相同：

假设您有一堆集合，每个集合都有几个子集。

Set1 = {（香蕉，菠萝，橙子），（苹果，羽衣甘蓝，黄瓜），（洋葱，大蒜）}

Set2 = {（香蕉，黄瓜，大蒜），（鳄梨，番茄）}

...

SetN = {...}

现在的目标是从每个集合中选择一个子集，而每个子集必须与任何其他选定的子集冲突。也就是说，一个元素不能包含在其他已选择的子集中。

例如，我编写了两个Java类。集合由单个字符标识，元素为纯数字。

我具体有两个问题：

1. 如何以这样的方式迭代所有集合/子集，以便使用启发式方法（选择具有最小元素、最小成本等）？

2. 如何维护已选择的集合/子集及其包含的元素。

我能找到的所有其他示例都是数独或n皇后，并且都使用固定的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>();
}

}

- user26372

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Quuxplusone · Accepted Answer

编辑：实际上听起来你已经实现了Dancing Links算法（使用“Algorithm X”这个名字），所以我不确定你在问什么。当你说“更基本的回溯变体”时，是指“更慢的变体”吗？Dancing Links已经是最基本的了....

原始答案：如果我要做这件事，我会尝试将其简化为一个精确覆盖问题，这可以通过Dancing Links来解决。也就是说，构造一个由0和1组成的矩阵，找到它的一个子集，使得每列恰好有一个1，然后将该行集转换回原始问题的答案。

以下答案用C++（11）编写，但希望你能看到如何将其翻译成Java。在Java中实现Dancing Links留给读者和/或您选择的搜索引擎作为练习。

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