Geek Answers Handbook

Efficient storage structure for optimal Pareto solutions

I am trying to solve a problem that requires storing optimal pareto solutions during computation. I will call the set of optimal solutions a Pareto bag.

So far, I have had only two criteria, which allowed a fairly effective solution based on an array in which elements were sorted in descending order in accordance with the first criterion and ascending by the second criterion. An example of such an array might be:

[(100, 0), (50, 1), (-10, 3)]

(about optimality pareto - wiki )

I recently found out that I need to add a third criterion, and this approach does not seem to be applicable for such an extension. I tried to understand, someone had already decided this, but did not find anything satisfactory. Perhaps I was asking the wrong Google question.

To be more precise about what I need : A structure capable of storing mutually acceptable optimal pareto elements. I need to insert elements into a structure, and I need to iterate over elements, but not in a specific order. In my case, there will usually not be more than 4-5 elements, but sometimes more than 10-20. Insertions into the bag occur very often in my algorithm, so I need them to be as fast as possible.

The application is written in C ++, but probably it does not really matter.

Any help would be greatly appreciated.

Edit: I already had some ideas about my own - organizing elements into some kind of triangular structure, but I can not formalize this idea.

Edit2: , , . , {(1,2,3), (3, 1, 1)} triple (3, 3, 3), set {(3,3,3)}.

Edit3: , , triple (a,b,c) (e,f,g) , a >= e && b >= f && c >= g - >.

+4
5

, , (, a*a + b*b + c*c), , , .

, , , . ( , ) , . , , , std::list std::map . .

, unsorted std::vector:

std::vector<Element> frontier;
void insert(const Element& newElement) {
    if (std::none_of(frontier.begin(), frontier.end(),  [&](const auto& e) {return dominates(e, newElement); })) {
        frontier.erase(std::remove_if(frontier.begin(), frontier.end(), [&](const auto& e) {return dominates(newElement, e); }),frontier.end());
        frontier.push_back(newElement);     
    }
}
+1

, , , .

// Taken from the question and translated.
// Is the dominance condition.
let x_doms_y x y =
    let (a,b,c) = x
    let (e,f,g) = y
    a >= e && b >= f && c >= g &&
    (a > e || b > f || c > g)

Naive O (n), , , . O (n), .

type Triplet = int * int * int
type TripletSet = Triplet list

module Naive =
    let insert (t : Triplet) (tset : TripletSet) : TripletSet =
        t :: (tset|> List.filter (fun u -> not (x_doms_y t u)))

, :

let foo =
[] |> show
|> Naive.insert (1,2,3) |> show
|> Naive.insert (3,1,1) |> show
|> Naive.insert (3,3,3) |> show

> []
  [(1, 2, 3)]
  [(3, 1, 1); (1, 2, 3)]
  [(3, 3, 3)]

.

, , , , , < . , .

. , . 1,2,3 , 0,0,0 .

? - . . x < y, x y, x >= y && X > y.

. .

. , , , , . , , , .

, :

  • qset - , .
  • vt - t: (a, b, c). vt = a * b * c
  • qt = (vt, a, b, c)
  • , pos qset .
  • pos ( v < vt) .
  • pos , .
  • , qset [0..pos-1]. , n/2, n - qset.
  • qt pos qset qset.
+1

, - std::set , , . ( , ++) , , , , , , . - multiset, "" . , , vector, , "" , .

, , Pareto set . , , . - , , , -, . , . , . , .

+1

, . , , , . , set ( ).

0

( ++ 'ish):

vec. :

void insert(const auto& e) {
    for (size_t i = 0; i < vec.size(); ++i) {
        if (e.dominates(vec.at(i))) {
            remove(vec.at(i));
        } else if (vec.at(i).dominates(e)) {
            return;
        }
    }
    vec.append(e);
}

This code needs to be more polished in order to effectively remove elements, but I suspect that this is not the best we can get, since we should always name dominatesfor each element (if the inserted element does not dominate), while in my solution which I had to check only before he first dominated the set, and the rest was perfectly eliminated.

0
source

More articles:


All Articles