关于修桥（Hashi）游戏解题算法

lee1892

wcymiss 发表于 2015-9-6 23:11
先上个能出结果的，代码没优化，效率先不考虑。

测试了几个，突然发现你这个代码会出错误答案：

1. 0202030202002101000000000002000000020102002070600303030000000000000040503010102020102030402020000000100000020002000202030020002002020300020002000000000102011003030303020

复制代码

13x13的，左边一列孤立了

wcymiss

今天出差在外，白天没空写，晚上回去看看

话说，没人应战，你是不是觉得很无聊啊？哈哈{:soso_e113:}

wcymiss

lee1892 发表于 2015-9-7 10:54
测试了几个，突然发现你这个代码会出错误答案：

13x13的，左边一列孤立了

嗯，真没注意还有连通的要求。

lee1892

wcymiss 发表于 2015-9-7 14:33
今天出差在外，白天没空写，晚上回去看看

话说，没人应战，你是不是觉得很无聊啊？哈哈

不无聊呀，做题才是乐趣。

我就惦记着你说过要写代码的，一直没发，算法也是语言描述了一下，数据结构设计我也没提，生怕扰了你的兴致，我多好啊~

Moneky

写了个随机的，结果无用。看来还是要动下脑子是正路。

wcymiss

经过几天努力，终于完工，效率应该还可以吧。试了25*25的第22个，可以秒杀。{:soso_e182:}

修桥题-wcymiss.rar (25.24 KB, 下载次数: 120)

2015-9-10 15:02 上传

点击文件名下载附件

代码思路:
1、将岛屿、邻岛、经过点，都整理为一维n*n行的数据，有关方向数据的，为(n*n行4列)大小的数组
2、经过点的数组(n*n行4列)大小，每个元素是一个数组，包含m个经过点索引号
3、创建一个(n*n行4列)大小的数组，储存每个经过点四周的岛屿索引号
4、创建一个动态修桥信息表(n*n行7列)，包含每个岛屿的：
   每个方向可修桥数(1至4列，数据不可超过2),可修桥的邻岛个数(5)，可修桥总数(6)，需修桥数(7)
   创建一个动态的已修桥数组 (n * n行4列)
5、先行判断:
   需修桥数均为1的的两个岛不能修桥 (会造成孤链)
   需修桥数均为2的的两个岛最多只能修1座桥 (修2座会造成孤链)
6、判断必然的修桥情况(整理了3种)，进行修桥
   需修桥数=可修桥总数，则修所有的桥
   需修桥数=有可修桥的邻岛的个数*2-1，则每个邻岛至少修一座桥
   需修桥数=总可修桥数-1，则，可修2座桥的邻岛至少修一座桥
   修桥时，动态数组变化：
   增加已修桥数
   减少桥两端岛屿的可修桥明细、个数、总数，需修桥数
   减少桥两端岛屿的邻岛的可修桥明细?个数?总数
   修桥经过点的交叉方向的两个岛切断联系(可修桥为明细为0，个数-1，总数减少)
7、搜索一个未完成修桥的岛，进行尝试修桥
8、同第6步
9、进行总共已修桥个数与连通性判断。失败则重复7、8、9，直到成功

假如公共变量全作为过程的参数进行传递恐怕要降低一部分效率。

lee1892

wcymiss 发表于 2015-9-10 12:59
经过几天努力，终于完工，效率应该还可以吧。试了25*25的第22个，可以秒杀。

非常棒，好玩的逻辑游戏我这还有很多呀，咱慢慢来。

就你的描述而言，对算法和数据结构设计，我还是有些建议的，嗯嗯～

wcymiss

lee1892 发表于 2015-9-10 17:06
非常棒，好玩的逻辑游戏我这还有很多呀，咱慢慢来。

就你的描述而言，对算法和数据结构设计，我还是有 ...

好的，慢慢来，慢慢跟大师学算法。努力学习，努力做题。

做题最希望能得到老师的点评了。非常期待

lee1892

wcymiss 发表于 2015-9-10 18:20
好的，慢慢来，慢慢跟大师学算法。努力学习，努力做题。

做题最希望能得到老师的点评了。非常期待

别，我最不喜欢当老师了，说说我的看法吧，仅对你的文字描述。

先说数据结构。
1，你实际上是用二维数组干自定义数据类型的事，当然可以实现，但显然代码的可读性很差，写代码的时候也非常考验记性。
2，你没有为桥分配内存，而是用经过的格子来储存桥之间的干涉信息，以动态查找，想来在处理建桥后代码会比较繁琐。
3，可以不需要用NxN这么多元素，有多少个岛就用多少元素就行，其行列位置可以作为岛的属性，然后岛有如下属性：数字，剩余数字、四个方向的邻岛编号、四个方向的可建桥的编号、四个方向已建桥的值，所有连接可能。桥的处理，先把所有可能的桥进行编号，通过其经过的格子可以找出哪些桥是互相干涉的，桥的属性有：连接的岛的编号、与其干涉的桥的编号集合、是否水平等，桥可以设成静态的，备查用。以上这些信息的收集都是O(N)过程。

