Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: [合集]问道简单的题（分治法的）
发信站: 哈工大紫丁香 (2002年08月28日17:26:37 星期三), 站内信件


────────────────────────────────────────
 Lucubrator (彻夜孤灯)                于 2002年08月24日20:10:37 星期六 说道:

判断国际象棋中的马在某个位置能否用63步走完剩下的63格
若能给出路线
请高手们指点一下
3x

────────────────────────────────────────
 kaiserking (傻了吧你)                于 Sun Aug 25 09:51:12 2002) 说道:

探讨探讨，
我的思路是这样的，
在某个位置上，马的下一步只有七个方向可走，若这七个方向有一个方向未去过，则选择
该方向作为下一步，若都去过，则回退到上一步。
思想跟八皇后问题一样，递归。



────────────────────────────────────────
 Lucubrator (彻夜孤灯)                于 2002年08月25日11:14:39 星期天 说道:

不过题目要求用分治法不是回溯法
我不知道该怎么分

────────────────────────────────────────
 sino (茶水)                          于 2002年08月25日13:13:20 星期天 说道:

这是什么书上的题？

────────────────────────────────────────
 kaiserking (傻了吧你)                于 Sun Aug 25 17:50:32 2002) 说道:

分治法和递归是混在一块的吧，其实分治法的思想是把一个问题分成几个子问题，然后解
决各个子问题，其实我的解题思路也应该是分治法，因为把马的下一步方向分为了七个方
向去解决，所以就`````
探讨探讨，不知说的对不对？
斑竹在吗，帮帮忙分析分析



────────────────────────────────────────
 kaiserking (傻了吧你)                于 Sun Aug 25 17:52:17 2002) 说道:

多半是王晓东的书吧



────────────────────────────────────────
 Lucubrator (彻夜孤灯)                于 2002年08月25日18:08:25 星期天 说道:

还真是王晓东的《计算机算法设计与分析》
呵呵

────────────────────────────────────────
 Lucubrator (彻夜孤灯)                于 2002年08月25日18:11:58 星期天 说道:

这样确实能算
不过题好像不是这个意思
应该有更简便的算法吧

────────────────────────────────────────
 sino (茶水)                          于 2002年08月25日19:23:26 星期天 说道:

这个不是哈密尔顿轨么？ 难道有构造方法？

────────────────────────────────────────
 sino (茶水)                          于 2002年08月25日19:25:00 星期天 说道:

a搜索解这个问题是标准方法，分治法没见过的说 ~

────────────────────────────────────────
 sino (茶水)                          于 2002年08月25日19:50:03 星期天 说道:

真的有分治方法，ft!!
有专门的论文讲这个

────────────────────────────────────────