人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

下記の表の用な物があります。
意味としては 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

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

●質問者: kichitaka
●カテゴリ:コンピュータ ウェブ制作
✍キーワード:PHP アルゴリズム ルート 大文字 検索
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● Mook
●60ポイント

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

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


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

<?
//----------------------------------------------------------------
// 経路検索
//----------------------------------------------------------------
 // 発見経路数
 $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";
}
?>
◎質問者からの返答

ありがとうございます!

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