• 締切済み

C：経路検索アルゴリズム

全経路検索について勉強中です。 「各ノードはポインタで繋がっている」という事は理解しましたが、それをどのように表せば良いのでしょう。 ダイクストラ法、深さ優先検索等の単語は見つかりましたが、どれを使用すれば良いのか…。 条件は、ノードの数は決まっておらず、つながり・出発,到着点は自由に決める事が出来ます。 　例）1-2 1-4 2-4 2-3 3-5 4-5 開始,3 到着,5 距離は関係ありません。 今はリスト構造で、構造体（下のようにしています）は動的に確保し、 再帰で処理をするようにしていますが、上手くいかず不安になってきました。 struct data{ 　　int x;　　　　　　　/*ノード*/ 　　struct data *next; /*次ノードへのつながり*/ }; よろしければ、何か些細な事でもヒントを下さると嬉しいです＾＾

  • niml
  • お礼率76% (10/13)

みんなの回答

  • N-iml
  • ベストアンサー率0% (0/0)
回答No.3

投稿者です。 nimlのアカウント紛失…orz の為、こちらから失礼致します。 折角ご回答下さったのに、ポイント等付けれずに申し訳無いです。 No.1 Tacosan さん 　プログラムにおいての表現、ですか。 　その事を考えずに（思いつかず）、何を使おうかと焦っていました。 　 　隣接リストで表現し、トラックバックなるものを使用して検索するのですね。 　本なりネットを参考に頑張りますっ。 　物事の考え方―何をすべきかを、最初に考えなければならないですね。 　考える為には、把握しないと駄目なのかな。 　何となく、思考の弱点がわかったような気がしました。 　　 No.2 JaritenCat さん 　ノード管理のリストと接続先管理のリストを、ですか。 　Tacosanさんにアドバイス頂いた隣接リストをネットで調べ、現在下記のようになりましたが…間違いのようですね； 　書いて下さったプログラムを研究して、考え直してみます。 　struct data{ 　　　int x;　/*ノード*/ 　　　struct connect *list;　/*つながり先のリスト*/ 　}; 　struct connect{ 　　　int y;　/*つながり先の頂点*/ 　　　struct connect *next;　/*次リスト*/　 　}; 　 　お二人のアドバイスで、すべき事が見えた気がします。 　ありがとうございました＾＾

回答No.2

ノード数が不定ですのでノードのリストを作るところはＯＫです。 ノードとノードのつながりをどう管理するかが問題ですが、接続先のリストも作ってはどうでしょう。 struct data { /* ノードを管理するリスト */ int x; /* ノード名 */ struct data *next; /* 次のノード */ 　struct path *list; /* 経路リストへのポインタ */ } struct path { /* 接続先を管理するリスト */ 　struct path *next; /* 接続先 */ }

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

とりあえず, 「プログラムにおいてグラフをどのように表現するか」を考えないとダメだねぇ. プログラム上は隣接行列でも隣接リストでも表現できるけど, 全経路探索するなら隣接リストで表現するのかなぁ. で, 全経路探索ということだと結局はバックトラックすることになるんだけど, この辺は OK?

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

