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 楼
蝗虫太牛鼻了！到底是什么背景？
相关阅读
竞争zz在俄罗斯大妈面前，美军神马的都是浮云zz 秦始皇的假期精分有木有！尼玛只要不是整段地照抄，也称不上什么"抄袭"ML的最高境界是叫床好听，彭丽媛的嗓音最好了。 (转载)Re: 偶的老ThinkpadT40已经7岁了 (转载)公安武警不给力啊，国破思良将，城管哪儿去了？美国加州小城妓女数量失控 (转载)00后的潮，你伤不起Re: 真诚求教：我这是不是跨国重婚罪？ (转载)Re: 中印战争 (转载)今天，你穿越了吗。。。绝代双骄这也能调整。。。看了半天也没明白，但是一定有内涵。求解。大美女，来亲一个！不知道火锅和人类的关系这么密切问一个单词，应该是一种颜色，大家看是啥颜色啊？一个胖纸的苦恼 (转载)Re: Church Growth = Increased Pastor Salary? -- The Almight (转载)