再说算法方面的
1、我在1楼里说的办法其实是个通用的逻辑归纳，你提到的几个都是特例。
      a、初始可能的简单排除，应该是该可能所连的所有数字之和等于该数字时予以排除，除1-1，2=2外，还有如3-1/1/1，3-1/2，4-1/1/2，4-2/2，5-1/2/2，6-2/2/2等
      b、前面提到的一个岛的全部连接可能性的收集其实是简单的组合计算，以一个4的岛其左1右3下2为例，则是由'左右右下下'中取四个的所有不重复组合，就构成左右右下，左右下下，右右下下，共三个可能，其中右下总是存在，所以右下这两个方向都至少要建一个桥。注意，这是一个通用的逻辑，而且贯穿整个解题过程，只是在初始化后，要使用剩余数字这个属性而已。上述的这个4的岛，建桥后，其剩余数字为2，可能连接则为左右，左下和右下。这和你所说的步骤6有根本的不同，更重要的是你的这个步骤6更像是一个初始化的过程，而不是解题循环办法。如果是这样的话，你的代码基本只能算暴力计算，而不是逻辑解题了。
2、1楼贴里提到的建桥后形成闭环的逻辑你没有做，实际做题时会经常用到的。
3、桥的建立导致其它桥的不能建立，进而导致某岛的连接数不够，这个逻辑我也没做，但实际做题时也会经常碰到，尤其难度高的。

逻辑解题，就是一个由简单逻辑到复杂逻辑不断循环查找的过程，一旦有变化，则再循环，只有在所有办法都用过后而没有变化才开始试错。

你的代码之所以快，就是因为用的逻辑太少了，而这个题暴力尝试是很快的，因为基本不会形成错误步骤树。

没看你代码，有说错的包涵，供参考

wcymiss

lee1892 发表于 2015-9-10 20:03
别，我最不喜欢当老师了，说说我的看法吧，仅对你的文字描述。

先说数据结构。

{:soso_e154:}没有一点优点啊，昨天做出题的成就感“噗”的一下全没了。。

1，你实际上是用二维数组干自定义数据类型的事，当然可以实现，但显然代码的可读性很差，写代码的时候也非常考验记性。
的确，下次改进。。

2，你没有为桥分配内存，而是用经过的格子来储存桥之间的干涉信息，以动态查找，想来在处理建桥后代码会比较繁琐。
这个没想过，后期试试。

3，可以不需要用NxN这么多元素，有多少个岛就用多少元素就行，其行列位置可以作为岛的属性，
我在得出岛的总个数后对数组进行Redim了。

然后岛有如下属性：数字，剩余数字、四个方向的邻岛编号、四个方向的可建桥的编号、四个方向已建桥的值，所有连接可能。
除了没有“连接可能”，其他数据都建了。“连接可能”在我之前写的几个版本里试过，感觉慢，所以弃用了。。

桥的处理，先把所有可能的桥进行编号，通过其经过的格子可以找出哪些桥是互相干涉的，桥的属性有：连接的岛的编号、与其干涉的桥的编号集合、是否水平等，桥可以设成静态的，备查用。以上这些信息的收集都是O(N)过程。
这个我觉得好复杂。。


初始可能的简单排除，应该是该可能所连的所有数字之和等于该数字时予以排除，除1-1，2=2外，还有如3-1/1/1，3-1/2，4-1/1/2，4-2/2，5-1/2/2，6-2/2/2等
这个我觉得判断起来麻烦。。虽然的确应该这样做。。

以一个4的岛其左1右3下2为例，则是由'左右右下下'中取四个的所有不重复组合，就构成左右右下，左右下下，右右下下，共三个可能，其中右下总是存在，所以右下这两个方向都至少要建一个桥
你这个就类似我的：需修桥数=总可修桥数-1，则，可修2座桥的邻岛至少修一座桥。4的岛其左1右3下2，其实就是4-1/2/2，4=1+2+2-1，所以两个2的地方至少要建一座桥

1楼贴里提到的建桥后形成闭环的逻辑你没有做
我觉得反正是否闭合要等到最后才能看得出，那我不如最后一次性判断了

桥的建立导致其它桥的不能建立，进而导致某岛的连接数不够
嗯，这个我可以在我的数据上加一个判断。

另外，大师的代码可否发上来学习下？