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

  • 主题发起人 chinaplate
  • 开始时间
C

chinaplate

Unregistered / Unconfirmed
GUEST, unregistred user!
大家一定玩过拼图吧，图版上有一个空位置，然后移动空位置附近的图片，
最后将散乱的图片拼成一张完整的美女图。现在我要把整个拼图过程用计算机
来实现。
把问题简化，一个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
------- -------- --------
通过移动空位置，将无续的数组，变为有序的数组。最后输出其转换过程。








这是个类似八皇后的问题，思路似乎很清晰，是一棵数的遍历问题，
但似乎这个树过于庞大.
 
?8皇后只是一个递归算法的问题，没有这么夸张
由于这个东西没有明显的规律，用一般的深度、广度、动态规划都是不可取的
最好用最佳图形a*算法。
 
????[:)][:)]
 
这是一个典型的人工智能搜索问题，我记得书上推荐的是双向+广度。
3*3的方格就是有9!种可能排列——不多。
 
Chenlili:用最佳图形a*算法，
能详细描述一下吗？
creation-zy:3*3的方格就是有9!种可能排列
具体的排列是有9！个，但这棵数中有大量的重复的节点（我曾试图滤去重复的节点，效果也不明显）
我的思路是这样的。
对于图版的每一个状态，都可以对应1到4种操作，就是0位置的
上移，下移，左移，右移。当然这些操作是有条件的
1。不能移出界，最左边的就不能向左移了。
2。从上一个状态上移来的就不能再下移了，这样就循环起来了
那么，就是说，初始状态是这棵树的根节点，对于这个例子来说，
这个根节点有四个孩子，对于每个孩子，也一样生成N（1..4）个
孩子，这样，只要给定了一个初始根接点，我们就得到了一个确定
的树（这棵树会有无穷层，无穷个节点），那么再这棵数中必定有
我们要得的结果，一个有序的节点。然后从这个节点倒推上去，就
得到了我们需要的步骤。
问题就转化为了这棵数的遍历问题（边生成，边遍历），
深度遍历要有个确定的条件知道这个分支走不下去了，但这个条件无法确定。
广度遍历要生成一棵完全树，要生成大量的节点，但也只能选它了。
但这个算法效率太低。（而且通常得不到正确的结果，溢出了）
 
探讨这个算法有实际意义吗？
 
也许他想用这个程序来自动拼图吧。:)
说笑了，其实我觉得这个算法就是 广度 + 剪枝，以哪个节点为根并不重要，因为都是从
初始状态出发寻找终止状态，以初始状态或终止状态为根都可以。只要建立一张表存储每
个节点是否访问过，就可以在重复的时候把重复的“枝”剪掉了，这样效率应该还可以，
而且正像creation-zy说的，“3*3的方格就是有9!种可能排列——不多”，所以空间也应
该不是问题。
 
怎么没有用啊？以前搞的链表、深度、广度，现在在linux下面写driver的时候都用上了。
 
看来，我的思路还是正确的，可能程序还有一些问题，我再推敲一下，
调试好了，我把程序贴上来，请大家指正。
我是用C#写的。
 
想起来了，这不是树的遍历，根本就是一个图的遍历嘛，其实深度和广度都可以，如果用深度遍历，
回溯条件就是遇到已出现的节点，只不过深度遍历的时间效率低了一些，但用的空间较少。
 
多人接受答案了。
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
快
100分继续挑战算法高手（50分求购算法的续集）up有分 (100分)
回复
13
查看
340
快刀不快
快
大
请问一个算法问题。(100分)
回复
14
查看
324
LeonSu
L
B
脸红呀！！！有个小问题！！(100分)
回复
5
查看
83
tseug
T
L
两道考研试题？(50分)
2
回复
21
查看
529
lbylby
L
顶部