1回答
我有一个这样的组合问题：
给你N个测试者。
每个测试仪都是M种不同类型中的一种。
可以将每个测试仪配置为使用P个不同配置中的一个。。
你有很多产品要测试，
每个产品只能在特定类型的测试仪上进行测试。
每个产品只能由配置了特定配置的测试仪进行测试。某些配置可以应用于多个产品。任何测试人员都可以在生产过程中更改其配置，但每次更改测试人员配置都会产生额外的时间U。每个批次都有一个确定其测试时间Q的批量大小。
现在我需要提出一个批量调度算法，以便完成所有批量测试的时间是最少的。
解决这类问题的最佳方法是什么？
浏览 0提问于2010-07-27得票数 5
回答已采纳
当我有一个具有最优子结构的问题，并且没有子问题共享子问题时，我可以使用分而治之的算法来解决它？
但是当子问题共享子问题(重叠子问题)时，我可以使用动态编程来解决问题吗？
这是正确的吗？
贪婪算法与动态编程有何相似之处？
浏览 3提问于2011-05-28得票数 9
回答已采纳
1回答
作业调度变体
、、
我正在尝试解决间隔调度问题的一个变体:给定一组n个作业，每个作业需要1个处理单元才能完成，并且每个作业都有一个可用的间隔(可以执行的开始时间和结束时间)，找出可以调度的最大作业数。
我尝试的解决方案是对作业进行排序，并始终选择可用性结束时间最早的作业，同时在每次迭代后删除不可用的作业。
while jobs are not empty:
remove jobs that are not available
find the job with earliest end_availability_time
execute the job
我使用优先级队列，在该队列中，我在开
浏览 4提问于2020-02-19得票数 0
3回答
给出了列表l= x_1，...，x_n。列表中的每个元素都是一块木头的长度。要粘合两块木头，长度a和b，你需要胶水的最大值(a，b)。在粘合之后，你得到一块长度为a+b的木头。计算胶水的最小用量来粘合所有的木块。
你认为贪婪算法在这里行得通吗？我想不出任何例子。说贪婪算法我的意思是:取两个最小长度的片段，将它们粘合在一起，直到所有的片段都粘合在一起。使用一些优先级队列，这可以在O(n log n)复杂度内完成。
这行得通吗？如果没有，请给我一些列表l的例子，它可以粘合在比贪婪算法所说的更少的胶水中。
浏览 4提问于2016-01-13得票数 3
我正在为即将到来的测试复习一下，想知道是否有人可以重复一下问题的b部分。这是发出去的复习表中的文本，但我不确定b部分到底在问什么。我猜更严格地说，什么是“产生一个不到0/1背包问题最优解的1%的解”。
a)解决背包问题的以下实例，即，给出所选每个对象的分数和最优背包的值。显示步骤：
背包容量C= 100
**在这里他列出了对象、它们的值和权重。在表中**
b) 10pt给出了一个具有两个对象的示例，表明用于分数背包问题的相同贪婪方法(略有修改，如果不适合，则去掉贪婪方法选择的最后一个对象)产生的解小于0/1背包问题的最优解的1%。
浏览 1提问于2012-11-26得票数 0
如何证明针对问题的动态规划(dp)策略是否有效？对于贪婪算法，我们可以通过证明子问题具有拟阵性质来证明。对于dp算法，有这样的方法吗？
浏览 0提问于2012-03-18得票数 4
2回答
谦卑，第14课，任务TieRopes ()。简单地说，问题是将正整数的列表A划分为(连续的)子列表的最大数目，该子列表至少有和K。
我只是想出了一个贪婪的解决方案，因为这就是教训的名称。它通过了所有的测试，但我不知道为什么它是一个最优的解决方案(如果它是最优的)。
int solution(int K, vector<int> &A) {
int sum = 0, count = 0;
for (int a : A)
{
sum += a;
if (sum >= K)
{
浏览 2提问于2014-10-08得票数 8
回答已采纳
2回答
如果用动态规划方法求解旅行商问题，它能给出比贪婪方法更好的可行解吗？
我知道，在最优解方面，贪婪算法被用来求解TSP，但是当顶点数(即城市)非常大时，它变得更加复杂，并且需要指数时间。
那么，到底哪种方法会更好呢？
浏览 2提问于2019-02-05得票数 1
我有一个矩阵，行是对象，列是目标，每一行代表一个对象到一个目标的距离。
例如，假设我有3个objects O1 O2 O3和3个objects，OA，OB，OC，矩阵如下所示
| OA OB OC
-------------
O1 | 2 4 6
O2 | 1 2 8
O3 | 3 5 3
我只是用随机数据填充了它，这可能没有意义，但它可能对问题有用。
我期望的输出是: O2-OA，O1-OB和O3-OC
因此，尽管OA是O1的持有者目标，但由于OA已经被OA使用，因此它将转到下一个目标。
浏览 0提问于2013-06-07得票数 2
2回答
假设我有256张图像，平均大小为70x150 (因此，如果大小可变)。我有一个Graphic-instance (从具有给定大小的BufferedImage创建)，我想在上面绘制图像。但我想把它们画在尽可能低的曲面上。所以，不是简单地在网格中，而是在彼此之间真正感到困惑。但是！：它们不能相互重叠。
也许这是只有人脑才能处理的事情。
我想，这是值得一问的……
提前谢谢你，
马提金
例如：
+------++------+
| || |
| img1 || img2 |
| |+------+
| |+-----------------+
+------+|
浏览 0提问于2010-12-14得票数 2
一个完整的算法是一个算法，如果有一个解决方案，如果有。最优算法是一种算法，它的任何解的返回都是最优的，换句话说，没有比返回的解更好的解。
这意味着最优性是建立在完全性的基础上的，对吧？这意味着一个算法不可能是最优的，而是不完整的。还是我搞错了？
浏览 1提问于2018-02-16得票数 1
回答已采纳
1回答
在上，贪婪算法仅适用于具有最优子结构的问题。
问题：
什么是最优/非最优子结构？
什么是局部和全球最优？
如何证明贪婪算法产生全局最优解？
浏览 5提问于2013-11-11得票数 8
回答已采纳
1回答
这个问题涉及到动态规划，特别是CLRS Pg 362中的杆切问题。
整体最优解包含两个相关子问题的最优解。
总最优解是通过寻找单个子问题的最优解，然后以某种方式得到的。我无法理解直觉和概念。有联系吗举个例子？
谢谢
浏览 5提问于2012-10-24得票数 2
根据的说法，当图是树时，Hu的算法是最优的。对于一般单位长度的边缘DAG，它会失败吗？在这种情况下它不是最优的原因是什么？有这样的失败的例子吗？
浏览 3提问于2019-09-17得票数 0
1回答
假设我们在一条长街的一侧有一组房屋，由配电箱供电，配电箱可以将房屋连接到距离d。我们需要使用最小数量的配电箱。演示如何定位配电箱。
浏览 0提问于2015-11-15得票数 0
1回答
那么，我们有一个贪婪的算法来调度作业(调度最大的作业数)。我们可以使用不同的技术
最短工作优先
最早开始时间
冲突最小的作业
最早结束时间
我有前三种策略的反例，但我找不到第四种策略的反例。
以下是前三种方法的反例
最短工作优先:
在这里，我们可以安排两个任务，而不是一个更短的工作。
最早启动时间:
在这里，我们可以安排6个较小的任务，而不是一个较早开始的任务。
冲突最小的作业:
这里我们可以调度冲突3,4,4,3的4个作业，而不是最小冲突的3个作业，即2,3,3
那么，最后一个最早结束时间第一个的反示例是什么--我找不到它的反示例。所以，它总是给
浏览 4提问于2016-08-31得票数 3
回答已采纳
1回答
是否有任何广义规则来决定是否将贪婪算法应用于一个问题的最优解？例如，一些流行的算法问题，如“硬币变化”问题和“旅行推销员”问题，都不能从贪婪的角度进行优化。
浏览 0提问于2017-02-19得票数 0
2回答
我必须通过归纳法来证明
如果w< w_i，则Opt(i，w) = Opt(i-1，w)，否则Opt(i，w) = max{ Opt(i-1，w)，Opt( i-1，w- w_i) + w_i) }
产生背包问题的最优解(动态规划方法)
我知道数学归纳法是如何工作的，但在这个练习中我被困在了如何做到这一点上。尤其是归纳步骤。作为基本情况，我想，我只有一个元素，只要这个元素的重量小于或等于我背包的容量，我就接受它。否则我就丢下它。
任何帮助都将不胜感激！谢谢
浏览 16提问于2019-07-09得票数 0
1回答
小偷可以选择要偷窃的n对象，但只有一个背包，背包可以承载M重量。每个object I都有weight w_i和profit p_i。假设他还知道以下内容:这些项按权重递增排序时的顺序与按值递减排序时的顺序相同。给出一个贪心算法来寻找背包问题的最优解。证明正确性和运行时间。
所以我提出的贪婪算法是根据增加的权重对项目进行排序，这也是递减的值。这意味着每个重量的价格是按递减顺序排列的。所以窃贼可以拿走价值最高的物品，直到重量>= M。运行时间应该是O(n log n)，因为排序需要O(n log n)，而遍历列表需要O(n)。我坚持的部分是正确性的证明。到目前为止，我的证据如下：
假设有一个
浏览 1提问于2020-10-09得票数 1
1回答
多项式中的实权背包
、、、
在讲座中，我们考虑了背包问题:有n个项目具有正权值w1，。。。、wn和values v1，.。。问题的可行解是项目的子集，使得它们的总重量不超过W，目的是求出一个最大可能总价值的可行解。对于所有权值均为正整数的情况，我们讨论了求解背包问题的动态规划解。
假设所有项目的值都是正整数，而不是权值。项目的权重可以是任意正整数。描述一个解决背包问题的动态规划算法，如果所有的值都是正整数。
想法-舍入值，但这只是一个近似，对吧？这只有当我们有有限的十进制空间时才能工作..。
还有别的办法吗？
接下来的问题让我更加困惑：
b)您的算法运行时间是多少？证明你的答案是正确的。
( c)背包
浏览 0提问于2019-08-24得票数 0
回答已采纳
2回答
隐图上令人惊叹的算法族
、、、
根据定义，动态编程几乎是在隐式dag上找到最短/最长路径。每个DP算法都是这样做的。
可以松散地描述为在隐式平面图中计算完美匹配的东西。
所以，我的问题是:有没有其他的算法家族在隐式图上使用众所周知的算法来实现相当大的加速比？
浏览 0提问于2010-04-22得票数 3
回答已采纳
2回答
我读到了一些几何路由算法，它说当在主算法的一个版本中使用启发式算法时，它可能会提高性能，但会失去渐近最优性。
为什么会这样呢？我们应该更喜欢渐近最优性而不是更好的性能吗？有没有一个人应该倾向于渐近最优的典型情况？是否有已知的基准？
浏览 1提问于2013-07-15得票数 0
回答已采纳
cytoscape.js dagre布局工作得非常好。
然而，对于特定的图形，并没有单一稳定的布局。布局算法似乎使用了一些随机数生成器来计算节点位置。当相同的图形有时在屏幕上以不同的方式呈现时，这会导致恼人的情况。
有什么简单的方法可以解决这个问题吗？通常可以将随机种子值设置为某个用户定义的数字。我在cytoscape.js文档中找不到关于如何做到这一点的建议。
浏览 5提问于2018-10-24得票数 0
2回答
带顶N解的遗传算法
、、、
基本上，我需要使用Java (得分最高的解)找到遗传算法的顶级N个解决方案。我正在使用Jenetics库作为遗传算法，但我无法找到如何在不侵入库源代码的情况下获得这些结果。
如果有人知道一个更好的库有好的文档/示例，我可以使用另一个库。
浏览 3提问于2014-10-08得票数 0
回答已采纳
我正在寻找一个具有已知完美解的完整图上的欧几里得TSP问题(多个点中的最短路径)的实例。有没有人遇到过这样的例子？或者有没有一个简单的算法来生成这样的实例，这样肯定不会有比生成的更短的路径？
浏览 0提问于2013-01-20得票数 0
回答已采纳
1回答
日安，
背包算法在我的脑海中并不完全是“点击”。我知道如何回答不同种类(0-1背包，带香料背包等)的背包问题，但我并不完全理解算法本身，我很想填补这个空白。
为了使我的问题不那么含糊不清，我把我的问题分解成几个子问题。这也是我对背包问题的典型答案，
构造X维矩阵(其中X是需要关注的许多变量)。从点0 {0,0，...0}出发，计算相邻节点，然后根据得到的结果，得到矩阵中的下一个对角线点，得到最优解。重复，直到算法中所有考虑的选项都被删除为止。
，我们如何知道背包算法的工作原理(除了经验观察)？特别是，我们如何确切地知道没有可选配置被认为是s.t。使用“X维矩阵”的在内存使用上看起来非常冗余，
浏览 1提问于2019-10-25得票数 0
回答已采纳
最近我一直在研究一些贪婪的算法问题。我对局部最优感到困惑。如你所知，贪婪算法是由局部最优选择组成的。但是组合局部最优决策并不一定意味着全局最优，对吧？
以找零为例:用最少的硬币制造15美分，如果我们有10美分，5美分和1美分的硬币，那么你可以用一个10美分和一个5美分来实现这一点。但如果我们添加一个12美分的硬币，贪婪算法就会失败，因为(1×12+3×1)使用的硬币比(1×10+1×5)多。
考虑一些经典的贪婪算法，例如Huffman，Dijkstra。在我看来，这些算法是成功的，因为它们没有退化的情况，这意味着局部最优步骤的组合总是等于全局最优。我没理解错吧？
如果我的理解是正确的，有没有一
浏览 5提问于2011-06-29得票数 9
回答已采纳
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
2回答
我读到了一个贪婪问题的两个性质，我试图理解两者之间的区别:-
最优子结构性质:最优整体解包含其所有子问题的最优解。
贪婪选择性质:贪婪地选择局部最优选择可以得到全局最优解。
这两个不是等价物吗？这两者似乎是一回事，你能给我一个例子吗，最优的子结构是满意的，但贪婪的选择不是？并举例说明当满足贪婪选择而不满足最优子结构时？
浏览 3提问于2014-10-18得票数 2
回答已采纳
1回答
我有一个逻辑问题，因此从两个解释中选择：
数学：，在2-14个节点上有一个无向加权完全图.节点总是成对出现(起始点到端点)。为此，我已经有了最小生成树，它认为对起始点总是在他的端点之前。现在，我想添加另一对节点。
真实生活的解释：我已经有了一条适合1-7人的最佳出租车路线。每个连接(起始点)和离开(端点)在不同的地方。现在，当我把另一个人加到出租车上时，我想找出最佳路线。我已经有了从数据库中的每个点到每个点的计算子路径(因此这是一个加权图)。所有计算的路径都是实值，而不是启发式。
现在，我试图找到解决这一问题的最有效的解决方案。我现在的想法是：
找到离新起点最近的点。在这一点之前
浏览 3提问于2014-01-15得票数 1
假设有n个球，每个球的重量最多为1。我们可以假设这些球的权重放在一个数组W1中。n与0 <= Wi <= 1对应所有的i。问题是把这些球放在最少的盒子中，使每个盒子中不包含两个球，每个盒子里的球的总重量是<= 1。
我将为此设计一种高效的贪婪算法。我认为一个明显的选择(首先选择最大的选择和最小的第二选择)是不正确的。但是，如果我首先选择了最大的可用球，然后是第二位的最大的剩余球，那该怎么办？我认为这是对的，但我不知道如何证明这一点。这样做会产生一个简单的O(n^2)算法。
这似乎也是背包问题上的某种变体，但贪婪算法并不是最优的。
浏览 2提问于2020-11-02得票数 2
回答已采纳
1回答
A*算法中的星星是什么意思？
、、、、
我确信，(星形)在A*算法中意味着该算法是可接受的，也就是说，如果存在该路径(当所使用的启发式是乐观的)，则保证该算法在图中找到最短路径。
我说的对吗？我没有成功地寻找任何关于这个主题的信息，但我找不到任何参考。希望这个社区中大多数有经验的用户比我更了解A*的历史。
顺便说一下，我认为其他算法如IDA*，D*，SMA*，MOA*，NAMOA*，.它基于A*遵循相同的名称约定。
浏览 2提问于2016-03-05得票数 4
回答已采纳
我读了的文章，它建议(第1025页最后一段)有一个多项式时间算法来寻找一个k-tsp问题的最优使用二进制搜索。使用二进制搜索将意味着有一个算法，以检查是否存在一个解决方案与cost<X，该算法用于二进制搜索。我搜索了一下这个算法，唯一能找到的算法是非确定性算法(这非常微不足道)，但很明显，我正在寻找一个确定性算法。
我对此感兴趣是为了学习，
如有任何帮助/链接，将不胜感激。
编辑
我指的是寻找最优解的价值，而不是寻找最优解本身。
浏览 6提问于2011-12-22得票数 1
回答已采纳
3回答
我想知道是否有一种很好的方法(最好使用JuMP)来获得线性规划的所有最优解(万一有多个最优解)。
一个例子
最小化两个概率分布之间的统计距离(Kolmogorov距离)。
min sum_{i=1}^{4} |P[i] - Q[i]| over free variable Q
P = [0.25,0.25,0.25,0.25]
sum_i P[i] = 1
Q[1] + Q[4] = 1
sum_i Q[i] = 1 -> Q[2],Q[3] = 0
注意，我们可以将优化描述为一个线性规划，目标变成
min S >= sum_i S[i]
S[i] >= P[i]-Q[i]
浏览 3提问于2016-04-02得票数 7
回答已采纳
3回答
C#有序组合算法
、、、
我正在尝试开发一个c#应用程序，它将在一定的限制和成本范围内生成所有可能的排列列表。例如，我有一个包含80个工作的列表。每个作业都有一个值(1-5) (通常是3)，每个工程师都有他们能做的数量限制，通常值是20。
目前，我已经开始生成所有可能组合的列表(n！/ (k！* (n-k)！其中n是作业的总数，k是2)。每个作业之间的链接应该用每个作业之间的距离进行加权。
从这里，我想挑选一个初始的开始作业，并生成一个列表，列出所有可能的作业组合(从开始作业开始)，直到限制为20，然后按权重的总和排序。权重最低的路由将获胜，并被分配给工程师。我的问题是，我不知道如何处理这个问题--什么样的数据结构最好
浏览 0提问于2010-09-15得票数 6
1回答
我正在实现来自的优化算法。
我有点困在第2.3章:线性规划的核化。
这种技术的思想(在ILP公式中)是将权重X_u \in \left\{ 0,1 \right\}分配给输入图G=\left\( V,E \right\)的每个顶点u (也称为v)，以满足以下约束：
最小化权重\Sigma_uX_u之和
当X_u + X_v \geq 1通过图中的一个边连接时，满足\left\{ u,v \right \}。
因此，作为输出，我得到一组顶点，其X_v为1，其余顶点的X_v为0。本文认为这种弛豫是基于用X_u \in \left \{ 0,1 \right \}代替X_u \ge
浏览 8提问于2014-07-20得票数 0
回答已采纳
2回答
AI -启发式函数要求
、、、、
关于人工智能(AI)中的Huristic函数，我有一个问题。我知道我们应该寻找单调和可接受的启发式函数。
我有两个问题：
为什么要求函数为admissible?What是单调启发式函数的优点？
谢谢!
浏览 2提问于2012-02-09得票数 3
回答已采纳
我的机器学习教科书提出了这个问题，讨论了感知器算法，但我真的想不出一个令人满意的答案。
有哪些案例？
浏览 1提问于2012-09-29得票数 0
大多数时候，令人困惑的事实是，是进行详尽的搜索(动态编程、回溯或暴力)来解决问题，还是采用贪婪的方法。
我不是在说使用贪婪来确定最佳可能的解决方案，我是在说使用贪婪算法来找到“解决方案”。我正在尝试一些标准的方法来验证这个问题是否可以用贪婪的方法来解决。比如最优化的子结构，动态规划的记忆。并且不涉及任何特定的问题。
是否有任何归纳的证据可以决定贪婪的方法是否总是能产生最好的解决方案？
浏览 3提问于2012-07-17得票数 11
回答已采纳
1回答
这个问题可能很简单，但是我想问关于statsmodel结果的问题。
根据参考资料，我们可以从
print(gamma_results.summary())
Generalized Linear Model Regression Results
==============================================================================
Dep. Variable: YES No. Observations:
浏览 4提问于2022-08-23得票数 1
回答已采纳
2回答
最优子结构
、、、
我试图更全面地了解最优子结构特性在动态规划中的应用，但我忽略了为什么我们必须证明问题的任何最优解都包含子问题的最优解。
如果证明问题的某些最优解具有这个性质，然后用它来论证我们的递归算法所建立的解至少和最优解一样好，那么它本身就会是最优的，这还不够吗？换句话说，在我们的算法的正确性论证中，我们需要所有的最优解都包含子问题的最优解。
澄清：
CLRS对最优子结构的定义指出，“如果问题的任何最优解都包含子问题的最优解，那么问题就表现出最优子结构”。
为什么说“如果问题的最优解中包含子问题的最优解”这一说法是不够的呢？
浏览 8提问于2014-02-27得票数 5
回答已采纳
假设我有10个数字的列表如下
lst = [1, 3, 6, 10, 15, 20, 27, 28, 30, 40]
我想得到一个子集的k数，其中每一对数字至少是不同的距离d。现在我使用的是itertools.combinations，代码在小列表中运行得很好。
from itertools import combinations
def k_subset_at_least_d_apart(nums, k, d):
for subset in combinations(nums, k):
a = sorted(subset)
if min([t - s
浏览 2提问于2021-09-18得票数 1
回答已采纳
这是计算给定数量变化的代码:然而，它并不是为了给出硬币的最小数目而写的，但是代码似乎给出了所需的最小硬币数。我想要一个没有给出最低限度的硬币要求的案例。
def change(amount):
money = ()
for coin in [25,10,5,1]:
num = amount/coin
money += (coin,) * num
amount -= coin * num
return money
print change(59)
output is:
(25, 25, 5, 1, 1, 1, 1)
浏览 1提问于2013-11-03得票数 1
回答已采纳
1回答
对于任何一个贪婪的方法不能给出最优值的问题，我们可以找到一个反例来证明这种方法。
然而，是否有可能证明，对于一个给定的问题，任何贪婪的方法在一般情况下是行不通的。
浏览 0提问于2014-11-25得票数 3
回答已采纳
1回答
进程分配算法
、、
我读了一些关于算法的材料，遇到了一个问题。
我们有n个进程，每个进程都有一个预定的开始和结束时间。我们希望使用最小数量的处理器来运行所有这些进程。
考虑以下算法：
在步骤一中，选择不重叠的当前未分配进程的最大数量，并将它们分配给处理器i。
当没有进程仍未分配时，此算法将完成。最大I是该算法的输出。如果这个算法不产生最优解，那么n的最小值是多少？
简短的回答: n=5。不过，我不知道这个答案是如何达到的。你能解释一下吗？
浏览 4提问于2014-10-17得票数 1
更新
求出全局极小值，绘图结果表明该函数具有多个局部极小值。
f[x_] = 0.5 x^2 + Cos[Pi x] 2 Sin[Pi x] + Cos[Pi x] + 2 Sin[Pi x];
plt1 = Plot[f[x], {x, -5, 5}, PlotStyle -> RGBColor[1, 0, 0],Frame -> True]
根据论文()，我将实现SA算法，但性能非常慢。
fTmp = fBest = xBest = xTmp = 999.0;
k = 0;
LIMIT = 10^6;
tTmp = tInit = 300;
Alpha = 0.99999999
浏览 1提问于2016-04-28得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
