3


我试图在优化问题中找到两个数组的非支配值。

我有两个数组，lost_bars_array并且prices_array. 我想做的是尽量减少丢失的酒吧，并最大限度地提高价格。我想得到一个以no_dominated两个数组的非支配值的索引命名的最终数组。这很容易理解。让我用一个例子来解释这一点。

我们有初始的两个数组：
在此处输入图像描述

理论过程是这样的：

1.获取第一个值
在此处输入图像描述

2.获取第二个（索引#1），看看它是否比第一个更好。这意味着我们必须看看第二个是否有更少的损失和更大的价格。事实并非如此，它有 LESS 酒吧，但价格也更低，所以我们不能说这是一个更好的解决方案。我们将其保存为可行的解决方案
在此处输入图像描述

3.现在是下一个，索引#2，这个改进了索引#1的解决方案，因为它丢失了更少的brs和更大的价格。但它并没有提高索引#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作为解决方案输出。我希望我正确地解释了这个问题。
任何帮助表示赞赏。提前致谢。

4

2 回答 2

1

如果您有 n 个指标来比较您的数据（在您的实现中，n = 2 个数组与要最大化/最小化的数据），您最多可以有 n (2) 个非支配元素。

因此，您可以在每个数组中找到最大/最小元素和索引，这将是您的解决方案（如果两个索引相同，只需添加其中一个）。

您根本不必担心统治，no_dominated也不必有输入的大小。它的大小将介于 1 和您的指标/数据数组数量之间（在示例中为 1 或 2）

于 2013-07-02T09:54:58.093 回答
1

下面的程序可以得到你想要的，但我只针对你的具体情况进行了测试；如果只有一个主导解决方案，或者在其他一些特殊情况下，它很可能会失败。但是你也许可以从这里开始工作。

两个注意事项：

  • 你忘了包括潜在的解决方案；布尔值&&只会保存保证更好的解决方案

  • 最后一个双循环有点小技巧；散列会更容易（解决方案索引将是散列），但我认为这需要 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;
}
于 2013-07-02T09:51:46.860 回答