グリーディー法による近似の問題(重みつき集合被覆問題）の問題がわかりません。

[ファイブマン]

こんにちは。初めてここを利用させていただきます。C言語は何年か学んでいるのですが勉強不足なため、課題がわからなくて困っています。
重みつき集合被服問題のグリーディー法による近似アルゴリズムを実装しなさいという問題です。

入力：探査対象の集合　U=｛e1,e2,…e9｝
　　　　探査軌道の集合　S=｛S1,S2,…S8｝
コスト関数　　　　　c：S→Q^+（正の有理数）

また、それぞれの軌道にある探査対象は、
S1=｛e3,e4,e5,e6｝
S2=｛e3｝
S3=｛e1,e2｝
S4=｛e5,e7｝
S5=｛e5,e6｝
S6=｛e8｝
S7=｛e1,e2,e3,e8,e9｝
S8=｛e9｝

それぞれの軌道のコストc（S）はS1から順にS8まで、｛90,34,23,30,20,98,100,2｝となります。

そして、出力がカバーC（U(Si∈C)）Si=Uとなるもの）で、総コスト∑(Si∈C)c(Si)が最小となるものにしてください。

探査対象1つあたりのコストが最小の軌道から、Cに加えていけば全体を網羅する軌道を求められると考えているのですが、それを具体的にどう表現していいのかがわかりません。
それと、文字列を数値に変換するのはatoi()などを使う、ということくらいはわかるのですがやり方が悪いのかコンパイルエラーになってしまいます。
以下、自分で書いたプログラムです。（ほとんど合ってないと思うのですが）2年は学習しているものの、恥ずかしながら知識が乏しいので詳しく教えていただきたいです。
まず、手のつけ方からわからないのでそこから教えてください。
恐縮ですがよろしくお願いします。

コード:

#include<stdio.h>
#include<stdlib.h>
int main(int argc, int argv[]){

  int atoi(const char *str);
  int inum;
  char str[8] = {90,34, 23, 30, 20, 98, 100, 2};
  int i, x, min;  
char a[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
 int j;
 inum = atoi(str[0]);
 printf("%d\n", inum);

 for(j=0, min = x; j < 8; j++) {
   if( min > x ) {
      min = x;
   }
 }
  
   return 0;
}

また、Sやeはべつのファイルに書き込んで挿入するという手もあるようなのですがどちらかやりやすい方でいいのでよろしくお願いします。

[bitter_fox]

コード:

#include<stdio.h>
#include<stdlib.h>
int main(int argc, int argv[]){
  int inum;
  char str[8] = {90,34, 23, 30, 20, 98, 100, 2};

 inum = atoi(str[0]);
 printf("%d\n", inum);

   return 0;
}

まず、atoi(str[0])としたときの第一引数(str[0])の型はchar型で一般に文字型と呼ばれるもので文字列ではありません。
文字列は文字の集合としてあらわされます。この場合はcharの配列であるstr自体が文字列として働きます。

また、str[0]は既に90という値になっています。

コード:

int main()
{
	char str[8] = {90, 34, 23, 30, 20, 98, 100, 2};
	int n = str[0];

	printf("%d", n);

	return 0;
}

// 出力結果:
// 90

ちなみに、この90という値はASCIIコードで変換すると'Z'となるのでstrを数値が書かれた文字列として解釈するのも無理があります。

もし、"90", "34", "23", ...などの文字列を数値に変換したいのであれば次のようにしてください。

コード:

	char *str[8] = {"90", "34", "23", "30", "20", "98", "100", "2"};
	int n;

	n = atoi(str[0]);
	printf("%d\n", n);

それから、インデントが曖昧だとソースコードが読みづらくなるのでしっかりとインデントされることをお勧めします。

[ファイブマン]

ありがとうございます。インデントし直して貼るため本文を編集することはできるのでしょうか？

そして次なのですが、
char aの配列はこの仕様で合ってるのでしょうか？

このaは縦をS、横をeにした2元配列にし、Sを最短経路順に選びすべてのeを通過するようにしたいのですが、ただSの重み順に小さい方から選ぶだけならおそらくできるのですが、例えばS7の後S1を選ぶときe3はすでに通過したので、それまでのS1の対象1個あたりの重み(90÷4=22.5)が大きくなり、30(=90÷3)になるようにするので、そうなるとどうすればよいのか方法がわかりません。

どのようにしていけばできるのでしょうか、追加してご回答よろしくお願いします。

[bitter_fox]

ありがとうございます。インデントし直して貼るため本文を編集することはできるのでしょうか？

ゲストアカウントで投稿されたものについては「グローバルモデレータ」や「admin」権限のアカウントの人しか編集できません。
ユーザアカウントで投稿されたものは「グローバルモデレータ」や「admin」権限のアカウントの人に加え、その投稿したユーザのアカウントの人は編集することが可能です。

char aの配列はこの仕様で合ってるのでしょうか？

このaは縦をS、横をeにした2元配列にし、Sを最短経路順に選びすべてのeを通過するようにしたいのですが、ただSの重み順に小さい方から選ぶだけならおそらくできるのですが、例えばS7の後S1を選ぶときe3はすでに通過したので、それまでのS1の対象1個あたりの重み(90÷4=22.5)が大きくなり、30(=90÷3)になるようにするので、そうなるとどうすればよいのか方法がわかりません。

配列でもできるでしょうが、僕ならば探査軌道Snに関する情報は構造体としてまとめますね。
構造体の使い方がよく分からないというのであればこのままでも良いかと思います。

e3を通過した場合は他の探査軌道のe3に当たるフラグを下せばよいのではないでしょうか？
重みを計算するときに立っているフラグの数を求めれば母数は随時変化しますよね？

[ファイブマン]

[quote= bitter_foxさん]e3を通過した場合は他の探査軌道のe3に当たるフラグを下せばよいのではないでしょうか？
重みを計算するときに立っているフラグの数を求めれば母数は随時変化しますよね？[/quote]

勉強不足ですみません。この文章の意味がよくわからないのですが、具体的にどういうことでしょうか？フラグを下すとはどういうことでしょうか？

[bitter_fox]

フラグを下すとはどういうことでしょうか？

具体的にソースを用いて説明します。

コード:

#include <stdio.h>

double calc(char a[9], char str)
{
	int e, count = 0;

	// 有効な探査対象の個数を探す(a[e]が1の物)
	for (e = 0; e < 9; e++)
	{
		if (a[e] == 1)
		{
			count++;
		}
	}

	return ((double)str) / count;
}

int main()
{
	char str[] = {72, 5};
	char a[2][9] =
	{
//		 e1 e2 e3 e4 e5 e6 e7 e8 e9
		{1, 1, 1, 1, 1, 1, 1, 1, 1}, // S'
		{0, 0, 1, 0, 0, 0, 0, 0, 0}, // S''
	};

	// S''評価前のS'の重み
	printf("%f\n", calc(a[0], str[0]));

	// S''を評価した(S''はe3を通過した)

	// S''がe3を通過したのでe3は探査個数から外れる(重みの計算の分母)
	a[0][2] = -1; // 外れても探査対象だったことが分かるように0ではなく-1にする(フラグを下す)
//       ↑ e3は添え字で言うと2

	// S''評価後のS'の重み
	printf("%f\n", calc(a[0], str[0]));

	return 0;
}

実際はe3だけでなく探査対象となっているすべてのeについてフラグを下げる作業を行い、
その対象もS1だけでなくすべてのSに対して行う必要があります。

あと、最初のソースコードのS7のe3に当たる部分が間違っています。

[ファイブマン]

返答ありがとうございます。
わかりやすくするためにわざわざソースコードを用いていただいてすみません。

つまりS1からS8までやるということなのでなかなか長いソースコードになるというわけですね。
早速やってみたいと思います。

またわからなくなったら参考にさせてください！

[bitter_fox]

返答ありがとうございます。
わかりやすくするためにわざわざソースコードを用いていただいてすみません。

つまりS1からS8までやるということなのでなかなか長いソースコードになるというわけですね。
早速やってみたいと思います。

またわからなくなったら参考にさせてください！

ループを用いてくださいね。
そうするとそんなに長くならないと思いますよ。

[ファイブマン]

ありがとうございました。またいろいろやってみまして、一応ここまで作ったのですが、どうも自分の意図したように動きません。下にそのソースコードを記したのですが、重みが大きい順にSを選んでいき、かつ通った起動は軌道は−１していくのも思ったように出力されません。−１する前のS、−１した後のSを出力した結果もなぜか出力結果が
22.500000

22.500000
34.000000

34.000000
11.500000

23.000000
15.000000

15.000000
10.000000

10.000000
98.000000

98.000000
20.000000

25.000000
2.000000

2.000000
となってしまいます。各行の通る前と通った後の重みをそれぞれ出力したいのですが。。。

通った軌道は消していき、かつ重みが小さい順に選んでいくのにはどうすればいいのでしょうか。
自分でもよくどうなっているかわからないでパニックになっているのですが御回答宜しくお願いします。

コード:

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

double calc(char a[9], char str)
{
  int e, count = 0;
  
  for (e = 0; e < 9; e++)
    {
      if (a[e] == 1)
        {
	  count++;
        }
    }
  
  return ((double)str) / count;
}

int main(int argc, int argv[]){
  
  int atoi(const char *str);
  int n;
  char str[] = {90, 34, 23, 30, 20, 98, 100, 2};
  int i, x;  
  char a[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
  
  for(i = 0; i < 8 ; i++){
    printf("%f\n\n", calc(a[i], str[i]));
    if(a[i][x] = 1)  a[i][x] = -1;
    printf("%f\n", calc(a[i], str[i]));
  }
  return 0;
}

[bitter_fox]

コード:

  int i, x;  
  
  for(i = 0; i < 8 ; i++){
    printf("%f\n\n", calc(a[i], str[i]));
    if(a[i][x] = 1)  a[i][x] = -1;
    printf("%f\n", calc(a[i], str[i]));
  }
  return 0;
}

xは初期化されていないので値は不定です。

これではただ、
calc(a, str)の結果を表示して
a[どこか]が1ならばそこを-1にして
再びcalc(a, str)の結果を表示するという意味です。

一度にすべてを実装しようとこんがらがってしまうと思うので、プログラム全体をいくつかのパートに分けていきましょう。

コード:

1.すべてのSnのコストを求め最小となるコストとその時のnを保存する。(保存先は配列あたりに・・・)
1.min_cost(最小のコスト値), min_n(min_costとなるSnの添え字)
1.min_n_list[要素数は8個で、未使用を示す-1で各要素を初期化](min_nの一覧)
1-1.ループ：Si(S[i]) = S1(S[0])からS8(S[7])
1-1-1.分岐：Si(S[i])がS1(S[0])なら常にコストは最小(最初だから常に最小)なのでmin_cost, min_nを更新
1-1-2.分岐：それ以外ならばSiのコストがmin_costより小さいときはmin_cost, min_nを更新(以下の時にどちらを優先するかは任せます)
1-2.この時のmin_nを配列に保存

2.Smin_nのすべてのeiについてすべてのSjのeiの値を調べフラグを下げる。
2-1.ループ：ei(S[min_n][i]) = e1(S[min_n][0])からe9(S[min_n][8])
2-1-1.分岐：eiが1(S[min_n][i] == 1)ならば
2-1-1-1.ループ：Sj(S[j]) = S1(S[0])からS8(S[7])
2-1-1-1-1.分岐：Sjのeiを調べ1ならフラグを下げる(-1にする)(S[j][i]) == 1ならばS[j][i] = -1)

3.すべての探査対象が探査されるまで1に戻って繰り返し。
　1ではmin_nのリストにあるSmin_nについては調べない。

4.min_nのリストからすべてのSnを表示

この様に大まかに4つに分けました。まず2, 3, 4は考えず1を実装してみてください。
1を実装するうえで重要なポイントやヒントは1-以下に書きましたので参考にしてください。(なおこの説明内に出てくる名称等は便宜上定めましたが好きに変えてもらって構いません。)

[ファイブマン]

細かくやり方をおしえてくれてありがとうございます．
その中でわからなくなったことがあるので，おしえていただけますでしょうか？

Snのコストはcalc(a[], str[])ですよね？
1-1-2.分岐の中でさらにif文を使ったときに

コード:

  else{ 
    if(char calc(a[i], str[i])< min_cost){
      min_cost = calc(a[0], str[0]);
      min_n = i ;  
    }
    

にすると，文法エラー が "char" の前にあります
となってしまいます．
どうしてでしょうか？

[ファイブマン]

すみません，上のは勘違いしていました．
1のループの件で質問なのですが，

コード:

    for(i = 0; i < 8 ; i++){
      if(i = 0){  
	min_cost = calc(a[0], str[0]);
	min_n = i;
	
      }
      else{ 
	if(calc(a[i], str[i])< min_cost){
	  min_cost = calc(a[i], str[0]);
	  min_n =  i;  
	}
      }
      printf("%f\n",min_cost);
    }
  

は間違っているのはわかるのですがどう間違っているのでしょうか？
それぞれの条件で更新して入れる値が間違っているのですか？
このまま実行すると出力結果は
0.000000
をエンドレスループします．
ご指摘宜しくお願いします．

[bitter_fox]

コード:

    for(i = 0; i < 8 ; i++){
      if(i = 0){  
	min_cost = calc(a[0], str[0]);
	min_n = i;
	
      }
      else{ 
	if(calc(a[i], str[i])< min_cost){
	  min_cost = calc(a[i], str[0]);
	  min_n =  i;  
	}
      }
      printf("%f\n",min_cost);
    }
  

それぞれの条件で更新して入れる値が間違っているのですか？
このまま実行すると出力結果は
0.000000
をエンドレスループします．

if (i = 0)の=は代入演算子なのでずっとiに0を入れています。
比較演算子は==です。

あと、min_cost = calc(a, str[0]);のaとstrの対応が間違っています。これでは常にS1のコストで評価しています。
[hr][追記]
ゼロ割を考慮してcalc関数を次のように変更しましょう。

コード:

double calc(char a[9], char str)
{
	int e, count = 0;

	// 有効な探査対象の個数を探す(a[e]が1の物)
	for (e = 0; e < 9; e++)
	{
		if (a[e] == 1)
		{
			count++;
		}
	}

	if (count == 0)
	{
		return -1;
	}
	return ((double)str) / count;
}

一つも探査対象が残ってない場合は-1を返すようにしました
それに伴って-1でないときだけmin_costと比較するようにしましょう。

コード:

for(i = 0; i < 8 ; i++){
	cost_buf = calc(a[i], str[i]);
	if (cost_buf != -1)
	{
		if(i == 0){
			min_cost = cost_buf;
			min_n = i;
		}
		else{
			if(cost_buf< min_cost){
				min_cost = cost_buf;
				min_n =  i;
			}
		}
	}
	printf("%f\n",min_cost);
}

[ファイブマン]

22.500000 0.000000
22.500000 0.000000
11.500000 2.000000
11.500000 2.000000
10.000000 4.000000
10.000000 4.000000
10.000000 4.000000
2.000000 7.000000

度々すみません．
出力結果が上のようになった原因がわかりません．
forループで1ずつiを上げているのに同じ値が2，3個ずつ出てしまうのはなぜなのでしょうか？下のコードのどこがおかしいからこうなってしまうのでしょうか？

コード:

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

double calc(char a[9], char str){
  int e, count = 0;
  
  // 有効な探査対象の個数を探す(a[e]が1の物)
  for (e = 0; e < 9; e++){
    if (a[e] == 1){
      count++;
    }
  }
  if (count == 0){
    return -1;
  }
  return ((double)str) / count;
}


int main(int argc, int argv[]){
  
  int atoi(const char *str);
  char str[] = {90, 34, 23, 30, 20, 98, 100, 2};
  int i,n;  
  double min_cost , min_n, cost_buf;
  double min_list[8] = {-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0} ;
  char a[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
  
  for(i = 0; i < 8 ; i++){
    cost_buf = calc(a[i], str[i]);
    if (cost_buf != -1)
      {
	if(i == 0){  
	  min_cost = cost_buf;
	  min_n = i;
	  
	}
	else{ 
	  if(cost_buf < min_cost){
	    min_cost = cost_buf;
	    min_n = i;  
	  }
	}
      }
    printf("%f\t%f\n",min_cost, min_n);
    
  }
 return 0;
}

[bitter_fox]

22.500000 0.000000
22.500000 0.000000
11.500000 2.000000
11.500000 2.000000
10.000000 4.000000
10.000000 4.000000
10.000000 4.000000
2.000000 7.000000

度々すみません．
出力結果が上のようになった原因がわかりません．
forループで1ずつiを上げているのに同じ値が2，3個ずつ出てしまうのはなぜなのでしょうか？下のコードのどこがおかしいからこうなってしまうのでしょうか？

なんらおかしいことは無いです。
最小値を表示しているので値が変化するのは最小値が更新された時だけです。

printf("%f(%d)\tmin->%f(%d)\n", cost_buf, i, min_cost, min_n);
としてみてください。最小値の推移が分かるかと思います。

[ファイブマン]

コード:

2.Smin_nのすべてのeiについてすべてのSjのeiの値を調べフラグを下げる。
2-1.ループ：ei(S[min_n][i]) = e1(S[min_n][0])からe9(S[min_n][8])
2-1-1.分岐：eiが1(S[min_n][i] == 1)ならば
2-1-1-1.ループ：Sj(S[j]) = S1(S[0])からS8(S[7])
2-1-1-1-1.分岐：Sjのeiを調べ1ならフラグを下げる(-1にする)(S[j][i]) == 1ならばS[j][i] = -1)

ありがとうございます．続けて作業2に移行したのですが，またつまづきました．
あらたに配列としてint S[8][9]をつくり，示していただいたのを文にして

コード:

int S[8][9];

while(S[min_n][i] < 8 && S[min_n][i]>0)
  if((S[j][i]) == 1)
    S[j][i] = -1;

としたのですが，min_nが整数の型ではないためS[min_n]が文として受け付けてくれません．min_nをint型にしたら今度は作業1においてmin_nが全て0になってしまい，どうすれば解決できるか教えて下さい．
宜しくお願いします．

[bitter_fox]

コード:

2.Smin_nのすべてのeiについてすべてのSjのeiの値を調べフラグを下げる。
2-1.ループ：ei(S[min_n][i]) = e1(S[min_n][0])からe9(S[min_n][8])
2-1-1.分岐：eiが1(S[min_n][i] == 1)ならば
2-1-1-1.ループ：Sj(S[j]) = S1(S[0])からS8(S[7])
2-1-1-1-1.分岐：Sjのeiを調べ1ならフラグを下げる(-1にする)(S[j][i]) == 1ならばS[j][i] = -1)

ありがとうございます．続けて作業2に移行したのですが，またつまづきました．
あらたに配列としてint S[8][9]をつくり，示していただいたのを文にして

S[8][9]に当たる配列はソース内のa[8][9]ですね。

min_nが整数の型ではないためS[min_n]が文として受け付けてくれません．min_nをint型にしたら今度は作業1においてmin_nが全て0になってしまい，どうすれば解決できるか教えて下さい．

min_nとmin_listはint型とint型配列にしてください。
また、そのようにしてもmin_nが0になることは無いように思うのですが・・・
[hr][追記]
フォーマット指定子が%fだと0.000000と表示されてしまうかもしれません。整数値には%dを使用してください。

[ファイブマン]

S[8][9]に当たる配列はソース内のa[8][9]ですね。

それはあらたにこのS[8][9]を作らなくても良いということでしょうか？

また、そのようにしてもmin_nが0になることは無いように思うのですが・・・

正確には 0.000000になってしまいます．
コードを貼ってみます．おそらくまた違ったことをやっていると思うのでご指摘宜しくお願いします．

コード:

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

double calc(char a[9], char str){
  int e, count = 0;
  
  // 有効な探査対象の個数を探す(a[e]が1の物)
  for (e = 0; e < 9; e++){
    if (a[e] == 1){
      count++;
    }
  }
  if (count == 0){
    return -1;
  }
  return ((double)str) / count;
}


int main(int argc, int argv[]){
  
  int atoi(const char *str);
  char str[] = {90, 34, 23, 30, 20, 98, 100, 2};
  int i,n, j, min_n;  
  double min_cost, cost_buf;
  int S[8][9];
  int min_list[8] = {-1, -1, -1, -1, -1, -1, -1, -1} ;
  char a[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
  
  for(i = 0; i < 8 ; i++){
    cost_buf = calc(a[i], str[i]);
    if (cost_buf != -1)
      {
	if(i == 0){  
	  min_cost = cost_buf;
	  min_n = i;
	  
	}
	else{ 
	  if(cost_buf < min_cost){
	    min_cost = cost_buf;
	    min_n = i;  
	  }
	}
      }
    printf("%f\t%f\n",min_cost, min_n);
    
  }

  while(S[min_n][i] < 8 && S[min_n][i]>0)
    if((S[j][i]) == 1)
      S[j][i] = -1; 
  return 0;
}

[bitter_fox]

それはあらたにこのS[8][9]を作らなくても良いということでしょうか？

そういう事です。

正確には 0.000000になってしまいます．
コードを貼ってみます．おそらくまた違ったことをやっていると思うのでご指摘宜しくお願いします．

コード:

    printf("%f\t%f\n",min_cost, min_n);

やはりフォーマット指定子の問題ですね。

コード:

printf("%f\t%d\n",min_cost, min_n);

とすれば正常にmin_nの値が表示されます。
[hr][追記]
そうそう、aとstrがchar型の配列である必要はなく特に利益はないんでint型の配列に変更しておくべきでしょう。
あと変数名も分かりやすい物にした方が良いでしょう。

[ファイブマン]

毎度毎度ありがとうございます．
文字もいわれたとおり少し変えてみたのですがもっとわかりやすくした方がいいでしょうか？

とりあえず作業2までは終えたつもりなのですが，
どうも出力結果が意図したようになりません．
軌道のコストが最小の値はS8で，そのフラグが下がってー１になるのはわかるのですが，
S7まで下がってしまう理由がわかりません．
今度はどこが誤っているのでしょうか．

コード:

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

double calc(int S[9], int str){
  int e, count = 0;
  
  // 有効な探査対象の個数を探す(a[e]が1の物)
  for (e = 0; e < 9; e++){
    if (S[e] == 1){
      count++;
    }
  }
  if (count == 0){
    return -1;
  }
  return ((double)str) / count;
}


int main(int argc, int argv[]){
  
  int atoi(const char *str);
  int str[] = {90, 34, 23, 30, 20, 98, 100, 2};
  int i,n, j, min_n;  
  double min_cost, cost_buf;
  int min_list[8] = {-1, -1, -1, -1, -1, -1, -1, -1} ;
  int S[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
  
  for(i = 0; i < 8 ; i++){
    cost_buf = calc(S[i], str[i]);
    if (cost_buf != -1)
      {
	if(i == 0){  
	  min_cost = cost_buf;
	  min_n = i;
	  
	}
	else{ 
	  if(cost_buf < min_cost){
	    min_cost = cost_buf;
	    min_n = i;  
	  }
	}
      }
    printf("%f\t %d\n",min_cost, min_n);
    
  }  //作業1

  while(i < 9 && i >= 0)
    if((S[min_n][i]) == 1)
      for(j = 0; j < 8; j++){
	if((S[j][i]) == 1)     
	  S[j][i] = -1;
          //作業2
	printf("%d\n", S[j][i]);
      }  
 return 0;
}

[bitter_fox]

文字もいわれたとおり少し変えてみたのですがもっとわかりやすくした方がいいでしょうか？

strは既に文字列(string)ではないのでS_costsやcost_listなどの名前にした方が良いでしょう。

とりあえず作業2までは終えたつもりなのですが，
どうも出力結果が意図したようになりません．
軌道のコストが最小の値はS8で，そのフラグが下がってー１になるのはわかるのですが，
S7まで下がってしまう理由がわかりません．

S7が下がるのは正常な結果です。
これは

このaは縦をS、横をeにした2元配列にし、Sを最短経路順に選びすべてのeを通過するようにしたいのですが、ただSの重み順に小さい方から選ぶだけならおそらくできるのですが、例えばS7の後S1を選ぶときe3はすでに通過したので、それまでのS1の対象1個あたりの重み(90÷4=22.5)が大きくなり、30(=90÷3)になるようにするので、そうなるとどうすればよいのか方法がわかりません。

の「例えばS7の後S1を選ぶときe3はすでに通過したので、それまでのS1の対象1個あたりの重み(90÷4=22.5)が大きくなり、30(=90÷3)になるようにする」為に探査済みという印をすべてのSに付けて行くという処理です。

2.png (3.72 KiB) 閲覧数: 13122 回

表で表すと上の様になり

コード:

2.Smin_nのすべてのeiについてすべてのSjのeiの値を調べフラグを下げる。
2-1.ループ：ei(S[min_n][i]) = e1(S[min_n][0])からe9(S[min_n][8])
2-1-1.分岐：eiが1(S[min_n][i] == 1)ならば
2-1-1-1.ループ：Sj(S[j]) = S1(S[0])からS8(S[7])
2-1-1-1-1.分岐：Sjのeiを調べ1ならフラグを下げる(-1にする)(S[j][i]) == 1ならばS[j][i] = -1)

の2-1に赤・緑が、2-1-1に緑が、2-1-1-1に緑・青・オレンジが、2-1-1-1-1に緑・オレンジが対応しています。

コード:

 
  for(i = 0; i < 8 ; i++){
    //略
  }  //作業1

  while(i < 9 && i >= 0)
    if((S[min_n][i]) == 1)
      for(j = 0; j < 8; j++){
	if((S[j][i]) == 1)     
	  S[j][i] = -1;
          //作業2
	printf("%d\n", S[j][i]);
      }  

iがfor (i = 0; i < 8; i++)のあとに変更されていないのでiの値は8となっています。
また、iの値を変動させる処理がwhile内に無いので無限ループになってしまっています。

3.png (3.46 KiB) 閲覧数: 13122 回

ちなみにこの処理を表で表すとこのようになり正しく評価できていないことが分かります。(min_n = 7(コストが最小となるものをS8)として仮定)

先の話になりますが、3について少しふれておきます。
2ができると最小のコストとなるSnを求めるアルゴリズムはほとんどできています。
1について少しの修正が必要ですが、後は未探査の探査対象がある間1と2をループに掛ければ近似となるSの集合が求まります。
この「未探査の探査対象がある」を判断する関数(引数:int S[8][9])を作ってみてください。
処理の中身は全てのS[j]を調べ一つでも1があれば真を返し(未探査の探査対象がある)、無ければ偽を返す(未探査の探査対象がある無い)様にしてください。

その関数(仮にcheck_continue)が出来たら

コード:

while (check_continue(S))
{
	// 1(修正が必要)

	// 2
}

とするだけで8割がた完成です。

偽の時の値は0あるいはFALSE、真の時の値は0以外あるいはTRUEを使ってください
1の修正についてはまた後ほど・・・

こんな関数があると後々便利なんで書いておきます。

コード:

#define FALSE (0)
#define TRUE (!FALSE)

// 大きさがsizeのlistにnumがあったら真を無かったら偽を返す
int exist_number(int *list, int size, int num)
{
	int i;

	for (i = 0; i < size; i++)
	{
		if (list[i] == num)
		{
			return TRUE;
		}
	}

	return FALSE;
}

[ファイブマン]

やはりS7まで−1になる理由がいまいち理解できません．

それと，作業2のiを変化させるために前にforループをつけたのですが，これで作業2自体は完成したのでしょうか．作業3に入る前にs8だけでなくs7まで下がるのでしょうか．
コスト的にs8が1番小さく，その次はs7でないと思うのですが僕は何を勘違いしているのでしょうか．
御回答宜しくお願いします．

[bitter_fox]

やはりS7まで−1になる理由がいまいち理解できません．

これはcalc関数の仕様によると言っても良いでしょう。
calc関数は1を「有効な探査対象」としてみなします。
それ以外は評価しません。

S8が最小のコストと認められる前のS7の状態は、
[e1, e2, e8, e9]([1, 1, 0, 0, 0, 0, 0, 1, 1])(cost = 100)でS7の重みは100 / 4(cost / 有効な探査対象(1)の数)で25となります。

S8が最小のコストとなるとS8の探査対象[e9]([0, 0, 0, 0, 0, 0, 0, 0, 1])は重みの評価外となります。
なので、S7の有効な探査対象もe9が除外され[e1, e2, e8]へと変化します。
この変化を表現するために[1, 1, 0, 0, 0, 0, 0, 1, -1]へと変更します。
この時の重みは100 / 3(cost / 有効な探査対象(1)の数)で33.333...となります。

重みの計算を上手に行うために1以外の値にして有効な探査対象から外してしまいます。
ではなぜ0ではなく-1なのかというと、「元は有効な探査対象であった」というのを表現するために「元から探査対象でなかった」を示す0と区別するためです。

それと，作業2のiを変化させるために前にforループをつけたのですが，これで作業2自体は完成したのでしょうか．作業3に入る前にs8だけでなくs7まで下がるのでしょうか．

ソースコードで言うとどのようになりましたか？

コード:

1-2.この時のmin_nを配列に保存

あと最新のソースコードを見る限りではこれは行われていません。
3で1, 2をループに掛けたときに最小のコストとなる物を適切に保存するために必要ですので行っておいてください。
[hr][追記]
それから、またインデントが崩れてしまっています。可読性にかかわるので適切にインデントしておいてください。
もし手動でインデントを行っている結果崩れてしまっているのであれば、スマートインデント(自動でインデントしてくれる)機能のあるエディタを使用することをお勧めします。

[ファイブマン]

なるほど，s7の件はわかりました．
配列にを保存する方法を理解していないのですが，ソースコードに記載したようではないですよね？
そのことを含めてソースコードを載せますので再度ご指摘宜しくお願いします．

コード:

#include<stdio.h>
#include<stdlib.h>
#define FALSE (0)
#define TRUE (!FALSE)

double calc(int S[9], int S_cost){
  int e, count = 0;
  
  // 有効な探査対象の個数を探す(a[e]が1の物)
  for (e = 0; e < 9; e++){
    if (S[e] == 1){
      count++;
    }
  }
  if (count == 0){
    return -1;
  }
  return ((double)S_cost) / count;
}

int exist_number(int *list, int size, int num)
{
  int i;
  
  for (i = 0; i < size; i++)
    {
      if (list[i] == num)
        {
	  return TRUE;
        }
    }
  
  return FALSE;
}

int search  (int S[8][9]){
  int i,j;
  if(S[i][j] = 1)
    return (int)exist_number;
}

int main(int argc, int argv[]){
  
  int atoi(const char *str);
  int S_cost[] = {90, 34, 23, 30, 20, 98, 100, 2};
  int i, n, j, min_n, k , Smin;  
  double min_cost, cost_buf;
  int min_list[8] = {-1, -1, -1, -1, -1, -1, -1, -1} ;
  int S[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
  
  for(k= 0; k < 9; k++){
    
    for(i = 0; i < 8 ; i++){
      cost_buf = calc(S[i], S_cost[i]);
      if (cost_buf != -1)
	{
	  if(i == 0){  
	    min_cost = cost_buf;
	    min_n = i;
	    
	  }
	  else{ 
	    if(cost_buf < min_cost){
	      min_cost = cost_buf;
	      min_n = i;  
	    }
	  }
	}
      int Smin[]= min_n;  
      printf("%f\t %d\n",min_cost, min_n, );
      
    }  //作業1
    
    for(i =0; i < 9; i++){
      if((S[min_n][i]) == 1)
	for(j = 0; j < 8; j++){
	  if((S[j][i]) == 1)     
	    S[j][i] = -1;
	  //作業2 printf("%d\n", S[j][i]);
	  
	} 
    } 
    printf("%d\n", min_n);
  }
  return 0;
}

[bitter_fox]

1Tabのスペース数の関係でインデントが崩れて見えていたのですね。

なるほど，s7の件はわかりました．
配列にを保存する方法を理解していないのですが，ソースコードに記載したようではないですよね？

コード:

    for(i = 0; i < 8 ; i++){
      cost_buf = calc(S[i], S_cost[i]);
      if (cost_buf != -1)
	{
	  if(i == 0){  
	    min_cost = cost_buf;
	    min_n = i;
	    
	  }
	  else{ 
	    if(cost_buf < min_cost){
	      min_cost = cost_buf;
	      min_n = i;  
	    }
	  }
	}
      int Smin[]= min_n;  
      printf("%f\t %d\n",min_cost, min_n, );
      
    }

保存するのは重みが最小となるSで、最小となるSが定まるのはfor(i = 0; i < 8 ; i++)を抜けたところです。
それから、Sminは要素数を探査軌道の数(ここでは8)で宣言しておき、それに代入して行ってください。(この時代入するたびに代入先のインデックスがずれるようにしておいてください。これは3でSminに重みが最小となるSがどんどん追加されていくようにするためです。)

それとよくよく考えたらexist_numberは必要ありませんでした。
ですが、search関数のヒントにはなりますので参考にしてみてください。

コード:

//
// int型でsize個確保されたint型ポインタlistの中からnumを探し、あればTRUEなければ
// FALSEを返す。
////////////////////////////////////////////////////////////////////////////////
int exist_number(int *list, int size, int num)
{
	int i;

	for (i = 0; i < size; i++) // 0からsizeまで(size含まず)
	{
		if (list[i] == num) // list内にnumがあった時点でTRUEを返す
		{
			return TRUE;
		}
	}

	return FALSE; // ここまで来るとlist内に一つもnumが無かったということになる
}
int search  (int S[8][9]){
  int i,j;
  if(S[i][j] = 1)
    return (int)exist_number;
}

現在のsearch関数の問題点を言えばiとjが初期化されていませんのでどこかわからない所にある数値と1を比較しています。

[ファイブマン]

いろいろ参考にさせていただいてここまでやってみたのですが，
作業1の配列に保存する表記がわかりません．
初め空の配列に要求通りに値を代入するにはどのように表せばいいのでしょうか
？
そして関数searchにおいてなのですが，以下のようにすると無限ループが起きてしまいます．ループを使うと思っているのですが，どうすれば思うように動作するでしょうか．

コード:

int search  (int S[8][9]){
  int i,j;
  for(i = 0; i < 8; i++,){
    if(S[i][j] = 1){
      return 1;
    }
  
  }
  return 0;
  
}

コード:

 while(search(S)){
    
    for(i = 0; i < 8 ; i++){
      cost_buf = calc(S[i], S_cost[i]);
      if (cost_buf != -1)
	{
	  if(i == 0){  
	    min_cost = cost_buf;
	    min_n = i;
	    
	  }
	  else{ 
	    if(cost_buf < min_cost){
	      min_cost = cost_buf;
	      min_n = i;  
	    }
	  }
	}
      int Smin[8];
      if(Smin[l]=min_n){
      for(l=0; l<9; l++){
	Smin[l+1] = min_n;
      }      
      }
    }  //作業1 

[bitter_fox]

そして関数searchにおいてなのですが，以下のようにすると無限ループが起きてしまいます．ループを使うと思っているのですが，どうすれば思うように動作するでしょうか．

コード:

int search  (int S[8][9]){
  int i,j;
  for(i = 0; i < 8; i++,){
    if(S[i][j] = 1){
      return 1;
    }
  
  }
  return 0;
  
}

現在のプログラムではjが使われておりません。また初期化もされていないので不定値です。
それからS[j] = 1の=は代入演算子です、比較演算子==を使ってください。
プログラムの流れとしては次のようになります。

コード:

S[0][どこか]に1を代入
S[1][どこか]に1を代入
S[2][どこか]に1を代入
S[3][どこか]に1を代入
S[4][どこか]に1を代入
S[5][どこか]に1を代入
S[6][どこか]に1を代入
S[7][どこか]に1を代入

いろいろ参考にさせていただいてここまでやってみたのですが，
作業1の配列に保存する表記がわかりません．
初め空の配列に要求通りに値を代入するにはどのように表せばいいのでしょうか
？

コード:

 while(search(S)){
    
    for(i = 0; i < 8 ; i++){
      //略
      int Smin[8];
      if(Smin[l]=min_n){
      for(l=0; l<9; l++){
	Smin[l+1] = min_n;
      }      
      }
    }  //作業1 

int Smin[8]はmain関数の頭の方で宣言しておいてください。またそれと同時にSmin用のカウンタを初期値0で宣言しておいてください。
このカウンタは1ではSminの添え字として使われ、それ以降ではSminに入ってる要素の個数として扱われます。

Smin[カウンタ]への代入はfor(i = 0; i < 8 ; i++)の外です。
もし中で行った場合、重みが最小となるSが決まっていないにも関わらずmin_nが代入されてしまいます。

代入した後にはインデックスとして扱われるカウンタをインクリメントさせてください。

[ファイブマン]

S[0][どこか]に1を代入
S[1][どこか]に1を代入
S[2][どこか]に1を代入
S[3][どこか]に1を代入
S[4][どこか]に1を代入
S[5][どこか]に1を代入
S[6][どこか]に1を代入
S[7][どこか]に1を代入

”どこか”というのはどう表せばいいのでしょうか？jのループを使えばいいのでしょうか？

コード:

int search  (int S[8][9]){
  int i,j=0;
  for(i = 0; i < 8; i++){
   
      if(S[i][j] == 1){
	S[i][j] = 1;
	return 1;   
      } 
  } 
  return 0;
}

int Smin[8]はmain関数の頭の方で宣言しておいてください。またそれと同時にSmin用のカウンタを初期値0で宣言しておいてください。

こういうことでしょうか？

コード:

   
int Smin[8] = {0,0,0,0,0,0,0,0};

//略
 
Smin[8] = min_n; 

[bitter_fox]

”どこか”というのはどう表せばいいのでしょうか？jのループを使えばいいのでしょうか？

その通りです。
1次元配列の全探索には1重ループを、2次元配列の全探索には2重ループを、一般にn次元配列の全探索にはn重ループを用いるのが一般的なテクニックです。
http://www.geocities.jp/ky_webid/c/025.html

int Smin[8]はmain関数の頭の方で宣言しておいてください。またそれと同時にSmin用のカウンタを初期値0で宣言しておいてください。

こういうことでしょうか？

コード:

   
int Smin[8] = {0,0,0,0,0,0,0,0};

//略
 
Smin[8] = min_n; 

「int Smin[8]はmain関数の頭の方で宣言しておいてください。」はそれで結構ですが、それ以降が反映されていません。

ちなみにですが、Smin[8] = min_nは上記の場合確保された領域の外を参照しています。
int Smin[8]として宣言された配列の有効な添え字は0, 1, 2, 3, 4, 5, 6, 7のいずれかです。
http://www.geocities.jp/ky_webid/c/023.html

[ファイブマン]

searchにおいて，i,jのループをして，S[j]が1のときを見つけた時は1を返して，1がなくなるまでループさせたいのですがこの場合，S[j] == 1は作業２の部分で-1にするので値を返る必要はないのでしょうか．そうしてこのまま実行すると無限ループが起きてしまいます．どのようにすればこの状況を回避できるのでしょうか．

コード:

int search  (int S[8][9]){
  int i=0;
  int j=0;
  for(i = 0; i < 8; i++){
    for(j=0; j<9; j++)   
      if(S[i][j] == 1){
	
	return 1;   
      } 
  } 
  return 0;
  
}

またそれと同時にSmin用のカウンタを初期値0で宣言しておいてください。
このカウンタは1ではSminの添え字として使われ、それ以降ではSminに入ってる要素の個数として扱われます。

．
この部分が理解できないのですがさらに詳しくいうとどういった意味でしょうか？

コード:

int Smin[8] = {0,0,0,0,0,0,0,0};
 
//略
    Smin[i] = min_n; 
    printf("%.1f\t %d\t%d\n",min_cost, min_n, Smin);
	

[bitter_fox]

searchにおいて，i,jのループをして，S[j]が1のときを見つけた時は1を返して，1がなくなるまでループさせたいのですがこの場合，S[j] == 1は作業２の部分で-1にするので値を返る必要はないのでしょうか．そうしてこのまま実行すると無限ループが起きてしまいます．どのようにすればこの状況を回避できるのでしょうか．

無限ループに陥ることはありません。
この二つのfor文には上限が決まっていますおり、S[0][0]からS[7][8]までです。
それまでに1が一つでもあれば1が、一つもなければ0が返ります。

この関数は、「まだ有効な探査対象が残ってるよ～」ということを教えるという役割です。
もしすべて1以外(-1など)になっていたとしたら0(偽)を返します。これは「有効な探査対象はもうないよ」ということを意味します。
ですのでmainでは「有効な探査対象が残っている」間、つまりこの関数が1を返している間調べます。

またそれと同時にSmin用のカウンタを初期値0で宣言しておいてください。
このカウンタは1ではSminの添え字として使われ、それ以降ではSminに入ってる要素の個数として扱われます。

．
この部分が理解できないのですがさらに詳しくいうとどういった意味でしょうか？

コード:

int Smin[8] = {0,0,0,0,0,0,0,0};
 
//略
    Smin[i] = min_n; 

iは直前で別の目的に使われてから変更されていないのでSminに用いるのは適切ではありません。

コードで言うと次のようにすれば良いです。

コード:

int Smin_count = 0;

// 略
Smin[Smin_count++] = min_n;

Smin_countを用いる理由は3において何度も重みが最小となるSを調べその値を保存していくのですが、その際にSminの添え字をずらしていくためです。

コード:

+----+
|Smin|
+----+--------------------+
| 0 | 1 | 2 | 3 | ... | 7 |
+-------------------------+-----------------------------+
|↑最初に最小の重みとなるSの添え字を入れる              | // 1回目(Smin_count = 0よってS[0]に代入、Smin_count++でSmin_count = 1に)
|    ↑二番目に最小の重みとなるSの添え字を入れる        | // 2回目(Smin_count = 1よってS[1]に代入、Smin_count++でSmin_count = 2に)
|        ↑三番目に最小の重みとなるSの添え字を入れる    | // 3回目(Smin_count = 2よってS[2]に代入、Smin_count++でSmin_count = 3に)
|            ↑四番目に最小の重みとなるSの添え字を入れる| // 4回目(Smin_count = 3よってS[3]に代入、Smin_count++でSmin_count = 4に)
|                ↑...                                  |
+-------------------------------------------------------+

この時、SminとSmin_countの値の関係を見ていくと、Sminに入れられている有効な値の個数とSmin_countの値が等しいことが分かります。
また、Smin[Smin_count]=nとするとまだ代入がされていない所に、うまくnが代入されます。

それから、Sminに入れられている有効な値の個数とSmin_countの値が等しいことから
for (i = 0; i < Smin_count; i++)
とすれば、Sminにある有効な値を調べたいを調べられます。

これも比較的よくあるテクニックかと思います。

[ファイブマン]

すみません，少し勘違いしてました．
作業3の時点で課題の用件は済んでいたようです．
あとはそれを文章にすればよかったのでできました．
いろいろ吟味した結果，以下のようになったのですが
一つだけわからないところがあります．
のSi添字とその時のコストを出したのですが，最後,添字0のときコスト8になるのがいらないのですが出てきてしまいます．
それが出力時消えれば完成なのですがどうすればいいでしょうか．
最後の最後まですみません，宜しくお願いします．

コード:

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

double calc(int S[9], int S_cost){
  int e, count = 0;
  
  // 有効な探査対象の個数を探す(a[e]が1の物)
  for (e = 0; e < 9; e++){
    if (S[e] == 1){
      count++;
    }
  }
  if (count == 0){
    return -1;
  }
  return ((double)S_cost) / count;
}

int main(void){
  
  int S_cost[] = {90, 34, 23, 30, 20, 98, 100, 2};
  int i, j,k, min_n;  
  double min_cost, cost_buf;
  int S[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
  
  for(k = 0; k < 8; k++){
    min_n = -1;    
    for(i = 0; i < 8; i++){
      cost_buf = calc(S[i], S_cost[i]);
      // printf("[%d]:%lf\n",i+1,cost_buf);
      if (cost_buf != -1)
 	{
	  if(min_n == -1){  
	    min_cost = cost_buf;
	    min_n = i;	    
	  }
	  else{ 
	    if(cost_buf < min_cost){
	      min_cost = cost_buf;
	      min_n = i;  
	    }
	  }
	} 
    }
    printf("Siの添字iは%d, その時のコストは%d\n", (min_n)+1, S_cost[min_n]);
    for(i =0; i < 9; i++){
      if((S[min_n][i]) == 1)
	for(j = 0; j < 8; j++){
	  if((S[j][i]) == 1)     
	    S[j][i] = -1;	 
	} 
    }    
  }
  return 0;
}

[naohiro19]

コンパイラによって違う結果になりました。

出力結果(Visual Studio 2010でコンパイルしたもの):

コード:

Siの添字iは8, その時のコストは2
Siの添字iは5, その時のコストは20
Siの添字iは3, その時のコストは23
Siの添字iは4, その時のコストは30
Siの添字iは2, その時のコストは34
Siの添字iは1, その時のコストは90
Siの添字iは6, その時のコストは98
Siの添字iは0, その時のコストは1079541760

出力結果(MinGWのGCCでコンパイルしたもの):

コード:

Siの添字iは8, その時のコストは2
Siの添字iは5, その時のコストは20
Siの添字iは3, その時のコストは23
Siの添字iは4, その時のコストは30
Siの添字iは2, その時のコストは34
Siの添字iは1, その時のコストは90
Siの添字iは6, その時のコストは98
Siの添字iは0, その時のコストは-1

[bitter_fox]

一つだけわからないところがあります．
のSi添字とその時のコストを出したのですが，最後,添字0のときコスト8になるのがいらないのですが出てきてしまいます．
それが出力時消えれば完成なのですがどうすればいいでしょうか．

コード:

  for(k = 0; k < 8; k++){
    min_n = -1;    
    for(i = 0; i < 8; i++){

    }
    printf("Siの添字iは%d, その時のコストは%d\n", (min_n)+1, S_cost[min_n]);
  }

これはmin_nが-1の時はループ(for(k = 0; k < 8; k++))を抜けるようにして、それ以外の時だけ出力すればよいかと思います。

[hr][追記]
出来上がったコードを見てみると同じような数字が幾つか見受けられます。

コード:

double calc(int S[9], int S_cost){
  for (e = 0; e < 9; e++){
  int S[8][9] = {
  for(k = 0; k < 8; k++){
    for(i = 0; i < 8; i++){
    for(i =0; i < 9; i++){
      if((S[min_n][i]) == 1)
	for(j = 0; j < 8; j++){

この8や9がそれです。
8という数字は探査軌道Sの個数、9という数字は探査対象eの個数で、いずれも意味のある数字です。
こういった意味のある数値が直接出てくるというのはマジックナンバーと呼ばれ、悪手となります。

なぜ悪手かというと探査軌道Sの個数を12などに増やしたとしましょう。そうするとプログラム内に出てくるSの個数を示す8をすべて適切に12へと書き換えなければなりません。
もし一つでも書き換え漏れがあるとプログラムは正常に動作しないでしょう。

また、単に8などではその値が何を示しているのか他の人が見たときに分かりません。
8にどういう意味があるのかを明示してあげるべきです。

そこで、定数を定めてそれ以降Sの個数、eの個数を示す数字はその定数を用いることにします。

コード:

#define S_COUNT 8
#define E_COUNT 9

double calc(int S[E_COUNT], int S_cost){
  for (e = 0; e < E_COUNT; e++){
  int S[S_COUNT][E_COUNT] = {
  for(k = 0; k < S_COUNT; k++){
    for(i = 0; i < S_COUNT; i++){
    for(i =0; i < E_COUNT; i++){
      if((S[min_n][i]) == 1)
	for(j = 0; j < S_COUNT; j++){

この様にするとただの数字でしかなかったものに名前がついたので何を示すかが一目瞭然になりました。
また、もしSの個数が12に変わったとしても変更する箇所はS_COUNTの定義だけで良いことになります。
マジックナンバー(by Wikipedia)

[ファイブマン]

コード:

for(k = 0; k < ORBIT; k++){
  
  
  if(min_n == -1)
    break;
 }

と，ループの最後に投入してみたのですがどうもきれいにループを抜け出せず値が変化しません．どこに投入すれば出力で「Siの添字iは0, その時のコストは8」が消えるのでしょうか．他にいろいろ試すと全て出力されなかったり，その他の値まで変わってしまい，正しい投入場所がわかりません．



マジックナンバーの件はいわれたとおり直したら自分で見てもわかりやすくなりました！ありがとうございます．

[bitter_fox]

コード:

for(k = 0; k < ORBIT; k++){
  
  
  if(min_n == -1)
    break;
 }

と，ループの最後に投入してみたのですがどうもきれいにループを抜け出せず値が変化しません．どこに投入すれば出力で「Siの添字iは0, その時のコストは8」が消えるのでしょうか．他にいろいろ試すと全て出力されなかったり，その他の値まで変わってしまい，正しい投入場所がわかりません．

マジックナンバーの件はいわれたとおり直したら自分で見てもわかりやすくなりました！ありがとうございます．

コード:

printf("Siの添字iは%d, その時のコストは%d\n", (min_n)+1, S_cost[min_n]);

がmin_n == -1の時実行されてほしくないのですからこの文の直前に入れれば実行されませんよね？

[ファイブマン]

何度にもわたってありがとうございます。
おかげでこっちの方は解決しました。
またよろしくお願いします。

[ファイブマン]

すみません、最後にソースコードをつけるのを忘れてしまいました。

コード:

#include<stdio.h>
#include<stdlib.h>
 
double calc(int S[9], int S_cost){
  int e, count = 0;
  
  // 有効な探査対象の個数を探す(a[e]が1の物)
  for (e = 0; e < 9; e++){
    if (S[e] == 1){
      count++;
    }
  }
  if (count == 0){
    return -1;
  }
  return ((double)S_cost) / count;
}
 
int main(void){
  
  int S_cost[] = {90, 34, 23, 30, 20, 98, 100, 2};
  int i, j,k, min_n;  
  double min_cost, cost_buf;
  int S[8][9] = {
    {0, 0, 1, 1, 1, 1, 0, 0, 0}, 
    {0, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1}
  };
  
  for(k = 0; k < 8; k++){
    min_n = -1;    
    for(i = 0; i < 8; i++){
      cost_buf = calc(S[i], S_cost[i]);
      // printf("[%d]:%lf\n",i+1,cost_buf);
      if (cost_buf != -1)
    {
      if(min_n == -1){  
        min_cost = cost_buf;
        min_n = i;      
      }
      else{ 
        if(cost_buf < min_cost){
          min_cost = cost_buf;
          min_n = i;  
        }
      }
    } 
    }
　　if(min_n == -1)
    　　break;
    printf("Siの添字iは%d, その時のコストは%d\n", (min_n)+1, S_cost[min_n]);
    for(i =0; i < 9; i++){
      if((S[min_n][i]) == 1)
    for(j = 0; j < 8; j++){
      if((S[j][i]) == 1)     
        S[j][i] = -1;    
    } 
    }    
  }
  return 0;
}