标签: backtracking

所以我一整天都试图解决这个任务,只是无法得到它.

以下函数接受2个字符串,第2个(不是第1个)可能包含*'s(星号).
An *是字符串的替换(空,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:？真
1 TheExamIsEasy:; 2 Th*mIsEasy*:？真
1 TheExamIsEasy:; 2 *:？真
1 TheExamIsEasy:; 2 TheExamIsEasy:？真
1 TheExamIsEasy:; 2 The*IsHard:？假

我尝试逐个比较字符,charAt直到遇到星号,然后通过比较连续的char(i+1)和s1at位置的char来检查星号是否为空i,如果为true,则继续递归,i+1作为s2&的计数器i反驳s1; …

我查看了类似的问题但找不到与我的问题相关的任何内容.我在努力寻找"回路",将找到一个路径的算法或设置CityA到CityB,使用数据库的

distance(City1,City2,Distance)

事实.到目前为止我设法做的是下面,但它总是回溯,write(X),然后在最后的迭代中完成,这是我想要它做的但只是在一定程度上.

例如,我不希望它打印出任何死胡同的城市名称,或者使用最后的迭代.我希望它基本上建立一条路径,CityA在路径上CityB写下它所去的城市的名称.

我希望有人可以帮助我!

all_possible_paths(CityA, CityB) :-
    write(CityA),
    nl,
    loop_process(CityA, CityB).

loop_process(CityA, CityB) :- 
    CityA == CityB.
loop_process(CityA, CityB) :-
    CityA \== CityB,
    distance(CityA, X, _),
    write(X),
    nl,
    loop_process(X, CityB).

我目前正在研究正则表达式的问题,当与某个输入匹配时,它可能最终在指数时间内运行,例如两者(a*)*并且当与字符串aaaaab匹配时(a|a)*可能表现出" 灾难性的回溯 " - 对于每个额外的"a"匹配字符串,尝试匹配字符串双精度所需的时间.仅当引擎使用回溯/ NFA方法尝试在失败之前尝试树中的所有可能分支(例如PCRE中使用的分支)时,才会出现这种情况.

我的问题是,为什么不(a?)*脆弱？根据我对回溯的理解,字符串"aaaab"中应该发生的事情本质上就是这样(a|a)*.如果我们使用标准的Thomspson NFA结构构建NFA,那么对于每次发生的epsilon转换,引擎必须继续采用它们并以与两个a的情况相同的方式进行回溯？例如(省略一些步骤,@替换epsilon):

"aaaa"匹配,但不能匹配'b',失败(回溯)
"aaaa @"匹配,'b'失败(回溯)
"aaa @ a"匹配,'b'失败(回溯)
"aaa @ a @ "匹配,'b'失败(回溯)
......
"@ a @ a @ a @ a @"匹配,'b'失败(回溯)

尝试所有可能的epsilons和a的组合,肯定会导致路线的指数爆炸？

从NFA中移除epsilon过渡是有意义的,但我相信这具有从(a*)*模式中去除所有非确定性的效果.这绝对是脆弱的,所以我不完全确定发生了什么!

非常感谢你提前!

编辑: Qtax已经指出,当传统的回溯遍历NFA时,epsilons仍然无法存在,否则(@)*将尝试永远匹配.那么NFA的实施可能会导致(a*)*并呈现(a|a)*指数,而(a?)*不是如此？这真的是问题的症结所在.

多集是一个集合,其中所有元素可能不唯一.如何枚举集合元素中的所有可能的排列？

对于一组表格A = {1, 2, 3, ..., n}.它被称为集合的分区,是A一组k<=n尊重以下定理的元素:

a)所有分区的A并集是A

b)2个分区的交集A是空集(它们不能共享相同的元素).

例如.A = {1, 2,... n}我们有分区: {1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3}

这些理论概念在我的算法教科书中提出(顺便说一下,这个子章节是"回溯"章节的一部分).我应该找到一个算法来生成给定集合的所有分区.我整天都在努力解决这个问题,但我找不到解决办法.你能解释一下这个算法是如何工作的吗？另外,你能给我一个算法的伪代码草图吗？

