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

[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;
}