1. 车厢调度(难度**)
一列货运列车共有n节车厢,每节车厢将停放在不同的车站。假定n个车站的编号分别为
1 ~n,货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢,必须重新排列车厢,使各车厢从前至后按编号1到n的次序排列。当所有的车厢都按照这种次序排列时,在每个车站只需卸掉最后一节车厢即可。我们在一个转轨站里完成车厢的重排工作,在转轨站中有一个入轨、一个出轨和k个缓冲铁轨(位于入轨和出轨之间),每个缓冲铁轨的容量小于总车厢个数的1/k。图5-5a 给出了一个转轨站,其中有k= 3个缓冲铁轨H1,H2和H3,每个缓冲铁轨的容量为2个车厢。开始时,n节车厢的货车从入轨处进入转轨站,转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站(通过出轨处)。在图5-5a 中,n= 9,车厢从后至前的初始次序为5,8,1,7,4,2,9,6,3。如下图所示,给出了按所要求的次序重新排列后的结果。
具有三个缓冲铁轨的转轨站 a) 开始 b) 结束
要求:对于给定的初始状态与终止状态,判断是否能在指定缓冲铁轨的容量条件下调度成功,如果能,请输出调度的过程。