s*l
2 楼
我还是贴到学术版来问算了。闺版的人不知道是不懂还是不屑。
发信人: stlstl (射天狼), 信区: JobHunting
标 题: 一个方阵途径问题，有点类似 travelling salesman problem
发信站: BBS 未名空间站 (Mon Oct 7 18:41:41 2013, 美东)
由于数学底子不行，不知道这样的问题该怎么解决，请牛们指教。
问题有点类似于 travelling salesman problem，但是有些不同。找了一下，大概和这
个网站的游戏类似：
http://www.coolmath-games.com/0-b-cubed/index.html
简单描述一下，希望能说明白。比如说有一个6x7的方阵，有总共42块方砖，其中一个
是起点，另外一个是目的地。要求从起点到目的地，最简单的时候是每一个方块都要经
过一次而且只有一次。复杂的情况就是某些方块不存在了，或者某些方块需要经过且必
须经过两次（或者更多次）。
怎么设计产生这样的方阵，或者怎么解决已提供的方阵是否有解。
发信人: stlstl (射天狼), 信区: JobHunting
标 题: 一个方阵途径问题，有点类似 travelling salesman problem
发信站: BBS 未名空间站 (Mon Oct 7 18:41:41 2013, 美东)
由于数学底子不行，不知道这样的问题该怎么解决，请牛们指教。
问题有点类似于 travelling salesman problem，但是有些不同。找了一下，大概和这
个网站的游戏类似：
http://www.coolmath-games.com/0-b-cubed/index.html
简单描述一下，希望能说明白。比如说有一个6x7的方阵，有总共42块方砖，其中一个
是起点，另外一个是目的地。要求从起点到目的地，最简单的时候是每一个方块都要经
过一次而且只有一次。复杂的情况就是某些方块不存在了，或者某些方块需要经过且必
须经过两次（或者更多次）。
怎么设计产生这样的方阵，或者怎么解决已提供的方阵是否有解。
p*g
3 楼
网上查状态
M*e
4 楼
hamiltonian path problem?
如果一个方格要经过n次，就画n vertices?
【在 s****l 的大作中提到】
: 我还是贴到学术版来问算了。闺版的人不知道是不懂还是不屑。
: 发信人: stlstl (射天狼), 信区: JobHunting
: 标 题: 一个方阵途径问题，有点类似 travelling salesman problem
: 发信站: BBS 未名空间站 (Mon Oct 7 18:41:41 2013, 美东)
: 由于数学底子不行，不知道这样的问题该怎么解决，请牛们指教。
: 问题有点类似于 travelling salesman problem，但是有些不同。找了一下，大概和这
: 个网站的游戏类似：
: http://www.coolmath-games.com/0-b-cubed/index.html
: 简单描述一下，希望能说明白。比如说有一个6x7的方阵，有总共42块方砖，其中一个
: 是起点，另外一个是目的地。要求从起点到目的地，最简单的时候是每一个方块都要经
如果一个方格要经过n次，就画n vertices?
【在 s****l 的大作中提到】
: 我还是贴到学术版来问算了。闺版的人不知道是不懂还是不屑。
: 发信人: stlstl (射天狼), 信区: JobHunting
: 标 题: 一个方阵途径问题，有点类似 travelling salesman problem
: 发信站: BBS 未名空间站 (Mon Oct 7 18:41:41 2013, 美东)
: 由于数学底子不行，不知道这样的问题该怎么解决，请牛们指教。
: 问题有点类似于 travelling salesman problem，但是有些不同。找了一下，大概和这
: 个网站的游戏类似：
: http://www.coolmath-games.com/0-b-cubed/index.html
: 简单描述一下，希望能说明白。比如说有一个6x7的方阵，有总共42块方砖，其中一个
: 是起点，另外一个是目的地。要求从起点到目的地，最简单的时候是每一个方块都要经
M*e
5 楼
这个图应该是bipartite的，我查了一下wiki,
Andreas Bjrklund provided an alternative approach using the inclusion–
exclusion principle to reduce the problem of counting the number of
Hamiltonian cycles to a simpler counting problem, of counting cycle covers,
which can be solved by computing certain matrix determinants. Using this
method, he showed how to solve the Hamiltonian cycle problem in arbitrary n-
vertex graphs by a Monte Carlo algorithm in time O(1.657^n); for bipartite
graphs this algorithm can be further improved to time O(1.414^n).[5]
【在 M*****e 的大作中提到】
: hamiltonian path problem?
: 如果一个方格要经过n次，就画n vertices?
Andreas Bjrklund provided an alternative approach using the inclusion–
exclusion principle to reduce the problem of counting the number of
Hamiltonian cycles to a simpler counting problem, of counting cycle covers,
which can be solved by computing certain matrix determinants. Using this
method, he showed how to solve the Hamiltonian cycle problem in arbitrary n-
vertex graphs by a Monte Carlo algorithm in time O(1.657^n); for bipartite
graphs this algorithm can be further improved to time O(1.414^n).[5]
【在 M*****e 的大作中提到】
: hamiltonian path problem?
: 如果一个方格要经过n次，就画n vertices?
s*l
6 楼
你是蝗虫的马甲吧，怎么也是百科全书编译出来的。
【在 M*****e 的大作中提到】
: hamiltonian path problem?
: 如果一个方格要经过n次，就画n vertices?
【在 M*****e 的大作中提到】
: hamiltonian path problem?
: 如果一个方格要经过n次，就画n vertices?
M*e
7 楼
过奖了。
每一步的方向有限制吗？这个图这么特殊，应该有更简单方法。
【在 s****l 的大作中提到】
: 你是蝗虫的马甲吧，怎么也是百科全书编译出来的。
每一步的方向有限制吗？这个图这么特殊，应该有更简单方法。
【在 s****l 的大作中提到】
: 你是蝗虫的马甲吧，怎么也是百科全书编译出来的。
s*l
8 楼
没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
【在 M*****e 的大作中提到】
: 过奖了。
: 每一步的方向有限制吗？这个图这么特殊，应该有更简单方法。
我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
【在 M*****e 的大作中提到】
: 过奖了。
: 每一步的方向有限制吗？这个图这么特殊，应该有更简单方法。
M*e
9 楼
那么方格最高次数大概是什么量级？
【在 s****l 的大作中提到】
: 没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
: 我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
【在 s****l 的大作中提到】
: 没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
: 我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
s*l
10 楼
2，3次吧。就算2次，如果好解一些。
【在 M*****e 的大作中提到】
: 那么方格最高次数大概是什么量级？
【在 M*****e 的大作中提到】
: 那么方格最高次数大概是什么量级？
s*l
11 楼
大部分的方格都是一次且必须一次，偶尔有一两个方格（节点）是两次且必须两次的。
【在 M*****e 的大作中提到】
: 那么方格最高次数大概是什么量级？
【在 M*****e 的大作中提到】
: 那么方格最高次数大概是什么量级？
R*a
12 楼
6x7的还是穷举省事
【在 s****l 的大作中提到】
: 没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
: 我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
【在 s****l 的大作中提到】
: 没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
: 我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
s*l
13 楼
每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
【在 R***a 的大作中提到】
: 6x7的还是穷举省事
【在 R***a 的大作中提到】
: 6x7的还是穷举省事
M*e
14 楼
可能是太穷的缘故。现代社会太物质了。
【在 s****l 的大作中提到】
: 每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
【在 s****l 的大作中提到】
: 每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
H*g
15 楼
如果每个方格一次且仅一次：
每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
数从0到4：
1，如果有1个结点外部连接为(0)显然无解，
2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
个是终点
3，连接为(2)的结点只有一种连接方式
4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
连接必须断开。可以循环使用这个规则，简化路径。
5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
不确定上面这几条能不能保证充分性。
不过如果只是设计游戏的话，如果你先设计好路径，然后往路径里加方块，就可以保证
有解。不过这样不能保证有唯一解。
每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
数从0到4：
1，如果有1个结点外部连接为(0)显然无解，
2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
个是终点
3，连接为(2)的结点只有一种连接方式
4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
连接必须断开。可以循环使用这个规则，简化路径。
5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
不确定上面这几条能不能保证充分性。
不过如果只是设计游戏的话，如果你先设计好路径，然后往路径里加方块，就可以保证
有解。不过这样不能保证有唯一解。
R*a
16 楼
肯定可以穷举的啊。
矩阵里每个格子的值就是可以访问的次数。
访问一次这个格子，格子值--.
如果四周格子值都是0了，算fail。
如果到了终点以后还有格子值不是0，算fail就成了
【在 s****l 的大作中提到】
: 每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
矩阵里每个格子的值就是可以访问的次数。
访问一次这个格子，格子值--.
如果四周格子值都是0了，算fail。
如果到了终点以后还有格子值不是0，算fail就成了
【在 s****l 的大作中提到】
: 每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
s*l
17 楼
你真是人才
我好好琢磨一下
【在 H********g 的大作中提到】
: 如果每个方格一次且仅一次：
: 每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
: 数从0到4：
: 1，如果有1个结点外部连接为(0)显然无解，
: 2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
: 个是终点
: 3，连接为(2)的结点只有一种连接方式
: 4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
: 连接必须断开。可以循环使用这个规则，简化路径。
: 5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
我好好琢磨一下
【在 H********g 的大作中提到】
: 如果每个方格一次且仅一次：
: 每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
: 数从0到4：
: 1，如果有1个结点外部连接为(0)显然无解，
: 2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
: 个是终点
: 3，连接为(2)的结点只有一种连接方式
: 4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
: 连接必须断开。可以循环使用这个规则，简化路径。
: 5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
s*l
18 楼
上面给出的网页里面的也不是唯一解。关键是要有解。
【在 H********g 的大作中提到】
: 如果每个方格一次且仅一次：
: 每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
: 数从0到4：
: 1，如果有1个结点外部连接为(0)显然无解，
: 2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
: 个是终点
: 3，连接为(2)的结点只有一种连接方式
: 4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
: 连接必须断开。可以循环使用这个规则，简化路径。
: 5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
【在 H********g 的大作中提到】
: 如果每个方格一次且仅一次：
: 每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
: 数从0到4：
: 1，如果有1个结点外部连接为(0)显然无解，
: 2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
: 个是终点
: 3，连接为(2)的结点只有一种连接方式
: 4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
: 连接必须断开。可以循环使用这个规则，简化路径。
: 5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
H*g
19 楼
要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
面狂加分岔路。
【在 s****l 的大作中提到】
: 上面给出的网页里面的也不是唯一解。关键是要有解。
面狂加分岔路。
【在 s****l 的大作中提到】
: 上面给出的网页里面的也不是唯一解。关键是要有解。
R*a
20 楼
如何保证没有比期望解的更优解呢？
【在 H********g 的大作中提到】
: 要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
: 面狂加分岔路。
【在 H********g 的大作中提到】
: 要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
: 面狂加分岔路。
H*g
21 楼
你要是设计游戏的话，如果是明显有多重解游戏乐趣会很低，无解也很挫折。
如果多重解的话，我觉得得像windows自带游戏里像蜘蛛纸牌和空当接龙这样路径比较
深，解也不是特别多的才可以。空当接龙虽然11902也无解，但是大部分还是有解的。
那个纸牌经常无解就没意思了。
【在 s****l 的大作中提到】
: 上面给出的网页里面的也不是唯一解。关键是要有解。
如果多重解的话，我觉得得像windows自带游戏里像蜘蛛纸牌和空当接龙这样路径比较
深，解也不是特别多的才可以。空当接龙虽然11902也无解，但是大部分还是有解的。
那个纸牌经常无解就没意思了。
【在 s****l 的大作中提到】
: 上面给出的网页里面的也不是唯一解。关键是要有解。
H*g
22 楼
故意把假路的都设计成死路。换句话说，每个假路跟主干路只有一个连接。
不过分叉路如果不很多的话其实也可以，比如一个岔路跟主路有两三个连接点，但是几
个连接点离得很近，这样就可以避免出现大量的次优解：
岔路 -------------------------继续乱分岔
| ||
主路--------------------------------------------------------------->终点
【在 R***a 的大作中提到】
: 如何保证没有比期望解的更优解呢？
不过分叉路如果不很多的话其实也可以，比如一个岔路跟主路有两三个连接点，但是几
个连接点离得很近，这样就可以避免出现大量的次优解：
岔路 -------------------------继续乱分岔
| ||
主路--------------------------------------------------------------->终点
【在 R***a 的大作中提到】
: 如何保证没有比期望解的更优解呢？
H*g
23 楼
哈哈，freecell解答全集
http://freecellgamesolutions.com/i/?i=120
这个网站看起来是即时计算解答路径的。输入11902会跳一个张老三出来解答。
【在 H********g 的大作中提到】
: 你要是设计游戏的话，如果是明显有多重解游戏乐趣会很低，无解也很挫折。
: 如果多重解的话，我觉得得像windows自带游戏里像蜘蛛纸牌和空当接龙这样路径比较
: 深，解也不是特别多的才可以。空当接龙虽然11902也无解，但是大部分还是有解的。
: 那个纸牌经常无解就没意思了。
http://freecellgamesolutions.com/i/?i=120
这个网站看起来是即时计算解答路径的。输入11902会跳一个张老三出来解答。
【在 H********g 的大作中提到】
: 你要是设计游戏的话，如果是明显有多重解游戏乐趣会很低，无解也很挫折。
: 如果多重解的话，我觉得得像windows自带游戏里像蜘蛛纸牌和空当接龙这样路径比较
: 深，解也不是特别多的才可以。空当接龙虽然11902也无解，但是大部分还是有解的。
: 那个纸牌经常无解就没意思了。
H*g
24 楼
stlstl看看这个：freecell stats
http://freecellgamesolutions.com/stats.html
http://freecellgamesolutions.com/stats.html
s*l
25 楼
你阅读太广泛了，呵呵。
谢谢了。
【在 H********g 的大作中提到】
: stlstl看看这个：freecell stats
: http://freecellgamesolutions.com/stats.html
谢谢了。
【在 H********g 的大作中提到】
: stlstl看看这个：freecell stats
: http://freecellgamesolutions.com/stats.html
H*g
26 楼
这个想法不对。如果要求所有的格子都遍历的话，后加的东西必须也是能遍历的。
【在 H********g 的大作中提到】
: 要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
: 面狂加分岔路。
【在 H********g 的大作中提到】
: 要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
: 面狂加分岔路。
M*n
27 楼
蝗虫太牛鼻了！到底是什么背景？
相关阅读
慎入毛新宇和妻子、儿子How are you? 怎么翻译最贴切? (转载)Re: 老公晚上睡觉磨牙怎么办啊？ (转载)如何将旧车倒回国（学术）有个ID叫mitbbs的... (转载)那晚上孝庄太后对洪成畴说了些什么 (转载)女友要你吃她嚼过10分钟的口香糖 (转载)收拾非处女友 (转载)学术讨论一下 真的吗扯妻内裤硬上 性侵还辩称性急Huan2007 封 kettle 在 Joke 版Re: 怀疑老婆出轨，这有道理吗？(ZT) (转载)直升飞机原地升空不动,能到美国吗?谁去applestore干点坏事 (转载)这个毛新宇是毛泽东孙子的可能性有多大？ (转载)才知道，人民币升值中国赚大了 (转载)best movie ever请问如何赚到第一个一百万美元? (转载)女朋友很怪的僻好，纠节是分还是离