美女拼图，探讨一个算法。(100分)

C

chinaplate

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-28

• #1

大家一定玩过拼图吧，图版上有一个空位置，然后移动空位置附近的图片，
最后将散乱的图片拼成一张完整的美女图。现在我要把整个拼图过程用计算机
来实现。
把问题简化，一个3*3的二维数组中存放9个数0..8,0代表空位置
------- -------- --------
3 6 2 3 0 2 1 2 3
4 0 5 ------》 4 6 5 。。。=====》 4 5 6
8 1 7 8 1 7 7 8 0
------- -------- --------
通过移动空位置，将无续的数组，变为有序的数组。最后输出其转换过程。








这是个类似八皇后的问题，思路似乎很清晰，是一棵数的遍历问题，
但似乎这个树过于庞大.

 

C

Chenlili

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-28

• #2

?8皇后只是一个递归算法的问题，没有这么夸张
由于这个东西没有明显的规律，用一般的深度、广度、动态规划都是不可取的
最好用最佳图形a*算法。

 

酷

酷尔贝塔

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-28

• #3

????[][]

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-29

• #4

这是一个典型的人工智能搜索问题，我记得书上推荐的是双向+广度。
3*3的方格就是有9!种可能排列——不多。

 

C

chinaplate

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-29

• #5

Chenlili:用最佳图形a*算法，
能详细描述一下吗？
creation-zy:3*3的方格就是有9!种可能排列
具体的排列是有9！个，但这棵数中有大量的重复的节点（我曾试图滤去重复的节点，效果也不明显）
我的思路是这样的。
对于图版的每一个状态，都可以对应1到4种操作，就是0位置的
上移，下移，左移，右移。当然这些操作是有条件的
1。不能移出界，最左边的就不能向左移了。
2。从上一个状态上移来的就不能再下移了，这样就循环起来了
那么，就是说，初始状态是这棵树的根节点，对于这个例子来说，
这个根节点有四个孩子，对于每个孩子，也一样生成N（1..4）个
孩子，这样，只要给定了一个初始根接点，我们就得到了一个确定
的树（这棵树会有无穷层，无穷个节点），那么再这棵数中必定有
我们要得的结果，一个有序的节点。然后从这个节点倒推上去，就
得到了我们需要的步骤。
问题就转化为了这棵数的遍历问题（边生成，边遍历），
深度遍历要有个确定的条件知道这个分支走不下去了，但这个条件无法确定。
广度遍历要生成一棵完全树，要生成大量的节点，但也只能选它了。
但这个算法效率太低。（而且通常得不到正确的结果，溢出了）

 

Z

zhukewen

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-29

• #6

探讨这个算法有实际意义吗？

 

J

jdshoot

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-29

• #7

也许他想用这个程序来自动拼图吧。
说笑了，其实我觉得这个算法就是 广度 + 剪枝，以哪个节点为根并不重要，因为都是从
初始状态出发寻找终止状态，以初始状态或终止状态为根都可以。只要建立一张表存储每
个节点是否访问过，就可以在重复的时候把重复的“枝”剪掉了，这样效率应该还可以，
而且正像creation-zy说的，“3*3的方格就是有9!种可能排列——不多”，所以空间也应
该不是问题。

 

C

Chenlili

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-29

• #8

怎么没有用啊？以前搞的链表、深度、广度，现在在linux下面写driver的时候都用上了。

 

C

chinaplate

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-30

• #9

看来，我的思路还是正确的，可能程序还有一些问题，我再推敲一下，
调试好了，我把程序贴上来，请大家指正。
我是用C#写的。

 

J

jdshoot

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-30

• #10

想起来了，这不是树的遍历，根本就是一个图的遍历嘛，其实深度和广度都可以，如果用深度遍历，
回溯条件就是遇到已出现的节点，只不过深度遍历的时间效率低了一些，但用的空间较少。

 

张

张剑波

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-15

• #11

多人接受答案了。