In case Flash no longer exists; a copy of this site is included in the Flashpoint archive's "ultimate" collection.

Dead Code Preservation :: Archived AS3 works from wonderfl.net

遺伝的アルゴリズムで巡回セールスマン問題を解くを改良してみた

■操作説明
start 開始
stop 停止
random node(都市)の位置をランダムにします
circle node(都市)を円状に配置
各nodeは移動(ドラッグ&ドロップ)可能です。

■パラメータ説明
node 都市の数
salesperson セールスマンの数(nodeの数だけ遺伝子を所有)
mutationVolume 突然変異の量
aliveVolume 生存率

■変更点
・交叉の方法を変更
 元の遺伝子が崩れない場合のみ交叉を行うように設定(サブツアー交換交叉)
・突然変異の種類を追加
 遺伝子配列の反転や挿入など
・2位以下の生存をランダムに設定
 1位のセールスマンは必ず生存し、2位はaliveVolumeの確率で生存、3位はaliveVolume * aliveVolumeの確率で生存…
・その他
 2位以下のセールスマンも見れるように設定。quickSeach機能(遺伝的アルゴリズムを使わない探索)追加など。
Get Adobe Flash player
by shohei909 03 Sep 2011
  • Forked from postnum's 人工知能(遺伝的アルゴリズム GA)で巡回セールスマン問題を解く
  • Diff: 628
  • Related works: 1
  • Talk

    postnum at 07 Sep 2011 20:34
    凄い! コード読んで勉強させてもらいます! ところで、大変厚かましくも質問なのですが、、、 こういった場合はenterframeで回さない場合はどういう方法が考えられるでしょう? ストレートに計算させ続けてしまってプチフリーズ状態になってyearカウント含めてenterframeにしちゃったんで…汗
    postnum at 07 Sep 2011 20:39
    きちんと確認せずにコメント投稿してしまいました。 スピードというパラメータつけてらっしゃいますね。 勉強させてもらいますね!
    shohei909 at 08 Sep 2011 09:17
    getTimerメソッドを使って時間をみて、適当に次のフレームに進めるのもありだと思います。 例えば、こんなふうに。 var t:int = getTimer(); do{ nextGeneration(); }while( t + 20 > getTimer() ) あとは、マルチスレッドをできるようにするライブラリがあるのでそちらを使ってみるのもいいかもしれません。 Threader: http://wonderfl.net/c/ipyi

    Tags

    Embed
/**
 * Copyright shohei909 ( http://wonderfl.net/user/shohei909 )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/u3b4
 */

