词意

试探法

步骤

递归回溯

回溯的设计

程序

绯儿歌曲《回溯》(概要 歌曲基本信息及歌词 出处 关于原唱歌手绯儿)

词意

huí sù [recall;look back upon;trace] 上溯,向上推导

1.回顾、回忆

2.某些水生生物的习性，详见回游。

试探法

回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。

步骤

用回溯算法解决问题的一般步骤为：

一、定义一个解空间，它包含问题的解。

二、利用适于搜索的方法组织解空间。

三、利用深度优先法搜索解空间。

四、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.

递归回溯

递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：

procedure try(i:integer);

var

begin

if i>n then 输出结果

else for j:=下界 to 上界do

begin

x:=h[j];

if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;

end;

end;

说明：

i是递归深度；

n是深度控制，即解空间树的的高度；

可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；

搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。

回溯即是较简单、较常用的搜索策略。

基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。

回溯的设计

1.用栈保存好前进中的某些状态.

2.制定好约束条件

【例1】从1到X这X个数字中选出N个，排成一列，相邻两数不能相同，求所有可能的排法。每个数可以选用零次、一次或多次。例如，当N=3、X=3时，排法有12种：121、123、131、132、212、213、231、232、312、313、321、323。

【分析】以N=3，X=3为例，这个问题的每个解可分为三个部分：第一位，第二位，第三位。先写第一位，第一位可选1、2或3，根据从小到大的顺序，我们选1；那么，为了保证相邻两数不同，第二位就只能选2或3了，我们选2；最后，第三位可以选1或3，我们选1；这样就得到了第一个解"121"。然后，将第三位变为3，就得到了第二个解"123"。此时，第三位已经不能再取其他值了，于是返回第二位，看第二位还能变为什么值。第二位可以变为3，于是可以在"13"的基础上再给第三位赋予不同的值1和2，得到第三个解"131"和"132"。此时第二位也已经不能再取其他值了，于是返回第一位，将它变为下一个可取的值2，然后按顺序变换第二位和第三位，得到"212"、"213"、"231""232"。这样，直到第一位已经取过了所有可能的值，并且将每种情况下的第二位和第三位都按上述思路取过一遍，此时就已经得到了该问题的全部解。

由以上过程可以看出，回溯法的思路是：问题的每个解都包含N部分，先给出第一部分，再给出第二部分，……直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。

程序

program p11_14;

const n=3;x=3;

var a:array [1..n] of 0..x;

p,c,I:integer;

begin

writeln;

p:=1; {从第一位开始}

c:=1; {从1开始选数字}

repeat

repeat

if (p=1) or (c<>a[p-1]) then {第一位可填任意数}

begin

a[p]:=c; {将数字C填到第P位上}

if p=n then {若已填到最后一位，则表明已求出了一个解}

begin

for I:=1 to n do write(a); {显示这个解}

writeln;

end;

P:=P+1; {继续下一位}

C:=1; {下一位从1开始}

End

Else

C:=c+1; {下一位仍然从1开始选数字}

Until (p>n) or (c>X); {直到已填完最末位，或本位再无数字可选}

Repeat

P:=p-1; {向前回溯}

Until (p=0) or (a[p]<x) ; {回溯到尚有选择余地的一位，或到首位}

If p>0 then {若非首位，则将该位变为下一个可取的数字}

C:=a[P]+1;

Until p=0; {将第一位回溯完毕后，程序结束}

End.

由键盘上输入任意n个符号，输出它的全排列。（一个符号只能出现一次）

program hh;

const n=3;

var i,k:integer;

x:array[1..n] of integer;

st:string[n];

t:string[n];

procedure input;

var i:integer;

begin

write('Enter string=');readln(st);t:=st;

end;

function place(k:integer):boolean;

var i:integer;

begin

place:=true;

for i:=1 to k-1 do

if x=x[k] then begin place:=false; break end;

end;

procedure print;

var i:integer;

begin

for i:=1 to n do write(t[x]);writeln;

end;

begin

input;

k:=1;x[k]:=0;

while k>0 do

