典型的回溯算法问题

1、典型的回溯算法问题一、购票问题有2n个人排队购一件价为0.5元的商品，其中一半人拿一张1元人民币，另一半人拿一张0.5元的人民币，找出所有排队的方案。问这2n个人应该如何排队？(2)该问题可以用二进制数表示：用0表示持0.5元的人，么2n个人排队问题化为2n个0、1的排列问题。这里我们用数组2n存放持币情况。(3)设k是B数组下标指针，BK=0或BK=1,另用数组用1表示持1元的人，那B1.d0、d1记录0与1的个数，且必须满足：nd0=d1。要使售货员在售货中，不发生找钱困难，(售货员一开始就没有准备零钱)分析：(1)根据题意可以看出，要使售货员在售货中，不发生找钱困难，则在排队中，应该是任

2、何情况下，持0.5元的排在前面的人数多于持1元的人数。(4)算法：回溯搜索。0，(a)先将B1、B2、B2n置1,从第一个元素开始搜索，每个元素先取再取1,即BK+1DBK,试探新的值，若符合规则，增加一个新元素；(b)若k2n,则k+1Dk,试探下一个元素，若k=2n则输出B1、B2,B2n。(c)如果BK的值不符合要求，则BK再加1,试探新的值，若BK=2,表示第k个元素的所有值都搜索过,均不符合条件,只能返回到上一个元素BK1,即回溯。(d)返回到上一个元素(5)直到求出所有解。k：=k1,并修改D0、D1。二、骑士游历问题在nDn的国际象棋上的某一位置上放置一个马，规则，要求这个马能不

3、重复地走完nDn个格子,试用计算机解决这个问题。分析：本题是典型的回溯算法问题,设骑士在某一位置,设步可以是如图(n=5)所示的8个位置之一。然后采用象棋中“马走日字”的(X,Y),按规则走,下一我们将重点考虑前进的方向：如果某一步可继续走下去,就试探着走下去且考虑下一步的走法,若走不通则返回,考虑另选一个位置。三、四色问题设有如图1的地图，每个区域代表一个省，区域中的数字表示省的编号，现在要求给每个省涂上红、蓝、黄、白四种颜色之一，同时使相邻的省份以不同的颜色区分。图2图1分析：（1）本题是图论中的一个搜索问题，我们可以将该问题简化：将每个省看着一个点，而将省之间的联系看作一条边，可以得到如

4、图2所示图形。（2）从图2可以知道各省之间的相邻关系，我们可以数据阵列表示矩阵，即用一个二维数组来表示：Rx，y=1表示省x与省y相邻0表示省x与省y不相邻由图2可以得到如下矩阵0100001101111101010000110100010101001001011100010（3）从编号为1的省开始按四种颜色顺序填色，当第一个省颜色与相邻省颜色不同时，就可以确定第一个省的颜色，然后，再依次对第二、第三，进行处理，直到所有省份颜色都涂上为止。（4）问题关键在于在填色过程中，如果即将填的颜色与相邻省的颜色相同，而且四种颜色都试探过，均不能满足要求，则需要回溯到上一个点（即前一个省），修改上一个省的

5、颜色，重新试探下一个省的颜色。四、填数问题在n*n的棋盘上（1二n=10）填入1,2,3,n*n,共有n*n个数，使得任意两个相邻数的和为素数。例如：当n=2时，有：当n=4时，一种可以填写的方案如下表，在这里我们约定：左上角的格子里必须填数字1。程序要求：输入n；输出：有多个解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！”12111216158513491467103分析：（1）从问题可以看出这是一个搜索问题，是素数的任务。程序中必须完成判断相邻两个数的和是否（2）如果一边填数，一边求和及判断素数，程序运行速度将大大减慢，所以我们可以采用数组结构，将2Dn*n之间所有素数存放在一个数组中。由于问题中指出n=10,所以，最大的相邻两个数的和是：99+100200。我们只需要将2D200之间的素数存放在数组中就可以了。（3）按行、列填入数据，并求相邻两个数的和，将其与素数数组比较，若是素数，则当前格可以填数，继续填数。若当前格没有数据可以填，则要回溯到上一格，重新填写上一格数据，再进行判断。数据结构：T表示1Dn*n之间的数是否用过，false表示