我试图了解Selectmonad是如何工作的.显然,它是表兄,Cont它可以用于回溯搜索.

我有这个基于列表的解决n-queens问题的方法:

-- All the ways of extracting an element from a list.
oneOf :: [Int] -> [(Int,[Int])] 
oneOf [] = [] 
oneOf (x:xs) = (x,xs) : map (\(y,ys) -> (y,x:ys)) (oneOf xs)

-- Adding a new queen at col x, is it threathened diagonally by any of the
-- existing queens?
safeDiag :: Int -> [Int] -> Bool
safeDiag x xs = all (\(y,i) -> abs (x-y) /= i) (zip xs [1..])

nqueens :: Int …

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

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

例:

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

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

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

解决方案:

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

在我的课上,我学习了Prolog回溯算法和Rete forprop算法,但我也被告知Rete可以用来做backprop.

这是如何运作的？它与Prolog回溯的方式类似/不同？

例如,这是我给出的练习之一:

(R1) 24fingers and antennas => origin(mars)
(R2) shy and 5feet => origin(mars)
(R3) shy and 4arms => origin(venus)
(R4) looksDownWhenTalking => shy
(R5) fleesWhenSeen => shy

目标是通过以下事实找到外星人的起源:

(F1) fleesWhenSeen
(F2) 4arms

在Prolog中,我们将通过模式匹配origin(X)规则的RHS 的目标来解决它.规则与R1,R2和R3匹配,因此首先会触发R1,我们会尝试解决24fingers and antennas失败的子目标.

然后我们将回溯到开头并触发R2,最终将失败,最后回溯并触发R3,这成功.

因此X,venus在成功查询中结束绑定,算法结束.

现在,我们如何使用rete backprop算法解决相同的练习？

我天真地假设我们将使用一个子目标列表,从origin(X)开始,触发RHS与子目标匹配的规则.

但是,当一些子目标失败时,我不清楚Rete算法如何处理回溯,或者一旦它解决了某个目标子集,它将如何知道它已经成功.

考虑:

a c p r c 
x s o p c 
v o v n i 
w g f m n 
q a t i t

字母表i_index是相邻于另一个字母j_index在瓦片如果i_index毗邻j_index在任何下列位置中:

* * *
* x *
* * *

这里所有的都*表示与之相邻的位置x.

任务是在tile中找到给定的字符串.条件是给定字符串的所有字符应该是相邻的,并且可以不多次使用图块中的任何一个字符来构造给定字符串.

我想出了一个简单的回溯解决方案,解决方案非常快,但最坏的情况时间真的更糟.

举一个例子:假设瓷砖有4x4填充了所有的 s,因此16 a,并且要查找的字符串是aaaaaaaaaaaaaa,即15 a和1 b.一个是消除字符串中没有出现的字符串.但仍然最坏的情况仍然可以出现说瓷砖有abababababababab和找到的字符串是abababababababbb.

我的尝试是这样的:

https://ideone.com/alUPf:

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

#define MAX 5 …

我已经被要求回答这个问题(这是技术上的功课).我考虑过哈希表,但我有点坚持我如何使这项工作的具体细节

这是问题:

鉴于ķ套整数阿₁,阿₂,..,甲_ķ总尺寸O(的Ñ),则应该确定是否存在 一个₁ ε 阿₁,一个₂ ε 阿₂,..,一个_ķ ε 甲_ķ,使得一个₁ + 一个₂ + .. + 一_{ķ -1} = 一个_ķ.您的算法应当T中运行_ķ(Ñ)时间,其中T _ķ(Ñ)= O(Ñ ^ķ/2 ×日志Ñ),用于甚至ķ,和O(Ñ ^{(ķ +1)/ 2})为奇数值ķ.

任何人都可以给我一个大方向,以便我能够更接近解决这个问题吗？