// forked from sabotenbrother's 人工知能(遺伝的アルゴリズム GA)で巡回セールスマン問題を解く
/*
もっと良くなりそうなところがあったので改造させていただきました。


■変更した部分の説明

まず、遺伝子の交叉方法です。
fork元では、交叉の際に交叉範囲外の経路をランダムにつなぎ合わせていました。
ある程度良い配列になってくると、ランダムな部分に邪魔されて、親より良い配列が生まれる確率が非常に低くなります。
このため、割と早い段階で経路が変わらなくなっていました。

これを、交叉の方法をサブツアー交換交叉に変えることで改良しています。
サブツアー交換交叉では、
[1,3,8,7]と[3,7,1,8]の様に同じ要素を持つ部分を見つけられた時に交叉を行います。
こうすることで、交叉時に経路が壊されることを防いでいます。




次に、突然変異です。
変異の種類が少ないと1回の変異で見つけられるルートが少なく、親に近いが、少し違う経路があまり探索できません。
(ある程度良い経路になってくると、何か所も変異させると偶然親より優秀になる確率というのは非常に低いくなる。)

変異の種類を増やしたことで、1か所のみ変異に幅を広げることができ、少ない変異で多くの経路を探索できるようになってます。




次に、生存する個体の選択方法
各個体に順位をつけて、上からn位までを生存させるという方法をとると、上位が同じ配列に独占される可能性が高くなり多様性が失われます。

1位だけ必ず生存させて、2位以下はある程度の確率で排除することでこれを防いでいます。



そのほかに、Arrayからリンクリストに変更するなどして高速化をしています。


■Quick Searchについて
Quick Searchは遺伝的アルゴリズムを使わない探索で、高速にそこそこ良い解を見つけてくれます。
*/
 package  
{
    import com.bit101.components.Component;
    import flash.display.Sprite;
    import flash.events.Event;
    
    import com.bit101.components.PushButton;
    import com.bit101.components.HUISlider;
    import com.bit101.components.VUISlider;
    import com.bit101.components.NumericStepper;
    import com.bit101.components.Label;
    import com.bit101.components.Text;
    import com.bit101.components.Style;
    
    [SWF(width = '465', height = '465', backgroundColor = '#EEEEFF', frameRate = '60')]
    
    /**
     * 人工知能(遺伝的アルゴリズム GA)で巡回セールスマン問題を解く
     * ...
     * @author sabotenbrother
     */
    public class World extends Sprite
    {
        private var node:Node;
        private var pool:Pool;
        
        private var running:Boolean = false;
        private var time:Number;
        
        // GUIパーツ
        private var startButton:PushButton;
        private var stopButton:PushButton;
        private var randomButton:PushButton;
        private var circleButton:PushButton;
        
        private var nodeLabel:Label;
        private var salespersonLabel:Label;
        
        private var nodeHUISlider:HUISlider;
        private var salespersonHUISlider:HUISlider;
        private var mutationVolumeHUISlider:HUISlider;
        private var aliveVolumeHUISlider:HUISlider;
        private var speedHUISlider:HUISlider;
        
        
        private var noStepper:NumericStepper;
        
        private var totalLengthText:Text;
        private var generationLengthText:Text;
        
        public function World():void 
        {
            if (stage) init();
            else addEventListener(Event.ADDED_TO_STAGE, init);
        }
        
        private function init(event:Event = null):void 
        {
            stage.quality = "middle"
            createWorld();
        }
        
        /**
         * 世界を創造する
         */
        public function createWorld():void{
            var nodeNum:int = 20;
            
            // ノード作成
            node = new Node( 20 );
            node.x = 2;
            addChild(node).y = 90;
            
            Style.BUTTON_FACE = 0xDDDDFD
            
            // GUI作成
            startButton = new PushButton(this, 0, 0, "restart", start);
            startButton.width = 60;
            
            stopButton = new PushButton(this, 60, 0, "stop", stop);
            stopButton.width = 60;
            stopButton.enabled = false;
            
            
            randomButton = new PushButton(this, 190, 0, "random", random);
            randomButton.width = 60;
            circleButton = new PushButton(this, 250, 0, "circle", circlePattern);
            circleButton.width = 60;
            
            
            nodeLabel = new Label(this, 10, 40, "node");
            salespersonLabel = new Label(this, 10, 60, "saleperson");
            
            nodeHUISlider = new HUISlider(this, 60, 40, "");
            nodeHUISlider.width = 185;
            nodeHUISlider.value = nodeNum;
            nodeHUISlider.minimum = 4;
            nodeHUISlider.maximum = 170;
            nodeHUISlider.tick = 1;
            
            salespersonHUISlider = new HUISlider(this, 60, 60, "");
            salespersonHUISlider.width = 185;
            salespersonHUISlider.value = 40;
            salespersonHUISlider.minimum = 10;
            salespersonHUISlider.maximum = 200;
            salespersonHUISlider.tick = 1;
            
            mutationVolumeHUISlider = new HUISlider(this, 305, 40, "");
            mutationVolumeHUISlider.width = 175;
            mutationVolumeHUISlider.value = 0.20;
            mutationVolumeHUISlider.minimum = 0;
            mutationVolumeHUISlider.maximum = 0.99;
            mutationVolumeHUISlider.tick = 0.01;
            mutationVolumeHUISlider.labelPrecision = 2;
            mutationVolumeHUISlider.addEventListener( "sliderChange", setValue );

            aliveVolumeHUISlider = new HUISlider(this, 305, 60, "");
            aliveVolumeHUISlider.width = 175;
            aliveVolumeHUISlider.value = 0.85;
            aliveVolumeHUISlider.minimum = 0;
            aliveVolumeHUISlider.maximum = 1;
            aliveVolumeHUISlider.tick = 0.01;
            aliveVolumeHUISlider.labelPrecision = 2;
            aliveVolumeHUISlider.addEventListener( "sliderChange", setValue );

            var mutationVolumeLabel:Label = new Label(this, 230, 40, "mutationVolume");
            var aliveVolumeLabel:Label = new Label(this, 230, 60, "aliveVolume");

            var generationLabel:Label = new Label(this, 5, 420, "Year");
            var totalLengthLabel:Label = new Label(this, 5, 440, "TotalLength");
            
            generationLengthText = new Text(this, 70, 420, "");
            generationLengthText.width  = 70;
            generationLengthText.height = 20;
            
            totalLengthText = new Text(this, 70, 440, "");
            totalLengthText.width  = 70;
            totalLengthText.height = 20;

            speedHUISlider = new HUISlider( this, 150, 420, "speed" );
            speedHUISlider.width  = 340;
            speedHUISlider.maximum = 50;
            speedHUISlider.tick = 0.1;
            speedHUISlider.value = 1;
        
            new Label(this, 270, 440, "No.");
            noStepper = new NumericStepper( this, 290, 440, onChange );
            noStepper.minimum = 0;
            noStepper.maximum = salespersonHUISlider.value;

            var searchButton:PushButton = new PushButton( this, 380, 440, "quickSearch", quickSearch );
            searchButton.width = 80;
            searchButton.height = 18;
            
            addEventListener(Event.ENTER_FRAME, nextGeneration);
            node.addEventListener( "change", onChange );
        }
        
        
        /**
         * 交叉を開始する
         * 
         * @param    event
         */
        private function start(event:Event):void 
        {
            if ( node.size != nodeHUISlider.value ) { 
                node.setNode( nodeHUISlider.value );
                node.randomize();
            }
            // 巡回セールスマン(遺伝子作成)
            pool = new Pool( salespersonHUISlider.value, node );
            running = true;
            time = 0;
            
            var c:Component;
            var enable:Array = [ stopButton ];
            var disable:Array = [ nodeHUISlider, salespersonHUISlider ];
            for each( c in enable ) { c.enabled = true; }
            for each( c in disable ){ c.enabled = false; } 
        }
        
        /**
         * 次の世代へ進める
         * 
         * @param    event
         */
        private function nextGeneration(event:Event):void 
        {
            if ( running ) {
                while( pool.age < time ){
                    pool.nextGeneration();
                }
                noStepper.maximum = pool.size;
                if( noStepper.value >= pool.size ){ noStepper.value = pool.size - 1 }
                node.drawRoute( pool.people[noStepper.value] );
                generationLengthText.text = pool.age.toString();
                totalLengthText.text = pool.people[noStepper.value].score.toFixed( 1 );
                time += speedHUISlider.value;
            }
        }
        
        private function quickSearch( evant:Event ):void {
            if( pool ){
                noStepper.maximum = pool.size;
                if( noStepper.value >= pool.size ){ noStepper.value = pool.size - 1 }
                var p:Person = pool.people[noStepper.value];
                if( node.size == p.genomeSize ){
                    p.quickSearch( node );
                    node.drawRoute( p );
                    generationLengthText.text = pool.age.toString();
                    totalLengthText.text = p.score.toFixed( 1 );
                    time += speedHUISlider.value;
                }else {
                    node.drawRoute( null );
                }
            }
        }
        
        /**
         * 交叉を停止する
         * 
         * @param    event
         */
        private function stop(event:Event):void {
            if ( running ) { 
                running = false;
                
                var c:Component;
                var disable:Array = [ stopButton ];
                var enable:Array = [ nodeHUISlider, salespersonHUISlider ];
                for each( c in enable ) { c.enabled = true; }
                for each( c in disable ){ c.enabled = false; } 
            }
        }
        
        /**
         * nodeの位置をランダムにする
         * 
         * @param    event
         */
        private function random(event:Event):void
        {
            node.setNode( nodeHUISlider.value );
            node.randomize();
        }
        
        /**
         * nodeをサークル上に配置する
         * 
         * @param    event
         */
        private function circlePattern(event:Event):void{
            node.setNode( nodeHUISlider.value );
            node.circlePattern();
        }
        
        /**
         * パラメータを再設定する
         * 
         * @param    event
         */
        private function setValue(event:Event):void
        {
            if( pool ){
                pool.mutationVolume = mutationVolumeHUISlider.value;     // 突然変異の量
                pool.aliveVolume    = aliveVolumeHUISlider.value;       // 生存率
                noStepper.maximum = pool.size;
                if( noStepper.value >= pool.size ){ noStepper.value = pool.size - 1 }
                node.drawRoute( pool.people[noStepper.value] );
            }
        }
        /**
         * ノードが移動したとき
         * 
         * @param    event
         */
        private function onChange(event:Event):void
        {
            if ( pool ) {
                noStepper.maximum = pool.size;
                if( noStepper.value >= pool.size ){ noStepper.value = pool.size - 1 }
                var p:Person = pool.people[noStepper.value];
                if( node.size == p.genomeSize ){
                    pool.resetScore( node );
                    node.drawRoute( p );
                    generationLengthText.text = pool.age.toString();
                    totalLengthText.text = p.score.toFixed( 1 );
                    time += speedHUISlider.value;
                }else {
                    node.drawRoute( null );
                }
            }
        }
        
    }
}
import flash.display.SpreadMethod;
import flash.geom.Point;
import flash.events.Event;
    
