c - 2 つの配列の非優越解を見つけようとしている

Question

最適化問題で 2 つの配列の優先されない値を見つけようとしています。

私は2つの配列を持っていlost_bars_arrayますprices_array. 私がやりたいことは、失われたバーを最小化し、価格を最大化することです. no_dominated両方の配列の非支配値のインデックスで名前が付けられた最終的な配列を取得したいと考えています。分かりやすいです。これを例を挙げて説明しましょう。

最初の 2 つの配列があります。

理論的なプロセスは次のようなものです。

1.最初の値を取得する

2. 2 番目のもの (インデックス #1) を取得し、最初のものよりも優れたソリューションであるかどうかを確認します。これは、2 番目の損失バーが少なく、価格が大きいかどうかを確認する必要があることを意味します。これは事実ではありません。バーが少ないだけでなく、価格も少ないため、より良い解決策とは言えません. 可能な解決策として保存します

3.次のインデックス #2 が来ます。これはインデックス #1 のソリューションを改善します。しかし、失われたバーが少ないだけでなく、価格も少ないため、インデックス #0 は改善しません。したがって、インデックス #0 とインデックス #2 を可能なソリューションとして保存します。

4.インデックス #3 と #4 は失われたバーが多く、価格が少ないため、可能なソリューションとして拒否します。

5.最後に、インデックス #5 は、インデックス #0 より損失バーが少なく、価格が高いため、インデックス #0 のソリューションは拒否され、最終的な支配されていない値は、インデックス #2 とインデックス #5 のものになります。

これは私がこれまでに試したことです。

#include <stdio.h>

int main(int argc, char** argv)
{
    int lost_bars_array[] = {15, 10,  8, 15, 17,  9};
    int prices_array[]    = {35, 25, 30, 10, 15, 36};
    int no_dominated[6];
    int cont              = 6;

    for (int actual_pos = 0; actual_pos < cont; actual_pos++)
    { 
        if (actual_pos == 0)
        {
            no_dominated[actual_pos] = actual_pos; 
        } 
        else
        {
            // Here's where I've the problems, I dont know how to handle the arrays
            for (int p = 0; p < actual_pos; p++)
            {
                if (lost_bars_array[p] > lost_bars_array[p + 1] && 
                    prices_array[p] < prices_array[p + 1])
                {
                    no_dominated[p] = p;
                }

            }
        }
    }

    printf("\nThe non-dominated solutions index are: %d");
    for (int i = 0; i < 6; i++)
    {
        printf(" %d ", no_dominated[i]);
    }

    printf("\n");

    return 0;
}

コードは、ソリューションとしてインデックス2 5を出力する必要があります。問題を正しく説明したことを願っています。
どんな助けでも大歓迎です。前もって感謝します。

Answer 1

データを比較するメトリックが n 個ある場合 (実装では、最大化/最小化するデータを含む n = 2 配列)、最大 n (2) 個の非優勢要素を持つことができます。

したがって、各配列の最大/最小要素とインデックスを見つけるだけで、それらが解決策になります (2 つのインデックスが同じ場合は、そのうちの 1 つだけを追加してください)。

支配についてまったく心配する必要no_dominatedはなく、入力のサイズを持つ必要もありません。サイズは 1 からメトリクス/データ配列の数 (この例では 1 または 2) の間になります。

Answer 2

以下のプログラムはあなたが望むものを取得しますが、特定のケースでのみテストしました。支配的なソリューションが 1 つしかない場合や、その他のいくつかの特殊なケースでは、失敗する可能性が非常に高くなります。しかし、あなたはこれから働くことができるかもしれません。

2 つの注意事項:

• 潜在的な解決策を含めるのを忘れました。ブール値&&は、より良いことが保証されているソリューションのみを保存します

• 最後の二重ループはちょっとしたハックです。ハッシュの方が簡単です（ソリューションインデックスはハッシュになります）が、c ++または追加のライブラリが必要だと思います。

コード：

#include <stdio.h>

int main() 
{
    int lost_bars_array[] = {15,10,8,15,17,9};
    int prices_array[] = {35,25,30,10,15,36};
    int no_dominated[6];
    int cont = 6;
    int ndom = 0;

    no_dominated[ndom] = 0;
    ndom++;
    for (int actual_pos = 1; actual_pos < cont; actual_pos++) { 
        int ntmp = ndom;
        for(int p = 0; p < ntmp; p++) {
            if (lost_bars_array[no_dominated[p]] > lost_bars_array[actual_pos] && 
                prices_array[no_dominated[p]] < prices_array[actual_pos]) {
                // Replace with a better solution
                no_dominated[p] = actual_pos;
        } else if (lost_bars_array[no_dominated[p]] > lost_bars_array[actual_pos] ||
               prices_array[no_dominated[p]] < prices_array[actual_pos]) {
                // Save as potential solution
                no_dominated[ndom] = actual_pos;
                ndom++;
            }
        }
    }
    // Remove double solutions
    for (int i = 0; i < ndom; i++) {
        for (int j = i; j < ndom; j++) {
            if (no_dominated[i] == no_dominated[j]) {
                ndom--;
            }
        }
    }
    printf("\nThe non-dominated solutions index are:");
    for(int i = 0; i < ndom; i++)
        printf(" %d ", no_dominated[i]);
    printf("\n");
    return 0;
}