标签: minimization

我一直在为即将到来的编程竞赛练习,我偶然发现了一个我完全不知所措的问题.然而,我觉得这是一个我现在应该学习的概念,而不是交叉指责它永远不会出现.

基本上,它涉及棋盘上的骑士棋子.您将获得两个输入:起始位置和结束位置.目标是计算并打印骑士可以到达目标位置的最短路径.

我从来没有处理过最短路径的事情,我甚至不知道从哪里开始.我采用什么逻辑来解决这个问题？

PS如果它有任何相关性,他们希望你补充骑士的正常动作,同时允许它移动到由骑士可以做的(潜在的)八个动作所形成的方形的四个角,因为方形的中心是骑士的位置.

我有一个（可能很大的）data小非负整数的三元组列表，例如

data = [\n    (1, 0, 5),\n    (2, 4, 2),\n    (3, 2, 1),\n    (4, 3, 4),\n    (3, 3, 1),\n    (1, 2, 2),\n    (4, 0, 3),\n    (0, 3, 5),\n    (1, 5, 1),\n    (1, 5, 2),\n]\n

我想对其中的元组进行排序data，以便相邻元组（data[i]和data[i+1]）“尽可能相似”。

将两个三元组的不相似度定义为它们之间不相等的元素数量。例如

\n
• (0, 1, 2)对比(0, 1, 2)：差异0。
\n
• (0, 1, 2)对比(0, 1, 3)：差异1。
\n
• (0, 1, 2)对比(0, 2, …

我想知道如何为 scipy.optimize.minimize 选择最佳的最小化方法以及结果可能有多大不同？

我试图最小化以下表达式（求解 g）：

|a1.g.x + a2.g.x^3 - K|

我正在研究一种算法,其目标是找到一组最小的软件包来安装软件包"X".

我将用一个例子更好地解释:

X depends on A and (E or C)
A depends on E and (H or Y)
E depends on B and (Z or Y)
C depends on (A or K)
H depends on nothing
Y depends on nothing
Z depends on nothing
K depends on nothing

解决方案是安装:AEB Y.

这是一个描述示例的图像:

有没有一种算法可以在不使用蛮力方法的情况下解决问题？

我已经阅读了很多关于算法的信息,比如DFS,BFS,Dijkstra等......问题是这些算法无法处理"OR"条件.

UPDATE

我不想使用外部库.

该算法不必处理循环依赖.

UPDATE

一种可能的解决方案是计算每个顶点的所有可能路径,并且对于可能路径中的每个顶点,执行相同的操作.因此,X的可能路径是(AE),(AC).现在,对于这两个可能路径中的每个元素,我们可以做同样的事情:A =(EH),(EY)/ E =(BZ),(BY)等等......最后我们可以结合可能的SET中每个顶点的路径,并选择最小长度的路径.

你怎么看？

我正在尝试进行一些参数估计,并希望选择参数估计值,以最大限度地减少预测方程中的平方误差超过约30个变量.如果方程是线性的,我只计算30个偏导数,将它们全部设为零,并使用线性方程求解器.但不幸的是,这个等式是非线性的,它的衍生物也是如此.

如果方程式超过单个变量,我只会使用牛顿方法(也称为Newton-Raphson).Web上有丰富的示例和代码来实现Newton的单个变量函数的方法.

鉴于我有大约30个变量,如何使用牛顿方法为这个问题编写数值解？我有闭合形式的方程,可以计算一阶和二阶导数,但我不知道如何从那里开始.我在网上发现了大量的治疗方法,但很快就会进入重基质表示法.我在维基百科上找到了一些适度的帮助,但我在将其转换为代码时遇到了麻烦.

我担心崩溃的地方是矩阵代数和矩阵求逆.我可以使用线性方程求解器反转矩阵,但我担心得到正确的行和列,避免换位错误,等等.

要非常具体:

• 我想使用表将变量映射到它们的值.我可以写一个这样一个表的函数,它返回给出这样一个表作为参数的平方误差.我还可以创建相对于任何给定变量返回偏导数的函数.

• 我对表中的值有一个合理的初始估计,所以我不担心收敛.

• 我不确定如何编写使用估计的循环(每个变量的值表),函数和部分导数函数表来产生新的估计.

最后一点是我要帮助的.任何直接的帮助或指向好的来源将受到热烈的赞赏.

编辑:由于我有封闭形式的第一和第二衍生物,我想利用它们并避免更简单的融合方法,如单面搜索.

我试图找到函数的局部最小值,并且参数具有固定的总和.例如,

Fx = 10 - 5x1 + 2x2 - x3

条件如下,

x1 + x2 + x3 = 15

(x1,x2,x3)> = 0

其中x1,x2和x3的总和具有已知值,并且它们都大于零.在R中,它看起来像这样,

Fx = function(x) {10 - (5*x[1] + 2*x[2] + x[3])}
opt = optim(c(1,1,1), Fx, method = "L-BFGS-B", lower=c(0,0,0), upper=c(15,15,15))

我还尝试使用constrOptim的不等式来强制求和.我仍然认为这可能是一个看似合理的工作,但我无法使其发挥作用.这是真实问题的简化示例,但任何帮助都将非常感激.

我曾经对神经网络感兴趣,并考虑在python中使用一个轻量级项目,比较时域中的各种最小化技术(这是最快的).

然后我意识到我甚至不知道NN是否有利于最小化.你怎么看？

ProGuard配置Android应用程序的常见模式是保留自定义View类,因为它们可能只是从布局XML而不是应用程序代码引用.

在项目创建时,ADT因此将这些规则添加到项目的proguard.cfg中:

-keepclasseswithmembernames class * {
   public <init>(android.content.Context, android.util.AttributeSet);
}

-keepclasseswithmembernames class * {
   public <init>(android.content.Context, android.util.AttributeSet, int);
}

我想这里的想法是说,每当一个类定义一个可以由布局inflater调用的构造函数,然后保留它.但是,根据ProGuard文档,keepclasseswithmembernames限定符是keepclasseswithmembers和的简写allowshrinking,如果我理解正确的意思是:它允许删除这些类,但如果保留它们,不要混淆其成员名称(可能不会破坏它们之间的绑定) XML属性名称和类设置器).