/**
 * セールスマンのプール(GAでコントロール)
 * ...
 * @author sabotenbrother
 */
class Pool{
    public var people:Array = [];    // 遺伝子プール
    public var node:Node;
    public var size:int;
    public var age:int = 0;                        // 世代
    public var mutationVolume:Number   = 0.7;    // 各個体に1回以上の変異が起こる確率
    public var aliveVolume:Number  = 0.2;        // 3番目に良い個体の生存率
    
    public function Pool( size:int, node:Node ) {
        this.size = size;
        this.node = node;
        
        for ( var i:int = 0; i < size; i++ ) { 
            var p:Person = new Person( node.size );
            p.setScore( node );
            people.push( p ) 
        }
    }
    
    //交差の回数
    private var x:int = 0;    
    /**
     * 次の世代へ進める
     */
    public function nextGeneration():void {
        var aliveVolume:Number = this.aliveVolume;
        var mutationVolume:Number = this.mutationVolume;
        var people:Array = this.people;
        var l:int = people.length;
        var nodeNum:int = node.size;
        var ar:Number = 1
        //交叉の判定に用いる部分
        for ( var i:int = 1; i < l; i++ ) {
            if ( ( ar *= aliveVolume ) < Math.random() ) {
                //新しい遺伝子の作成
                var p0:Person = people[ (i * Math.random()) >> 0];    //親0
                var p1:Person = people[ (i * Math.random()) >> 0];    //親1
                var p2:Person = people[ i ];                            //子
                var p3:Person;
                
                var g0:uintNode = p0.gene;
                var g1:uintNode = p1.gene;
                var g2:uintNode = p2.gene;
                var f0:uintNode = g0;
                
                //遺伝子の交叉
                //遺伝子を半分に切って構成要素が一致したときのみ交叉を行う。
                /* 実際のところ、交叉できる確率が低いので交叉はしなくても探索の性能は大してかわらない。 */
                var f:Boolean = false;
                var l1:int = p0.genomeSize, s:int, e:int, l2:int = l1 / 2, j:int, vl:int,vl2:int;    
                if( p0 != p1 ){
                    vl = Math.random() * (l2 - 3) + 3;
                    s = Math.random() * l1;
                    g0 = f0 = g0.at( s );
                    g1 = g1.at( s );
                    var a0:Array = [];
                    var a1:Array = [];
                    for ( j = 0; j < vl; j++ ) {
                        if ( (a0[j] = g0.value) != (a1[j] = g1.value) ) { f = true; }
                        g0 = g0.next; g1 = g1.next;
                    }
                    if ( f ) { 
                        g0 = f0; 
                        a0.sort( Array.NUMERIC ); a1.sort( Array.NUMERIC );
                        for( j = 0; j < l2; j++ ){ if ( a0[j] != a1[j] ) { f = false; break; } }
                    }
                }
                
                if ( f ) {
                    for( j = 0; j < vl; j++ ){ g2.value = g0.value; g0 = g0.next; g2 = g2.next; }
                    for ( ; j < l1; j++ ) { g2.value = g1.value; g1 = g1.next; g2 = g2.next; }
                    p2.setScore( node );
                    if ( ++i < l ) {
                        p2 = people[ i ];
                        g2 = p2.gene;
                        for( j = 0; j < vl; j++ ){ g2.value = g1.value; g1 = g1.next; g2 = g2.next; }
                        for ( ; j < l1; j++ ) { g2.value = g0.value; g0 = g0.next; g2 = g2.next; }
                        p2.setScore( node );
                    }
                }else {
                    for ( j = 0; j < l1; j++ ) { g2.value = g0.value; g0 = g0.next; g2 = g2.next; }
                    
                    //突然変異
                    do {
                        f = true;
                        var firNode:uintNode, secNode:uintNode, thrNode:uintNode; 
                        var rand:int = Math.random() * 6;
                        var sa0:Array, sa1:Array, tmp:uint;
                        if ( rand < 4 ) {
                            if( rand < 3 ){
                                if( rand == 0 ){
                                    //単塩基交換
                                    firNode = g2.at( Math.random() * l1 );
                                    secNode = firNode.at( Math.random() * (l2 - 1) + 1 );
                                    tmp = firNode.value;
                                    firNode.value = secNode.value;
                                    secNode.value = tmp;
                                }else {
                                    //部分反転(逆位)
                                    //※この変異が割と重要
                                    firNode = g2.at( Math.random() * l1 );
                                    secNode = firNode.at( Math.random() * (l2 - 1) + 1 );
                                    firNode.reverse( secNode );
                                }
                            }else{
                                //単塩基挿入
                                firNode = g2.at( Math.random() * l1 );
                                secNode = firNode.at( Math.random() * (l1 - 2) + 2 );
                                firNode.add( secNode )
                            }
                        }else if ( rand < 6 ){
                            if( rand == 4 ){
                                //複数塩基挿入
                                firNode = g2.at( Math.random() * l1 );
                                vl = Math.random() * (l1 - 2) + 2;
                                secNode = firNode.at( vl );
                                thrNode = secNode.at( Math.random() * (l1 - 1 - vl) + 1 );
                                thrNode.addList( firNode, secNode )
                            }else {
                                //隣接交換
                                firNode = g2.at( Math.random() * l1 );
                                secNode = firNode.next;
                                tmp = firNode.value;
                                firNode.value = secNode.value;
                                secNode.value = tmp;
                            }
                        }else {
                            firNode = g2.at( Math.random() * l1 );
                            vl = ( Math.random() * l2 - 1 ) + 1
                            vl2 = ( Math.random() * l1 - 2 * vl );
                            firNode.changeList( firNode.at(vl + vl2), vl );
                        }
                    }while ( mutationVolume > Math.random() );
                    p2.setScore( node );
                }
            }
        }
        people.sortOn( "score", Array.NUMERIC );
        age++;
    }
    public function resetScore( node:Node ):void {
        for each( var p:Person in people ) { p.setScore( node ); }
        people.sort( function _( a:Person, b:Person ):Number { return a.score < b.score ? -1 : 1; } )    
    }
}

