问个算法问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

问个算法问题

问个算法问题# Programming - 葵花宝典

c*z2008-02-12 08:02

1 楼

就是那种九个格，一个空，开始八个数字是打乱得
要求排成按顺序得，这种puzzle英文叫什么？
有算法吗，能否给个链接看看，谢谢！
比如给你
2 1 3
4 * 7
5 6 8
排好之后是这样得
1 2 3
4 5 6
7 8 *

k*f2008-02-12 08:02

2 楼

a* search

【在 c*****z 的大作中提到】

: 就是那种九个格，一个空，开始八个数字是打乱得
: 要求排成按顺序得，这种puzzle英文叫什么？
: 有算法吗，能否给个链接看看，谢谢！
: 比如给你
: 2 1 3
: 4 * 7
: 5 6 8
: 排好之后是这样得
: 1 2 3
: 4 5 6

p*o2008-02-12 08:02

3 楼

穷举呗，36万种情况，用BFS估计一秒钟都用不到。

【在 c*****z 的大作中提到】

c*z2008-02-12 08:02

4 楼

知道这个问题得英文名吗，我好去嗖嗖

【在 k****f 的大作中提到】

: a* search

c*z2008-02-12 08:02

5 楼

为什么是穷举啊，难道在一定步数内肯定可以解出？

【在 p***o 的大作中提到】

: 穷举呗，36万种情况，用BFS估计一秒钟都用不到。

p*o2008-02-12 08:02

6 楼

It's a problem of reachability. Either you show it's reachable or
prove it's not. For the simple case of 9 boxes, there are only 9!
vertices in the graph so brute-force search will work. Otherwise
you need some heuristics like a* search.

【在 c*****z 的大作中提到】

: 为什么是穷举啊，难道在一定步数内肯定可以解出？

c*z2008-02-12 08:02

7 楼

cool, i haven't thought it in that way, can you give some more
details about how to detect reachability? or give a link, thanks!

【在 p***o 的大作中提到】

: It's a problem of reachability. Either you show it's reachable or
: prove it's not. For the simple case of 9 boxes, there are only 9!
: vertices in the graph so brute-force search will work. Otherwise
: you need some heuristics like a* search.

p*o2008-02-12 08:02

8 楼

http://en.wikipedia.org/wiki/Graph_search_algorithm

【在 c*****z 的大作中提到】

: cool, i haven't thought it in that way, can you give some more
: details about how to detect reachability? or give a link, thanks!