• 締切済み

Ｃ言語　経路探索　経路リストの作成

S→B→Ｃ → Ｄ →Ｇ 　　↓　 ↓→Ｅ→↑ 　　→Ｆ→→↑ Start(S)からＧoal(G)までのとりうる全経路を自動作成するプログラムを Ｃ言語で作成したいです。 上の例だと、 ルート1: SBCDG ルート2: SBCEG ルート3: SBFEG の３つのルートを算出できるプログラムです。 節と節の接続情報は持っているものとします。 S→B B→C C→D D→Ｇ Ｃ→E Ｅ→Ｇ B→Ｆ Ｆ→Ｅ struct connectList{ int node1; int node2; } struct root{ int nodeId; int nodeCost; root_t** next; }; 木構造のような構造体で作成していこうとしたのですが、 ひとつのS→Ｇまでのパスは作成できるのですが、 すべてのパスを求めるにはどうしたらよいのでしょうか？ データ構造、プログラムサンプルを教えていただけないでしょうか？

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

普通はそんな感じでしょう＞#1. ただ, 分岐の有無を考えると却って面倒で, 常にスタックに積む方がシンプルだと思います. 一言で言えば「深さ優先探索」.

回答No.1

分岐があったら、それまでにたどった経路をスタックに積んで、一方の枝に進む。 目的に到達したら、スタックから下して、前に辿らなかったほうの枝に進む。 スタックが空になっていたら終わり。 というアルゴリズムはどうですか。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • C言語の問題について

    #include <stdio.h> #define NMAX 20 struct node_tag { ??????? }; int main(void) { ??????? struct node_tag *p; int i; for (???????) { ??????? } p = ???????; while (p!=NULL){ printf("%d %s\n", ???????, ???????); p = ??????? } return 0; } 「　日付(整数)　と　曜日名(文字)　と　次の要素を指すポインタ　」を要素に持つ自己参照構造体 struct note_tag を定義して、この構造体を利用して線形リストを作成し，日付と曜日を表示させるプログラムを作成したいのですが？がわからなくて困ってます・・・どうか教えてください

  • C言語　リスト

    (1) /* list.c */ #include <stdio.h> #include <stdlib.h> struct node { int num; struct node *next; }; main() { struct node *head, *p; int x; head = NULL; while(scanf("%d",&x) != EOF) { p = (struct node *)malloc(sizeof(struct node)); p->num = x; p->next = head; head = p; } //　リストの要素のnumの値を先頭から順に表示する p=head; while(p!=NULL) { printf("%d\n" ,p->num); p = p->next; } } (2) struct node *q; q = head; while(q->next != NULL) q = q->next; (1)を(2)を使い新しいノードをリストの最後に追加するようにしたいのですが どう書いたら良いのか教えていただきたいです

  • ポインタ版リスト構造によるスタックの実装

    C言語を用いてアルゴリズムの勉強をしています。 現在、ポインタ版リスト構造によるスタックを実装し、入力された文字列の中で括弧の整合性を判定するプログラムを作成しているのですが、難航しています。 プログラムの内容は、以下の通りです。 入力：a{z[e(b){j}(p)]w}(j) 結果：整合 入力：a{z[e(b){j}(p)}w](j) 結果：不整合 ですが、所持している参考書の例題プログラムには、スタックに入れる要素が整数値のものしかなく、文字をスタックに入れるところからわかりません。 また、先輩に尋ねたところ、以下のような構造体を使うと良いとアドバイスされました。 typedef struct { int max; int num; List stk; } Stack; typedef struct { Node *head; Node *crnt; } List; typedef struct node { char data; struct node *next; } Node; 先輩には申し訳ないのですが、余計にわからなくなってしまいました。 この構造体を用いてプログラムをかける方、ご指導のほどよろしくお願いします。

  • 円周率を求めるC言語のプログラム

    int a=10000,b,c=8400,d,e,f[8401],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b); というのが本（「π魅惑の数」）に載っていたので #include <stdio.h> int main(void){ int a=10000,b,c=8400,d,e,f[8401],g; for(;b-c;)f[b++]=a/5; for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a) for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b); return 0; } としたのですが 円周率を表示してくれません。 （ｂ＝0にすると一応は出てくるのですが微妙に間違ってます（よく分からないですけどそのくらいの誤差のあるプログラムなのでしょうか？)）

  • C言語

    main() { int a = 5,b=2,e,f,g=3,i; double c,d,h=2.0; c = a/b; printf("c = %f\n",c); d = a/h; printf("d=%f\n",d); e = a++; f = ++b; g+= 4; i= ++a + b; printf(" a = %d\n",a); printf(" b = %d\n"b); printf(" e = %d\n"e); printf(" f = %d\n"f); printf(" g = %d\n"g); printf(" i = %d\n" i); 答え a=7,b=3,c=2.0,d=2.5,e=5,f=3,g=7,i=10 この問題のa,b,iがどうやってこの値になるのかがわかりません解説お願いします。

  • C言語初心者です。

    C言語初心者です。 構造体について勉強してるのですが、不明点があるため質問させて頂きます。 ---------------------------------- struct A{ int (*a)(struct B, struct C); int (*b)(struct B, struct C); } ---------------------------------- 上記の処理(構造体の中身)の書式について、書籍などで調べたのですが分かりません。 何を意味しているのでしょうか？ ご回答のほど、よろしくお願いします。

  • C言語のプログラムなのですが、２点の座標(SとR)を指定して片方からも

    C言語のプログラムなのですが、２点の座標(SとR)を指定して片方からもう片方への道筋を座標でcsvファイルに記述していくプログラムを作りたいのですが、うまく動きません。 参照渡しの所が間違っている様な気もするのですがわかりません。わかる方いましたらご指摘ください！ エラー内容：Segmentation Fault(core dumped) #include<stdio.h> #include<stdlib.h> #include<math.h> #include<time.h> int Fugo(int); void Flooding(int *,int *,int *,int *); typedef struct{ int id; int dX; int dY; }NodeStates; NodeStates Node1[50]; NodeStates Node2[50]; int main(void) { int SX1,SY1; int RX1,RY1; int SX2,SY2; int RX2,RY2; int i=1; int j=1; FILE *fp; fp=fopen("test.csv","w"); if(fp!=NULL){ printf("S1 Node PointX>>"); scanf("%d",&SX1); printf("S1 Node PointY>>"); scanf("%d",&RX1); printf("R1 Node PointY>>"); scanf("%d",&RY1); Node1[0].id = 1; Node1[0].dX = SX1; Node1[0].dY = SY1; printf("S2 Node PointX>>"); scanf("%d",&SX2); printf("S2 Node PointY>>"); scanf("%d",&SY2); printf("R2 Node PointX>>"); scanf("%d",&RX2); printf("R2 Node PointY>>"); scanf("%d",&RY2); Node2[0].id=1; Node2[0].dX=SX2; Node2[0].dY=SY2; srand((unsigned int)time(NULL)); fprintf(fp,"First\n"); fprintf(fp,"NodeID,X,Y\n"); fprintf(fp,"%d,%d,%d\n",Node1[0].id, SX1, SY1); while(!(SX1==RX1 && SY1==RY1)){ Flooding(&SX1, &SY1, &RX1, &RY1); Node1[i].dX=SX1; Node1[i].dY=SY1; Node1[i].id=i+1; fprintf(fp,"%d,%d,%d\n",Node1[i].id,Node1[i].dX,Node1[i].dY); i++; } fprintf(fp,"Second\n"); fprintf(fp,"NodeID,X,Y\n"); fprintf(fp,"%d,%d,%d\n",Node2[0].id, SX2, SY2); while(!(SX2==RX2 && SY2==RY2)){ Flooding(&SX2,&SY2,&RX2,&RY2); Node2[j].dX=SX2; Node2[j].dY=SY2; Node2[j].id=j+1; fprintf(fp,"%d,%d,%d\n",Node2[j].id,SX2,SY2); j++; } } fclose(fp); return 0; } void Flooding(int *a,int *b,int *c,int *d){ int *e,*f,r; *a=*a-*c; *b=*b-*d; *e=Fugo(*a); *f=Fugo(*b); *a=abs(*a); *b=abs(*b); r=rand()%3; if(*a!=0&&*b!=0){ if(r==0){ *a=*a-1; } else if(r==1){ *a=*a-1; *b=*b-1; } else *b=*b-1; } else if(*a==0)*b=*a-1; else if(*b==0)*a=*b-1; *a=*a**e+*c; *b=*b**f+*d; } int Fugo(int a){ int n; if(a>=0){ n=1; } else{ n=-1; } return n; }

  • c言語プログラムについて

    http://www.post.japanpost.jp/zipcode/dl/kokagi.html から全国一括(1,735,160Byte)をダウンロード このファイルを使って、 Linuxマシン上で、 例えば、北海道札幌市中央区旭ケ丘　と入力すれば、0640941 と返却されるプログラム（引数はコマンドラインで）をcで作成したいと思っているのですが、ファイルのダウンロードとファイルの読み込みまでは出来たのですが、その後の「北海道札幌市中央区旭ケ丘　と入力すれば、0640941」からが分かりません。どなたか続きを教えて頂けないでしょうか？ 使用OS：fedora 一応、ソースを載せておきます #include <stdio.h> int main(void){ FILE *fp; char *fname="ken_all.csv"; char d[100]; char e[100]; char f[100]; char g[100]; char h[100]; char i[100]; int ret,a,b,c; fp = fopen("ken_all.csv", "r"); if (fp == NULL) { printf("ファイルをオープンできませんでした\n",fname); return -1; } while( (ret = fscanf( fp, "%[^, ],%d,%d,%s,%s,%s,%s,%s,%s", &a, &b, &c, d, e, f, g, h, i ) ) != EOF ){ printf( "%d %d %d %s %s %s %s %s %s", a, b, c, d, e, f, g , h , i); } fclose(fp); return 0; }

  • 用語の正式名称は？(C++)

    C++のクラスや構造体で、 class TEST { private: int a;　//A int func1(); //B protected: int b; //C int func2(); //D public: int c; //E int func3(); //F } struct XXX { int x; //G } というのがあったとします。 //A～//G の正式な読み方はなんでしょうか？ たとえば//Bなら、「プライベートメソッド」「プライベートメンバ関数」ですか？ ご存知なかた、ご教授おねがいします。 できればその定義が書かれていた出所(URL)もおしえてください。

  • 【C言語】構造体内の領域解放（free）の仕方

    C言語について教えてください。 大学の課題でCを書いています。 freeの仕方について教えてください。 構造体 struct word { struct word *next; char *st; int *line_no; int line_cnt; }; を用意し、char* stにstrdupにて文字列を格納します。 そして、簡単なリストを作り、表示をさせfreeをするプログラムです。 freeをする際にfreeしてはいけないメモリをfreeしているようです。 しかし、正しい場所をfreeしていると思うので、なぜエラーなのか分かりません。 理由と解決方法を御教授願えませんでんしょうか。 よろしくお願いします。 /************以下ソース****************/ #include<stdio.h> #include<stdlib.h> #include<string.h> struct word { struct word *next; char *st; int *line_no; int line_cnt; }; struct word *head; void Add_List(char *buf,int no){ struct word* node = malloc(sizeof(struct word*)); struct word* crnt; /*nodeの準備*/ node->next = NULL; node->st = strdup(buf); node->line_no = malloc(sizeof(int*)); node->line_no[0] = 1; node->line_cnt= 1; if(head == NULL) { head = node; } else { crnt = head; while( crnt->next != NULL) { crnt = crnt->next; } crnt->next = node; } } void printlist(){ struct word *crnt = head; while( crnt != NULL ) { printf("%s\n",crnt->st); crnt = crnt->next; } } int main(){ head = NULL; char buf1[] = {'A','B','C','D','E','\0'}; char buf2[] = {'F','G','H','I','J','\0'}; char buf3[] = {'K','L','M','N','O','\0'}; Add_List(buf1,1); Add_List(buf2,1); Add_List(buf3,1); printlist(); /*この部分がうまくいかない*/ free(head->st); /*********************/ } （以下実行結果です。OS:CentOS） [yuichiro-ito@localhost test]$ ./a.out ABCDE FGHIJ KLMNO *** glibc detected *** ./a.out: free(): invalid pointer: 0x0000000001a01030 *** ======= Backtrace: ========= /lib64/libc.so.6[0x365a4760e6] ./a.out[0x40072f] /lib64/libc.so.6(__libc_start_main+0xfd)[0x365a41ecdd] ./a.out[0x4004d9]　 ======= Memory map: ======== 00400000-00401000 r-xp 00000000 08:02 390975 /home/yuichiro-ito/test/a.out 00600000-00601000 rw-p 00000000 08:02 390975 /home/yuichiro-ito/test/a.out 01a01000-01a22000 rw-p 00000000 00:00 0 [heap] 3659c00000-3659c20000 r-xp 00000000 08:02 785966 /lib64/ld-2.12.so 3659e1f000-3659e20000 r--p 0001f000 08:02 785966 /lib64/ld-2.12.so 3659e20000-3659e21000 rw-p 00020000 08:02 785966 /lib64/ld-2.12.so 3659e21000-3659e22000 rw-p 00000000 00:00 0 365a400000-365a58a000 r-xp 00000000 08:02 785967 /lib64/libc-2.12.so 365a58a000-365a789000 ---p 0018a000 08:02 785967 /lib64/libc-2.12.so 365a789000-365a78d000 r--p 00189000 08:02 785967 /lib64/libc-2.12.so 365a78d000-365a78e000 rw-p 0018d000 08:02 785967 /lib64/libc-2.12.so 365a78e000-365a793000 rw-p 00000000 00:00 0 3666c00000-3666c16000 r-xp 00000000 08:02 785985 /lib64/libgcc_s-4.4.7-20120601.so.1 3666c16000-3666e15000 ---p 00016000 08:02 785985 /lib64/libgcc_s-4.4.7-20120601.so.1 3666e15000-3666e16000 rw-p 00015000 08:02 785985 /lib64/libgcc_s-4.4.7-20120601.so.1 7fc7b9e92000-7fc7b9e95000 rw-p 00000000 00:00 0 7fc7b9ea0000-7fc7b9ea3000 rw-p 00000000 00:00 0 7fffbce3c000-7fffbce51000 rw-p 00000000 00:00 0 [stack] 7fffbce9d000-7fffbce9e000 r-xp 00000000 00:00 0 [vdso] ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する