import flash.display.Sprite;

class Person {
    /** 遺伝子情報 */
    public var gene:uintNode;
    public var genomeSize:int;
    
    /** 評価値(低い方が良い) */
    public var score:Number = Infinity; 
    function Person( genomeSize:int ):void {
        if( (this.genomeSize = genomeSize) > 0 ){
            var vec1:Vector.<uint> = new Vector.<uint>();
            for ( var i:uint = 0; i < genomeSize; i++ ) { vec1.push( i ); } 
            var j:uint = genomeSize;
            gene = new uintNode( vec1.splice( Math.random() * j, 1 )[0] );
            while( --j > 0 ){ gene.add( new uintNode( vec1.splice( Math.random() * j, 1 )[0] ) ); }
        }
    }
    
    public function setScore( node:Node ):void {
        var arr:Array = node.nodeArr, l:int = arr.length, dx:Number, dy:Number;
        var un:uintNode = gene, n0:Sprite = arr[ un.prev.value ], n1:Sprite = arr[ un.value ];
        score = 0;
        do{
            score += Math.sqrt( (dx = n0.x - n1.x) * dx + (dy = n0.y - n1.y) * dy );
            n0 = n1; n1 = arr[ (un = un.next).value ];
        }while ( gene != un );
    }
    
    /*
     * 手抜きサーチ
     * 遺伝的アルゴリズムを使わない検索法。
     * 最適解とは限らない。
     **/
    public function quickSearch( node:Node ):void {
        for ( var i:int = 0, c:int = 0; c < 2; i = 1 - i, c++ ) {
            if( [ quickSearch1, quickSearch2 ][i]( node ) ){ c = 0 };
        }
        setScore( node );
    }
    
