バックトラック法での経路探索の結果を並び替えたいです。

Question

やりたいこと

C言語でのバックトラック法の経路探索について勉強しています。
下に示すソースコードの実行結果を
文字数の小さい順番に並び替えることはできますか？
ソースコードは以下のサイトを参考にしたものです。
http://www.nct9.ne.jp/m_hiroi/linux/clang16.html

#include <stdio.h>
#include <stdbool.h>

enum {S, A, B, C, D, E, F, G};

#define N 7
#define M 4

// 隣接リスト
int adjacent[N + 1][M] = {
  {S},
  {B, C, S},
  {A, C, D, S},
  {A, B, E, S},
  {B, E, F, S},
  {C, D, G, S},
  {D, S},
  {E, S},
};

// 経路
int path[N];
bool visited[N + 1];

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

// 深さ優先探索
void dfs(int n, int goal)
{
  int x = path[n - 1];
  if (x == goal) {
    print_path(n);
  } else {
    for (int i = 0; i < M; i++) {
      int y = adjacent[x][i];
      if (y == 0) break;
      if (!visited[y]) {
        path[n] = y;
        visited[y] = true;
        dfs(n + 1, goal);
        visited[y] = false;
      }
    }
  }
}

int main(void)
{
  path[0] = A;
  visited[A] = true;
  dfs(1, G);
  return 0;
}

実行結果

A B C E G 
A B D E G 
A C B D E G 
A C E G 

試したこと

文字列を他の文字列の配列に格納して、
その文字列で昇順にできるか試しました。
出来ませんでした。

他の探索方法を用いれば、文字列を並び替えることなく昇順の結果を実行出来ることは認識しております。
ただ、今回は出来ればバックトラック法を活用できたらよいなと考えています。
プログラミング言語初心者ですので、そもそもこのソースコードで文字の並び替えが可能なのかすらわかりません。
出来ないようでしたら、諦めて別の探索方法を用いるつもりです。
拙い文章ですが、ご協力いただけると幸いです。

Comments

[fana]

> 実行結果

は，「4つの経路が見つかった」という結果表示なのだと見えますが，
本件の話が「4つの経路が見つかった後で　→　それらを並び替える」なのであれば，
少なくとも，「並び替える」処理を行う時点で「４つの経路」なるデータが存在していなければならないでしょう．

なので，まずは
「探索処理の結果データは，見つかった分だけ全部どこかに保持される」という形のプログラムにする必要があるでしょう．
（→それは可能ですか？）

[fana]

さて，無事に「全経路データがどこかに保持される」形にできたならば，
問題は「こういうデータがあるんだけど，並び替えるにはどうすればいい？」になります．
話は純粋な「ある形のデータをソートする方法（あるいはその実装）」です．

つまりこの時点で，もはやデータの出所や内容は問題と無関係な事柄となります．
そのデータを得る手段がバックトラック法だったとか，そもそもデータが経路を表すものだとかいう情報は無用となります．

[fana]

というわけで，とりあえず

・関数 dfs の中で経路を表示しているのをやめて，dfs は見つかった経路をどこかに（見つかった分だけ全て）保存する
・結果の表示は main 関数内（ dfs の実行後．return の直前あたり）でまとめて行う

という形をまずは目指すと良いのではないかと．

[rike]

回答ありがとうございます。
データを格納するのは、何かしらのファイルにデータを保存するということでしょうか。
print_pathの結果をテキストファイルなどに書き込めば良いかと考えました。
fopen,fprint等を使ってやってみたのですが、コードを書く場所が悪いのか、うまく出来ません。
fprintを使う際、
print_pathを引数にするのかと思ったのですが、voidで設定してあるのでできません。
どこの箇所を引数にすれば良いのでしょうか。。

[fana]

ファイルを介在させてもまぁ良いですが，とりあえず　変数　に格納する感じにすればどうでしょう．

（理屈上の経路の最大数がいくつになるのかはわかりませんが）
まずは簡便に「経路データを最大でX個まで保持できるとして」実装するならば，
単一の経路を表すデータの型を仮に Route 型だとすれば，

#define X 100 //何個くらいあればいいのかわからんですが
Route FoundRoute[X]; //X個までの経路データを持てる
int nFoundRoute = 0; //見つかった経路の個数カウント用

