精华区文章阅读

发信人: sino (茶水先生), 信区: Algorithm
标  题: ZSUCPC 2001中山同志们的题解--第1试第5题
发信站: 哈工大紫丁香 (2001年08月27日10:18:31 星期一), 站内信件

发信人: splutter (呆子), 信区: ACMICPC
标  题: 第一试第五题                           splutter
发信站: 逸仙时空 Yat-sen Channel (Tue Jun 19 05:19:32 2001), 站内信件

发信人: splutter (呆子), 信区: ACMICPC
标  题: [合集]关于第五题                       forgetful
发信站: 逸仙时空 Yat-sen Channel (Tue Jun 19 04:40:20 2001), 站内信件
------------------------------------------------------
oldcat (想猪的猫) 于Sun May 13 01:16:02 2001提到：

  这一题其实很简单的，就是一个动态规划就可以了，具体方法我就不讲了
  我相信以大家的实力可以解决的。
------------------------------------------------------
notrom (早睡早起~身体好) 于Sun May 13 02:02:16 2001提到：

  动态规划的思路并不难想，但优化是个大问题。随着问题规模的增长，
时空膨胀很快。
  J.Culberson 在1997年的论文Sokoban is PSPACE-complete中证明了
这个问题是个NP-hard. 目前解决这个问题比较前沿的办法是把问题看作
Robot Motion Planning Problem，然后用各种方法去优化它，比如
Domain-Dependent Single-Agent Search, Relecance Cut, Linear Bounded
Automata (Finite Tape Turing Machine)等等。
  但是目前的各种方法都不能解决Sokoban标准Test Suite中的全部90个
问题。最好的成绩是用可接受的时空资源解出81个。
  一个朋友就是用一种新的算法获得了University of Alberta的Ph.D.
  所以，这个问题不简单 :)

------------------------------------------------------
oldcat (想猪的猫) 于Sun May 13 09:10:07 2001提到：

  我没有看过你说的东西，不过这一题的规模很小，而且是只有一个箱子
  是很容易解决的。
------------------------------------------------------

Holmaming (更加风采动朝端) 于Sun May 13 14:03:55 2001提到：

    确实不难，但当时不知道搞错什么地方，只对了一半，55555~~~~~~
------------------------------------------------------

jqqwin (jqq) 于Sun May 13 23:27:30 2001提到：

怎么动法啊？给个公式出来吧

------------------------------------------------------
Holmaming (更加风采动朝端) 于Sun May 13 23:28:11 2001提到：

    动不了就广度呗，呵呵
------------------------------------------------------

jqqwin (jqq) 于Sun May 13 23:29:34 2001提到：

广度很麻烦的喔，有人说可以动的喔

------------------------------------------------------
monster@argo (不再堕落，不再�) 于Sun May 13 23:30:53 2001)

广度不麻烦吧。。。只不过不太够内存存结点罢了
------------------------------------------------------
Holmaming (更加风采动朝端) 于Sun May 13 23:31:17 2001提到：

    用广度的方法实现动态规划的思想。

------------------------------------------------------
mk (逐风) 于Sun May 13 23:32:23 2001提到：

用protect mode，动态分配就够啦。
------------------------------------------------------
mk (逐风) 于Sun May 13 23:34:38 2001提到：

说得对！  一个是实现形式，一个是算法思想。
------------------------------------------------------
axing (CS99+:axing) 于Mon May 14 00:04:18 2001提到：

不需要吧，我只用了基本内存64k加堆栈64k而已
------------------------------------------------------

--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]

Algorithm 版 (精华区)