    //ねじれを解く
    public function quickSearch1( node:Node, all:Boolean = true ):Boolean {
        var re:Boolean = false;
        var arr:Array = node.nodeArr, gene:uintNode = this.gene;
        var l:int = genomeSize, c:int = 0;
        var n0:uintNode, n1:uintNode = gene, n2:uintNode, n3:uintNode;
        var p0:Sprite, p1:Sprite = arr[ n1.value ], p2:Sprite, p3:Sprite;
        do {
            p0 = p1; n0 = n1;
            p1 = arr[ (n1 = n1.next).value ];
            var min:Number = Infinity;
            var minP:int = 0;
            var sx1:int = p0.x, sy1:int = p0.y, ex1:int = p1.x, ey1:int = p1.y;
            p2 = arr[ (n2 = n1.next).value ];
            p3 = arr[ (n3 = n2.next).value ];
            do {
                var sx2:int = p2.x, sy2:int = p2.y, ex2:int = p3.x, ey2:int = p3.y;
                var cx:Number, cy:Number, dx:Number, dy:Number;
                var r:Number = ( cx = sx1 - ex1 ) * ( dy = sy2 - ey2 ) - ( cy = sy1 - ey1 ) * ( dx = sx2 - ex2 );
                if( r != 0 ){
                    var ax:Number = sx1 - sx2;
                    var ay:Number = sy1 - sy2;
                    var s:Number = (dy * ax - dx * ay ) / r
                    var t:Number = (cy * ax - cx * ay ) / r
                    if ( 0 <= t && t < 1 && 0 <= s  && s < 1 ) {
                        n1.reverse( n2 );
                        p1 = arr[ n1.value ];
                        if (! all ) { return true; } re = true; c = 0;
                        break;
                    }
                }
                p2 = p3; n2 = n3; p3 = arr[ (n3 = n3.next).value ];
            }while ( n0 != n3 )
        }while ( c++ < l );
        return re;
    }
     
    //各点を現在つっかっているルートのうち最短になる部分に組み込む。
    public function quickSearch2( node:Node, all:Boolean = true ):Boolean {
        var re:Boolean = false;
        var arr:Array = node.nodeArr, gene:uintNode = this.gene;
        var l:int = genomeSize, c:int = 0;
        var n0:uintNode = gene, n1:uintNode, n2:uintNode;
        var p0:Sprite, p1:Sprite, p2:Sprite;
        do {
            p0 = arr[ (n0 = n0.next).value ];
            var min:Number = Infinity;
            var minN:uintNode;
            p1 = arr[ (n1 = n0.prev).value ];
            p2 = arr[ (n2 = n0.next).value ];
            do{
                var dx:Number, dy:Number;
                var l0:Number = Math.sqrt( ( dx = p0.x - p1.x ) * dx + ( dy = p0.y - p1.y ) * dy );
                var l1:Number = Math.sqrt( ( dx = p2.x - p1.x ) * dx + ( dy = p2.y - p1.y ) * dy );
                var l2:Number = Math.sqrt( ( dx = p0.x - p2.x ) * dx + ( dy = p0.y - p2.y ) * dy );
                var s:Number = (l0 + l2) - l1;
                if ( min > s ) { minN = n1; min = s; }
                p1 = p2; n1 = n2; p2 = arr[ (n2 = n2.next).value ]
            }while( n0 != n2 ) 
            if ( minN.next != n0 ) { 
                minN.add( n0 );
                if (! all ) { return true; } 
                c = 0; re = true;
            }
        }while ( c++ < l );
        return re;
    }        
}