関連するQ&A

  • List構造

    Listの尻にノードを追加する関数で困っています。 以下に、ソースの一部を掲載させていただきます。 typedef struct __node{ int data; struct __node *next; }Node; ... /*リストの尻にノードを追加する関数 * 引数： head. リストの先頭ノードのポインタ data. リストの尻に追加したいint型の変数*/ void Insert_Tail(Node *head, int data) { Node *ptr = head; if(ptr == NULL){ /*<ノードが存在しない時には追加されない>*/ /*領域の確保*/ 　　　　　head = (Node*)calloc(1,sizeof(Node)); /*データをセット*/ head->data = data; head->next = NULL; return ; }else{ /*<ノードが存在するときには正常に動作>*/ while(ptr->next != NULL){ ptr = ptr->next; } /*領域の確保*/ ptr->next = (Node*)calloc(1,sizeof(Node)); 　　　　　/*データのセット*/ ptr->next->data = data; ptr->next->next = NULL; } } コメントアウトにも書かせていただきましたが、ノードがすでに存在するときには、正常にノードの最後に追加してくれるのですが、ノードが存在しない時にはリストに追加してくれません。 どうかご指導、ご指摘の程お願いします。

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

    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→Ｇまでのパスは作成できるのですが、 すべてのパスを求めるにはどうしたらよいのでしょうか？ データ構造、プログラムサンプルを教えていただけないでしょうか？

  • C言語の構造体についてなんですが。

    struct LIST { 　　　　struct Num* number; 　　　　struct LIST* next;/* 次の要素へのポインタ */ }*root; struct Num{ 　　　　int a; 　　　　struct Num* next; /* 次の要素へのポインタ */ }*numroot; と構造体を定義したときに、 main(){ 　　　　struct LIST *p; 　　　　for(p = root; p != NULL; p = p->next) ; } とすれば、pの先頭からNULLまでを参照していくことは分かるんですが、pのnumberの先頭からNULLまでの参照方法(プログラムのfor文の記述方法)がイマイチわかりません。つまり、構造体の構造体をどのように参照するかということです。 これを実現したい理由は、構造体内での数の格納を配列(固定長)ではなく可変長で格納したいからです。 分かる方は解答をお願いします。

  • C言語　線形探索

    #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXBUFFERSIZE 256 struct LinkedListNode{ int data; struct LinkedListNode *next; }; struct LinkedList{ int node_num; struct LinkedListNode *head; }; LinkedList *LinkedListMake(char *filename) { FILE *fp; LinkedList *list; char buffer[MAXBUFFERSIZE]; /* ファイル有無のチェック */ if ((fp = fopen(filename, "r")) == NULL) { fprintf(stderr, "No Such File : %s\n", filename); exit (1); } list = LinkedListAlloc(); if (list == NULL) { /* 領域確保失敗 */ exit (0); /* 終了 */ } while (fgets(buffer, MAXBUFFERSIZE, fp)) { /* ファイル終端に到達するまでループ */ buffer[strlen(buffer) - 1] = '\0'; /* 改行文字を削除 */ LinkedListDataAdd(list, atoi(buffer)); } fclose(fp); return (list); } LinkedList *LinkedListAlloc(void) { LinkedList *list; list = (LinkedList *)malloc(sizeof(LinkedList)); if (list == NULL) { /* 領域確保失敗 */ return (NULL); } list->node_num = 0; list->head = NULL; return (list); } LinkedListNode *LinkedListDataAdd(LinkedList *list, int x) { LinkedListNode *ptr; /* 注目するノードへのポインタ */ LinkedListNode *prev; LinkedListNode *new_node; ptr = list->head; prev = NULL; while (ptr) { /* 終端ノードに到達するまでループ */ if (ptr->data < x) { prev = ptr; /* 直前ノードの更新 */ ptr = ptr->next; /* 注目ノードの更新 */ } else if (ptr->data == x) { /* x は登録済み */ return (NULL); } else { /* x を注目ノードの直前に追加 */ new_node = LinkedListNodeAlloc(); if (new_node == NULL) { /* 領域確保失敗 */ exit (0); /* 終了 */ } new_node->data = x; new_node->next = ptr; /* ポインタの付け替え(注目ノードの直前) */ if (prev != NULL) { /* 連結リストの先頭以降に追加 */ prev->next = new_node; /* ポインタの付け替え */ } else { /* 連結リストの先頭に追加 */ list->head = new_node; } list->node_num++; /* ノード総数の更新 */ return (new_node); } } /* 終端ノードに到達 */ /* x を終端に追加 */ new_node = LinkedListNodeAlloc(); if (new_node == NULL) { /* 領域確保失敗 */ exit (0); /* 終了 */ } new_node->data = x; new_node->next = NULL; /* new_node は新たな終端ノード */ if (prev != NULL) { /* list は少なくともひとつのノードを有している */ prev->next = new_node; /* 更新前の終端ノードの直後が new_node となる */ } else { /* list は空(ノードがひとつも含まれない) */ list->head = new_node; } list->node_num++; /* ノード総数の更新 */ return (new_node); } LinkedList *LinkedListSearch(LinkedList *list, int x)←ここがわかりません★ { for(i = 0; i < node_num) 　　　　　？？？ int main(int argc, char *argv[]) { int a, i, x; printf("xの値を入力"); scanf("%d", &x); LinkedListMake(argv[1]); LinkedListSearch(list, x); 連結リストに格納されたint型データから目的の値を線形探索するプログラムをつくってます。 連結リスト作成関数まではできたので、あと連結リストにおいて目的の値を線形探索する関数LinkedListSearchをつくればだいたい完成だと思うのですが、関数LinkedListSearchの作り方がわかりません。 引数で連結リストのポインタと目的値をとって、目的値が存在すればそのノードのポインタ、存在しない場合はNULLを返すようにするつもりです。 わかる方、是非とも教えてください！ お願いいたします。

  • リスト

    プログラムのデータ構造の勉強を進めてるのですが リストのところである問題がどうしてもリスト（ポインタ）で解けません 基礎的なことがわかるのですが（ノードの使い方などマロックなど） その問題は人の名前を入力し国語、数学、英語の点数を入力して３教科の点数を合計し名前、それぞれの点数、合計の表示、そしてまた入力を続けると指示した場合また名前３教科の点数をいれてと繰り返すのですが、繰り返したときに今まで入っているデータの人々の合計を比較して表示を昇順にしなくちゃなりません。どうすればいいか検討もつきません。 typedef struct _node { char name[10]; int Jap; int math; int eng; struct _node *next; } Node; で構造体はいいのでしょうか？ できればくわしくプログラムを教えてください。 お願いします。

  • 構造体について

    構造体について分からない点があり，教えて頂きたく投稿いたします． 現在，以下のような構造体を作成しています． typedef struct{ int data; struct node *NEXT; }node; また，それを管理するためのリストを以下の構造体にて宣言しました． typedef struct{ node *crnt; node *last; }node_list; また，使用する関数内での宣言は以下の通りです． node_list *non_dscvr_node_list; //未探査ノードを格納する node *crt_dscvr_node; //現在探査中のノードを示す node *start; そして， start->data = 10; start->NEXT = NULL; non_dscvr_node_list->crnt = start; non_dscvr_node_list->last = start; : : crt_dscvr_node = non_dscvr_node_list->crnt; non_dscvr_node_list->crnt = crt_dscvr_node->NEXT; //ここでエラーがでる． エラーの詳細は以下の通りです． warning: assignment from incompatible pointer type 私としては，リストに格納されている先頭ノードをポップして，次のノードを先頭にしたつもりだったのですが，ポインタタイプに互換性がないと怒られてしまいました． 少し調べては見ましたが，nodeの構造体を管理するために別に構造体を定義しているページがあまり見あたりません． 従って，そのようなページがあれば教えて頂きたいと思います． このような方法はあまりよくないのでしょうか． 併せて教えていただけますようお願いいたします．

  • C言語の自己参照型プログラムについて

    #include <stdio.h> #include <string.h> #include <stdlib.h> struct list { int key; /* キー */ char name[20]; /* 名前 */ struct list *next; /* 次のデータへのポインタ */ }; struct list *add_list(int key, char *name, struct list *head); void show_list(struct list *p); void free_list(struct list *p); int main(void) { struct list *head; /* 先頭ポインタ */ char name[20]; int key = 0; head = NULL; /* 先頭ポインタにNULLを設定 */ printf("キーと名前（MAX:19文字）を入力（終了:CTRL+Z）\n"); while (scanf("%d %s", &key, name) != EOF) { /* リストにデータを登録 */ head = add_list(key, name, head); } /* リストの表示 */ show_list(head); /* リストの開放 */ free_list(head); return 0; } /*** リストにデータを登録 ***/ struct list *add_list(int key, char *name, struct list *head) { struct list *p; /* 記憶領域の確保 */ if ((p = (struct list *) malloc(sizeof(struct list))) == NULL) { printf("malloc error\n"); exit(EXIT_FAILURE); } /* リストにデータを登録 */ p->key = key; strcpy(p->name, name); /* ポインタのつなぎ換え */ p->next = head; /* 今までの先頭ポインタを次ポインタに */ head = p; /* 新たな領域を先頭ポインタに */ return head; } /*** リストの表示 ***/ void show_list(struct list *p) { while (p != NULL) { /* 次ポインタがNULLまで処理 */ printf("%3d %s\n", p->key, p->name); p = p->next; } } /*** リストの開放 ***/ void free_list(struct list *p) { struct list *p2; while (p != NULL) { /* 次ポインタがNULLまで処理 */ p2 = p->next; free(p); p = p2; } } これを実行すると、 新しく入力された順にリストが表示されます。 そうではなく、キーの昇順に表示したいです。 どなたかそのように実行できるようにプログラムを書き換えてくれませんか？ 図々しいですがよろしくお願いいたします。m(_ _)m

  • C言語　二分木探索

    今、int型の二分木にデータを追加する関数(引数は二分木へのポインタと追加する値、追加されたノードへのポインタを返す)をつくろうとしてます。 以前リストにデータを追加する関数をつくったのでそれを変更してつくろうとしているのですが途中までいってつまってしまいました。 つくりかたを教えてください。 よろしくお願いします！ struct BinaryTreeNode{ int data; struct BinaryTreeNode *l_next; struct BinaryTreeNode *r_next; }; struct BinaryTree{ int node_num; struct BinaryTreeNode *root; }; BinaryTreeNode *BinaryTreeNodeAlloc(void) { BinaryTreeNode *node; node = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode)); if (node == NULL) { return (NULL); } node->l_next = NULL; node->r_next = NULL; return (node); } BinaryTreeNode *BinaryTreeDataAdd(BinaryTree *list, int x) { BinaryTreeNode *ptr; BinaryTreeNode *prev; BinaryTreeNode *new_node; ptr = list->root; prev = NULL; while (ptr) { 　　　　　　←？？ if (ptr->data < x) { prev = ptr; ptr = ptr->next; } else if (ptr->data == x) { return (NULL); } else { new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); 　　　　　　　　　　　　　　　←？？ } new_node->data = x; new_node->next = ptr; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); } } new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); } new_node->data = x; new_node->r_next = NULL; new_node->l_next = NULL; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); }

  • Ｃ言語　リスト構造

    --(装置A)--(装置B)---(装置C)--- 　　　　　　　　　　 | 　　　　　　　　　　　---(装置E)--- 上の例のように途中で分岐があるリスト構造を あらわすために、Ｃ言語でどのような構造体をもつべきでしょうか？ (装置A),（装置B),(装置C)のつながりだけをリスト構造で持つ場合は、 struct device { int no; char name[NAME_SIZE]; device_t *next; //次の device 構造体へのポインタ }; のような構造体を使いリスト構造にできましたが、 (装置A),（装置B),(装置C)のつながりと (装置A),（装置B),(装置Ｅ)のつながりの両方に対応する（分岐のある構造にも対応する） ためには、どのようなつくりにすればよいでしょうか？ できれば、サンプルなどでおしえていただけますとありがたいです。 よろしくお願い致します。

  • Ｃ言語　自己参照型　複数木構造

    Ｃ言語の自己参照型を使用しプログラムを作ろうとしていますが、 2分探索木についての解説、サンプルをのせているサイトは たくさんあり勉強になったのですが、 木が２以上の複数の場合になった場合、どういったプログラムをくめば いいのかわからず、学習したいと思っています。 参考となる、サイト、サンプルを教えていただけないでしょうか？ //2分木の場合 struct node{ int nodeID; struct node *nextA; struct node *nextB; } //複数木の場合？ struct node{ int nodeID; struct node **next; } のように複数木の場合は、次の木が複数に対応できるように ポインタのポインタを使用するのかと思いますが、 構造体のメンバでポインタのポインタの使用の仕方が いまいち理解できませんでした。 よろしくお願い致します。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する