経路検索のアルゴリズムについて教えてください。


下記の表の用な物があります。
意味としては A は D E に行く事が出来る。 例 A d e
という意味です。
下記のような表から BからEに行く事が出来るのか判断する、出来るのならば全てのルートを羅列する方法を教えてください。
言語はPHPを考えています。

A d e
B d c a
C d e a
D b e
E a b c d

*分かりやすくするために小文字と大文字をわけていますが同じ物だと考えてください。

回答の条件
  • 1人2回まで
  • 登録:2007/01/17 17:17:52
  • 終了:2007/01/24 17:20:02

回答(1件)

id:Mook No.1

Mook回答回数1312ベストアンサー獲得回数3912007/01/17 20:03:02

ポイント60pt

おもしろそうなので、試しに作ってみました。

アルゴリズムというほどたいした処理はしていませんが、簡単な実装例です。


(表記の仕様は、勝手に変更させていただきました。)

<?
//----------------------------------------------------------------
// 経路検索
//----------------------------------------------------------------
    //  発見経路数
    $numPath = 0;
    //  移動可能点の定義
    $ar = array( "A"=>array( "D", "E" ),
                 "B"=>array( "A", "C", "D" ),
                 "C"=>array( "A", "E", "D" ),
                 "D"=>array( "B", "E" ),
                 "E"=>array( "A", "B", "C", "D" ) );

    $start = "B";
    $goal  = "E";
    print "$start から $goal までの経路を検索します<br><br>\n";
    searchPath( array( $start ), $goal );

    if ( $numPath > 0 ) {
        print "<br>[$numPath] 経路見つかりました<br>\n";
    } else {
        print "$start から $goal までの経路はありません<br>\n";
    }

//----------------------------------------------------------------
function searchPath( $pathArray, $goal ) {
//----------------------------------------------------------------
    global $ar;
    global $numPath;

    $lastPoint = $pathArray[count( $pathArray ) - 1];
    foreach( $ar[$lastPoint] as $point ) {
        // ゴール判定
        if ( strcmp( $point, $goal ) == 0 ) {
            printPath( array_merge( $pathArray, array( $goal ) ) );
            $numPath++;
        // すでに通過した点でなければ先を検索
        } else if ( !in_array( $point, $pathArray ) ){
            searchPath( array_merge( $pathArray, array( $point ) ), $goal );
        }
    }
}

//----------------------------------------------------------------
function printPath( $pathArray ) {
//----------------------------------------------------------------
// 配列の経路を表示
    print $pathArray[0];
    for( $i=1 ; $i<count( $pathArray ) ; $i++ ) {
        print " ⇒ ".$pathArray[$i];
    }
    print "<br>\n";
}
?>
id:kichitaka

ありがとうございます!

ここ迄して頂けるとは感謝です。

自分が考えていたよりもかなり効率化されていて非常に勉強になりました。

2007/01/18 12:48:24

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません