迷路で眺める探索アルゴリズム(Search algorithm visualize)
8種類の基本的な探索アルゴリズム
【深さ優先、幅優先、反復深化深さ優先、最良優先、間違い制限探索、幅優先ビームサーチ、最良優先ビームサーチ】
と、
2種類のオリジナル(?)の探索アルゴリズム
【優良優先探索、二重制限探索】(仮称)
を迷路を使って可視化しました。
☆迷路の見方
■ 青色: Sがスタート、Gがゴール
■ 白色: 未探索のマス
■ 灰色: 探索済みのマス
■ 赤色: 探索により発見されて、リストに保持されているの分岐点
■ 橙色: 枝刈りにより、リストから削除された分岐点
赤マスに書いてある数字は、リスト内のマスにゴールに近い順に順位を付けたものです。ただし、間違い制限探索のみ間違い数(discrepancy)です。
詳しい解説は以下を見てください
http://spheresofa.net/blog/?p=1044
/**
* Copyright shohei909 ( http://wonderfl.net/user/shohei909 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/hq8p
*/
package {
import com.bit101.components.CheckBox;
import com.bit101.components.ComboBox;
import com.bit101.components.Component;
import com.bit101.components.HBox;
import com.bit101.components.HUISlider;
import com.bit101.components.Label;
import com.bit101.components.NumericStepper;
import com.bit101.components.PushButton;
import com.bit101.components.Slider;
import com.bit101.components.Style;
import com.bit101.components.VBox;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Graphics;
import flash.display.Sprite;
import flash.events.Event;
[SWF(frameRate="60")]
public class Main extends Sprite {
private const SEARCH_LIST:Array = [DepthFirst, BreadthFirst, IDDepthFirst, HillClimbing, BestFirst, LimitedDiscrepancy, BreadthFirstBeam, BestFirstBeam, GoodFirst, DoubleLimit ];
private const SPEED_LIST:Array = [ 120, 60, 35, 15, 10, 7, 5, 3, 2, 1 ]
public var bitmap:Bitmap;
public var maze:Maze;
public var log:Log;
public var running:Boolean;
private var speed:int = 5;
private var count:int = 0;
private var stepItems:Array;
private var speedSlider:HUISlider;
private var stepSlider:Slider;
private var stepLabel:Label;
private var output:Label;
private var startBtn:PushButton;
private var combo:ComboBox;
private var mapCheck:CheckBox;
private var mapBtn:PushButton;
private var steppers:Array = [];
private var labels:Array = [];
private var changedCount:int = 0;
private var params:Array;
private var footer:HBox;
public function Main():void {
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e:Event = null):void {
removeEventListener(Event.ADDED_TO_STAGE, init);
addEventListener(Event.ENTER_FRAME, onFrame);
//UI
var back:BitmapData = new BitmapData( 2, 2, false, 0xF6F6F6 );
back.setPixel(0, 1, 0xFFFFFF);
var g:Graphics = graphics;
g.beginFill( 0xFAFAFA, 1 )
g.beginBitmapFill( back );
g.drawRect( 0, 0, 465, 465 );
//ボタン
Style.embedFonts = false;
Style.fontSize = 10;
Style.fontName = "ＭＳ ゴシック,MS Gothic,Meiryo UI,Osaka";
var vbox:VBox = new VBox( this, 0, 4 );
var hbox:HBox = new HBox( vbox, 5, 0 );
hbox.height = 20;
hbox.spacing = 4;
//hbox.alignment = "middle";
function getNames( item:*, ...args ):String { return item.name; }
combo = new ComboBox( hbox, 0, 0, null, SEARCH_LIST.map( getNames ) );
combo.selectedIndex = 0;
combo.width = 240;
combo.height = 20
combo.addEventListener( Event.SELECT, onSearchChange );
combo.numVisibleItems = SEARCH_LIST.length;
mapCheck = new CheckBox( hbox, 0, 5, "", remap );
mapCheck.width = 10;
mapBtn = new PushButton( hbox, 0, 0, "new", remap );
mapBtn.width = 35;
var slider:HUISlider = speedSlider = new HUISlider( hbox, 0, 2, "| speed" );
slider.width = 160;
slider.maximum = SPEED_LIST.length;
slider.minimum = 1;
slider.value = 3;
slider.tick = 1;
slider.labelPrecision = 0;
//--
hbox = new HBox( vbox, 5, 0 );
hbox.height = 20;
hbox.spacing = 3;
//hbox.alignment = "middle";
stepItems = [];
startBtn = new PushButton( hbox, 0, 0, "start", onStart )
startBtn.width = 45;
new Label( hbox, 0, 0, "|" );
var btn:PushButton;
btn = new PushButton( hbox, 0, 0, "<<", top );
btn.width = 30; stepItems.push( btn );
btn = new PushButton( hbox, 0, 0, "<", prev );
btn.width = 30; stepItems.push( btn );
stepSlider = new Slider( "horizontal", hbox, 0, 5, slide );
stepSlider.width = 190;
stepSlider.tick = 1;
stepSlider.minimum = 0;
stepItems.push( stepSlider );
stepLabel = new Label( hbox, 0, 2, "10000/10000" );
btn = new PushButton( hbox, 0, 0, ">", next );
btn.width = 30; stepItems.push( btn );
btn = new PushButton( hbox, 0, 0, ">>", end );
btn.width = 30; stepItems.push( btn );
//--
footer = hbox = new HBox( vbox, 5, 0 );
hbox.height = 20;
hbox.spacing = 3;
//hbox.alignment = "middle";
for ( var i:int = 0; i < 2; i++ ) {
labels.push( new Label( hbox, 0, 0, "ビーム幅(beam width)" ) );
var stepper:NumericStepper = new NumericStepper( hbox, 0, 0, onStepperChange );
stepper.maximum = 99;
stepper.minimum = 1;
stepper.width = 60;
steppers.push( stepper );
}
//--
output = new Label( this, 5, 450, "" );
//迷路初期化
maze = new Maze( 41, 33 );
maze.make();
addChild( bitmap = new Bitmap( maze.bitmapData() ) );
bitmap.x = (stage.stageWidth - bitmap.width) / 2;
bitmap.y = 80;
onSearchChange( null );
onStart( null );
}
private function onFrame( e:Event ):void {
stepLabel.text = (log.position + 1) + "/" + log.length;
var p:int = stepSlider.value = log.position;
stepSlider.maximum = log.length - 1;
if ( changedCount > 0 ) {
changedCount--;
if ( changedCount == 0 ) { search(); update(); }
}
if (! running || count++ % SPEED_LIST[speedSlider.value - 1] ) return;
if(! log.isLast() ){
log.next();
update();
}
}
private function update():void {
log.apply( maze );
maze.draw( bitmap.bitmapData, log.isLast() ? log.goal : null );
output.text = "";
for ( var key:String in maze.data ) {
var d:int = maze.data[key];
output.text += Maze.NAMES[key] + ":" + d + " ";
}
footer.draw();
}
private function onStepperChange( e:Event ):void {
changedCount = 30;
for ( var i:int = 0, l:int = params.length; i < l; i++ ) {
params[i] = steppers[i].value;
}
}
private function onSearchChange( e:Event ):void {
setupSearchCtrl();
search();
update();
}
private function onStart( e:Event ):void {
if ( running ) {
running = false;
startBtn.label = "start";
//setStepCtrl( true );
}else {
running = true;
startBtn.label = "pause";
//setStepCtrl( false );
}
update();
}
private function search():void {
var algorithm:Object = SEARCH_LIST[ combo.selectedIndex ];
searchId++;
maze.reset();
if ( params ) {
log = algorithm.search.apply( null, [maze].concat( params ) );
}else{
log = algorithm.search( maze );
}
stepSlider.value = 0;
update();
}
private function top( e:Event ):void {
log.position = 0;
update();
}
private function prev( e:Event ):void {
log.prev();
update();
}
private function next( e:Event ):void {
log.next();
update();
}
private function end( e:Event ):void {
log.position = log.length - 1;
update();
}
private function slide( e:Event ):void {
if (log.position == stepSlider.value) return;
log.position = stepSlider.value;
update();
}
private function remap( e:Event ):void {
maze.make( mapCheck.selected ? 0 : 1 );
search();
}
private function setupSearchCtrl():void {
var s:Object = SEARCH_LIST[ combo.selectedIndex ];
params = s.params;
var num:int = params ? params.length : 0;
for ( var i:int = 0, l:int = steppers.length; i < l; i++ ) {
if ( i < num ) {
labels[i].visible = true;
labels[i].text = s.paramNames[i];
steppers[i].visible = true;
steppers[i].value = params[i];
if ( s.mins ) steppers[i].minimum = s.mins[i];
else steppers[i].minimum = 1;
}else {
labels[i].visible = false;
steppers[i].visible = false;
}
}
}
private function setStepCtrl( enabled:Boolean ):void {
for each(var c:Component in stepItems ) {
c.enabled = enabled;
}
}
}
}
import adobe.utils.CustomActions;
import flash.display.BitmapData;
import flash.events.StatusEvent;
import flash.geom.Matrix;
import flash.geom.Rectangle;
import flash.text.AntiAliasType;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFieldType;
import flash.text.TextFormat;
import flash.utils.ByteArray;
class Maze {
public static const CELL:int = 9;
public static const WALL:int = 2;
public static const COLORS:Array = [
0x333333,
0xf0f0f0,
0xB5B5B5,
0xF82018,
0xFF9822,
0x777777,
0x2233F4,
0x2233F4
];
public static const DIRS:Array = [
[0, -1],
[-1, 0],
[0, 1],
[1, 0]
];
//0:壁,
//1:未開拓の道
//2:探索済みの道
//3:探索中の道
//4:探索保留中の道
//5:枝刈り済みの道
//6:スタート
//7:ゴール
public var map:Array;
public var start:Position;
public var end:Position;
public var width:int;
public var height:int;
public var branches:Array/*Position*/;
public var informed:Boolean;
public var data:Object;
static public const NAMES:Object = {
memory: "分岐数(mem)",
maxMemory: "最大分岐数(max mem)",
time: "探索回数(time)",
depthLimit: "深さ制限(depth limit)",
discrepancy: "間違い制限(discrepancy)"
}
function Maze( width:int, height:int ) {
this.width = width;
this.height = height;
}
public function make( type:int = 1 ):void {
data = { memory:1, maxMemory:1, time:1 };
switch( type ) {
case 0: _makeDigMaze(); break;
case 1: _makeClusterMaze(); break;
}
start = new Position( 1, 1 );
do end = new Position( int(Math.random() * width) * 2 + 1, int(Math.random() * height) * 2 + 1 );
while ( end.x == start.x && end.y == start.y );
branches = [start];
start.score = evalute( start );
map[start.x][start.y] = 3;
}
public function reset():void {
data = { memory:1, maxMemory:1, time:1 };
for ( var x:int = 0; x < (width * 2); x++ ) {
for ( var y:int = 0; y < (height * 2); y++ ) {
switch( map[x][y] ) {
case 0: map[x][y] = 0; break;
default: map[x][y] = 1; break;
}
}
}
branches = [start];
map[start.x][start.y] = 3;
}
//穴掘り法で迷路作成。
private function _makeDigMaze():void {
_initMap( 0 );
var joints:Vector.<Position> = new Vector.<Position>();
var p:Position = new Position( int(Math.random() * width) * 2 + 1, int(Math.random() * height) * 2 + 1 );
var w:int = width * 2 + 1;
var h:int = height * 2 + 1;
do {
map[ p.x ][ p.y ] = 1;
var arr:Array = [];
for each( var d:Array in DIRS ) {
var nx:int = p.x + 2 * d[0];
var ny:int = p.y + 2 * d[1];
if ( 0 <= nx && nx < w && 0 <= ny && ny < h && map[nx][ny] == 0 ) {
arr.push( d );
}
}
var l:int = arr.length
if ( l == 0 ) {
l = joints.length;
if ( l == 0 ) break;
var r:int = l - 1;//int(l * Math.random());
p = joints[ r ];
joints[ r ] = joints[l - 1];
joints.pop();
continue;
}
joints.push( p );
d = arr[ int(l * Math.random()) ];
map[ p.x + d[0] ][ p.y + d[1] ] = 1;
p = new Position( p.x + d[0] * 2, p.y + d[1] * 2 );
}while ( true );
}
//クラスタリングアルゴリズムで迷路作成。
private function _makeClusterMaze():void {
var cluster:Vector.<Vector.<int>> = _initCluster();
var walls:Vector.<Position> = new Vector.<Position>();
_initMap( 1 );
for ( var x:int = 0; x < width; x++ ) {
for ( var y:int = 0; y < height; y++ ) {
if( y + 1 != height ) walls.push( new Position(x, y, 2) );
if( x + 1 != width ) walls.push( new Position(x, y, 3) );
}
}
//1つづつ壁を壊す
var l:int;
while ( (l = walls.length) > 0 ) {
var rand:int = Math.random() * walls.length;
var p:Position = walls[rand];
walls[rand] = walls[l - 1] ;
walls.length--;
var d:Array = DIRS[ p.dir ];
var num:int = cluster[p.x + d[0]][p.y + d[1]];
if ( num != cluster[p.x][p.y] ) {
map[p.x * 2 + d[0] + 1][p.y * 2 + d[1] + 1] = 1;
connectCluster( p.x, p.y, num, cluster );
}
}
}
//
private function connectCluster( x:int, y:int, num:int, cluster:Vector.<Vector.<int>> ):void {
var old:int = cluster[x][y];
cluster[x][y] = num;
for each( var d:Array in DIRS ) {
var nx:int = x + d[0];
var ny:int = y + d[1];
if ( 0 <= nx && nx < width && 0 <= ny && ny < height && old == cluster[nx][ny] ) connectCluster( nx, ny, num, cluster );
}
}
private function _initCluster():Vector.<Vector.<int>> {
var cluster:Vector.<Vector.<int>> = new Vector.<Vector.<int>>();
for ( var x:int = 0, i:int = 0; x < width; x++ ) {
cluster[x] = new Vector.<int>();
for( var y:int = 0; y < height; y++, i++ ) {
cluster[x][y] = i;
}
}
return cluster;
}
private function _initMap(type:int):void {
map = [];
for ( var x:int = 0, w:int = width * 2 + 1; x < w; x++ ) {
map[x] = [];
for( var y:int = 0, h:int = height * 2 + 1; y < h; y++ ) {
map[x][y] = int(type > 0 && (x % 2 == 1) && (y % 2 == 1));
}
}
}
public function bitmapData():BitmapData {
return new BitmapData( CELL * width + WALL * (width + 1), CELL * height + WALL * (height + 1), false );
}
public function draw( b:BitmapData, goal:Position = null ):void {
b.fillRect( b.rect, 0xFFFF );
var r:Rectangle = new Rectangle();
var bx:int = 0, by:int = 0;
for ( var x:int = 0, w:int = width * 2 + 1; x < w; x++, r.x = (bx += bw), r.y = by = 0 ) {
for ( var y:int = 0, h:int = height * 2 + 1; y < h; y++ ) {
var bw:int = r.width = (x % 2 == 0) ? WALL : CELL;
var bh:int = r.height = (y % 2 == 0) ? WALL : CELL;
b.fillRect( r, COLORS[ map[x][y] ] );
r.x = bx;
r.y = (by += bh);
}
}
if ( informed )
for ( var i:int = 0, l:int = branches.length; i < l; i++ ) {
var p:Position = branches[i];
drawText( "" + i, p.x, p.y, b );
}
if ( goal ) {
var p0:Position = goal, p1:Position;
while ( (p1 = p0.prev) ) {
var sx:Number = (p0.x + 1) / 2 * (WALL + CELL) - CELL / 2;
var sy:Number = (p0.y + 1) / 2 * (WALL + CELL) - CELL / 2;
var ex:Number = (p1.x + 1) / 2 * (WALL + CELL) - CELL / 2;
var ey:Number = (p1.y + 1) / 2 * (WALL + CELL) - CELL / 2;
var tmp:Number;
if ( sx > ex ) { tmp = sx; sx = ex; ex = tmp; }
if ( sy > ey ) { tmp = sy; sy = ey; ey = tmp; }
b.fillRect( new Rectangle( sx - 0.5, sy - 0.5, (ex - sx) + 1, (ey - sy) + 1 ), 0xFFFFFF );
p0 = p1;
}
}
b.fillRect( cellRect( start.x, start.y, CELL - 2), COLORS[6] );
b.fillRect( cellRect( end.x, end.y, CELL - 2), COLORS[6] );
drawText( "S", start.x, start.y, b );
drawText( "G", end.x, end.y, b );
}
private function drawText( str:String, x:int, y:int, b:BitmapData, color:uint = 0xFFFFFF ):void {
var text:TextField = new TextField();
text.autoSize = TextFieldAutoSize.LEFT;
text.embedFonts = true;
text.antiAliasType = AntiAliasType.NORMAL;
text.defaultTextFormat = new TextFormat("PF Ronda Seven", 8, color);
text.text = str;
var px:int = (x + 1) / 2 * (WALL + CELL) - CELL / 2 - text.width / 2 + 0.5;
var py:int = (y + 1) / 2 * (WALL + CELL) - CELL / 2 - 9.5;
b.draw( text, new Matrix( 1, 0, 0, 1, px, py) );
}
private function cellRect( x:int, y:int, size:Number ):Rectangle {
var rx:Number = (x + 1) / 2 * (WALL + CELL) - (CELL + size) / 2;
var ry:Number = (y + 1) / 2 * (WALL + CELL) - (CELL + size) / 2;
return new Rectangle( rx, ry, size, size )
}
public function clone():Maze {
var c:Maze = new Maze( width, height );
c.map = [];
for ( var x:int = 0, w:int = map.length; x < w; x++ ) {
c.map.push([]);
for ( var y:int = 0, h:int = map[x].length; y < h; y++ )
c.map[x].push( map[x][y] );
}
c.branches = [];
for ( var i:int = 0, l:int = branches.length; i < l; i++ )
c.branches.push( branches[i] );
c.data = { };
for ( var k:String in data ) c.data[k] = data[k];
c.informed = informed;
c.start = start;
c.end = end;
return c;
}
//ゴールまでのマンハッタン距離。低いほど良い。
public function evalute( pos:Position ):int {
return (Math.abs( pos.x - end.x ) + Math.abs( pos.y - end.y )) >> 1;
}
public function searchAt( index:int ):void {
var p:Position = branches[ index ];
var count:int = 0;
for( var i:int = 0; i < 4; i++ ){
var d:Array/*int*/ = DIRS[i];
var x:int = d[0] + p.x;
var y:int = d[1] + p.y;
if ( x < 0 || (width * 2) <= x || y < 0 || (height * 2) <= y ) continue;
if ( map[x][y] == 0 || map[x][y] == 2 ) continue;
if ( ++count == 2 ) { break; }
map[x][y] = 2;
x += d[0]; y += d[1];
map[x][y] = 3;
var next:Position = new Position( x, y, i );
next.prev = p;
next.depth = p.depth + 1;
branches.push( next );
next.score = evalute( next );
data.time++;
}
if ( count < 2 ) {
branches.splice( index, 1 );
map[p.x][p.y] = 2;
}
data.memory = branches.length;
if ( data.maxMemory < branches.length ) data.maxMemory = branches.length;
}
public function searchAllAt( index:int ):Array {
var arr:Array = [];
var p:Position = branches[ index ];
branches.splice( index, 1 );
map[p.x][p.y] = 2;
for( var i:int = 0; i < 4; i++ ){
var d:Array/*int*/ = DIRS[i];
var x:int = d[0] + p.x;
var y:int = d[1] + p.y;
if ( x < 0 || (width * 2) <= x || y < 0 || (height * 2) <= y ) continue;
if ( map[x][y] == 0 || map[x][y] == 2 ) continue;
map[x][y] = 2;
x += d[0]; y += d[1];
map[x][y] = 3;
var next:Position = new Position( x, y, i );
next.prev = p;
next.depth = p.depth + 1;
branches.push( next );
arr.push( next );
next.score = evalute( next );
data.time++;
}
data.memory = branches.length;
if ( data.maxMemory < branches.length ) data.maxMemory = branches.length;
return arr;
}
public function sort():void {
branches.sortOn( "score", Array.NUMERIC );
}
public function cut( p:Position ):void {
map[p.x][p.y] = 4;
branches.splice( branches.indexOf( p ), 1 );
}
public function cutRange( start:int, end:int = int.MAX_VALUE ):void {
if ( end > branches.length ) end = branches.length;
for ( var i:int = start; i < end; i++ ) {
var p:Position = branches[i];
map[p.x][p.y] = 4;
}
branches.splice( start, end - start );
}
public function isFinish():Position {
for each (var p:Position in branches)
if (p.score == 0) return p;
return null;
}
}
//
class Position {
//0:上, 1:左, 2:下, 3:右
public var dir:int;
public var x:int;
public var y:int;
public var score:int;
public var discrepancy:int;
public var prev:Position;
public var depth:int = 0;
function Position(x:int, y:int, dir:int = -1) {
this.x = x; this.y = y; this.dir = dir;
}
}
class Log {
public var goal:Position;
public var map:Vector.<Array> = new Vector.<Array>();
public var branches:Vector.<Array> = new Vector.<Array>();
public var data:Array = new Array();
public var position:int = 0;
public var informed:Boolean;
public function get length():int { return map.length; }
function Log( maze:Maze, informed:Boolean = false ) {
this.informed = informed;
add( maze );
}
public function add( maze:Maze ):void {
maze = maze.clone();
this.data.push( maze.data );
this.map.push( maze.map );
this.branches.push( maze.branches );
}
public function isFirst():Boolean { return position == 0; }
public function isLast():Boolean { return position == map.length - 1; }
public function next():int {
return isLast() ? position : ++position;
}
public function prev():int {
return isFirst() ? position : --position;
}
public function apply( maze:Maze, pos:int = -1 ):void {
if( pos == -1 ) pos = position
maze.map = map[ pos ];
maze.branches = branches[ pos ];
maze.data = data[pos];
maze.informed = informed;
}
}
class Node {
public var cost:Number;
public var position:Position;
}
class BreadthFirst {
static public const name:String = "幅優先(breadth-first)";
static public function search(maze:Maze):Log {
var log:Log = new Log(maze);
do {
for (var i:int = 0, l:int = maze.branches.length; i < l; i++ )
maze.searchAllAt( 0 );
log.add( maze );
if ( maze.branches.length == 0 || (log.goal = maze.isFinish()) ) { break; }
}while ( true );
return log;
}
}
class DepthFirst{
static public const name:String = "深さ優先(depth-first)";
static public function search(maze:Maze):Log {
maze = maze.clone();
var log:Log = new Log(maze);
do {
maze.searchAt( maze.branches.length - 1 );
log.add( maze );
log.goal = null;
if ( maze.branches.length == 0 || (log.goal = maze.isFinish()) ) {
trace( log.goal );
trace( maze.end.x, maze.end.y );
trace( log.goal.x, log.goal.y );
break;
}
}while ( true );
return log;
}
}
import flash.utils.setTimeout;
import flash.utils.getTimer;
var searchId:int = 0;
class IDDepthFirst{
static public const name:String = "反復深化深さ優先(iterative deepening)";
static public var best:int;
static public const paramNames:Array/*String*/ = ["margin"];
static public const params:Array/*int*/ = [4];
static public const mins:Array/*int*/ = [0];
static public function search(maze:Maze, margin:int ):Log {
best = int.MAX_VALUE;
maze = maze.clone();
var limit:int = maze.evalute( maze.start ) + margin;
maze.data.depthLimit = limit;
var log:Log = new Log( maze );
limitSearch( maze, limit, margin, log, searchId );
return log;
}
static private function limitSearch( maze:Maze, limit:int, margin:int, log:Log, id:int ):void {
if ( id != searchId ) return;
var startTime:int = getTimer();
var cut:Boolean = false;
do {
var end:int = maze.branches.length - 1;
var p:Position = maze.branches[ end ];
if( p.depth < limit ){
if ( cut ) log.add( maze );
maze.searchAt( end );
log.add( maze );
cut = false;
}else {
var d:int = p.depth + maze.evalute( p );
if ( best > d ) { best = d; }
maze.cutRange( end-- );
cut = true;
}
if ( maze.branches.length == 0 ) {
maze.reset();
limit = best + margin;
maze.data.depthLimit = limit;
log.add( maze );
best = int.MAX_VALUE;
limitSearch( maze, limit, margin, log, id );
break;
}
if ( (log.goal = maze.isFinish()) ) { break; }
//フリーズ回避
if ( cut == false && (getTimer() - startTime) > 30 ) {
setTimeout( limitSearch, 10, maze, limit, margin, log, id );
break;
}
}while ( true );
}
}
class HillClimbing {
static public const name:String = "山登り法(hill climbing)";
static public function search(maze:Maze):Log {
return DoubleLimit.search( maze, 1, 1 );
}
}
class BestFirst {
static public const name:String = "最良優先(best-first)";
static public function search(maze:Maze):Log {
return DoubleLimit.search( maze, 1, int.MAX_VALUE );
}
}
class LimitedDiscrepancy {
static public const name:String = "間違い制限(limited discrepancy)";
static public function search(maze:Maze):Log {
maze = maze.clone();
maze.data.discrepancy = "0";
var log:Log = new Log( maze, true );
limitSearch( maze, 0, log, searchId );
return log;
}
static public function limitSearch( maze:Maze, limit:int, log:Log, id:int ):void {
if ( id != searchId ) return;
var startTime:int = getTimer();
do {
var d:int = limit;
var l:int = maze.branches.length;
if ( d >= l ) d = l - 1;
var arr:Array = maze.searchAllAt( d );
arr.sortOn( "score" );
for (var i:int = 0, al:int = arr.length; i < al; i++ ) {
var p:Position = arr[ i ];
p.discrepancy = d + i;
}
maze.branches.sortOn( "discrepancy" );
log.add( maze );
l = maze.branches.length;
if ( l == 0 ) {
maze.reset();
limit++;
maze.data.discrepancy = limit;
log.add( maze );
continue;
}
if( (log.goal = maze.isFinish()) ) { break; }
if ( l > limit + 1 ) {
maze.cutRange( limit + 1 );
log.add( maze );
}
if( (getTimer() - startTime) > 30 ) {
setTimeout( limitSearch, 10, maze, limit, log, id );
break;
}
}while( true );
}
}
class BreadthFirstBeam {
static public const name:String = "幅優先ビーム(breadth-first beam)";
static public const paramNames:Array/*String*/ = ["ビーム幅(beam width)"];
static public const params:Array/*int*/ = [5];
static public function search(maze:Maze, beamWidth:int):Log {
return DoubleLimit.search( maze, beamWidth, beamWidth );
}
}
class BestFirstBeam {
static public const name:String = "最良優先ビーム(best-first beam)";
static public const paramNames:Array/*String*/ = ["ビーム幅(beam width)"];
static public const params:Array/*int*/ = [5];
static public function search(maze:Maze, beamWidth:int):Log {
return DoubleLimit.search( maze, 1, beamWidth );
}
}
class GoodFirst {
static public const name:String = "優良優先(good-first)";
static public const paramNames:Array/*String*/ = ["優先幅(good-first width)"];
static public const params:Array/*int*/ = [3];
static public function search(maze:Maze, goodWidth:int):Log {
return DoubleLimit.search( maze, goodWidth, int.MAX_VALUE );
}
}
class DoubleLimit{
static public const name:String = "二重制限(double limit)";
static public const paramNames:Array/*String*/ = ["優先幅(good width)", "ビーム幅(beam width)"];
static public const params:Array/*int*/ = [3, 7];
static public function search(maze:Maze, goodWidth:int, beamWidth:int ):Log {
var log:Log = new Log( maze, true );
do {
var l:int = maze.branches.length;
if ( l > goodWidth ) l = goodWidth;
for ( var i:int = 0; i < l; i++ ) {
maze.searchAllAt( 0 );
}
maze.sort();
log.add( maze );
l = maze.branches.length;
if ( l == 0 || (log.goal = maze.isFinish()) ) { break; }
if( beamWidth < l ) {
maze.cutRange( beamWidth );
log.add( maze );
}
}while ( true );
return log;
}
}