标签: recursive-backtracking

我试图实现深度优先深度搜索状态空间图.我有一个带有三个顶点的图形,它们是两个激活边和两个禁止边.每个节点都有一个二进制值,统称这是图的状态.通过查看其中一个节点是高于阈值还是低于阈值(通过对所有传入节点求和计算),图形可以转换到新状态.每个转换最多只有一个节点会发生变化.由于它们是三个节点,它们是三个状态转换边缘,在状态转换图中留下每个状态.

我认为我的state_change/3工作正常,例如我可以查询:

?-g_s_s(0,1,1,Begin),node(Arc),state_change(g_s(Begin),Second,Arc).

它给了我三个正确的答案:

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v1,
Second = g_s([node(v1, 1), node(v2, 1), node(v3, 1)]) ;

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v2,
Second = g_s([node(v1, 0), node(v2, 0), node(v3, 1)]) ;

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v3,
Second = g_s([node(v1, 0), node(v2, 1), node(v3, 0)]) 

我正在尝试使用Bratkos Prolog中为AI书提供的谓词id_path,这是问题11.3的解决方案,但我在使用/调整它时遇到了问题. 我想创建一个从起始节点到其他节点的路径,而没有进入循环 - 我不希望它有重复元素或在路径不存在时卡住.我希望路径说出起始状态,然后是一系列可以从起始状态访问的状态.如果有一个自循环,我希望每次到达那里都包含一次.即我想跟踪我进入状态空间的方式并使其独特,而不仅仅是状态空间在路径中是唯一的.

例如,从011开始,我希望所有三条长度为1的路径都可以找到弧线.

 ?-id_path(g_s([node(v1,0),node(v2,1),node(v3,1)],Last,[Temp],Path).
Path = [[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,1)],v1)];
Path =[[node(v1,0),node(v2,1),node(v3,1)], to([node(v1,0),node(v2,0),node(v3,1)],v2)];
Path=[[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,0)],v3)];

然后在下一个级别所有具有三个节点的路径,显示它需要到达节点的两个弧,然后在下一个级别所有具有四个节点的路径显示它需要的三个弧等

如果这有用,我还将我的代码放在SWISH中？(第一次尝试这个？!) …

假设有一个1和0的2D网格,例如 -

0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0

网格被"折叠"以形成1个更少行和1个更少列的更小网格,因此上面的示例将"折叠"以形成3行3列的网格.

新值由以下规则确定 -

new_grid[i][j] is dependent on 
  i) old_grid[i][j], 
 ii) old_grid[i][j+1], 
iii) old_grid[i+1][j] 
 iv) old_grid[i+1][j+1]

If exactly one of the above values are 1, then new_grid[i][j] will be 1, else 0.

因此,对于例如网格,出来的[0][0], [0][1], [1][0] and [1][1],只有[0][1]就是1,所以[0][0]在新的网格将是1.类似地,出[0][1], [0][2], [1][1] and [1][2],两者[0][1] and [1][2]都1,所以[0][1]在new_grid将0.

输入以new_grid …

示例：使用回溯解决数独

你如何在没有递归的情况下回溯 - 使用循环？我只在您调用 backtrack() 本身时才找到解决方案。

我正在尝试使用 Python 实现遍历所有图顶点的任意路径（不一定是循环）的递归搜索。这是我的代码：

def hamilton(G, size, pt, path=[]):
    if pt not in set(path):
        path.append(pt)
        if len(path)==size:
            return path
        for pt_next in G[pt]:
            res_path = [i for i in path]
            hamilton (G, size, pt_next, res_path)

这里，pt是起点，path是之前遍历过的所有顶点的列表，不包括pt，默认为空。问题是，每当找到这样的路径时，返回语句都会引用过程的某些内部调用，因此程序不会终止或返回该路径。

例如，获取G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]}（即完整的 4 图）并运行hamilton(G,4,1,[])。它返回None，但如果您打印路径而不是将其作为值返回，您会发现它实际上找到了从 1 开始的所有六个路径。

如果我告诉程序将路径与 return 语句一起打印，它最终会打印所有此类路径，因此运行时间比需要的时间长得多。

如何修复代码，以便在找到第一个合适的路径后终止执行？

例如，让我们考虑一个任务，我们需要找到给定字符串的所有排列，保留字符序列但改变大小写。

这是没有以下情况的回溯解决方案.pop()：

def letterCasePermutation(S):
    """
    :type S: str
    :rtype: List[str]
    """
    def backtrack(sub="", i=0):
        if len(sub) == len(S):
            res.append(sub)
        else:
            if S[i].isalpha():
                backtrack(sub + S[i].swapcase(), i + 1)
            backtrack(sub + S[i], i + 1)
            
    res = []
    backtrack()
    return res

这是一个解决方案.pop()：

def letterCasePermutation(s):
    def backtrack(idx, path):
        if idx == n:
            res.append("".join(path))
            return
        
        ele = s[idx]
        if ele.isnumeric():
            path.append(ele)
            backtrack(idx + 1, path)
            path.pop()
        else:
            path.append(ele.lower())
            backtrack(idx + 1, path)
            path.pop()
            path.append(ele.upper())
            backtrack(idx + 1, path)
            path.pop() …

