Tag: np

用启发式实现回溯搜索？

我对搜索算法和回溯编程非常感兴趣。 现在，我已经实现了算法X（请参阅我的其他post： 确定无冲突集？ ）来解决确切的覆盖问题。 这非常有效，但我现在有兴趣用更基本的回溯变体来解决这个问题。 我无法弄清楚如何做到这一点。 问题描述与以前相同： 假设你有一堆集合，而每个集合都有几个子集。 Set1 = {（香蕉，菠萝，橙子），（苹果，羽衣甘蓝，黄瓜），（洋葱，大蒜）} Set2 = {（香蕉，黄瓜，大蒜），（鳄梨，番茄）} … SetN = {…} 现在的目标是从每个集合中选择一个子集，而每个子集必须与任何其他所选子集无冲突（一个元素不包含在任何其他所选子集中）。 作为一个例子，我写了两个Java类。 集合由单个字符标识，元素是普通数字。 我特别有两个问题： 如何迭代所有集合/子集，以便可以使用启发式（选择具有最小元素，最低成本的子集……） 如何维护选定的集+子集及其包含的元素。 我能找到的所有其他例子都是Sudoku或n-Queens，并且都使用固定的for循环。 除此之外，我正在考虑一种相当普遍的方法，其中如果所选择的路径/集合可能与先前选择的子集/元素冲突，则可以使用函数“isPossiblePartialSolution”来检查。 以下是两个Java类： import java.util.ArrayList; public class Main { public static void main(String[] args) { ArrayList allSets = buildRandomTest(); for(Set r : allSets) { System.out.print(“Set with id: ” + r.id + […]