草庐IT

c++ - 用于存储帕累托最优解的高效结构

coder 2024-02-22 原文

我正在尝试解决需要在计算过程中存储帕累托最优解的问题。我将一组帕累托最优解称为 Bag。

到目前为止，我只有两个标准，这允许基于数组的非常有效的解决方案，其中元素根据第一个标准按降序排序，并根据第二个标准按升序排序。这种数组的一个例子是:

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

(关于帕累托最优 - wiki)

但是最近我发现我需要添加第三个标准，对于这样的扩展，上述方法似乎并不适用。我试图用谷歌搜索是否有人已经解决了这个问题，但没有找到令人满意的结果。也许我在问谷歌错误的问题。

更准确地说我需要的:能够存储相互非支配的帕累托最优元素的结构。我需要将元素插入到结构中，我需要遍历元素但没有特定的顺序。在我的例子中，通常不会超过 4-5 个元素，但有时会超过 10-20 个。在我的算法中，插入包的次数非常频繁，因此我需要它们尽可能快。

该应用程序是用 C++ 编写的，但它可能并不真正相关。

如有任何帮助，我们将不胜感激。

编辑:我已经有了自己的一些想法 - 将元素排列成某种三角形结构，但我无法将这个想法形式化。

Edit2:请注意，我要求在每次插入后，结构中只保留相互非支配的元素。例如，如果我有一组非支配三元组 {(1,2,3), (3, 1, 1)} 并添加三元组 (3, 3, 3) 我会设置 {(3,3,3)}。

Edit3:为了更清楚地说明元素的支配地位——我们说，在这种特殊情况下，三元组 (a,b,c) 支配 ( e,f,g) 当且仅当 a >= e && b >= f && c >= g 并且至少有一个不等式是严格的 - >。

最佳答案

首先是简单的方法，这样我们就可以看到我们尝试改进和验证的内容，这个答案实际上与问题相关。

// 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)))

从一个空列表开始，然后在下一个 yield 之后添加一个三元组:

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 的立方体一端到其对角线角的 vector 。

体积较小的立方体能否支配较大的立方体？答案是不。 我们可以在一维等价物上通过类比来证明这一点。如果 x < y，x="" 不能支配="" y="" 因为要支配，它应该满足="">x >= y && X > y。

可以为二维构想类似的等价关系。这对我们的三胞胎也有同样的意义。

现在，我们缩小了搜索范围。现有集合中体积小于新三元组的那些项目可以但不必由新三元组支配。体积大于新三元组的不能被支配。

因此，一种改进的方法是:

  • 令 qset 为已排序的四元组序列，已插入。
  • 令 vt 为新三元组 t 的体积:(a,b,c)。 vt = a * b * c
  • 令 qt = (vt,a,b,c)
  • 使用二进制搜索按体积查找 qset 中的索引位置。
  • pos 左侧的所有四元组(v <>
  • pos 右边的所有 quadlets 都不能被支配，因为它们更大。
  • 所以，现在，我们只需将朴素方法应用于子集 qset[0..pos-1]。如果插入的值关于此关系是随机的，平均而言，我们只需过滤 n/2，其中 n 是 qset 的大小。
  • 将qt at pos插入qset并返回qset。

关于c++ - 用于存储帕累托最优解的高效结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36280055/

amp43codestrong的c++optimizationdata-structures

有关c++ - 用于存储帕累托最优解的高效结构的更多相关文章

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

  3. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  4. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  5. Ruby Sinatra 配置用于生产和开发 - 2

    我已经在Sinatra上创建了应用程序，它代表了一个简单的API。我想在生产和开发上进行部署。我想在部署时选择，是开发还是生产，一些方法的逻辑应该改变，这取决于部署类型。是否有任何想法，如何完成以及解决此问题的一些示例。例子:我有代码get'/api/test'doreturn"Itisdev"end但是在部署到生产环境之后我想在运行/api/test之后看到ItisPROD如何实现？ 最佳答案 根据SinatraDocumentation:EnvironmentscanbesetthroughtheRACK_ENVenvironm

  6. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  7. ruby - inverse_of 是否适用于 has_many？ - 2

    当我使用has_one时，它​​工作得很好，但在has_many上却不行。在这里您可以看到object_id不同，因为它运行了另一个SQL来再次获取它。ruby-1.9.2-p290:001>e=Employee.create(name:'rafael',active:false)ruby-1.9.2-p290:002>b=Badge.create(number:1,employee:e)ruby-1.9.2-p290:003>a=Address.create(street:"123MarketSt",city:"SanDiego",employee:e)ruby-1.9.2-p290

  8. ruby - Rack:如何将 URL 存储为变量？ - 2

    我正在编写一个简单的静态Rack应用程序。查看下面的config.ru代码:useRack::Static,:urls=>["/elements","/img","/pages","/users","/css","/js"],:root=>"archive"map'/'dorunProc.new{|env|[200,{'Content-Type'=>'text/html','Cache-Control'=>'public,max-age=6400'},File.open('archive/splash.html',File::RDONLY)]}endmap'/pages/search.

  9. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  10. ruby-on-rails - 一般建议和推荐的文件夹结构 - Sinatra - 2

    您将如何构建一个简单的Sinatra应用程序？我正在制作，我希望该应用具有以下功能:“应用程序”更像是一个包含所有信息的管理仪表板。然后另一个应用程序将通过REST访问信息。我还没有创建仪表板，只是从数据库中获取东西session和身份验证(尚未实现)您可以上传图片，其他应用可以显示这些图片我已经使用RSpec创建了一个测试文件通过Prawn生成报告目前的设置是这样的:app.rbtest_app.rb因为我实际上只有应用程序和测试文件。到目前为止，我已经将Datamapper用于ORM，将SQLite用于数据库。这是我的第一个Ruby/Sinatra项目，所以欢迎任何和所有建议-我应

随机推荐