Implementazione ottimizzazione funzione dominio discreto

[erotavlas1]

Ho una funzione del tipo $ max_{x} min_{y} \... max_{z} f(x,y,...,z) $ di cui devo calcolare il valore ottimo.
Non ci sono vincoli e le variabili assumono valori da domini discreti.
Per calcolare i valori di x e y per cui è ottima seguo i seguenti passi:
Un esempio banale $min_{x} max_{y} f(x,y) = (x+1)^y$.
1) mi costruisco una tabella dei possibili valori di x e y.
2) Per tutti i valori di x, trovo il valore di y che
massimizza f(x,y).
3) Cerco nel sottoinsieme delle coppie (x,y) dal passo precedente (y fissato), i valori di x che minimizzano
l'espressione.
Supponendo che x prenda valori dal dominio (0,1) e y dal dominio (0,1,2):
1)
[tex]\begin{bmatrix} 0 0 0 \\ 0 1 1 \\ 0 2 1 \\ 1 0 1 \\ 1 1 2 \\ 1 2 4\end{bmatrix}[/tex]
dove le prime due variabili sono x,y mentre la terza è f(x,y).
2) il valore di y per cui f(x,y) è massima è y = 2
3) il valore di x per cui f(x,2) è minima è x = 0
La funzione f(0,2) = 1.
Tale procedura è matematicamente corretta?
Devo implementare la procedura al calcolatore. Il problema è nella memorizzazione della matrice delle possibili combinazioni delle variabili la quale diventa ingestibile per problemi reali. Avete qualche idea?

Grazie

[apatriarca]

Come è definita la funzione f? Ha caratteristiche particolari? E' garantita ad esempio l'unicità del minimo o del massimo assoluto ad ogni passo? Ha valori in che insieme?

[erotavlas1]

La funzione può avere diverse forme: somma di gaussiane, produttoria di funzioni generiche, etc. In generale non ha una forma particolare. Il minimo/massimo può non essere unico ovvero ci possono essere più configurazioni dell'ingresso che restituiscono lo stesso valore. L'insieme dei valori della funzione sono numeri reali (dominio e codominio).
In pratica devo fare una verifica per tutte le combinazioni di valori dell'ingresso sul valore che la funzione assume e massimizzare o minimizzare ad ogni passo.
Pensavo di utilizzare, al posto della matrice di tutte le combinazioni, un algoritmo di backtracking che esplora l'albero di tutte le possibili combinazioni. Passo per passo devo tenere memorizzato il valore massimo o minimo della funzione e il corrispondente insieme di valori di input.
Secondo voi è un approccio valido o avete qualche idea migliore?

[erotavlas1]

Sto ancora valutando come realizzare la ricerca del valore ottimo della funzione.
La procedura che ho riportato nel primo post è valida? Posso calcolare passo passo il valore ottimo per ogni variabile?
Grazie

[erotavlas1]

Salve,

credo di aver risolto il mio problema. Questo è il codice che lo risolve... La mia domanda è: è valida la procedura che ho usato per ottimizzare la funzione? Dalla variabile più interna alla variabile più esterna passo passo?.

int compute(const std::vector<std::pair<std::string, int> > & Indexes)
{

    int f = 0;
    for (int k = 0; k < Indexes.size(); ++k)
    {
        f += Indexes[k].second;
    }
    return f;

}

int min(const std::vector<int>& valueVector)
{

    int temp = valueVector[0];
    for (int i = 1; i < valueVector.size(); ++i)
    {
        if (valueVector[i] < temp)
            temp = valueVector[i];
    }

    return temp;

}

