Tag: 回溯

递归回溯的问题: 嘿伙计们，最近发布了我的算法问题。从一组中查找给出最少量废物的数字我略微修改了代码，所以它现在回溯到一定程度，但输出仍然存在缺陷。我已经调试了这个大大调查所有变量值，似乎无法找出问题。与直接解决方案相反的建议再次提供了很大的帮助。我认为我的代码只有几个问题，但我无法解决问题。 //来自上一篇文章：基本上，一个集合被传递给下面的这个方法，并且还传入一个条形的长度。解决方案应该输出集合中的数字，如果从条形长度中移除了集合中的某些数字，则给出最小量的浪费。因此，条形长度10，设置包括6,1,4，因此解决方案是6和4，并且浪费是0.我在通过集合回溯的条件有一些麻烦。我也尝试使用浪费的“全局”变量来帮助回溯方面，但无济于事。 SetInt是一个手动创建的集合实现，它可以添加，删除，检查集合是否为空并从集合中返回最小值。 /* * To change this template, choose Tools | Templates * and open the template in the editor. */ package recursivebacktracking; /** * * @author User */ public class RecBack { int WASTAGE = 10; int BESTWASTAGE; int BARLENGTH = 10; public void work() […]

用于将字符串与通配符模式匹配的递归函数: 所以我一整天都试图解决这个任务，只是无法得到它。以下函数接受2个字符串，第2个（不是第1个）可能包含* （星号）。 *是字符串的替换（空，1个字符或更多），它可以出现（仅在s2中）一次，两次，更多或根本不存在，它不能与另一个* （ ab**c ）相邻，无需检查。 public static boolean samePattern(String s1, String s2) 如果字符串具有相同的模式，则返回true。它必须是递归的，不能使用任何循环，静态和全局变量。可以使用局部变量和方法重载。只能使用以下方法： charAt(i) ， substring(i) ， substring(i, j) ， length() 。例子： 1： TheExamIsEasy ; 2： The*xamIs*y →true 1： TheExamIsEasy ; 2： Th*mIsEasy* →true 1： TheExamIsEasy ; 2： * →true 1： TheExamIsEasy ; 2： TheExamIsEasy →true 1： TheExamIsEasy […]

解决填字游戏: 我有一个填字游戏和一个可以用来解决它的单词列表（单词可以放置多次或甚至不放一次）。对于给定的填字游戏和单词列表，始终存在解决方案。我搜索了如何解决这个问题的线索，发现它是NP-Complete。我的最大填字游戏大小是250乘250，列表的最大长度（可以用来解决它的单词数量）是200.我的目标是通过powershell/回溯来解决这个大小的填字游戏，这应该是可能的几秒钟（这是我的粗略估计，如果我错了，请纠正我）。例：可用于解决填字游戏的给定单词列表：能够音乐金枪鱼嗨给定的空填字游戏（X是无法填写的字段，需要填充空字段）：解决方案：现在我的方法是将填字游戏表示为二维数组并搜索空格（填字游戏上的2次迭代）。然后我根据它们的长度将单词与空格匹配，然后我尝试所有单词组合来清空具有相同长度的空格。这种方法变得非常混乱非常快，我迷失了试图实现这一点，是否有更优雅的解决方案？

