java - ヒューリスティックでバックトラック検索を実装していますか?

Question

検索アルゴリズムとバックトラック プログラミングにかなり興味を持っています。今のところ、正確なカバー問題を解決するためにアルゴリズム X を実装しました (こちらの他の投稿を参照してください:競合のないセットを決定しますか? )。これは非常にうまく機能しますが、バックトラッキングのより基本的なバリアントでこれを解決することに興味があります。どうすればこれができるのかわかりません。問題の説明は以前と同じです。

セットの束があり、各セットにはいくつかのサブセットがあるとします。

Set1 = { (バナナ、パイナップル、オレンジ)、(リンゴ、ケール、キュウリ)、(タマネギ、ニンニク) }

Set2 = { (バナナ、きゅうり、にんにく)、(アボカド、トマト) }

...

SetN = { ... }

ここでの目標は、各セットから 1 つのサブセットを選択することですが、各サブセットは他の選択されたサブセットと競合しないようにする必要があります (1 つの要素が他の選択されたサブセットのいずれにも含まれていません)。

例として、2 つの Java クラスを作成しました。セットは 1 文字で識別され、要素は単純な数値です。

具体的には次の 2 つの問題があります。

• ヒューリスティックを使用できるようにすべてのセット/サブセットを反復処理する方法 (最小要素、最小コストなどのサブセットを選択)
• 選択したセットとサブセット、およびそれらに含まれる要素を維持する方法。

私が見つけることができる他のすべての例は、数独または n-Queens のいずれかであり、すべて固定 for ループを使用しています。それに加えて、選択したパス/セットが以前に選択したサブセット/要素と競合する可能性があるかどうかを確認するために、関数「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>();
}

}