BFS使用哪种启发式方法来解决此“游戏"(查找路径)? [英] What kind of heuristics for BFS use to solve this 'game' (find path)?

问题描述

我想解决一个游戏". 我有5个圆圈，我们可以将圆圈旋转到左侧或右侧(90度).

示例:

目标:1、2、3，...，14、15、16 前任.起始情况:16、15、14，...，3、2、1

我正在使用BFS查找路径，但是我无法发明启发式函数(我的每个解决方案都不好).我正在尝试曼哈顿距离和其他距离...(也许想法不错，但是我的解决方案出了点问题).请帮忙！

解决方案

一个简单的保守(允许的)启发式方法是:

1. 对于每个数字1< = i< = 16，找到使i返回其正确位置所需的最小旋转次数(不考虑所有其他数字)
2. 取所有这些最小值中的最大值.

这等于报告正确定位最差"数字所需的最小旋转次数，因此，绝不会高估所需的移动次数(因为同时固定所有数字的位置至少需要固定与固定任何一个旋转次数相同的移动次数).他们).

但是，它可能大大低估了所需的移动次数.您可以通过计算每个数字1 <= i <= 16和每个车轮1 <= j <= 5来变得更复杂，该车轮j的最小旋转次数取决于该位置所需要的任何移动顺序我正确.然后，对于每个车轮j，您可以对所有数字i取一个单独的最大值，最后将这5个最大值加在一起，因为它们都是独立的. (这可能少于以前的启发式方法，但是始终允许您采用两者中的较大者，因此这不会有问题.)

I want to solve a 'game'. I have 5 circles, we can rotate circles into left or into right (90 degrees).

Example:

Goal: 1,2,3,....,14,15,16 Ex. of starting situations: 16,15,14,...,3,2,1

I'm using BFS to find path but I can't invent heuristic function (my every solutions are not good). I was trying manhattan distance and others... (Maybe idea is good but something wrong with my solution). Please help!

解决方案

A simple conservative (admissible) heuristic would be:

1. For each number 1 <= i <= 16, find the minimum number of rotations needed to put i back in its correct position (disregarding all other numbers)
2. Take the maximum over all these minimums.

This amounts to reporting minimum number of rotations needed to position the "worst" number correctly, and will therefore never overestimate the number of moves needed (since fixing all numbers' positions simultaneously requires at least as many moves as fixing any one of them).

It may, however, underestimate the number of moves needed by a long way. You can get more sophisticated by calculating, for each number 1 <= i <= 16 and for each wheel 1 <= j <= 5, the minimum number of rotations of wheel j needed by any sequence of moves that positions i correctly. For each wheel j, you can then take a separate maximum over all numbers i, and finally add these 5 maxima together, since they are all independent. (This may be less than the previous heuristic, but you are always allowed to take the greater of the two, so this won't be a problem.)

这篇关于BFS使用哪种启发式方法来解决此“游戏"(查找路径)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！