大塞车游戏活动的算法解
最近在公司组织的培训上，遇到了一个很有意思的算法题，这篇文章就借这个为题提供一个解。
解的代码用Java实现，并配有演示，已经放到了github上https://github.com/neoremind/big-traffic-jam-solver。
首先感谢李培英老师，《职业化研讨》这门课非常值得公司内的一线管理人员去学习。在讲到职业化内涵里的“规则意识”一节时，让大家做了一个简单的大塞车游戏，规则如下：
1、邀请10人以上的学员（注意是偶数，当然越多越好），列成两队，面对面的坐在椅子上。
2、中间叫做“鸿沟”，是不允许越过的。
3、在“鸿沟”的一端，有一把空椅子，暂且把靠近这一端的队叫做队头。
4、要求两队只能通过空椅子这条路来交换位置，自己只允许两种行动方式，第一往前走一步，第二可以隔着对方跳一步。
例如，分为A，B两队，每队8人，初始状态如下：
A8 | A7 | A6 | A5 | A4 | A3 | A2 | A1 | -------------------------------------- 鸿沟 | | -------------------------------------- B8 | B7 | B6 | B5 | B4 | B3 | B2 | B1 | |
那么第一步只有一种选择，A1或者B1有一个人去空位，然后下面的继续，按照规则，要达到这种最终状态：
B8 | B7 | B6 | B5 | B4 | B3 | B2 | B1 | -------------------------------------- 鸿沟 | | -------------------------------------- A8 | A7 | A6 | A5 | A4 | A3 | A2 | A1 | |
可以走的规则如下，出现下面的两种情况A4可以行动，要么走要么跳，也就是走或者跳到空格，否则A4是动不了的。
| A4 | | A3| | A4 | B3 | | A3 | |
有兴趣的读者可以自己组织一些同学试试，会非常容易陷入迷茫的，走不下去了。当然不排除聪明的学员们能够很快的解决:-)
这道题老师想表达的是规则一部分是看得见的客观存在，另外一大部分是看不见的，总结其规律往往较为困难，但是我们应用尊重规则，这里面的道理可能很多人看不到，但是他是简单有效的，anyway，圆规正传，本文是解题：
如果你让1万人做这个游戏，你怎么用通俗的语言告诉每一个人规则，让他们怎么行动？
我总结的规律如下：
1、任意一方先行动，做到空椅子，行动权转移到另一方。
2、如果前面是对方，则跳过去。
3、如果前面的前面是对方，或者前面全是自己人，或者前面就是终点了，则“贪婪地”往前走一步。
4、如果前面的前面是自己人，就别动了，交换行动权到对方的队头。
按照这种规则，我的算法放到了github上，具体演示见下面的gif图。
每队1人：
每队2人：
每队3人：
每队4人：
每队5人：
这道题目，重点在于总结这个行动的规则，并且用算法描述实现，大言不惭的说可以post到leetcode上了，看谁能解了，我的解法不一定最好，边界条件的判断非常多，需要小心处理。
算法入口如下，BigTrafficJam构造函数是两队人数加上空椅子的个数，所以是一个大于等于3的奇数，调用solve方法即可：
new BigTrafficJam(17).solve(); //new BigTrafficJam(17).setDebug(false).solve(); //用于打印中间状态的debug信息与否 //new BigTrafficJam(17).setPrintOutIntervalMs(1200).solve(); //如果打印debug信息，中间停顿的毫秒数 |
最后，还是回到《职业化研讨》这门课上，体会最深的一句管理的话就是“管理就是激发人善意的潜能”。
转载请注明转自neoremind.com。
附录：
回调下另外读后感作者鲍老师的博文再谈大塞车游戏活动，证明了本文所述的最优解法，同时给出了模拟算法的时间复杂度为O(n^2)。
我这里有个思路：
第一阶段：将AAAAAAAAA……A*B……BBBBBBBBB经过特定步骤后转化为*BABABABA………BA或者BABABA…….BA*
第二阶段：将第一阶段的结果经过特定步骤后转化为BBBBBBBBBBB……B*A……AAAAAAAAA
两阶段整体的思路都类似于数学归纳法，或者计算机上讲也可以叫分治。
先讲第一阶段，通俗点用数学归纳法的步骤：
1. 初始状态AAAAAAAAAA……A*B……BBBBBBBBBB，A向右走一步，然后B向左跳过A，变成了AAAAAAAAA……ABA*B……BBBBBBBBB
2. 若中间状态为AAAAAA……ABABABA……BA*B……BBBBBB，则B向左一步后，左边的A都向右跳过来，变成了AAAAAA……A*BABABA……BAB……BBBBBB，其中，BA对组合多了一对；
3. 若中间状态为AAAAAA……A*BABABA……BAB……BBBBBB，则A向右一步后，右边的B都向左跳过来，变成了AAAAAA……ABABABA……BA*B……BBBBBB，其中，BA对组合多了一对；
4. 不断重复2、3过程，最终可以达到第一阶段的两种情况之一；
第二阶段其实是第一阶段反操作的过程，仔细推敲下也能从理论上证明出来，不再详述