确定数独是否具有唯一解决方案: 我正在努力使用回溯算法来确定数独有一个独特的解决方案，或者它是否有多个解决方案。这是我使用的回溯代码： static boolean solve(int i, int j, int[][] cells) { if (i == 9) { i = 0; if (++j == 9) return true; } if (cells[i][j] != 0) // skip filled cells return solve(i+1,j,cells); for (int val = 1; val <= 9; ++val) { if (legal(i,j,val,cells)) { cells[i][j] = val; if (solve(i+1,j,cells)) return […]

数独回溯无效数独: 我创建了一个Sudoku Backtracking解算器，它工作正常，但现在我想发出一个错误，如果数独无法解决，因为它是无效的，例如，如果给出这个数独： http://img5.imageshack.us/img5/2241/sudokugq.jpg 如果不能解决，我该怎么办才能使我的求解方法出错？我总是最终使用Zeros或陷入循环。 public void solve( int row, int col ) throws Exception { // Throw an exception to stop the process if the puzzle is solved if( row > 8 ){ //Gelöst } // If the cell is not empty, continue with the next cell if( sudo[row][col] != 0 ){ next( row, […]

如何从数组中删除最后一个元素？: 现在我正在使用递归回溯，我的任务是找到迷宫中最长的路径，质量表示为用坐标覆盖的字段，并且墙壁的坐标在文件中是酸痛的。我已经创建了一个解析器来解析输入文件并构建墙，但我还将这个坐标存储在一个对象类型Coordinate的数组中，以检查是否有可能在下一个“蛇”上移动下一个“蛇”字段，然后我创建了这个方法，现在我已经明白我需要一个方法来从数组中删除最后一个坐标，当我使用回溯时，我该怎么办？目标不是使用数组列表或链表只有arrays！谢谢！ public class Coordinate { int xCoord; int yCoord; Coordinate(int x,int y) { this.xCoord=x; this.yCoord=y; } public int getX() { return this.xCoord; } public int getY() { return this.yCoord; } public String toString() { return this.xCoord + “,” + this.yCoord; } } 和 public class Row { static final int MAX_NUMBER_OF_COORD=1000; Coordinate[] coordArray; […]

如何通过此回溯找到第一个解决方案: 我正在尝试编写一个只返回第一个可能解决方案的数独求解器。我设法用void方法打印所有可能的解决方案，但我不能停止第一次找到。我知道首选方法是切换到布尔方法并在树中返回true – 但我找不到正确的方法来编写它。我试过的任何方式总是给出编译错误（ method must return boolean ）。 public boolean recursiveSolve(int line, int column) { if(line == N) // N is the board size (9) return true; // if Cell is not empty – continue if(board1.getCell(line, column) != 0) { return nextCell(line, column); } // if Cell empty – solve else { […]

给定n和k，返回第k个排列序列: 集合[1,2,3，…，n]总共包含n！独特的排列。通过按顺序列出和标记所有排列，我们得到以下序列（即，对于n = 3）： “123” “132” “213” “231” “312” “321”给定n和k，返回第k个排列序列。例如，给定n = 3，k = 4，ans =“231”。那里有多种解决方案。但是它们都使用阶乘或者复杂度大于O（n），例如O（n！）。如果你使用阶乘并在位置找到k /（n-1）!,那么当n很大（n = 100）时会出现问题。这里n很大，（n-1）！溢出并变为0.结果，我得到一个零除错误…任何解决方案或算法？这是我的代码： public class KthPermutation { public String getPermutation(int n, int k) { // initialize all numbers ArrayList numberList = new ArrayList(); for (int i = 1; i <= n; i++) […]

Sudoku生成器的递归解决方案: 我正在尝试编写一个算法，用Java或Javascript创建一个合法的数独板。既不工作，也不完全确定原因。从本质上讲，两个程序中的问题是x或y的增量都超过它应该增加（跳过正方形）。我不能为我的生活弄清楚这是怎么回事。如果需要，我可以提供完成JS解决方案的HTML。我最好的猜测是它与我如何使用递归创建堆栈有关，但据我所知，它应该工作。在我的旧代码中有一个不正确的for循环，我知道这一点。我粘贴了一个旧版本，现在已经修好了。 Java的： import java.util.*; public class SudokuGenerator { //credit:cachao //http://stackoverflow.com/questions/9959172/recursive-solution-to-sudoku-generator public static final int BOARD_WIDTH = 9; public static final int BOARD_HEIGHT = 9; public SudokuGenerator() { board = new int[BOARD_WIDTH][BOARD_HEIGHT]; } //Recursive method that attempts to place every number in a square public int[][] nextBoard() { nextBoard(0,0); […]

这个正则表达式不应该发生灾难性的回溯: 有人可以解释为什么Java的正则表达式引擎会在这个正则表达式上进入灾难性的回溯模式吗？根据我的判断，每次交替都是互相排斥的。 ^(?:[^’\”\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\”\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*| \”(?:[^\”]+|\”\”)+\”| ‘(?:[^’]+|”)+’) 文字： ‘pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE]) 为一些替换添加所有格匹配修复了问题，但我不知道为什么 – Java的正则表达式lib必须非常错误才能在互斥的分支上回溯。 ^(?:[^’\”\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\”\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*| \”(?:[^\”]++|\”\”)++\”| ‘(?:[^’]++|”)++’)