编写了一种算法来查找具有最大叶子数的生成树。编写了一种算法来找到具有最小节点数的生成树。
我还未能就以下问题提出解决办法。
对于第一部分，我想的是找到最高度的顶点，然后把它放在第二层，最后一层得到最大的叶子数。
浏览 3提问于2020-03-20得票数 0
2回答
竞赛图的控制集
、、
我正在写一个寻找锦标赛图的支配集的算法。有向图的最小生成树是否等同于图的支配集？换句话说，如果我找到了锦标赛图的最小MST (通过迭代所有的顶点)，那么我能说这等同于图的支配集吗？
浏览 2提问于2008-11-17得票数 0
回答已采纳
1回答
下面的问题似乎与顶点覆盖问题有一些相似之处。
我们有一个有向图G=(V，E)，它有维V的复顶点，并有E的复边。假设一个顶点代表一个人，从顶点A到顶点B的边代表从B到A的一条信息路径，也就是说，如果给B一条信息，那么A也有它。但是，如果另一个边从顶点C到顶点A，则信息不会到达C，除非从C到B有一个边，或者信息也直接给A。
现在的问题是，通过向(最多)k个顶点/人提供信息，我们能达到的最大顶点/人数是多少？我认为这与顶点问题密切相关，但我们只需要覆盖k个顶点，而不是全部。但是，这似乎并不完全符合另一个问题。
谁能说出一个众所周知的、结构相似的问题呢？这将帮助我更好地接近它的近似算法。
编辑:我对这
浏览 6提问于2020-04-20得票数 2
回答已采纳
1回答
我正在寻找一个算法(而不是代码)来帮助解决python中的问题。
给出了一个无向加权图，其中有若干个节点代表军事基地，假设A，B，C和D。每个节点都有一个加权边来表示从一个基地到另一个基地的距离。
一座望塔能向四面八方望去15英里。我们想把最小数量的了望塔放在基础上，使从了望塔全面覆盖。
找出最小子集的算法是什么？
浏览 8提问于2022-02-19得票数 1
回答已采纳
1回答
我们从一个字母表a1,a2,...aN中得到了一个元素E数组。假设是|N| >> |E|。
对于字母表的每个符号，我们定义了唯一的整数优先级= V(sym)。为了简单起见，让我们定义V{i} := V(symbol(ai))。
我如何才能找到优先功能五，其中：
Count(i)->MAX | V{i} < V{i+1}
换句话说，我需要找到字母表的优先级/排列，其中满足条件i的位置数V{i}<V{i+1}是最大的。
编辑-1：，请仔细阅读。给我一个数组ai，任务是生成一个函数V。这是关于使用优先级函数对输入数组排序的而不是。
编辑-2:示例
E = {a,b,c}
浏览 3提问于2011-02-10得票数 7
回答已采纳
2回答
加权无向图划分
、、、
给定一个顶点权重为W(V)的无向循环平面图G(V，E)，有一个固定平面嵌入E(G)和两个结点s和t，我需要找到G的一个划分，将它分成两个连通分支S(G)和T(G)，其中s在S(G)中，t在T(G)中。在嵌入E(G)中，顶点s和t都属于外面。
我希望这些分区能够很好地平衡--它们应该具有几乎相等的顶点权重和。
对一个好的算法有什么想法吗？
浏览 6提问于2011-02-07得票数 0
回答已采纳
1回答
给定V个顶点(城镇)和E边(城镇之间的路线)。一家公司决定建造仓库，以确保任何X镇都会有一个仓库，要么位于X，要么位于邻近的X镇。
如何找到公司必须建造的最小数量的仓库。
示例:设V=10和E=7，边缘对为：
1 2
2 4
2 5
3 6
8 6
9 7
10 7
这里的答案将是3，因为它足以在2,6,9镇建造仓库。
我的方法：
我首先计算每个城市的程度，然后在城市中放置一个最大程度的仓库。然后，我标记所有邻近城市的访问，然后转移到下一个未访问的最大节点，并放置一个仓库他们的。我是这样做的，直到没有人来看我。我的方法正确吗？请帮帮我。
浏览 2提问于2014-06-22得票数 1
回答已采纳
1回答
设G是包含圈的加权有向图。我正在寻找一种算法，通过删除循环的最小权边来查找和删除这些循环。
我想我有可能做几个DFS，但我想知道是否有更好的解决方案。
谢谢你的帮助:)
浏览 2提问于2013-03-15得票数 3
1回答
用贪婪算法求最小指数型支配集
、、、、
我开发了一个基于距离约束的图的最小独立支配集的算法。(我使用Python和NetworkX生成图形并获取对)
该算法使用了一种蛮力方法：
找出所有可能的边对
检查哪些节点满足距离约束
寻找所有可能的独立支配集
比较发现的独立支配集并找出最小支配集
对于少量的节点来说，这并没有什么区别，但是对于大量的节点来说，程序是非常慢的。
有什么办法可以让它用另一种方法跑得更快吗？
谢谢
浏览 6提问于2016-11-07得票数 1
1回答
我想开发一个分析集合的程序。我认为我能描述这个程序的最好的方式就是用一个例子。对于那些熟悉切换复盖的人来说，这就是本应用程序的目的。
我们的目标是达到100%的覆盖率。TestA强调芯片的X%，但%并不重要，重要的是芯片的哪一组管脚/部分受到强调。因此，假设TestA强调setA，TestB强调setB，依此类推，Y个测试，直到我们达到100%的覆盖率。
这就是问题所在，我们希望将Y减少到Y‘，这样Y’就是所需的最小测试量。多么?让我们假设TestA可以被消除，因为通过运行TestB，C，D，我们获得了TestA应该覆盖的集合。
我的问题是，我想在这个领域做研究(IEEE文章等)，但不知道要搜
浏览 3提问于2014-02-07得票数 1
9回答
我试图理解顶点覆盖和支配集之间的区别。
据了解，在支配集中，集合D包含与不在D中的其他顶点相邻的顶点(对于V中的每个V，要么v在D中，要么它与D中的一个相邻)。
在顶点覆盖中，D中的所有顶点都覆盖了所有的边，但是通过这样做，它们与D中的其他顶点相邻-那么为什么它不是一个支配集？
浏览 7提问于2013-01-27得票数 25
回答已采纳
1回答
我们正在为在线商店(市场)建立运输API，以便根据能够接受订单上所有项目的最优容器来计算航运价格。我们有三种类型的集装箱：
尺寸10x10x10，装船价格=50美元的自行车
尺寸为50x120x100，装船价格为150美元的货车
尺寸为300x500x1000，装船价格为350美元的大货车
市场应该提供订单中每个项目的尺寸(高度、长度和宽度)。
我需要一个算法来确定每个订单应该使用哪个容器。请注意，容器只能处理一个订单，但订单可能有多个项。
浏览 1提问于2018-02-15得票数 1
1回答
我有一组'n‘节点。函数返回两个节点之间的某种距离，这样dist(a，c)可能不是dist(a，b)+dist(b，c)。基于阈值，我通过边缘连接某些节点。我希望选择最小的节点数，这样这些节点的集合及其相邻的边缘连接就构成了整个n个节点的集合。最优的解决方案可能吗？在纸上涂鸦使我认为中心感可以帮助我(程度，亲密？)集群发生在我身上，但是这个图中的节点没有属性。如何选择节点的最小数目？提前感谢
浏览 4提问于2016-04-18得票数 2
回答已采纳
3回答
以下是问题所在。我想知道是否有明确而有效的证据：
顶点覆盖:输入无向G，整数k> 0。是否存在覆盖所有边的顶点S的子集|S|<=k？
支配集:输入无向G，整数k> 0。是否存在控制所有顶点的顶点子集S，|S|<= k？
顶点覆盖了它的关联边，并控制了它的邻居和自身。
假设VC是NPC，证明DS是NPC。
浏览 11提问于2011-03-15得票数 6
1回答
在给定的图中，我想要计算将图中的某些节点彼此断开连接的最小成本。示例：
在这个图中，假设我想通过删除这些节点之间的一些边来断开node A、node C和node F之间的连接。即通过移除edge A-B和edge F-E，将断开节点A、C和F的连接。这里的成本指的是被移除的边的长度。在此示例中，将Node A、Node C和Node F彼此断开的总最小成本为2+1=3。
有没有人能给点提示。我无法将这个问题归类，无论这是一种shortest path problem还是minimum spanning tree problem
浏览 1提问于2012-04-25得票数 6
回答已采纳
3回答
是否有算法可以找到一个无向图的生成树，使连接到多个边的顶点数最小化？
例如，给定一个4x4网格图，我们想要找到一个像左边的生成树(它有7个顶点连接到多个边)，而不是在右边的生成树(它有12)：
编辑:如果我们只考虑平面图(甚至只是网格图)，这个问题会更简单吗？
浏览 8提问于2015-07-25得票数 25
我有期末考试的复习，这道题让我特别困惑。本文给出了一个关于旅行商问题(TSP)的2倍最优逼近算法在三角不等式不成立的情况下不计算2倍最优解的例子。我试过一个三角形的例子，它的代价是1，1，10。然而，要得到哈密顿循环，所有三条边都要经过。这样，最优解将与此算法的近似解没有什么不同。我看错了吗？我希望能在这方面提供任何帮助。
浏览 1提问于2015-05-09得票数 2
回答已采纳
1回答
我正在努力寻找一种算法，它将找到资源的最优使用。
示例：
List_1有3引脚，可以放置在point_a或point_c
List_2有1引脚，可以放在point_c上。
List_3有2引脚，可以放置在point_b或point_c
List_4有2引脚，可以放置在point_a
我正在试图找到最小数量的点，我可以使用它来满足所有4列表。因此，在上面的示例中，我只需要point_a和point_c，因为point_b引脚也可以放置在point_c。
数据放在不同的列表中，但是列表没有按任何顺序排序，列表中的点也没有按任何顺序排序。
引脚是一个给定的值。所有的引脚都必须在某个时刻放置。我在尽量
浏览 3提问于2019-11-12得票数 1
回答已采纳
这是一个不同于编程面试元素的问题，并且没有解决方案。
如何计算攻击每个未覆盖的方块时可以放置的最小皇后数量？
浏览 4提问于2016-08-29得票数 4
1回答
我必须执行一项挑战，其中包括详细说明计算Pareto (集)边界的算法。声明的基本内容是：
给出了正方形0，1x0，1中n个点的集合S，给出了由S的非支配点构成的S中包含的子集P的确定算法。
本文还提出了一种实现这一目的的n*n阶点比较算法。嗯，我想出了一个算法，我在这里和那里进行研究。现在的挑战仍然是如何实现顺序n*log(n)的算法。我如何得到这些算法的顺序？
提前感谢！
#data
set.seed(103)
x = runif(200)
y = runif(200)
#algorithm
pareto = 1:length(x)
for(i in 1:length(x)){
浏览 6提问于2021-03-29得票数 1
回答已采纳
1回答
让我们说，保罗，被允许(最高机密，{A，C})的最高机密是他的许可和A&C隐私。他想获得一个机密文件(秘密，{B，C})。
最高机密高于秘密，但为了让paul“支配”文档权限，必须是pauls的一个子集。哪一个B，C不是A，C的子集。
那么，我的问题是，保罗是否必须支配这份文件，才能进入这段时间？我曾读过“支配”只提供了某种形式的传家宝。BLP模型系统的读取是允许的，所以我对这种情况有点困惑。
浏览 0提问于2018-10-09得票数 2
回答已采纳
我有X个正数，索引的x_i。每个x_i需要进入K个组中的一个(其中K是预先确定的)。假设S_j是K_j中所有x_i的总和，我需要分配所有x_i，使所有S_j的方差最小。什么算法可以做到这一点？我相信有一些算法可以解决这样的问题，但我不知道。
谢谢
浏览 10提问于2017-03-04得票数 1
回答已采纳
1回答
最小化图中的交叉边
、、、
我正在为我的一个项目使用networkx (一个python图形绘制包) 。虽然networkx相当酷，但由于交叉边的数量，显示功能有点糟糕。有没有一种方法可以最小化图中的交叉边？我的意思是一种算法，它可以以一种方式对节点进行排序，使交叉边最小化？
浏览 8提问于2011-02-21得票数 11
回答已采纳
1回答
我想开发一个类似于动画gifs的网络动画系统，比如这一个。我在固定的时间间隔捕捉一系列的截图，然后我想给它们动画。我可以微乎其微地计算从一个帧到另一个帧之间变化的像素，但是我想计算一组矩形，以便将这些矩形在前一帧上进行裁剪，得到新的矩形。在矩形数和“浪费”像素数之间有一种权衡，即存储和复制的像素数在两个帧之间没有变化。有一个很好的算法可以让我在某种形式上控制权衡参数吗？
浏览 0提问于2017-11-06得票数 2
我遇到一个我不知道如何解决的问题：
我有一组集A = {A_1, A_2, ..., A_n}和一组B集。
现在的目标是从B中删除尽可能少的元素(创建B')，这样，在删除所有1 <= i <= n的元素之后，A_i就不是B'的子集。
例如，如果我们有A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5}和B={1,2,3,4,5}，我们可以从B中删除1和2(这将产生B'={3,4,5}，它不是一个A_i的超集)。
是否有一种算法来确定要删除的元素的最小数量？
浏览 0提问于2010-05-19得票数 6
回答已采纳
1回答
要找到无向图G的最小支配集，可以使用如下贪心算法:从一个空集D开始，直到D是一个支配集，添加一个具有最大未覆盖邻居数的顶点v。
该算法一般不会找到最优解，它是一个ln(增量)-approximation。(如果增量是G中顶点的最大次数)
现在我正在寻找一个简单的例子，其中贪婪算法找不到最优解。我找到的唯一一个是集合覆盖问题的相关实例。(右侧的图片)将此图转换为图将导致至少14个顶点和大量边。
有人知道一个小例子吗？
提前感谢
浏览 6提问于2012-06-04得票数 4
回答已采纳
我有一个以网格方式相互连接的无向节点网络(即每个节点的程度是>= 2)。我试图找到一种方法来找到连接到网络中其他节点的最小节点数。
例如，如果我在图中有10个节点，其中一个节点连接到所有其他节点，那么我可以直接说，节点是连接我的所有图的节点，覆盖图的连通性的最小节点数是1。
但通常情况并非如此，因为我需要手动找到其他节点。我认为我可以使用最高度节点(例如x)作为源，使用nx.shortest_path(G, x)查找到达其他节点的最短路径。然后，我可以在最短路径上迭代以找到其他节点。但是这个方法很繁琐，我想知道是否有人会使用networkx中的工具来优化解决这个问题。
浏览 0提问于2019-03-20得票数 1
回答已采纳
1回答
我想在Java中找到最小反馈弧集的近似算法的实现，但到目前为止我还没有找到任何东西。有没有人有什么想法？
浏览 2提问于2012-11-30得票数 1
回答已采纳
1回答
在从基本块的控制流程图中获得“自然循环”之后。如何将这些循环从最内层排序到最外层？也就是说，最里面的循环不包含其他循环？
我使用支配者方法获得了循环，请参阅标题为“使用支配者识别自然循环”的幻灯片：
此外，应该使用什么算法来遍历控制流图，以便写出每个节点将产生正确的输出代码？
浏览 2提问于2014-12-05得票数 0
令我惊讶的是，我在任何地方都找不到这个问题的答案，所以我在这里问，希望了解它背后的想法将帮助我更快地了解他们的立场。
那么，为什么数字在编程dvorak上的位置是怎样的呢？
提前谢谢。
浏览 4提问于2014-02-14得票数 4
对于一些字符串片段，我希望找到包含所有片段的最短的单个字符串(“输出字符串”)。片段可以在输出字符串中相互重叠。
示例：
对于字符串片段：
BCDA
AGF
ABC
以下输出字符串包含所有片段，是由朴素追加的：
BCDAAGFABC
但是，这个输出字符串更好(更短)，因为它使用了重叠：
ABCDAGF
^
ABC
^
BCDA
^
AGF
我在寻找解决这个问题的算法。找到严格最短的输出字符串并不是绝对重要的，但越短越好。我正在寻找一种比明显的简单算法更好的算法，即尝试追加输入片段的所有排列并删除重叠(这似乎是NP-完全的)。
我已经开始研究一个解决方案，事实证明它非常有趣
浏览 0提问于2012-09-25得票数 12
回答已采纳
1回答
算法问题在这里。
我有一个包含产品权重的无序数组，例如，需要将[3, 2, 5, 5, 8]划分为较小的数组。
规则：
必需的：应该返回一个或更多个数组。
必需的：任何数组的总和都不应超过12。
必需的：返回尽可能多的数组，例如。以上示例的总权重为23，可分为两个数组。
理想的：数组应该尽可能均匀地加权。
在上面的例子中，理想的回报是[ [3, 8], [2, 5, 5] ]
我现在的想法是：
返回的数组数为(sum(input_array) / 12).ceil
一个可以工作得足够好吗？
浏览 2提问于2015-01-23得票数 2
1回答
GCC C++功率精度
、、、、
我在一次计算机竞赛中发现了一个奇怪的bug。pow(26,2)总是返回675，有时返回674？即使正确答案是676。这些类型的错误也发生在pow(26,3)，pow(26,4)等在比赛后的一些调试之后，我相信答案与int向下舍入的事实有关。有趣的是，这种错误以前从未在我身上发生过。
#include <cmath>
#include <iostream>
using namespace std;
int main() {
cout<<pow(26,2)<<endl;
cout<<int(pow(26,2))
浏览 0提问于2012-12-08得票数 12
假设我们有一个格式为1.n像素的图像(r，g，b)。
我们现在也可以选择X颜色的格式(r，g，b)来生成第二个相同大小的图像。这些X颜色中的每一种都将代表我们新图像的任意选择像素。
现在，我们计算出从原始图像到新生成的图像的平方偏差，方法是对这两幅图像上的每个像素对进行检查，并对它们的色差sqrt(sqr(R1-R2)+sqr(G1-G2)+sqr(B1-B2))进行求和。
现在假设我们分布了所有的X颜色，所以这个平方偏差之和是最小的。
，我这里的问题是：如何找到完美的X颜色，所以在完美分布之后，我们的平方偏差与其他颜色集相比是最小的？
如果有一些信息丢失或不清楚(由于我的英语不好)，请告诉我
浏览 4提问于2015-04-01得票数 0
回答已采纳
1回答
对于以下问题，有没有什么算法或相关工作？
给定2D中的一组线段，如何移动线段(水平或垂直)以消除相交，从而使整体移动最小化？可以允许在端点处相交。
浏览 0提问于2011-03-08得票数 1
我正在对一个庞大的数据集进行XGBoost分类，并显示：
Tree method is automatically selected to be 'approx' for faster speed. to use old behavior(exact greedy algorithm on single machine), set tree_method to 'exact'
我怎么才能准确地改变它呢？
我尝试过clf = xgb(tree_method='exact')，它返回了错误！
浏览 0提问于2017-07-24得票数 1
回答已采纳
1回答
我正在寻找一种近似算法来解决以下问题-我有一个未加权的无向图，有圈，并希望找到从给定节点开始的最长路径。我确实更看重速度而不是性能(所以O(n^5)算法可能是一种过度的杀伤力)。
这不是家庭作业(我发誓！)或工作相关，但我将感谢您可能有任何提示。
浏览 0提问于2010-02-08得票数 7
回答已采纳
4回答
作业-大O分析
、、
我的作业涉及大O分析，我想我已经掌握了它的诀窍，但我不是百分之百确定。你们这些可爱的人会不会介意看一眼，告诉我我是不是走对了路？
作业如下所示。对于问题1和3，我的分析和答案在//符号之后的右侧。对于问题2，我的分析和答案低于算法类型。
提前感谢您的帮助！:-)
1.For each of the following program fragments, give a Big-Oh analysis of the running time in terms of N:
(a) // Fragment (a)
for ( int i = 0, Sum = 0; i <
浏览 0提问于2012-03-13得票数 3
1回答
二维点的多列表排序算法
、、、、
我需要一个算法来排序2D平面中的多个点列表，以便每个列表中的对应点之间的距离最小。
即，对于长度相等的两个列表，第一列表的第一点到第二列表的第一点的距离最小，第一的第二点到第二列表的第二点的距离最小，依此类推。
我的第一个想法是简单地按x和y坐标的平均值排序，但我觉得这并不完全准确。
浏览 2提问于2013-03-14得票数 2
回答已采纳
1回答
LLVM中的活值
、、
假设我的CFG中有两个基本块A和B，边从A到B，我需要做以下工作：
将活动值的集合S跨越该边缘(这可能是一个过度逼近，即它可能包含不再是活动的值)
将它们映射到另一个值(S->S')
用映射值(S')替换-在B中及其后人-S中的所有值的用法
LLVM是否提供了一种简单的方法来完成第一点和第三点(因为我似乎找不到它)？如果没有，你对怎么做有什么建议吗？
注意:在LLVM邮件列表上交叉标记
浏览 0提问于2011-06-14得票数 4
2回答
我正在尝试解决一个有大约10,000个城市的非常大的TSP。为了使我的任务并行化，我想将这些城市划分为集群，并求解每个集群的TSP。
我想要一种可以将我的城市划分为集群的方法(基于城市密度/集群中每个城市之间的邻近度)。
有谁知道做这件事的有效顺序吗？
浏览 1提问于2012-12-14得票数 1
回答已采纳
1回答
我有一个客户和他们各自的销售人员之间的距离列表，我想应用TSP算法来优化每个销售人员在给定的一天中的旅行距离。在R或Python中解决这个问题的最佳方法是什么？
注:我不需要通过任何地图可视化这一点，我只需要最短的距离之间的每个客户之间的开始和结束销售人员的位置。
浏览 1提问于2019-07-02得票数 0
回答已采纳
给定图中所有节点的列表G、所有现有连接(边)的列表和所有节点的邻接列表，如何才能继续查找给定节点的支配者列表？
我想到的一种方法是：
对于给定的节点，N，找出从根节点到N的所有路径，这些路径的交集将给我一组支配N的节点，但这里的问题是，我如何真正找到路径？尤其是在用JAVA编写代码时。
任何有用的答案，特别是，将不胜感激。
谢谢!
浏览 1提问于2012-11-29得票数 2
回答已采纳
2回答
近似算法是否与多项式时间近似算法(PTAS)相同？例如，可以证明A(I) <= 2*选择(I)作为顶点覆盖。这是否意味着顶点覆盖有2-多项式时间近似算法或PTAS？
谢谢!
注意:斜体字的文本是我在发布问题后所做的编辑。
浏览 3提问于2014-04-19得票数 1
回答已采纳
2回答
我正在用X代码编写一个应用程序。它正在收集传感器数据(陀螺仪)，然后将其转换为FFTW。最后，我将在数组中得到结果。在应用程序里。我正在绘制图表，但是有那么多的山峰(见图中的红色)，我想把它平滑。
我的阵列：
double magnitude[S];
...
magnitude[i]=sqrt((fft_result[i][0])*(fft_result[i][0])+ (fft_result[i][1])*(fft_result[i][1]) );
一个示例数组(对于30个样本，通常我正在处理256个样本)："0.9261901713034604“、"
浏览 1提问于2014-07-27得票数 3
回答已采纳
由于任何NP困难问题都可以通过映射简化为任何其他NP困难问题，因此我的问题是前进一步；例如，算法的每一步:这也可以映射到其他NP困难问题吗？
提前感谢
浏览 1提问于2013-05-06得票数 1
1回答
我得到了一个无向加权连通图。如果我选择一个顶点，我会自动选择与其直接连接的所有顶点。有什么算法可以让我用最少的尝试次数来选择图中的所有顶点？在每次尝试中，我都会选择一个顶点。例如，对于邻接矩阵a={1，1，0，0，1,1,1,1,0 ,0,1,1,0,0，0，1，1，1，0，0，1，1}，我必须选择顶点2和4或顶点2和5。
浏览 3提问于2009-08-20得票数 1
回答已采纳
1回答
最小叶数的生成树
、、、、
因此，我的问题是：
我有一个无向(完全)加权图G=(V，E)，我想用最小叶数()生成所有可能的生成树()，也就是1级顶点的最小数，让我们称这类树为MIN_LEAF。
可能，我想直接在所有叶数最少的树中生成()，也就是具有最小总重量的树(请注意，这不一定是最小生成树)。判定树T是否是给定图G的MIN_LEAF的问题是完全的吗？
如果是这样的话，我想知道是否存在某种启发式算法(贪婪或局部搜索)，它至少可以给出这个问题的近似解。
提前谢谢。
浏览 7提问于2017-01-16得票数 0
回答已采纳
1回答
我正在尝试解决以下问题:我们有一些图。如何求K3完全图的(仅有个数)最大值，这些图是输入图的子图且彼此不相交。
我不需要一个代码，一个完整的解决方案。我需要一个从哪里开始的建议。我想过DFU和一些遍历，但它没有给出解决方案，至少没有一些良好的时间复杂性。
浏览 1提问于2011-03-31得票数 0
回答已采纳
2回答
查找天际线集合
、、
在讨论这个问题之前，让我先解释一些定义：
比方说点A是一个坐标(可以有两个值)，比方说(1.2,3.5,4.3,2.6)，和点B一样。
A点支配B点当且仅当1. A点中的所有坐标<= B点中的所有坐标；2. A点的一个坐标<B点的相应坐标
例如:给定
A=(2,3,4,5)
B=(2,3,4,6)
A支配B，因为条件1成立，并且对于条件2，A的第四个分量<B的第四个分量。
再举一个例子，
A=(2,3,4,5)
B=(2,3,4,5)
A不能支配B，反之亦然，因为条件2在两种情况下都不成立。
现在给出一个n维的坐标列表，我希望找到不受其他坐标支配的坐标集合，这些坐标称为天际线
浏览 5提问于2012-09-13得票数 4
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
