问题标签 [mathematical-optimization]

我正在将数学公式转换为程序。这个公式被称为易腐烂产品的最优定价策略。我在一篇文章中看到了这一点，它被称为 Karush-Kuhn-Tucker 条件。不知何故，我失去了所有的数学技能，无法理解其中解释的公式。我能够理解如何想出一个获得最优价格的解决方案，但我担心我可能无法解决本文中给出的条件。供您参考，我在此处提供链接。如果有人可以用简单的英语向我解释这个 Karush-Kuhn-Tucker 条件，以便我可以用编程语言来思考。我对语言不感兴趣，我准备用任何语言实现。

还给出了我在数学堆栈交换中发布的问题的链接。

有没有人遇到过这种情况？如何为这种数学公式提出程序化解决方案？

相同的维基文章在这里

如果有任何已经为这种公式开发的库，请告诉我。

我需要找到构成一定金额的硬币的最佳组合。所以本质上，我想用最少的硬币到达那里。

例如：

如果货币系统有硬币：{13, 8, 1}，贪心解决方案会将 24 的零钱变为 {13, 8, 1, 1, 1}，但真正的最优解决方案是 {8, 8, 8} .

我希望用 Javascript 编写它，但是伪代码很好，因为我确信这会帮助更多的人。

我正在研究一个我怀疑是 NP-hard 的组合优化问题，并且遗传算法在我们的数据集上运行良好。我们是一个研究小组，并计划在我们的领域（而不是数学或 CS）发表我们的结果，我想在将手稿送审之前探索 NP 难题。

有两个主要问题：

1）我想知道是否研究过这个特定的优化问题。我已经仔细搜索了点燃，但没有看到任何完全相同的东西。

2）如果这个问题还没有被研究过，我可能会尝试做一个可还原性证明，并且想要一些关于还原的良好 NP-完全候选者的指针。

这个问题可以用两种方式来描述，一个子序列变体，一个二分图问题。

在子序列风格中，我想找到一个允许排列的“宽松”子序列，并优化以最小化排列计数。例如： (. = 任何其他字符)

查询：abc，目标：..babc，结果：abc（正常子序列）

查询：abc，目标：..baca，结果：bac（一个排列的子序列）

二分公式是一个匹配问题或线性分配问题，将图划分为查询字符节点和目标字符节点。边将查询字符连接到目标字符，使得从每个查询字符到目标字符只有一条边。目标函数是最小化边缘交叉的数量（在 lit 中也称为“交叉数”）。这类似于重新排序节点放置以最小化边缘交叉的二分图布局算法，但我的问题要求两个节点顺序保持固定。

专家对问题 1 或 2 有何想法？

提前致谢！

在 3D Max Studios 中，我记得有一个函数（我不记得函数的名称，抱歉）将 3D 模型一分为二。例如，您创建一个球体，然后在中间切割它，留下 2 个半球体。那么，人体呢？想象一个武士在腹部切开敌人，现在敌人的模型将变成2个模型：一个是从头到胃的上半部分，另一个是从胃到脚的下半部分。此外，为了防止玩家看到切割模型内部，还必须在两个模型中放置一个额外的多边形。（最好在这个多边形中添加血液纹理，给人一种这是体内血液的印象）对不起，如果我的解释很糟糕，你明白我想说什么吗？

在 3D Max Studios 中，我们可以做到以上。现在，在 3D 编程方面，如果我想实现这样的目标，我该怎么做？当然，一种便宜的方法是预先制作切割模型，但这并不现实。

我正在寻找一种将模型实时切割成两部分的方法。这可能吗？

我正在检查 R 中的简单移动平均交叉策略。我不想在 2 维参数空间（短期移动平均线的长度，长期移动平均线的长度）上运行巨大的模拟，而是想实现粒子群寻找最优参数值的优化算法。我一直在浏览网页并且读到这个算法非常有效。此外，算法的工作方式让我着迷......

你们中有人有在 R 中实现这个算法的经验吗？有没有有用的包可以使用？

非常感谢您的评论。

马丁

假设我在 NumPy 中有一个包含连续可微函数评估的数组，我想找到局部最小值。没有噪音，所以每个点的值都低于其所有邻居的值，都符合我的局部最小值标准。

我有以下列表理解，它适用于二维数组，忽略边界上的潜在最小值：

但是，这很慢。我也想让它适用于任意数量的维度。例如，有没有一种简单的方法可以在任意维度的数组中获取一个点的所有邻居？还是我完全以错误的方式解决了这个问题？我应该numpy.gradient()改用吗？

是否有可靠且有据可查的 Python 库，该库可以快速实现算法，在有向图中找到最大流和最小割？

来自python-graph的pygraph.algorithms.minmax.maximum_flow解决了这个问题，但它非常缓慢：在具有 4000 个节点和 11000 个边的有向图中找到最大流和最小切割需要 > 1 分钟。我正在寻找至少快一个数量级的东西。

赏金：我在这个问题上提供赏金，看看自提出这个问题以来情况是否发生了变化。如果您对推荐的图书馆有个人经验，则可以加分！

我有以下问题要解决，也许您可​​以就解决问题的方法给我一些想法：

有：

• 8间教室
• 16名教师
• 201名学生
• 149位家长
• 241 次预约（大多数家长需要见多位老师，要么是因为有不止一个孩子，要么是因为一个孩子由两个或更多老师教）

• 2天。

• 对于每一天：

  • 7 间教室每天 20 小时。
  • 每天有 1 间教室可供使用 10 小时。

• 每位教师占用一间教室

• 每次约会持续一小时

进一步的限制： - 对于每位家长，所有约会必须按顺序进行（最多暂停 1 小时） - 每位家长只能访问学校一天。- 对于每位教师，一天内的所有约会都必须是连续的（最多暂停 2 小时） - 在 16 名教师中，3 名只能在两天中出席。

我正在尝试找到一种方法来生成约会时间表，显然在满足所有要求之前不必计算所有可能的变化。有任何想法吗？

我最近遇到了以下问题。给定一个包含整数条目的向量列表（这里我的意思是元组），是否有一个包（语言不是太大的问题，越快越好，所以我猜是 C）可以非常快速地确定另一个整数向量何时在原始列表的跨度？我需要对整数进行此算术运算（无除法）。我敢肯定有一个，但想绕过冗长的文献回顾。

我有兴趣有效地跟踪整数格上的大盒子的质心，从该格子中反复雕刻出正交形状的区域。我一直在研究计算几何文献，并且有多种可能相关的数据结构，但大部分讨论都是关于可见性计算（用于计算机图形学）或最近邻查找（用于数据挖掘等）。

论文 http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf，即：

讨论了一个通过“二元空间划分树”表示几何对象的系统，支持集合操作，并且有趣地提到（没有细节）在集合操作之后重新计算对象的质心。也许我有一个盲点，但是在树合并算法期间如何有效地更新质心对我来说并不是很明显，而且我还没有在引用 Naylor 的论文中找到关于质心计算的讨论。任何指针？