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

2024-03-11 03:04
文章标签 设计 问题 功能 详细 华容道 求解 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));}}

函数中增加了 动画部分，因此做了相应的处理，这一部分将在后文赘述。

回放时，需要用户点击回放按钮。也支持了Undo功能，以方便用户观察棋子的移动过程。目前，执行Undo功能时没有做动画处理。

说明如下：
首先在下拉列表中选择一个布局的Hash值，例如第一个（就应该是最少步骤那个，BFS决定的）
在这里插入图片描述

点击[>>],棋子移动一步

在这里插入图片描述
点击[<<]，恢复到上一步

在这里插入图片描述
（待续）
MaraSun BJFWDQ
2024-03-10

这篇关于华容道问题求解_详细设计(五）之hash值和回放功能的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/796394。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
usaco 1.2 Milking Cows（类hash表）

usaco 1.2 Milking Cows（类hash表）

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时！！ 第一种思路：我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2