- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
您有一组N = 400个对象,每个对象在例如19维的空间中都有自己的坐标。
您计算(欧几里得)距离矩阵(所有成对距离)。
现在,您要选择n = 50个对象,以使所选对象之间的所有成对距离之和最大。
我设计了一种通过线性编程解决此问题的方法(下面的代码为一个较小的示例),但对我来说似乎效率不高,因为我使用的是N *(N-1)/ 2个二进制变量,对应于所有非冗余距离矩阵的元素,然后有很多约束来确保解向量的自洽。
我怀疑必须有一种更简单的方法,其中仅使用N个变量,但我无法立即想到一个。
This post简要提到了一些“ Bron-Kerbosch”算法,该算法显然解决了距离和部分。
但是在该示例中,距离的总和是一个特定的数字,因此我看不到直接适用于我的情况。
我简要介绍了二次编程,但我再也看不到与我的情况直接平行的情况,尽管理论上可以使用“ b%*%bT”矩阵(其中b是(列)二进制解矢量)乘以距离矩阵等;但我真的不熟悉这种技术。
任何人都可以建议(/指向其他文章进行解释)是否以及仅使用N个二进制变量通过线性编程可以解决这种问题?
或就如何更有效地解决问题提供其他建议?
谢谢!
PS:这是我上面提到的代码。
require(Matrix)
#distmat defined manually for this example as a sparseMatrix
distmat <- sparseMatrix(i=c(rep(1,4),rep(2,3),rep(3,2),rep(4,1)),j=c(2:5,3:5,4:5,5:5),x=c(0.3,0.2,0.9,0.5,0.1,0.8,0.75,0.6,0.6,0.15))
N = 5
n = 3
distmat_summary <- summary(distmat)
distmat_summary["ID"] <- 1:NROW(distmat_summary)
i.mat <- xtabs(~i+ID,distmat_summary,sparse=T)
j.mat <- xtabs(~j+ID,distmat_summary,sparse=T)
ij.mat <- rbind(i.mat,"5"=rep(0,10))+rbind("1"=rep(0,10),j.mat)
ij.mat.rowSums <- rowSums(ij.mat)
ij.diag.mat <- .sparseDiagonal(n=length(ij.mat.rowSums),-ij.mat.rowSums)
colnames(ij.diag.mat) <- dimnames(ij.mat)[[1]]
mat <- rbind(cbind(ij.mat,ij.diag.mat),cbind(ij.mat,ij.diag.mat),c(rep(0,NCOL(ij.mat)),rep(1,NROW(ij.mat)) ))
dir <- c(rep("<=",NROW(ij.mat)),rep(">=",NROW(ij.mat)),"==")
rhs <- c(rep(0,NROW(ij.mat)),1-unname(ij.mat.rowSums),n)
obj <- xtabs(x~ID,distmat_summary)
obj <- c(obj,setNames(rep(0, NROW(ij.mat)), dimnames(ij.mat)[[1]]))
if (length(find.package(package="Rsymphony",quiet=TRUE))==0) install.packages("Rsymphony")
require(Rsymphony)
LP.sol <- Rsymphony_solve_LP(obj,mat,dir,rhs,types="B",max=TRUE)
items.sol <- (names(obj)[(1+NCOL(ij.mat)):(NCOL(ij.mat)+NROW(ij.mat))])[as.logical(LP.sol$solution[(1+NCOL(ij.mat)):(NCOL(ij.mat)+NROW(ij.mat))])]
items.sol
ID.sol <- names(obj)[1:NCOL(ij.mat)][as.logical(LP.sol$solution[1:NCOL(ij.mat)])]
as.data.frame(distmat_summary[distmat_summary$ID %in% ID.sol,])
最佳答案
该问题称为p-色散和问题。可以使用N个二进制变量来表示,但可以使用二次项。据我所知,在线性程序中不可能仅用N个二进制变量来表述它。
This paper by Pisinger给出二次公式,并讨论边界和分支定界算法。
希望这可以帮助。
关于r - 如何从一组N个对象中选择n个对象,从而最大化它们之间的成对距离之和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56761115/
给定一个包含 n 个非负整数的数组:A1、A2、...、AN。如何找到一对整数 Au, Av (1 ≤ u ans) { ans=arr[i] & arr[j
有人知道这段代码的正确解决方案吗? BOOL maximized = [myWindow isMaximized]; 最佳答案 也许看看 isZoomed 关于cocoa - NSWindow 最大化
当前有一个 MySQL 数据库,但遇到 MySQL 以 600% CPU 使用率运行的问题。 规范: 2.3 GHz Intel Xeon® E5-2686 v4 (Broadwell) 处理器或 2
我已将 Skype 配置为在 Windows 启动时最小化启动。 现在我需要通过全屏应用程序按钮中的一个按钮将 Skype 置于最前面。我有这段代码: For Each p As Proces
我已经有一段时间没有做任何生疏的程序了。我正在研究代码以最大化和最小化其他应用程序。所以我找到了一些基本的东西,这就是我所拥有的,对原来的东西稍作修改。它希望我生成一些我所做的 FindWindow
我有一个 Windows CE 应用程序,它记录移动设备的击键。有一个用于初始化录制功能的按钮,它通过调用强制主窗口最小化: ShowWindow (hWnd, SW_MINIMIZE); 在最小化窗
我想显示一个占据尽可能多屏幕空间的对话框。 所以,这是一个示例: AlertDialog dialog = new AlertDialog.Builder(ctx)......create(); Wi
对Wndows用户来说,最小化/最大化/关闭按钮放在系统窗口的右上角是肯定的。而大多数朋友都是成为Wndows用户之后才成为Ubuntu用户的,因此Ubuntu程序窗口中将这些按键放在左上角使用起来
1.Ctrl+Alt+T调出终端 2.首先安装gconf-editor: sudo apt-get install gconf-editor 会提示叫你安装 gconf-editor 安装完成
Width最大化窗口时,屏幕的属性似乎没有更新到完全最大化的宽度。如果我调整它的大小,一切正常,但在最大化时就不行。 我的代码如下: private void Window_SizeChanged(o
我正在这个 fiddle 中使用指令和 = 绑定(bind)。我收到以下错误: Uncaught Error: 10 $digest() iterations reached. Aborting! W
是否有任何快捷方式可以最大化您在 Eclipse 中使用的选项卡?假设我正在处理代码的一部分,并且我想最大化选项卡而不是使用鼠标双击它,有人知道一种方法吗? 最佳答案 CtrlM 将最大化/恢复编辑器
在 Glassdoor 评论中遇到这个问题,觉得很有趣。 Given an integer consisting of 4 digits, we need to maximize it in 24 h
在 VB6 中,我创建了一个带有一些文本框、列表框和命令按钮的表单。我使用类似 的方法设置所有这些控件的 X-Y 位置 control2.Top = form.Height * 0.50 'set
到处都有人告诉我使用这个: frame.setExtendedState(JFrame.MAXIMIZED_BOTH); 但问题是我的 JMenuBar 时断时续地消失(发生在我身上的奇怪错误),并且
我有一个 JDesktopPane 和一个 JInternalFrame。我希望 JInternalFrame 在创建后自动最大化。如何对“最大化窗口”事件进行硬编码? 最佳答案 使用JInterna
这个问题已经有答案了: JFrame doesn't take the actual screen size (2 个回答) 已关闭 3 年前。 我想最大化我的 JFrame,就像按下“关闭”旁边的按
我正在使用 vim 和 python 编程,并使用 tpope's vim-dispatch通过运行当前文件 :Dispatch python main.py 程序的打印输出被定向到quickfix窗
假设我们有一个名为 total 的 NSDecimal 常量,它包含 3.33333333 除以 10/3 的值。 10 和 3 都是NSDecimalNumber。我们希望 Swift 中的 NSD
有谁知道如何在发生特定操作后最大化 JFrame?我将在下面发布我的代码,我是一个不评论我的代码的恶魔(我会在某个时候这样做)但它应该是相当 self 解释的。我试图做的是在从菜单中选择选项后使框架最
我是一名优秀的程序员,十分优秀!