Ami Tavory
2020-11-28 19:27:30
假设你为每个边分配一个容量1，一次运行FF，并得到结果图。另外，将最大流量设为M'。直观地，我们发现最小割为$ M'$，这意味着在这种情况下，从a到b有M'条边不相交的路径。这告诉我们如何通过适当地缩放流量来获得⌈M / M'solution的解。例如，假设$ M = 5 $，并且将容量设置为1时，我们得到$ M'= 2 $。那么我们知道最小割为2。如果将容量增加到5/2 = 2.5，那么我们将确切地得到5的流量。由于这是非整数，因此我们会将某些边（形成从a到b的路径）的容量增加到3，再将一些容量增加到2。
你所得到的任何东西都不会比发现的东西低。如果你可以得到更低的值，例如说M''<⌈M / M'⌉，那么如果将所有边的容量设置为M''，则流程不会改变。根据最大流/最小割定理，这意味着存在M / M''> M'边的最小割。这与最小切割仅是M'相矛盾。
热门帖子
热门github
1
2
4
The Python Risk Identification Tool for generative AI (PyRIT) is an open access automation framework to empower security professionals and machine learning engineers to proactively find risks in their generative AI systems.
(翻译：用于生成式 AI 的 Python 风险识别工具 (PyRIT) 是一个开放式访问自动化框架，使安全专业人员和机器学习工程师能够主动发现其生成式 AI 系统中的风险。)
5
7
8
9
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.
(翻译：Mamba 是一种新的状态空间模型架构，在信息密集型数据（例如语言建模）上显示出良好的性能，而之前的二次模型在 Transformers 方面存在不足。它基于结构化状态空间模型的进展，并本着FlashAttention的精神进行高效的硬件感知设计和实现。)
10
11
13
不错的算法+1。用简单的语言直观地说明这个问题，按比例缩放流量的作用是什么？
我已经更新了答案，以澄清一些要点。希望这可以帮助。
@MK如果M = 10且M'= 5，则缩放比例为2，如您所述。在这种情况下，瓶颈是2。不确定您要我纠正什么。
@MK如果M = 10，并且M'= 2，则瓶颈为5，并且从a到b有2条边缘不相交的路径。如果将所有边的容量缩放为5，则每条路径给出5，总流量为10，恰好是M。