【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は謹んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.18633

経路探索
投稿者---あり(2004/12/12 03:52:25)


http://www.geocities.jp/m_hiroi/puzzle/puzdoc01.htmlの経路を求めるプログラムですが、search( 0, 6 )の部分でスタートとゴールを決めるのですが、ランダムにスタートとゴールを決めたいです。その際、スタートとゴールの番号は異なります。
このプログラムはいくつかの経路が探索され、一番最初に表示されるのが最短経路ですが最短経路だけを表示させたいです。
お願いします。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NODE 7
#define SIZE 64

/* 隣接リスト */
const char adjacent[NODE][4] = {
1, 2, -1, -1, /* A */
0, 2, 3, -1, /* B */
0, 1, 4, -1, /* C */
1, 4, 5, -1, /* D */
2, 3, 6, -1, /* E */
3, -1, -1, -1, /* F */
4, -1, -1, -1, /* G */
};

/* Queue */
char path[SIZE][NODE];
char length[SIZE];

/* 経路の表示 */
void print_path( int n, int goal )
{
int i;
int len = length[n];
for( i = 0; i <= len; i++ ){
printf("%c ", path[n][i] + 'A' );
}
printf("%c\n", goal + 'A' );
}

/* 幅優先探索 */
void search( int start, int goal )
{
int rear = 1, front = 0;
path[0][0] = start;
length[0] = 0;
while( front < rear ){
int len = length[front];
int node = path[front][len];
int i, n;
for( i = 0; (n = adjacent[node][i]) != -1; i++ ){
if( memchr( path[front], n, len + 1 ) == NULL ){
if( n == goal ){
print_path( front, goal );
} else {
memcpy( path[rear], path[front], len + 1 );
path[rear][len + 1] = n;
length[rear] = len + 1;
rear++;
}
}
}
front++;
}
}

int main()
{
search( 0, 6 );
return 0;
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:経路探索 18634 ※ソースの添付は「HTML変換ツール」で字下げ! 2004/12/12 04:48:04


No.18634

Re:経路探索
投稿者---※ソースの添付は「HTML変換ツール」で字下げ!(2004/12/12 04:48:04)


「供廚砲覆辰討泙垢「経路探索」で丸投げしてるたかし氏も君?


> ランダムにスタートとゴールを決めたいです。

そうですか。では「乱数」を使えばよろしかろ。

> その際、スタートとゴールの番号は異なります。

そうですか。ではそのようなコードを書けばよろしかろ。

>このプログラムはいくつかの経路が探索され、
> 一番最初に表示されるのが最短経路ですが最短経路だけを
> 表示させたいです。

そうですか。ではそのように直せばよろしかろ。

>お願いします。

んで何を?





この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