我编写了递归回溯算法来查找给定集合的所有子集.

void backtracke(int* a, int k, int n)
{
    if (k == n)
    {
        for(int i = 1; i <=k; ++i)
        {
            if (a[i] == true)
            {
                std::cout << i << " ";
            }
        }
        std::cout << std::endl;
        return;
    }
    bool c[2];
    c[0] = false;
    c[1] = true;
    ++k;
    for(int i = 0; i < 2; ++i)
    {       
        a[k] = c[i];
        backtracke(a, k, n);
        a[k] = INT_MAX;
    }
}

现在我们必须编写相同的算法但是以迭代的形式,如何做到这一点？

例如,我的计划的目标是将所有可能的变更解决方案输出到给定数额的金额

期望的输出

Change: 9
[1, 1, 1, 1, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1]

(9 = $ 0.09)但是我的输出有点不同,我的输出看起来像这样

我的输出

Change: 9
[1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 5]
[1, 1, 1, 5, 1]
[1, 1, 5, 1, 1]
[1, 5, 1, 1, 1]
[5, 1, 1, 1, 1]

正如您所看到的,它可以为我提供所有可能的解决方案.我只关心前两个答案.很明显,当要求更大的金额时,这将是一个大问题.所以这是我的问题:基于我的代码,如何将其修复到只显示一个组合的位置？

码

import java.io.*;
import java.util.*;
import java.lang.*;

public class homework5 {

 public static int change;

   public static void …

我试图了解回溯，但是我陷入了这个问题，这是提示：

给定一组不同的整数，返回所有可能的子集。

输入示例： [1,2,3]

输出示例： [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

这是我的代码：

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

def backtrack(res, temp, nums, start):
    # print(temp)
    res.append(temp)
    for i in range(start, len(nums)):
        temp.append(nums[i])
        backtrack(res, temp, nums, i + 1)
        temp.pop() # Backtrack

当我返回时，res我得到一个空列表size的列表2^(len(nums))，该列表是正确的大小，但是数字不存在。但是，temp在执行此操作之前res.append(temp)，打印表明temp进行了正确的输出。

例如

res = [[], [], [], [], [], [], [], []]

打印报表：

[] [1] [1, 2] [1, 2, …

您需要爬上n个台阶的楼梯，然后决定跳上台阶进行一些额外的锻炼。一次跳转最多可以覆盖k个步骤。返回您可能要爬上楼梯的所有可能跳序列，已排序。

我的实现显然给了我错误的答案。

def climbingStaircase(n, k):
    final_res=[]
    final_res.append(CSR(n,k,[]))
    return final_res

def CSR(n,k,res):
    if n == 0:
        return res        
    else:
        for i in range(1,k+1):
            if n-i>=0:
                res.append(i)
                n=n-i
                res=CSR(n,i,res)
        return res

对于n = 4和k = 2，输出应为

[[1, 1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [2, 1, 1],
 [2, 2]]

实际输出：

[[1,1,1,1,2,1]]

有人可以指出我缺少的那一部分吗？

我正在尝试创建一个递归创建迷宫函数，但是，我被卡住了，因为我不知道如何递归调用它并放置墙壁。

有人可以告诉我如何编辑我的代码以使其正常工作吗？谢谢

编辑：由于我没有添加我的迷宫类，我想我会添加它来帮助查看整个代码。

class Maze:
    def __init__(self, Width, Height):
        assert Width>= 1 and Height>= 1

        self.Width= Width
        self.Height= Height
        self.board = np.zeros((Width, Height), dtype=WALL_TYPE)
        self.board.fill(EMPTY)

    def set_borders(self):
        self.board[0, :] = self.board[-1, :] = WALL
        self.board[:, 0] = self.board[:, -1] = WALL

    def is_wall(self, x, y):
        assert self.in_maze(x, y)
        return self.board[x][y] == WALL

    def set_wall(self, x, y):
        assert self.in_maze(x, y)
        self.board[x][y] = WALL

def create_maze(Width, Height, seed=None):
        Width = (Width // 2) * 2 + 1
        Height = (Height // 2) …

我在这个堆栈溢出答案中发现了这个代码,我试图理解这个递归函数是如何终止的.我没有在该线程上提出问题的原因是我的问题是关于递归,而不是那里讨论的内容(加密).

/// <summary>
/// Simple Encryption (AES) then Authentication (HMAC) for a UTF8 Message.
/// </summary>
/// <param name="secretMessage">The secret message.</param>
/// <param name="cryptKey">The crypt key.</param>
/// <param name="authKey">The auth key.</param>
/// <param name="nonSecretPayload">(Optional) Non-Secret Payload.</param>
/// <returns>
/// Encrypted Message
/// </returns>
/// <exception cref="System.ArgumentException">Secret Message Required!;secretMessage</exception>
/// <remarks>
/// Adds overhead of (Optional-Payload + BlockSize(16) + Message-Padded-To-Blocksize +  HMac-Tag(32)) * 1.33 Base64
/// </remarks>
public static string SimpleEncrypt(string secretMessage, byte[] cryptKey, byte[] authKey,
                   byte[] nonSecretPayload = …