# Sokoban

**Repository Path**: hackydh/Sokoban

## Basic Information

- **Project Name**: Sokoban
- **Description**: 解决推箱子问题
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2015-11-04
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#解决推箱子问题

##历史
* 2015.2.25
此方案使用STL实现的BFS算法，优点是总能找到解，不会浪费内存
但是速度慢，并且方案设计扩展状态有很多重复的，而且查找状态也很慢。
最简单的1关 解需要10步，但是此方案需要138步。
复杂的地图需要很长时间，需要改进。
* 2015.6.30
使用策略模式，可以输出解的序列

增加了bool Status::Dead()来判断一个状态是否已经没有任何前途 以此剪枝

##估价函数
f^() = g^() + h^() = 当前已经走得步数 + h^()
h^()怎么确定呢？一步只能推一个箱子，所以说，箱子、目标一一配对，其中欧几里得距离的和的最小值就是至少要走的步数，显然 h^() <= h()，所以估价函数的正确性不用怀疑；又显然当 h^() = 0 时 h() = 0。

本解决方案偷懒了，使用了各个点到距（欧几里得距离）其最近的目标的欧几里得距离之和作为h^()，这样可以节约计算h^()的时间。