华容道问题求解_详细设计(五）之hash值和回放功能

本文主要是介绍华容道问题求解_详细设计(五）之hash值和回放功能，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

（续上文）

布局的hash 值计算

笔者也参考了之前的一些文章，很多文章提到了怎么节省存贮空间来查找最优解，这不是笔者的目的。笔者的目的比较单一，就是找到最优解就行了。因此并没有在存贮上面进行过多的优化，曾经尝试使用移位指令进行棋子的移动，然而并没有发现运行速度比使用庞大的对象速度更快。（或许是算法的问题）因此索性就使用了高级语言的高级方法，放弃了对存贮空间的限制和约束。基于前面的设计，每个布局保存在一个4*5的整数数组里面（保存的棋子的ID），因此为了简单起见笔者将这个20个整数构成一个字符串，然后利用C#提供的现有的字符串hash函数，就得到了这个布局的hash值。这个方法简单粗暴，并不美丽，但是解决问题就行了。
一个细节：在实际棋子的移动过程当中，我们关心的是棋子的形状而非棋子的名字，因此在棋子布局的时候，尽管每个棋子都赋予了名字，在进行查找的时候，是忽略了这些名字的。因此在使用DFS结合Dijkstra 算法查找时会出现名字改变的情况，这里笔者没有对名字进行一致处理，因为这种处理对解法其实没有什么帮助，只是界面看着更连贯些。（具体原因也不解释了，很简单）。在BFS的查找过程当中，不会有这个问题。
hash 函数如下：

      public int GetMyHashCode(GameState gameState){string val = string.Empty;for (int i = 1; i <= 4; i++){for (int j = 1; j <=5; j++){var pcs  = gameState.layoutOfObj[i, j];val += pcs.GetHrdType().ToString();}}return val.GetHashCode();}

注意上面只取了Type值进行hash处理。

回放功能

找到了解法，还要能进行回放，否则也看不到效果，也不能证明是否成功了，因此增加回放功能很有必要。
回放功能，就是记录每个布局的hash值和布局，然后根据hash值从布局记录中查找对应的布局，在映射到UI上就可以了。

最佳结果保存在如下定义的数据字典里

       // the shorest path will be stored in the following variable.// key:the hash code of the current layout, value.item1, the hashcode of the source layout , item2 the number of the shortest steps.Dictionary<int, (int,int)> hCodeAndShotShortPathDict = new Dictionary<int, (int,int)>();

hash值和布局快照保存在如下定义的数据字典中

// store the hash code and the layout shot , selpcs index,dstPcs.idx Dictionary<int, (Piece[],int,int)> hCodeAndShotDict = new Dictionary<int, (Piece[], int, int)>();

回放时，将这两个数据字典结合起来，就可以找到快照，将快照映射到界面上就可以了。

具体的保存过程

DFS中的用了Dijkstra 算法，算法本身就包括了最短路径的记录，因此这里不再赘述。
BFS算法中，找到的方法都是对应不同布局的最佳步骤，因此在尝试移动棋子的过程当中，记录当前的布局就可以了。
代码如下：
在AddEdgeToGraph 中的函数AdjustShortPath 就是用于记录解法的。

       private void AddEdgeToGraph(StateShot source, StateShot dest){var toHashCode = GetMyHashCode(dest);var frmHashCode = GetMyHashCode(source);AdjustShortPath(dest, toHashCode, frmHashCode);AddEdge(frmHashCode, toHashCode, 1);}private void PushState(StateS

AdjustShortPath 代码如下：

      private void AdjustShortPath(StateShot dest, int toHashCode, int frmHashCode){(int, int) lastItem;if (hCodeAndShotShortPathDict.TryGetValue(toHashCode, out lastItem)){if (lastItem.Item2 > dest.bestSteps){//这是笔者增加的视图记录最短路径的判断，DFS时，找到了比原来步骤少的方法，但是不是最优的。BFS时，这里执行不到。hCodeAndShotShortPathDict[toHashCode] = (frmHashCode, dest.bestSteps);}//hCodeAndShotShortPathDict.Add(toHashCode, (dest.basePcs, selPcs.idx, dstPcs.idx, frmHashCode, pathLen));}else{// 查找过程记录，BFS时，记录的就是最佳结果hCodeAndShotShortPathDict.Add(toHashCode, (frmHashCode, dest.bestSteps));}}

回放过程

程序先找到要回放的结果布局，然后将这个结果布局的对应的保存的所有过程布局，放到一个数组中，每执行一步，数组的索引加一，指向下一个过程布局。代码如下：

     private void MoveNext(){//allShortPath = allShortPath2;if (allShortPath == null){MessageBox.Show(string.Format("The shortest path is now being searched ,wait for a moment."), "Notice", MessageBoxButtons.OK, MessageBoxIcon.Exclamation);return;}//solutionPcsIdx 布局数组索引//cbbSolutionIdx 保存在CBB 中的结果布局索引（hash 值）if (solutionPcsIdx >= 0 && solutionPcsIdx < allShortPath[cbbSolutionIdx].Count){if (solutionPcsIdx < allShortPath[cbbSolutionIdx].Count - 1)solutionPcsIdx++;var lastKey = allShortPath[cbbSolutionIdx][solutionPcsIdx - 1];//txt_Notice.Text = string.Format("Layout code:{0} Graph node info {1}\r\n{2}",lastKey, _hrdGame.adjacencyList[lastKey],txt_Notice.Text);var lastLayoutArr = _hrdGame.GetLayoutIdxArrByHashCode(lastKey);var key = allShortPath[cbbSolutionIdx][solutionPcsIdx];var layoutArr = _hrdGame.GetLayoutIdxArrByHashCode(key);//get the moving pieces by comparing the two layoutsvar movedPcs = GetMovedPieces(lastLayoutArr.Item1, layoutArr.Item1);var frmIdx = layoutArr.Item2;var toIdx = frmIdx;// layoutArr.Item3;var srcPcs = movedPcs.Item1;var dstPcs = movedPcs.Item2;var passPcs = movedPcs.Item3;// animation moving var selPos = srcPcs.GetHrdPos();var emptySpPos = dstPcs.GetHrdPos();var passPos = passPcs.GetHrdPos();// the following used to add animation effectvar srcPos = new HrdPoint(selPos.X, selPos.Y);var dstPos = new HrdPoint(emptySpPos.X, emptySpPos.Y);_hrdGame.gameState.pieces = layoutArr.Item1;_hrdGame.MovePcsWithAnimation(srcPcs, srcPos, dstPos, passPos, dstPcs, null);btn_ShowSteps.Text = string.Format("{0}/{1}", solutionPcsIdx, allShortPath[cbbSolutionIdx].Count - 1);//MessageBox.Show(string.Format("Click for next step, current step: {0}/{1}", i, allPath[0].Count));}}