实施启发式回溯搜索? [英] Implementing a backtrack search with heuristic?

问题描述

我对搜索算法和回溯编程非常感兴趣.目前，我已经实现了算法X(请参见我的其他文章:确定无冲突集吗?)来解决确切的覆盖问题.效果很好，但我现在有兴趣通过更基本的回溯方式解决此问题.我只是不知道如何做到这一点.问题描述与以前相同:

I'm getting quite interested in search algorithms and backtrack programming. For now, I have implemented Algorithm X (see my other post here: Determine conflict-free sets? ) to solve an exact cover problem. This works very well but I'm now interested in solving this with a more basic variant of backtracking. I just can't figure out how this can be done. The problem description is the same as before:

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

Suppose you have a bunch of sets, whereas each set has a couple of subsets.

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

Set1 = { (banana, pineapple, orange), (apple, kale, cucumber), (onion, garlic) }

Set2 = {(香蕉，黄瓜，大蒜，鳄梨，番茄)}

Set2 = { (banana, cucumber, garlic), (avocado, tomato) }

...

SetN = {...}

SetN = { ... }

现在的目标是从每个集合中选择一个子集，而每个子集必须与任何其他选定的子集无冲突(一个元素不包含在任何其他选定的子集中).

The goal now is to select one subset from each set, whereas each subset must be conflict free with any other selected subset (one element is not contained in any of the other chosen subsets).

作为示例，我编写了两个Java类.这些集合由单个字符标识，元素为纯数字.

As an example, I wrote two Java classes that. The sets are identified by a single character and the elements are plain numbers.

我特别有两个问题:

• 如何以可能使用启发式的方式遍历所有集合/子集(选择具有最少元素，最小代价的子集……)
• 如何维护选定的集合+子集及其包含的元素.

我可以找到的所有其他示例都是Sudoku或n-Queens，并且都使用固定的for循环.除此之外，我还在考虑一种比较通用的方法，其中可以使用函数"isPossiblePartialSolution"来检查所选择的路径/集合是否可能与先前选择的子集/元素冲突.

All other examples I can find are either Sudoku or n-Queens and are all using fixed for-loops. In addition to that, I was thinking about a rather general approach where a function "isPossiblePartialSolution" may be used to check, if a chosen path/set may be in conflict with a previously chosen subset/element.

这是两个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>();
}

}

推荐答案

实际上，听起来您已经实现了跳舞链接"(使用名称"Algorithm X")，所以我我不确定您要的是什么.所谓回溯的更基本的变体"，您是说较慢的变体"吗?跳舞链接是您所能获得的基本知识....

Actually it sounds like you've already implemented Dancing Links (using the name "Algorithm X"), so I'm not sure what you're asking for. By "a more basic variant of backtracking", do you mean "a slower variant"? Dancing Links is about as basic as you can get....

原始答案::如果我这样做，我会尝试将其减少为精确覆盖的问题，可以通过

ORIGINAL ANSWER: If I were doing this, I'd try to reduce it to an exact-cover problem, which could be solved with Dancing Links. I.e., construct a matrix of 0s and 1s, find a subset of its rows such that there is exactly one 1 in each column, and then convert that row-set back into an answer to your original problem.

以下答案是用C ++(11)编写的，但希望您能看到如何将其转换为Java.留给读者和/或您选择的搜索引擎的练习是用Java来实现跳舞链接的.

The following answer is written in C++(11), but hopefully you can see how to translate it to Java. Implementing Dancing Links in Java is left as an exercise for the reader and/or your search engine of choice.

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

这篇关于实施启发式回溯搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！