class uintNode{
    public var value:uint = 0;
    public var next:uintNode;
    public var prev:uintNode;
    
    function uintNode( value:uint ):void { this.value = value; next = this; prev = this; }
    
    /** このノードを取り除きます */
    public function remove():uintNode {
        next.prev = prev; prev.next = next; next = this; prev = this;
        return this;
    }
    
    /** このノードの直後に新たなノードを加えます。 */
    public function add( node:uintNode ):void {
        if ( node == this || node == next ) { return; }
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = this;
        node.next = next; 
        next.prev = node; 
        next = node;
    }
    
    /** このノードの直後にfirstから始まりlastで終わるリンクリストを挿入します。 */
    public function addList( first:uintNode, last:uintNode ):void {
        if ( first == this || first == next ) { return; }
        first.prev.next = last.next;
        last.next.prev = first.prev;
        first.prev = this;
        last.next = next; 
        next.prev = last; 
        next = first;
    }
    
    /** 指定した位置にあるノードを呼び出す */
    public function at( pos:int ):uintNode {
        var n:uintNode = this;
        while ( pos-- > 0 ) { n = n.next; }
        return n;
    }
    
    public function reverse( node:uintNode ):void {
        if( node == this ){ return }
        var n0:uintNode = this, n1:uintNode = node, tmp:uint;
        do{
            tmp = n0.value;
            n0.value = n1.value;
            n1.value = tmp;
        }while ( n1 != (n0 = n0.next) && n0 != (n1 = n1.prev) )
    }
    
    public function changeList( node:uintNode, l:int ):void {
        if( node == this ){ return }
        var n0:uintNode = this, n1:uintNode = node, tmp:uint;
        for ( var i:int = 0; i < l; i++ ) {
            tmp = n0.value;
            n0.value = n1.value;
            n1.value = tmp;
            n0 = n0.next; n1 = n1.next;
        }
    }
}

import flash.events.MouseEvent;
import flash.geom.Rectangle;

/**
 * ノード = 各都市
 * ...
 * @author sabotenbrother
 */
class Node extends Sprite
{
    public var nodeArr:Array = new Array();
    private var blocker:Sprite = new Sprite();
    private var line:Sprite = new Sprite();
    private var boundary:Sprite = new Sprite();
    private var _size:int = 0;
    private var person:Person;
    
    public function get size():int { return _size; }
    private const radius:int = 4;
    public static const WIDTH:int = 460;
    public static const HEIGHT:int = 320;
    
    public function Node(nodeNum:int){
        initNode(nodeNum);
    }
    
    /**
     * nodeを引数の数だけ初期化
     * 
     * @param    nodeNum    ノードの数
     */
    public function initNode(nodeNum:int):void
    {
        _size = nodeNum;
        
        // ノード表示区域境界線用のスプライト
        boundary.graphics.lineStyle(1, 0x0);
        boundary.graphics.beginFill(0xFFFFFF);
        boundary.graphics.drawRect(0, 0, WIDTH, HEIGHT);
        boundary.graphics.endFill();
        addChild(boundary);
        
        for (var i:int = 0; i < nodeNum; i++) {
            var sp:Sprite = new Sprite();
            nodeArr.push(sp);

            nodeArr[i].graphics.beginFill(0x000000);
            nodeArr[i].graphics.drawCircle(0, 0, radius);
            nodeArr[i].graphics.endFill();
            nodeArr[i].buttonMode = true;
            
            nodeArr[i].x = radius + Math.floor(Math.random() * (WIDTH - radius * 2));
            nodeArr[i].y = radius + Math.floor(Math.random() * (HEIGHT - radius * 2));
            nodeArr[i].addEventListener(MouseEvent.MOUSE_DOWN, startDragging);
            addChild(nodeArr[i]);
        }
        
        // ルート表示用のスプライト
        addChild(line);
        
        // 非選択用のレクタングル
        blocker.graphics.beginFill(0x000000);
        blocker.graphics.drawRect(0, 0, WIDTH, HEIGHT);
        blocker.graphics.endFill();
        blocker.alpha = 0.1;
        blocker.visible = false;
        addChild(blocker);
    }