但这是否意味着在缩小阶段(allowshrinking = true)仍会删除这些类,除非它们直接在代码中引用？事实上,这就是我们在我们的应用程序中使用的自定义小部件所发生的事情,我可以通过将规则设置为刚好来解决问题,keepclasseswithmembers因为这将完全保留匹配的类(值得注意的是这就是官方的ProGuard Android例子也是如此).

我误读了ProGuard文档,或者这是ADT项目向导中的错误？

我有一个函数实际上是对另一个程序的调用(一些Fortran代码).当我调用这个函数(run_moog)时,我可以解析4个变量,并返回6个值.这些值都应该接近0(为了最小化).但是,我把它们组合起来:np.sum(results**2).现在我有一个标量函数.我想最小化这个功能,即np.sum(results**2)尽可能接近零.
注意:当此函数(run_moog)接受4个输入参数时,它会为Fortran代码创建一个依赖于这些参数的输入文件.

我已经尝试了几种方法来从scipy docs中优化它.但没有一个按预期工作.最小化应该能够对4个变量进行限制.这是一个尝试:

from scipy.optimize import minimize # Tried others as well from the docs
x0 = 4435, 3.54, 0.13, 2.4
bounds = [(4000, 6000), (3.00, 4.50), (-0.1, 0.1), (0.0, None)]
a = minimize(fun_mmog, x0, bounds=bounds, method='L-BFGS-B')  # I've tried several different methods here
print a

然后这给了我

  status: 0
 success: True
    nfev: 5
     fun: 2.3194639999999964
       x: array([  4.43500000e+03,   3.54000000e+00,   1.00000000e-01,
         2.40000000e+00])
 message: 'CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL'
     jac: array([ 0., 0., …

我在用scipy.optimize.minimize从函数中找到最佳值。这是最简单的示例，使用内置 Rosenbrock 函数：

>>> from scipy.optimize import minimize, rosen\n>>> x0 = [1.3, 0.7, 0.8, 1.9, 1.2]\n>>> # Minimize returns a scipy.optimize.OptimizeResult object...\n>>> res = minimize(rosen, x0, method='Nelder-Mead') \n>>> print res\n  status: 0\n    nfev: 243\n success: True\n     fun: 6.6174817088845322e-05\n       x: array([ 0.99910115,  0.99820923,  0.99646346,  0.99297555,  0.98600385])\n message: 'Optimization terminated successfully.'\n     nit: 141\n

x只是最终的最佳输入向量。\xe2\x80\x8b我可以从返回的结果中获取所有迭代的列表（即具有相应输入向量的目标函数）scipy.optimize.OptimizeResult？