int max(const std::vector<int>& valueVector)
{

    int temp = valueVector[0];
    for (int i = 1; i < valueVector.size(); ++i)
    {
        if (valueVector[i] > temp)
            temp = valueVector[i];
    }

    return temp;

}

    std::vector<std::pair<std::string, int> > myVector;
    std::vector<std::string> operatorType;

    std::pair<std::string, int> element1("x", 2);
    std::pair<std::string, int> element2("y", 3);
    std::pair<std::string, int> element3("z", 2);

    myVector.push_back(element1);
    myVector.push_back(element2);
    myVector.push_back(element3);
    
    operatorType.push_back("forall");
    operatorType.push_back("exists");
    operatorType.push_back("exists");
   
    unsigned long cardinality = 1;

    std::vector<std::vector<int> > tempResults;
    std::vector<std::vector<int> > finalResults;

    // new "cardinality", index
    std::vector<std::pair<int, int> > cardinalityIndexVector;

    // reverse the order of the vector of the variables
    reverse(myVector.begin(), myVector.end());
    reverse(operatorType.begin(), operatorType.end());

    std::vector<int> temp(0);

     std::cout << "Function " << std::endl;

    for (int i = 0; i < myVector.size(); ++i)
    {
        cardinality *= myVector[i].second;
        cardinalityIndexVector.push_back(std::pair<int, int> (cardinality, 0));
        tempResults.push_back(temp);
        finalResults.push_back(temp);
        std::cout << operatorType[i] << " " << myVector[i].first << " (" << myVector[i].second << ") ";
    }

    std::cout << "f() =" << std::endl;
    finalResults.push_back(temp);
    for (int i = 0; i < cardinalityIndexVector.size(); ++i)
    {
        cardinalityIndexVector[i].first = cardinalityIndexVector[i].first / myVector[i].second;
        
    }

    std::cout << "Cardinality " << cardinality << std::endl;

    for (unsigned long i = 0; i < cardinality; ++i)
    {
        std::vector<std::pair<std::string, int> > Indexes;
        std::vector<std::pair<std::string, int> > domainsVector;

        // loop over the vector of the quantified variable
        for (int j = 0; j < myVector.size(); ++j)
        {
            if (j == 0)
            {
                // first variable, initialization
                Indexes.push_back(std::pair<std::string, int> (myVector[j].first, i % myVector[j].second));
                domainsVector.push_back(std::pair<std::string, int> (myVector[j].first, i / myVector[j].second));

            }
            else if (j < myVector.size())
            {
                Indexes.push_back(std::pair<std::string, int> (myVector[j].first, domainsVector[j - 1].second % myVector[j].second));
                domainsVector.push_back(std::pair<std::string, int> (myVector[j].first, domainsVector[j - 1].second / myVector[j].second));
            }

            if (i == 0)
            {
                std::cout << myVector[j].first << " ";
            }

        }

        if (i == 0)
            std::cout << std::endl;

        for (int k = 0; k < Indexes.size(); ++k)
        {
            std::cout << Indexes[k].second << " ";
        }
        std::cout << std::endl;

        // loop over the vector of the quantified variable
        for (int j = 0; j < myVector.size(); ++j)
        {
            //std::cout << "i " << i << "j " << j << std::endl;
            // check if the current for loop is termined
            if (cardinalityIndexVector[j].second == cardinalityIndexVector[j].first - 1)
            {
                // compute the value of the function
                if (j == 0)
                {
                    //std::cout << "Compute " << compute(Indexes) << std::endl;
                    tempResults[j].push_back(compute(Indexes));
                    finalResults[j].push_back(compute(Indexes));
                }
                if (j > 0)
                {
                    if (operatorType[j - 1] == "forall")
                    {
                        //std::cout << "Max " << max(tempResults[j - 1]) << std::endl;
                        tempResults[j].push_back(max(tempResults[j - 1]));
                        finalResults[j].push_back(max(tempResults[j - 1]));
                        tempResults[j - 1].clear();
                    }
                    else if (operatorType[j - 1] == "exists")
                    {
                        //std::cout << "Min " << min(tempResults[j - 1]) << std::endl;
                        tempResults[j].push_back(min(tempResults[j - 1]));
                        finalResults[j].push_back(min(tempResults[j - 1]));
                        tempResults[j - 1].clear();
                    }
                }
                cardinalityIndexVector[j].second = 0;
            }
            else
                cardinalityIndexVector[j].second++;
        }

        if (i == cardinality - 1)
        {
            if (operatorType.back() == "forall")
            {
               // std::cout << "Final Max " << max(tempResults[myVector.size() - 1]) << std::endl;
                finalResults.back().push_back(max(tempResults[myVector.size() - 1]));
            }
            else if (operatorType.back() == "exists")
            {
                //std::cout << "Final Min " << min(tempResults[myVector.size() - 1]) << std::endl;
                finalResults.back().push_back(min(tempResults[myVector.size() - 1]));
            }

        }

    }
   
    std::cout << "Results " << std::endl;
    for (int i = 0; i < finalResults.size(); ++i)
    {
        for (int j = 0; j < finalResults[i].size(); ++j)
            std::cout << finalResults[i][j] << " ";
        std::cout << std::endl;
    }
    std::cout << std::endl;