s****l
发帖数: 10462 | 1 我还是贴到学术版来问算了。闺版的人不知道是不懂还是不屑。
发信人: 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
发帖数: 11621 | 2 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块方砖，其中一个
: 是起点，另外一个是目的地。要求从起点到目的地，最简单的时候是每一个方块都要经
|
M*****e
发帖数: 11621 | 3 这个图应该是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?
|
s****l
发帖数: 10462 | 4 你是蝗虫的马甲吧，怎么也是百科全书编译出来的。
【在 M*****e 的大作中提到】
: hamiltonian path problem?
: 如果一个方格要经过n次，就画n vertices?
|
M*****e
发帖数: 11621 | 5 过奖了。
每一步的方向有限制吗？这个图这么特殊，应该有更简单方法。
【在 s****l 的大作中提到】
: 你是蝗虫的马甲吧，怎么也是百科全书编译出来的。
|
s****l
发帖数: 10462 | 6 没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
【在 M*****e 的大作中提到】
: 过奖了。
: 每一步的方向有限制吗？这个图这么特殊，应该有更简单方法。
|
M*****e
发帖数: 11621 | 7 那么方格最高次数大概是什么量级？
【在 s****l 的大作中提到】
: 没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
: 我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
|
s****l
发帖数: 10462 | 8 2，3次吧。就算2次，如果好解一些。
【在 M*****e 的大作中提到】
: 那么方格最高次数大概是什么量级？
|
s****l
发帖数: 10462 | 9 大部分的方格都是一次且必须一次，偶尔有一两个方格（节点）是两次且必须两次的。
【在 M*****e 的大作中提到】
: 那么方格最高次数大概是什么量级？
|
R***a
发帖数: 41892 | 10 6x7的还是穷举省事
【在 s****l 的大作中提到】
: 没有方向，但是有经过的次数限制。次数为零了，就不能再踏上了。
: 我也觉得没有那么复杂。。。不过不知道从哪里下嘴。。。
|
|
|
s****l
发帖数: 10462 | 11 每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
【在 R***a 的大作中提到】
: 6x7的还是穷举省事
|
M*****e
发帖数: 11621 | 12 可能是太穷的缘故。现代社会太物质了。
【在 s****l 的大作中提到】
: 每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
|
H********g
发帖数: 43926 | 13 如果每个方格一次且仅一次：
每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
数从0到4：
1，如果有1个结点外部连接为(0)显然无解，
2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
个是终点
3，连接为(2)的结点只有一种连接方式
4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
连接必须断开。可以循环使用这个规则，简化路径。
5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
不确定上面这几条能不能保证充分性。
不过如果只是设计游戏的话，如果你先设计好路径，然后往路径里加方块，就可以保证
有解。不过这样不能保证有唯一解。 |
R***a
发帖数: 41892 | 14 肯定可以穷举的啊。
矩阵里每个格子的值就是可以访问的次数。
访问一次这个格子，格子值--.
如果四周格子值都是0了，算fail。
如果到了终点以后还有格子值不是0，算fail就成了
【在 s****l 的大作中提到】
: 每个方块还要有两次的可能，有些方块还不存在，穷举似乎不举。
|
s****l
发帖数: 10462 | 15 你真是人才
我好好琢磨一下
【在 H********g 的大作中提到】
: 如果每个方格一次且仅一次：
: 每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
: 数从0到4：
: 1，如果有1个结点外部连接为(0)显然无解，
: 2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
: 个是终点
: 3，连接为(2)的结点只有一种连接方式
: 4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
: 连接必须断开。可以循环使用这个规则，简化路径。
: 5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
|
s****l
发帖数: 10462 | 16 上面给出的网页里面的也不是唯一解。关键是要有解。
【在 H********g 的大作中提到】
: 如果每个方格一次且仅一次：
: 每个方块当一个结点，然后算和相邻几个方块有连接，显然对二维方块来说连接
: 数从0到4：
: 1，如果有1个结点外部连接为(0)显然无解，
: 2，如果3个结点和外部连接为(1)显然无解，如果两个连接为(1)，那一个必然是起点一
: 个是终点
: 3，连接为(2)的结点只有一种连接方式
: 4，如果一个结点连接了2个(<=2)连接的节点，它自己也变成一个2连接的结点，其余的
: 连接必须断开。可以循环使用这个规则，简化路径。
: 5，如果一个结点连接了>=3个(<=2)连接的结点，此图无解。
|
H********g
发帖数: 43926 | 17 要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
面狂加分岔路。
【在 s****l 的大作中提到】
: 上面给出的网页里面的也不是唯一解。关键是要有解。
|
R***a
发帖数: 41892 | 18 如何保证没有比期望解的更优解呢？
【在 H********g 的大作中提到】
: 要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
: 面狂加分岔路。
|
H********g
发帖数: 43926 | 19 你要是设计游戏的话，如果是明显有多重解游戏乐趣会很低，无解也很挫折。
如果多重解的话，我觉得得像windows自带游戏里像蜘蛛纸牌和空当接龙这样路径比较
深，解也不是特别多的才可以。空当接龙虽然11902也无解，但是大部分还是有解的。
那个纸牌经常无解就没意思了。
【在 s****l 的大作中提到】
: 上面给出的网页里面的也不是唯一解。关键是要有解。
|
H********g
发帖数: 43926 | 20 故意把假路的都设计成死路。换句话说，每个假路跟主干路只有一个连接。
不过分叉路如果不很多的话其实也可以，比如一个岔路跟主路有两三个连接点，但是几
个连接点离得很近，这样就可以避免出现大量的次优解：
岔路 -------------------------继续乱分岔
| ||
主路--------------------------------------------------------------->终点
【在 R***a 的大作中提到】
: 如何保证没有比期望解的更优解呢？
|
|
|
H********g
发帖数: 43926 | 21 哈哈，freecell解答全集
http://freecellgamesolutions.com/i/?i=120
这个网站看起来是即时计算解答路径的。输入11902会跳一个张老三出来解答。
【在 H********g 的大作中提到】
: 你要是设计游戏的话，如果是明显有多重解游戏乐趣会很低，无解也很挫折。
: 如果多重解的话，我觉得得像windows自带游戏里像蜘蛛纸牌和空当接龙这样路径比较
: 深，解也不是特别多的才可以。空当接龙虽然11902也无解，但是大部分还是有解的。
: 那个纸牌经常无解就没意思了。
|
H********g
发帖数: 43926 | |
s****l
发帖数: 10462 | 23 你阅读太广泛了，呵呵。
谢谢了。
【在 H********g 的大作中提到】
: stlstl看看这个：freecell stats
: http://freecellgamesolutions.com/stats.html
|
H********g
发帖数: 43926 | 24 这个想法不对。如果要求所有的格子都遍历的话，后加的东西必须也是能遍历的。
【在 H********g 的大作中提到】
: 要有解简单，你就先画靶再射箭嘛。实际就是画迷宫的搞法，先做个通的，然后再在上
: 面狂加分岔路。
|
M*******n
发帖数: 10087 | |
