？

Question

私は検索アルゴリズムとバックトラックプログラミングにかなり興味を持っています。今のところ、正確なカバーの問題を解決するために、アルゴリズムX（私の他の投稿：Determine conflict-free sets?を参照）を実装しました。これは非常にうまくいくが、私は今、バックトラックのより基本的な変種でこれを解決することに興味がある。私はこれをどうやって行うことができないのか分かりません。問題の説明は前と同じです：

あなたは一組の束を持っているとしますが、各組にはいくつかの部分集合があります。

セット1 = {（バナナ、パイナップル、オレンジ）、（リンゴ、ケール、キュウリ）、（タマネギ、ニンニク）}

SET2 = {（バナナ、キュウリ、ニンニク）、（アボカド、トマト）}各サブセットは、競合他の選択されたサブセットとの自由でなければならないのに対し

... = {...}

目標

SETNは現在（各セットからの1つのサブセットを選択するために、1つの要素であります他の選択されたサブセットのいずれにも含まれない）。

例として、私は2つのJavaクラスを書いています。セットは単一の文字で識別され、要素はプレーン・ナンバーです。

私は特に二つの問題があります（最小の要素、最小のコスト、...とのサブセットを選択）ヒューリスティックの使用が可能であるように、全てのセット/サブセットを反復処理する方法

• を
• 選択したセット+サブセットとその含まれた要素を維持する方法。

私が見つけることができる他のすべての例は、数独またはn-Queensであり、すべて固定ループを使用しています。それに加えて、私は、選択されたパス/セットが前に選択されたサブセット/要素と矛盾している可能性があるかどうかをチェックするために、関数 "isPossiblePartialSolution"を使用することができる、かなり一般的なアプローチについて考えていました。ここで

は、2つの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>(); 
} 

} 

Answer 1

EDIT：あなたはすでに（名称 "アルゴリズムX" を使用して）ダンスリンクを実装しましたように実際にそれが聞こえますあなたが何を求めているのか分かりません。 「バックトラッキングのより基本的な変種」とは、「より遅い変種」を意味しますか？リンクを踊ることはあなたが得ることができると同じくらい基本的なものです....

ORIGINAL ANSWER：私はこれをやっていたならば、私はDancing Linksで解決することができ、正確なカバーの問題、それを減らすために試してみました。つまり、0と1の行列を作成し、その列のサブセットを見つけ、それぞれの列に1つの1が存在するようにしてから、その行セットを元の問題の答えに変換し直します。

次の回答はC++（11）で書かれていますが、うまくいけばJavaに変換する方法がわかります。 Javaでダンスリンクを実装することは、リーダーや検索エンジンの選択肢として練習問題として残されています。

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