    /**
     * nodeを再設定
     * 
     * @param    nodeNum
     */
    public function setNode(nodeNum:int):void
    {
        var length:int = nodeArr.length;
        if( _size != nodeNum ){
            _size = nodeNum; drawRoute( null );
        }
        for (var i:int = 0; i < length; i++) {
            removeChild(nodeArr[0]);
            nodeArr.shift();
        }
        
        for (var j:int = 0; j < nodeNum; j++) {
            var sp:Sprite = new Sprite();
            nodeArr.push(sp);

            nodeArr[j].graphics.beginFill(0x000000);
            nodeArr[j].graphics.drawCircle(0, 0, radius);
            nodeArr[j].graphics.endFill();
            nodeArr[j].buttonMode = true;
            
            nodeArr[j].addEventListener(MouseEvent.MOUSE_DOWN, startDragging);
            addChild(nodeArr[j]);
        }
    }
    
    /**
     * セールスパーソンのルートを描画
     * 
     * @param    person セールスパーソン
     */
    public function drawRoute( person:Person ):void {
        this.person = person;
        line.graphics.clear();
        if ( person == null ) { return; }
        line.graphics.lineStyle(1, 0x0);
        
        var l:int = _size;
        var n:uintNode = person.gene
        line.graphics.moveTo( nodeArr[n.value].x, nodeArr[n.value].y );
        for (var i:int = 0; i < l; i++) {
            n = n.next;
            line.graphics.lineTo(nodeArr[n.value].x, nodeArr[n.value].y);
        }
    }
    
    /**
     * nodeの位置をランダムにする
     */
    public function randomize():void
    {
        for (var i:int = 0; i < nodeArr.length; i++) {
            nodeArr[i].x = 6 + Math.floor(Math.random() * (WIDTH - 12));
            nodeArr[i].y = 6 + Math.floor(Math.random() * (HEIGHT - 12));
        }
        dispatchEvent( new Event( "change" ) );
    }
    
    /**
     * nodeを円状に配置
     */
    public function circlePattern():void
    {
        var angle:Number = 0.02;
        var radius:int = 140;
        
        for (var i:int = 0; i < nodeArr.length; i++) {
            nodeArr[i].x = (stage.stageWidth / 2) + radius * Math.cos(angle + i / nodeArr.length * Math.PI * 2);
            nodeArr[i].y = 160 + radius * Math.sin(angle + i / nodeArr.length * Math.PI * 2);
        }            
        dispatchEvent( new Event( "change" ) );
    }
    /*
    ///**
     * 全nodeを移動できるようにする
     /
    public function dragTrue():void
    {
        blocker.visible = false;
    }

    /**
     * 全nodeを移動できないようにする
     /
    public function dragFalse():void
    {
        blocker.visible = true;
    }
    */
    private function startDragging(event:MouseEvent):void 
    {
        event.target.startDrag(false, new Rectangle(0 + radius, 0 + radius, WIDTH - radius * 2, HEIGHT - radius * 2));
        this.addEventListener(MouseEvent.MOUSE_UP, stopDragging);
    }

    private function stopDragging(event:MouseEvent):void 
    {
        event.target.stopDrag();
        this.removeEventListener(MouseEvent.MOUSE_UP, stopDragging);
        dispatchEvent( new Event( "change" ) );
    }
}