Tag: backtracking

用启发式实现回溯搜索？

我对搜索算法和回溯编程非常感兴趣。 现在，我已经实现了算法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 + […]

回溯powershellJava密码破解者

我有这个家庭作业，以一个递归的方法来破解给定长度的密码，n（无限和未知！）由小英文字母组成，只有az。 这是创建随机密码的“密码”类： import java.util.Random; public class Password { private String _password = “”; public Password(int length) { Random generator = new Random(); for (int i = 0; i < length; ++i) { this._password = this._password + (char) (generator.nextInt(26) + 97); } } public boolean isPassword(String st) { return st.equals(this._password); } public String getPassword() { return […]

Java中的数独求解器，使用回溯和递归

我正在用Java编写一个用于9×9网格的数独求解器。 我有方法： 打印网格 用给定的值初始化电路板 测试冲突（如果相同的数字在同一行或3×3子网格中） 一种逐个放置数字的方法，这需要最多的工作。 在我详细介绍该方法之前，请记住我必须使用递归来解决它，以及回溯（在这里观看applet作为示例http://www.heimetli.ch/ffh/simplifiedsudoku.html ） 另外，我通过垂直向下移动来解决这个数独，从左上角开始，到第一列，然后到第二列，等等。 到目前为止，我有以下内容： public boolean placeNumber(int column){ if (column == SUDOKU_SIZE){ // we have went through all the columns, game is over return true; } else { int row=0; //takes you to the top of the row each time while (row < SUDOKU_SIZE) loops through the column downwards, […]