みたいな変数でも用意すればここに貯め込んでいけるでしょう．

[fana]

Route の実際の型は適当に都合よく決めればよいでしょう．

struct Route{ char Str[N+1]; }; //結局文字列かよ^^

みたいな物でも良いのかもしれません．

現状，経路が１個見つかる度に関数 print_path が呼ばれて，そこで見つかった経路を表示しているのであれば（そんな感じに見えますが，そこらへんの実情は確認してください），
print_path を呼んでいる場所を適当に別の関数を呼ぶように書換え，その関数内で見つかった経路情報を上記の変数に格納する作業をすればよいのではないでしょうか．

Answer 1

バックトラックによる検索と結果の(ソート)表示は全く関係ありませんので、お互いのデータの持ち方さえ合わせれば、組み合わせは自由です。

以下は文字列として (alloc した )buf に保存する形です。

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

enum {S, A, B, C, D, E, F, G};

#define N 7
#define M 4

// 隣接リスト
int adjacent[N + 1][M] = {
    {S},
    {B, C, S},
    {A, C, D, S},
    {A, B, E, S},
    {B, E, F, S},
    {C, D, G, S},
    {D, S},
    {E, S},
};

// 経路
int path[N];
bool visited[N + 1];

char *buf = NULL;
char buf_size = 0;
int buf_lastindex = 0;
int buf_strcount = 0;

//ソート
void sort(char *a[], int n) {
  for(int i=0; i<n-1; i++) {
    for(int j=i+1; j<n; j++) {
      int s = strlen(a[i]) - strlen(a[j]);
      if(s == 0) s = strcmp(a[i], a[j]);
      if(s > 0) { char *t=a[i]; a[i]=a[j]; a[j]=t; }
    }
  }
}
//ソートして表示(して開放)
void sort_and_print() {
  if(buf == NULL) return;
  char *paths[buf_strcount];
  for(int i=0, j=0; i<buf_strcount; j+=strlen(paths[i++])+1) paths[i] = &buf[j];
  sort(paths, buf_strcount);
  for(int i=0; i<buf_strcount; i++) printf("%s\n", paths[i]);
  free(buf);
}
//文字列化して保存
void store_path(int n) {
  if(buf_lastindex+(n+1) >= buf_size) {
    buf_size += (N+1);
    buf = realloc(buf, buf_size); //buf=NULL なら malloc 同等
    if(buf == NULL) exit(1); //拡張できなかったら(行儀悪く)即終了
  }
  for(int i=0; i<n; i++) buf[buf_lastindex++] = 'A'+(path[i]-1);
  buf[buf_lastindex++] = 0; //End Of String
  buf_strcount++;
}

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

// 深さ優先探索
void dfs(int n, int goal) {
  int x = path[n - 1];
  if (x == goal) {
    store_path(n); //print_path(n);
  } else {
    for (int i = 0; i < M; i++) {
      int y = adjacent[x][i];
      if (y == 0) break;
      if (!visited[y]) {
        path[n] = y;
        visited[y] = true;
        dfs(n + 1, goal);
        visited[y] = false;
      }
    }
  }
}

int main(void) {
  path[0] = A;
  visited[A] = true;
  dfs(1, G);
  sort_and_print();
  return 0;
}

実行結果

ACEG
ABCEG
ABDEG
ACBDEG

Answer 2

#define SIZE 1000

int path2[SIZE][N];
int idx[SIZE];
int size = 0;

void add(int n)
{
	int i;
	path2[size][0] = n;
	for (i = 0; i < n; i++) path2[size][i+1] = path[i];
	for (i = size; i > 0 && path2[idx[i-1]][0] > n; i--) 
		idx[i] = idx[i-1];
	idx[i] = size++;
}

void print_all(void)
{
	for (int i = 0; i < size; i++) {
		int k = path2[idx[i]][0];
		for (int j = 1; j <= k; j++)
			printf("%c ", path2[idx[i]][j] + 'A' - 1);
		putchar('\n');
	}
}

このコードを int path[N]; より後に追加し、
dfs関数の中の、print_path(n); を add(n); に変更し、
main関数の dfs(1, G); の後に print_all(); を追加してみてください。