begin

x[k]:=x[k]+1;

while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;

if x[k]>n then k:=k-1

else if k=n then print

else begin k:=k+1;x[k]:=0

end

end ;

readln

end.

<i id="bke_bwmm753w">

绯儿歌曲《回溯》

概要

歌曲《回溯》是由绯之精灵论坛会员月の节奏填词，歌手绯儿原唱的一首原创词网络歌曲。

歌曲基本信息及歌词

歌名：回溯

歌手：绯儿

填词：月の节奏

作曲：The-2th mvmt

夜空浅白月牙，

梦里风吹篱笆

夏日静夜时，

愿为君唤取流云。

曾经红尘俗世，

几度迷幻人生。

咫尺却天涯，

也许是人心复杂。

生命那么脆弱，

能否改变未来。

地平线风景，

一切美丽的奇迹。

注定中一个人，

所谓孤独终老。

承受着伤痛，

找不到梦的港湾。

叹息过往 曾经只有受伤 的心痛

乘着风 那些泪让它随梦 凋零。

痛哭掩藏不 住的 懦弱而感*的地平线，

明天的路还漫长。

你给我的 最温馨最美丽 的天堂，

一个人 从这里纷繁中 逃离。

我看到每一 次斗转星移历史的轨迹，

回溯旧梦见明晖

纵然相隔 海角天涯，

脆弱的生命 只能顾影自怜。

向着青空 释放过往，

轮回了以后 还能续情吗？

叹息过往 曾经只有受伤 的心痛

乘着风 那些泪让它随梦 凋零。

痛哭掩藏不 住的 懦弱而感*的地平线，

明天的路还漫长。

你给我的 最温馨最美丽 的天堂，

一个人 从这里纷繁中 逃离。

我看到每一 次斗转星移历史的轨迹，

回溯旧梦见明晖

出处

出品站点: FEIAIR-绯之精灵论坛（歌曲原发布页及论坛地址请见扩展阅读）

关于原唱歌手绯儿

曾在2008年9月举行的Press Start 2008最终幻想主题歌手选举大赛中，凭借《生命的旋律》和《恋爱写真》两部作品一举夺得前十（精彩入围大奖） 。之前绯儿也曾与词作者细雨游风共同给生命的旋律进行中文填词并演唱中文版，其中文版命名为《爱的旋律》。

绯儿演唱的填词中文作品中一些经典歌曲也广为流传而被网友所熟悉和翻唱，类似：水果篮子主题曲中文版《划风之吻》，水星领航员主题曲中文版《天使的羽翼》、夕颜的填词中文版《醉古依情》 ，以及魔卡少女樱HONEY的填词中文版《晴天娃娃》，情衷的二次填词《新情衷》，超时空要塞钻石裂痕的中文版《无所顾忌》等……其中部分中文填词作品收录在《绯语》音乐集中！

其他被网友所熟悉的一些歌曲：（可能未逐一例举到）

如：恶魔城月下夜想曲《夜曲》、《蜜雨》、《星の在り処-星之所在》、《爱在RO雪季日、中文版》、《硝子镜の梦》、《拥抱粉雪》、《素敌だね》、《飞羽》、 《ウンディーネ日文版》、《agony》、《秋蝉鸣泣之时》、《HIKARI~光芒》、《可曾记得爱》、《爱のカケラ_爱的碎片》、《恋爱写真》、《化作泪水》、《It's only the fairy tale》、《Rain Of Love》、《星象仪》、《金鱼花火》、《honey日文版》、《for fruits basket日文版》、《白夜》、《运命~SADAME~》、《魂のルフラン》、《星空的华尔兹》、《LOVE》、《夜の歌》等……犬夜叉系列《送魂歌~魂送りの歌》《four seasons》、《Every Heart》《ANGELUS》等……KEY社系列歌曲《团子大家族》、《小手~小さなてのひら》、《florescence》、《时を刻む呗》等都是被大家熟悉的一些歌曲作品！ 无法都例举到，绯儿用甜美的嗓音和打动人心的感情感染着越来越多的人……