Rub*_*bys 33 language-agnostic algorithm artificial-intelligence
如果您不熟悉高峰时段,游戏包含一系列不同大小的汽车,水平或垂直设置在具有单个出口的NxM网格上.
只要另一辆车没有挡住它,每辆车都可以按照它设定的方向前进/后退.你永远不能改变汽车的方向.
有一辆特别的车,通常是红色的.它设置在出口所在的同一排,游戏的目标是找到一系列动作(移动 - 向前或向前移动N步),这将允许红色汽车驶出迷宫.
我一直在努力思考如何在计算上解决这个问题,我真的不能想到任何好的解决方案.
我想出了一些:
所以问题是 - 如何创建一个采用网格和车辆布局的程序,并输出一系列步骤来获得红色汽车？
次级问题:
示例:如何在此设置中移动汽车,以便红色汽车可以通过右侧的出口"退出"迷宫？
http://scienceblogs.com/ethicsandscience/upload/2006/12/RushHour.jpg
pol*_*nts 29
对于经典的尖峰时刻,这个问题非常简单,只需要进行简单的广度搜索.声称最难知的初始配置需要93次移动来解决,总共只有24132个可达配置.甚至一个天真地实现的广度优先搜索算法也可以在1秒内探索整个搜索空间,即使是适度的机器也是如此.
这是一个以C风格编写的广度优先搜索穷举求解器的完整源代码.
import java.util.*;
public class RushHour {
// classic Rush Hour parameters
static final int N = 6;
static final int M = 6;
static final int GOAL_R = 2;
static final int GOAL_C = 5;
// the transcription of the 93 moves, total 24132 configurations problem
// from http://cs.ulb.ac.be/~fservais/rushhour/index.php?window_size=20&offset=0
static final String INITIAL = "333BCC" +
"B22BCC" +
"B.XXCC" +
"22B..." +
".BB.22" +
".B2222";
static final String HORZS = "23X"; // horizontal-sliding cars
static final String VERTS = "BC"; // vertical-sliding cars
static final String LONGS = "3C"; // length 3 cars
static final String SHORTS = "2BX"; // length 2 cars
static final char GOAL_CAR = 'X';
static final char EMPTY = '.'; // empty space, movable into
static final char VOID = '@'; // represents everything out of bound
// breaks a string into lines of length N using regex
static String prettify(String state) {
String EVERY_NTH = "(?<=\\G.{N})".replace("N", String.valueOf(N));
return state.replaceAll(EVERY_NTH, "\n");
}
// conventional row major 2D-1D index transformation
static int rc2i(int r, int c) {
return r * N + c;
}
// checks if an entity is of a given type
static boolean isType(char entity, String type) {
return type.indexOf(entity) != -1;
}
// finds the length of a car
static int length(char car) {
return
isType(car, LONGS) ? 3 :
isType(car, SHORTS) ? 2 :
0/0; // a nasty shortcut for throwing IllegalArgumentException
}
// in given state, returns the entity at a given coordinate, possibly out of bound
static char at(String state, int r, int c) {
return (inBound(r, M) && inBound(c, N)) ? state.charAt(rc2i(r, c)) : VOID;
}
static boolean inBound(int v, int max) {
return (v >= 0) && (v < max);
}
// checks if a given state is a goal state
static boolean isGoal(String state) {
return at(state, GOAL_R, GOAL_C) == GOAL_CAR;
}
// in a given state, starting from given coordinate, toward the given direction,
// counts how many empty spaces there are (origin inclusive)
static int countSpaces(String state, int r, int c, int dr, int dc) {
int k = 0;
while (at(state, r + k * dr, c + k * dc) == EMPTY) {
k++;
}
return k;
}
// the predecessor map, maps currentState => previousState
static Map<String,String> pred = new HashMap<String,String>();
// the breadth first search queue
static Queue<String> queue = new LinkedList<String>();
// the breadth first search proposal method: if we haven't reached it yet,
// (i.e. it has no predecessor), we map the given state and add to queue
static void propose(String next, String prev) {
if (!pred.containsKey(next)) {
pred.put(next, prev);
queue.add(next);
}
}
// the predecessor tracing method, implemented using recursion for brevity;
// guaranteed no infinite recursion, but may throw StackOverflowError on
// really long shortest-path trace (which is infeasible in standard Rush Hour)
static int trace(String current) {
String prev = pred.get(current);
int step = (prev == null) ? 0 : trace(prev) + 1;
System.out.println(step);
System.out.println(prettify(current));
return step;
}
// in a given state, from a given origin coordinate, attempts to find a car of a given type
// at a given distance in a given direction; if found, slide it in the opposite direction
// one spot at a time, exactly n times, proposing those states to the breadth first search
//
// e.g.
// direction = -->
// __n__
// / \
// ..o....c
// \___/
// distance
//
static void slide(String current, int r, int c, String type, int distance, int dr, int dc, int n) {
r += distance * dr;
c += distance * dc;
char car = at(current, r, c);
if (!isType(car, type)) return;
final int L = length(car);
StringBuilder sb = new StringBuilder(current);
for (int i = 0; i < n; i++) {
r -= dr;
c -= dc;
sb.setCharAt(rc2i(r, c), car);
sb.setCharAt(rc2i(r + L * dr, c + L * dc), EMPTY);
propose(sb.toString(), current);
current = sb.toString(); // comment to combo as one step
}
}
// explores a given state; searches for next level states in the breadth first search
//
// Let (r,c) be the intersection point of this cross:
//
// @ nU = 3 '@' is not a car, 'B' and 'X' are of the wrong type;
// . nD = 1 only '2' can slide to the right up to 5 spaces
// 2.....B nL = 2
// X nR = 4
//
// The n? counts how many spaces are there in a given direction, origin inclusive.
// Cars matching the type will then slide on these "alleys".
//
static void explore(String current) {
for (int r = 0; r < M; r++) {
for (int c = 0; c < N; c++) {
if (at(current, r, c) != EMPTY) continue;
int nU = countSpaces(current, r, c, -1, 0);
int nD = countSpaces(current, r, c, +1, 0);
int nL = countSpaces(current, r, c, 0, -1);
int nR = countSpaces(current, r, c, 0, +1);
slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1);
slide(current, r, c, VERTS, nD, +1, 0, nU + nD - 1);
slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1);
slide(current, r, c, HORZS, nR, 0, +1, nL + nR - 1);
}
}
}
public static void main(String[] args) {
// typical queue-based breadth first search implementation
propose(INITIAL, null);
boolean solved = false;
while (!queue.isEmpty()) {
String current = queue.remove();
if (isGoal(current) && !solved) {
solved = true;
trace(current);
//break; // comment to continue exploring entire space
}
explore(current);
}
System.out.println(pred.size() + " explored");
}
}
源代码中有两个值得注意的行:
break;当找到解决方案
current = sb.toString();在slide
该算法本质上是广度优先搜索,通常使用队列实现.维护先前的映射,以便可以将任何状态追溯到初始状态.永远不会重新映射密钥,并且当条目以广度优先搜索顺序插入时,保证最短路径.
状态表示为NxM-length String.每个char代表一个实体在板上,以行主要顺序存储.
通过从空白区域扫描所有4个方向,寻找合适的车型,在房间容纳时滑动它,可以找到相邻状态.
这里有许多冗余的工作(例如,多次扫描多长的"小巷"),但如前所述,虽然广义版本是PSPACE完整版,但经典的"尖峰时刻"变体非常易于使用.
小智 7
这是我的答案.它在不到6秒的时间内解决了大师级拼图.
它使用广度优先搜索(BFS).诀窍是寻找之前在早期搜索中看到的电路板布局并中止该序列.由于BFS,如果你已经看到那个布局,你已经有一个更短的方式,所以让这个序列继续尝试解决它而不是这个更长的.
#!perl
# Program by Rodos rodos at haywood dot org
use Storable qw(dclone);
use Data::Dumper;
print "Lets play Rush Hour! \n";
# Lets define our current game state as a grid where each car is a different letter.
# Our special car is a marked with the specific letter T
# The boarder is a * and the gloal point on the edge is an @.
# The grid must be the same witdh and height
# You can use a . to mark an empty space
# Grand Master
@startingGrid = (
['*','*','*','*','*','*','*','*'],
['*','.','.','A','O','O','O','*'],
['*','.','.','A','.','B','.','*'],
['*','.','T','T','C','B','.','@'],
['*','D','D','E','C','.','P','*'],
['*','.','F','E','G','G','P','*'],
['*','.','F','Q','Q','Q','P','*'],
['*','*','*','*','*','*','*','*']
);
# Now lets print out our grid board so we can see what it looks like.
# We will go through each row and then each column.
# As we do this we will record the list of cars (letters) we see into a hash
print "Here is your board.\n";
&printGrid(\@startingGrid);
# Lets find the cars on the board and the direction they are sitting
for $row (0 .. $#startingGrid) {
for $col (0 .. $#{$startingGrid[$row]} ) {
# Make spot the value of the bit on the grid we are looking at
$spot = $startingGrid[$row][$col];
# Lets record any cars we see into a "hash" of valid cars.
# If the splot is a non-character we will ignore it cars are only characters
unless ($spot =~ /\W/) {
# We will record the direction of the car as the value of the hash key.
# If the location above or below our spot is the same then the car must be vertical.
# If its not vertical we mark as it as horizonal as it can't be anything else!
if ($startingGrid[$row-1][$col] eq $spot || $startingGrid[$row+1] eq $spot) {
$cars{$spot} = '|';
} else {
$cars{$spot} = '-';
}
}
}
}
# Okay we should have printed our grid and worked out the unique cars
# Lets print out our list of cars in order
print "\nI have determined that you have used the following cars on your grid board.\n";
foreach $car (sort keys %cars) {
print " $car$cars{$car}";
}
print "\n\n";
end;
&tryMoves();
end;
# Here are our subroutines for things that we want to do over and over again or things we might do once but for
# clatiry we want to keep the main line of logic clear
sub tryMoves {
# Okay, this is the hard work. Take the grid we have been given. For each car see what moves are possible
# and try each in turn on a new grid. We will do a shallow breadth first search (BFS) rather than depth first.
# The BFS is achieved by throwing new sequences onto the end of a stack. You then keep pulling sequnces
# from the front of the stack. Each time you get a new item of the stack you have to rebuild the grid to what
# it looks like at that point based on the previous moves, this takes more CPU but does not consume as much
# memory as saving all of the grid representations.
my (@moveQueue);
my (@thisMove);
push @moveQueue, \@thisMove;
# Whlst there are moves on the queue process them
while ($sequence = shift @moveQueue) {
# We have to make a current view of the grid based on the moves that got us here
$currentGrid = dclone(\@startingGrid);
foreach $step (@{ $sequence }) {
$step =~ /(\w)-(\w)(\d)/;
$car = $1; $dir = $2; $repeat = $3;
foreach (1 .. $repeat) {
&moveCarRight($car, $currentGrid) if $dir eq 'R';
&moveCarLeft($car, $currentGrid) if $dir eq 'L';
&moveCarUp($car, $currentGrid) if $dir eq 'U';
&moveCarDown($car, $currentGrid) if $dir eq 'D';
}
}
# Lets see what are the moves that we can do from here.
my (@moves);
foreach $car (sort keys %cars) {
if ($cars{$car} eq "-") {
$l = &canGoLeft($car,$currentGrid);
push @moves, "$car-L$l" if ($l);
$l = &canGoRight($car,$currentGrid);
push @moves, "$car-R$l" if ($l);
} else {
$l = &canGoUp($car,$currentGrid);
push @moves, "$car-U$l" if ($l);
$l = &canGoDown($car,$currentGrid);
push @moves, "$car-D$l" if ($l);
}
}
# Try each of the moves, if it solves the puzzle we are done. Otherwise take the new
# list of moves and throw it on the stack
foreach $step (@moves) {
$step =~ /(\w)-(\w)(\d)/;
$car = $1; $dir = $2; $repeat = $3;
my $newGrid = dclone($currentGrid);
foreach (1 .. $repeat) {
&moveCarRight($car, $newGrid) if $dir eq 'R';
&moveCarLeft($car, $newGrid) if $dir eq 'L';
&moveCarUp($car, $newGrid) if $dir eq 'U';
&moveCarDown($car, $newGrid) if $dir eq 'D';
}
if (&isItSolved($newGrid)) {
print sprintf("Solution in %d moves :\n", (scalar @{ $sequence }) + 1);
print join ",", @{ $sequence };
print ",$car-$dir$repeat\n";
return;
} else {
# That did not create a solution, before we push this for further sequencing we want to see if this
# pattern has been encountered before. If it has there is no point trying more variations as we already
# have a sequence that gets here and it might have been shorter, thanks to our BFS
if (!&seen($newGrid)) {
# Um, looks like it was not solved, lets throw this grid on the queue for another attempt
my (@thisSteps) = @{ $sequence };
push @thisSteps, "$car-$dir$repeat";
push @moveQueue, \@thisSteps;
}
}
}
}
}
sub isItSolved {
my ($grid) = shift;
my ($row, $col);
my $stringVersion;
foreach $row (@$grid) {
$stringVersion .= join "",@$row;
}
# We know we have solve the grid lock when the T is next to the @, because that means the taxi is at the door
if ($stringVersion =~ /\T\@/) {
return 1;
}
return 0;
}
sub seen {
my ($grid) = shift;
my ($row, $col);
my $stringVersion;
foreach $row (@$grid) {
$stringVersion .= join "",@$row;
}
# Have we seen this before?
if ($seen{$stringVersion}) {
return 1;
}
$seen{$stringVersion} = 1;
return 0;
}
sub canGoDown {
my ($car) = shift;
return 0 if $cars{$car} eq "-";
my ($grid) = shift;
my ($row, $col);
for ($row = $#{$grid}; $row >= 0; --$row) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[++$row][$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub canGoUp {
my ($car) = shift;
return 0 if $cars{$car} eq "-";
my ($grid) = shift;
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[--$row][$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub canGoRight {
my ($car) = shift;
return 0 if $cars{$car} eq "|";
my ($grid) = shift;
my ($row, $col);
for $row (0 .. $#{$grid}) {
for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[$row][++$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub canGoLeft {
my ($car) = shift;
return 0 if $cars{$car} eq "|";
my ($grid) = shift;
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[$row][--$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub moveCarLeft {
# Move the named car to the left of the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving left requires sweeping left to right.
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only horizontal cards can move left
die "Opps, tried to move a vertical car $car left" if $cars{$car} eq "|";
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car left into an occupied spot\n" if $grid->[$row][$col-1] ne ".";
$grid->[$row][$col-1] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub moveCarRight {
# Move the named car to the right of the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving right requires sweeping right to left (backwards).
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only horizontal cards can move right
die "Opps, tried to move a vertical car $car right" if $cars{$car} eq "|";
my ($row, $col);
for $row (0 .. $#{$grid}) {
for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car right into an occupied spot\n" if $grid->[$row][$col+1] ne ".";
$grid->[$row][$col+1] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub moveCarUp {
# Move the named car up in the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving right requires sweeping top down.
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only vertical cards can move up
die "Opps, tried to move a horizontal car $car up" if $cars{$car} eq "-";
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car up into an occupied spot\n" if $grid->[$row-1][$col] ne ".";
$grid->[$row-1][$col] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub moveCarDown {
# Move the named car down in the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving right requires sweeping upwards from the bottom.
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only vertical cards can move up
die "Opps, tried to move a horizontal car $car down" if $cars{$car} eq "-";
my ($row, $col);
for ($row = $#{$grid}; $row >=0; --$row) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car down into an occupied spot\n" if $grid->[$row+1][$col] ne ".";
$grid->[$row+1][$col] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub printGrid {
# Print out a representation of a grid
my ($grid) = shift; # This is a reference to an array of arrays whch is passed as the argument
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
print $grid->[$row][$col], " ";
}
print "\n";
}
}