一道高深数据结构题,大家来讨论看看(50分)

T

tranke

Unregistered / Unconfirmed
GUEST, unregistred user!
假设有一个正方型的框框,里面划分为9格或者16格,相应的里面存放1~8或者1~15个数字,表示其中总存在一个空位;并且存在这种情况,将以上的数字格位打乱,然后采用一种算法(根据空格来交换位置)来重新排列数字为:
1 2 3
4 5 6
7 8

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

等格式。就目前来说,我认为可以采用贪满法或者归塑法来实现的,但是不知道应该怎样以哪个基点开始进行排列,并且排列的过程中应该考虑到什么条件?
大家一起讨论学习吧!
相信对一些人来说还是有意思的拉~
 
W

winion

Unregistered / Unconfirmed
GUEST, unregistred user!
我记得这种游戏我以前玩过,有规律的,先排什么,后排什么,以及每一个数子如何走,都有规则的。忘记了,好像不难。
 
W

weiwei81123

Unregistered / Unconfirmed
GUEST, unregistred user!
很简单,先是从上到下,从左到右,剩下最后两行时改为从左到右,从下到上,最后剩下2*2很容易就搞定了.
 
T

tranke

Unregistered / Unconfirmed
GUEST, unregistred user!
又是weiwei81123啊!
你是不是做过类似的算法呢?
 
J

JackKen

Unregistered / Unconfirmed
GUEST, unregistred user!
经典的八数码问题?这学期刚学的AI有教。就是用那个空格搜索四个方向。
关键是设一个价值函数,计算每步的价值,看应该走那个方向。
 
H

hiyaolee

Unregistered / Unconfirmed
GUEST, unregistred user!
你想做拼圖的遊戲。
 
W

weiwei81123

Unregistered / Unconfirmed
GUEST, unregistred user!
这是我玩拼板的方法,很管用的,每行前N-1个很容易就位的,
而最后一个有固定的模式可以套,所以应可以用程序来实现.
因为是模拟手算的过程,速度应该很快,或者说可以对付很大
的拼板.不过该方法只能求可行解,要求最优解还得BFS.
 
T

tranke

Unregistered / Unconfirmed
GUEST, unregistred user!
我到不是想做拼图游戏,只是导师给我一个题目试试!
不过,后来我发现这也是一个拼图游戏的算法,到是有点意思想在算出算法后有空就做个拼图游戏来玩的阿拉!
weiwei81123,能否给我说说应该怎样入手开始设计思路呢?
不用跟我说清楚算法,只想能否给我一些提示即可,谢谢了!
 
T

tranke

Unregistered / Unconfirmed
GUEST, unregistred user!
因为我对这个算法很感兴趣,也想自己搞出来,谢谢大家支持
 
T

tseug

Unregistered / Unconfirmed
GUEST, unregistred user!
我记得这是人工智能这本教材上的作业题, 输上好像给了个爬山函数...用它给的算法和函数就可以解决这个问题...
 
G

gztiger

Unregistered / Unconfirmed
GUEST, unregistred user!
呵呵...在d8的demo中有一個例子,想不出來是可去研究研究...
 
J

jhaiwa

Unregistered / Unconfirmed
GUEST, unregistred user!
我可以做出来,但要好好想想,只有50分?太少了吧!:(
 
G

gztiger

Unregistered / Unconfirmed
GUEST, unregistred user!
不好意思,沒看清題目,D8 demo中的隻是有這個遊戲,但沒有重新排序算法。Sorry!
 
T

tranke

Unregistered / Unconfirmed
GUEST, unregistred user!
To jhaiwa:
我只是希望大家来讨论讨论,并不是请谁帮我做出来的,目的是能从某人的思路中得到启示的。[:)]
 
W

weiwei81123

Unregistered / Unconfirmed
GUEST, unregistred user!
1 2 5 1 2 1 2
6 4 --> 6 4 5 --> 6 4 5
8 7 3 8 7 3 8 7 3
1 4 2 1 4 2 1 4 2
--> 6 5 --> 6 5 --> 6 5 3
8 7 3 8 7 3 8 7
1 4 2 1 4 2 1 2
--> 6 5 3 --> 6 3 --> 6 4 3
8 7 8 5 7 8 5 7
1 2 3
--> 6 4
8 5 7
 

无敌笨牛

Unregistered / Unconfirmed
GUEST, unregistred user!
根据我玩这个游戏的经验为什么不先弄完一排再弄一排呢?这样也蛮快呀。比如1~9的话第一排先排好后面两排就好弄了。也就是说不管怎样,先把123找到位呀。
 

无敌笨牛

Unregistered / Unconfirmed
GUEST, unregistred user!
我想删了自己的贴。没看清楚就瞎说,果然像WEIWEI说的那样。
 

老人家

Unregistered / Unconfirmed
GUEST, unregistred user!
这是一道数学提阿
 
Top Bottom