下面将一个集合传递给此方法,并且还会传入一个条形长度.如果从条形长度中移除了集合中的某些数字,则解决方案应输出集合中的数字,这些数字会产生最少量的浪费.因此,条形长度10,设置包括6,1,4,因此解决方案是6和4,并且浪费是0.我在通过集合回溯的条件有一些麻烦.我也尝试使用浪费的"全局"变量来帮助回溯方面,但无济于事.

SetInt是一个手动创建的集合实现,它可以添加,删除,检查集合是否为空并从集合中返回最小值.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package recback;


public class RecBack {

   public static int WASTAGE = 10;

    public static void main(String[] args) {



         int[] nums = {6,1,4};
        //Order Numbers

        int barLength = 10;
        //Bar length

        SetInt possibleOrders = new SetInt(nums.length);
        SetInt solution = new SetInt(nums.length);
        //Set Declarration


        for (int i = 0; i < nums.length; i++)possibleOrders.add(nums[i]);
        //Populate Set

        SetInt result = tryCutting(possibleOrders, solution, barLength); …

我一直想知道这件事.没有书明确说明这一点.

回溯正在探索所有可能性,直到我们发现一种可能性无法引导我们找到可能的解决方案,在这种情况下我们放弃它.

据我所知,动态编程的特点是重叠的子问题.那么,动态编程是否可以表示为缓存回溯(对于以前探索过的路径)？

谢谢

假设您有 n 个排序的数字数组，您需要从每个数组中选择一个数字，以使 n 个所选元素之间的最小距离最大化。

例子：

arrays:
[0, 500]
[100, 350]
[200]

2<=n<=10每个数组都可以有~10^3-10^4元素。

在此示例中，最大化最小距离的最佳解决方案是选择数字：500、350、200 或 0、200、350，其中最小距离为 150，并且是每个组合的最大可能值。

我正在寻找一种算法来解决这个问题。我知道我可以对最大最小距离进行二分搜索，但我不知道如何确定是否存在最大最小距离至少为 d 的解决方案，以便二分搜索起作用。我在想动态编程可能会有所帮助，但还没有找到 dp 的解决方案。

当然，用 n 个元素生成所有组合效率不高。我已经尝试过回溯，但速度很慢，因为它尝试了每种组合。

关于深度优先搜索的维基百科:

深度优先搜索(DFS)是用于遍历或搜索树,树结构或图的算法.一个从根开始(在图形情况下选择一个节点作为根)并在回溯之前尽可能地沿着每个分支进行探索 .

那么什么是广度优先搜索？

"选择起始节点,检查所有节点回溯,选择最短路径,选择邻居节点回溯,选择最短路径,最终找到最佳路径的算法,因为由于连续回溯而遍历每条路径.

正则表达式find的修剪 - 回溯？

由于其使用的多样性,回溯一词令人困惑.UNIX find修剪SO用户解释了回溯.如果您不限制正则表达式的范围,Regex Buddy使用术语"灾难性回溯".它似乎是一个过于广泛使用的伞形术语.所以:

1. 你如何专门为图论定义"回溯"？
2. 什么是广度优先搜索和深度优先搜索中的"回溯"？

[添加]

关于回溯和示例的良好定义

1. 蛮力方法
2. Stallman(？)发明了术语"依赖性指导的回溯"
3. 回溯和正则表达式的例子
4. 深度优先搜索定义.

我正在尝试实现一个类,它将生成所有可能的无序n元组或给定多个元素和组合大小的组合.

换句话说,在调用时:

NTupleUnordered unordered_tuple_generator(3, 5, print);
unordered_tuple_generator.Start();

print()是构造函数中设置的回调函数.输出应该是:

{0,1,2}
{0,1,3}
{0,1,4}
{0,2,3}
{0,2,4}
{0,3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}

这是我到目前为止:

class NTupleUnordered {
public:
    NTupleUnordered( int k, int n, void (*cb)(std::vector<int> const&) );
    void Start();
private:
    int tuple_size;                            //how many
    int set_size;                              //out of how many
    void (*callback)(std::vector<int> const&); //who to call when next tuple is ready
    std::vector<int> tuple;                    //tuple is constructed here
    void add_element(int pos);                 //recursively calls self
};

而这是递归函数的实现,Start()只是一个启动函数,具有更清晰的接口,它只调用add_element(0);

void NTupleUnordered::add_element( int pos )
{

  // base case
  if(pos …

我正在为一个类制作一个SudokuSolver,而我在使用solve方法时遇到了麻烦.我目前的解决方案使用递归回溯(我认为).

作业要求

int solve() - 尝试使用上述策略解决难题.返回解决方案的数量.

(上述策略)

为某个地点指定一个数字时,请不要指定一个数字,此时此数字与该地点的行,列或方形冲突.我们很谨慎地将法律数字分配给某个地点,而不是分配任何数字1..9并在递归后期找到问题.假设初始网格都是合法的,之后只进行合法的分配.

伪代码的想法

我可以迭代地关注这个小输入.例如,假设我必须处理未解决的Cell#1和Cell#2.#1有可能{1,3},#2有可能{2,3}.那我会的

set 1 to 1
    set 2 to 2
        hasConflicts? 0 : 1
    set 2 to 3
        hasConflicts? 0 : 1
set 1 to 3
    set 2 to 2
        hasConflicts? 0 : 1
    set 2 to 3
        hasConflicts? 0 : 1

实际代码

public int solve() {
    long startTime = System.currentTimeMillis();
    int result = 0;

    if (!hasConflicts()) {
        Queue<VariableCell> unsolved = getUnsolved();
        reduceUnsolvedPossibilities(unsolved);  // Gets the possibilities down from all of 1-9 …

考虑这个正则表达式.

a*b

这将失败的情况下 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

这会使67调试器中的步骤失败.

现在考虑这个正则表达式.

(?>a*)b

这将失败的情况下 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

这会使133调试器中的步骤失败.

最后这个正则表达式:

a*+b  (a variant of atomic group)

这将失败的情况下 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

这会使67调试器中的步骤失败.

当我检查基准测试atomic group (?>a*)b执行179%得更快.

现在原子组禁用回溯.所以比赛中的表现很好.

1. 但为什么步数更多呢？有人可以解释一下吗？

2. 为什么会有差异.在两个原子团(?>a*)b和之间的步骤a*+b.

他们的工作方式不同吗

在回溯中,我们使用bfs和dfs.Even在分支和绑定中我们使用bfs和dfs以及最低成本搜索.

所以我们何时使用回溯,何时使用分支和绑定

使用分支和绑定会减少时间的复杂性吗？

什么是分支机构中的最低成本搜索？

如果我错了,请纠正我

谢谢

我有网格N×M,其中每个单元格用一种颜色着色.

当玩家点击颜色α网格的任何单元格时,网格最左上角的颜色为β的单元格接收颜色α,但不仅仅是:所有那些通过颜色连接到源的单元格仅使用颜色α或β的路径也接收颜色α.

应仅在水平和垂直方向上考虑单元之间的连接以形成路径.例如,当玩家点击左图中突出显示的单元格时,网格会在右侧接收图形的颜色.游戏的目标是使网格单色化.

输入描述

输入的第一行由2个整数N和M(1≤N≤4,1≤M≤5)组成,它们分别代表网格的行数和列数.下面的N行描述了网格的初始配置,用0到9之间的整数表示每种颜色.输入不包含任何其他行.

输出描述

打印包含单个整数的行,该整数表示播放器必须执行的最小点击次数才能使网格变为单色.

输入样本

1:

4 5
01234
34567
67890
90123

2:

4 5
01234
12345
23456
34567

3:

4 5
00162
30295
45033
01837

输出样本

1:

12

2:

7

3:

10

我正在尝试找回带回溯的解决方案(因为8秒的时间限制和网格的小尺寸).但它超出了时间限制.有些人刚刚在0秒时完成了它.

还有其他算法可以解决这个问题吗？

#include <stdio.h>
#include <string.h>

#define MAX 5
#define INF 999999999

typedef int signed_integer;

signed_integer n,m,mink;
bool vst[MAX][MAX];

signed_integer flood_path[4][2] = {
    {-1,0},
    {1,0},
    {0,1},
    {0,-1}
};

//flood and paint all possible cells... the root is (i,j)
signed_integer flood_and_paint(signed_integer cur_grid[MAX][MAX],signed_integer i, signed_integer j, …

我有一个填字游戏和一个可用于解决它的单词列表(单词可以放置多次或甚至不放一次).对于给定的填字游戏和单词列表,始终存在解决方案.

我搜索了如何解决这个问题的线索,发现它是NP-Complete.我的最大填字游戏大小是250乘250,列表的最大长度(可以用来解决它的单词数量)是200.我的目标是通过强力/回溯来解决这个大小的填字游戏,这应该是可能的几秒钟(这是我的粗略估计,如果我错了,请纠正我).

例:

可用于解决填字游戏的给定单词列表:

• 能够
• 音乐
• 金枪鱼
• 嗨

给定的空填字游戏(X是无法填写的字段,需要填充空字段):

解决方案:

现在我的方法是将填字游戏表示为二维数组并搜索空格(填字游戏上的2次迭代).然后我根据它们的长度将单词与空格匹配,然后我尝试所有单词组合来清空具有相同长度的空格.这种方法变得非常混乱非常快,我迷失了尝试实现这一点,是否有更优雅的解决方案？