草庐IT

java - 我认为维基百科上的 Java 矩阵链乘法算法不正确

coder 2024-04-01 原文

我几乎可以肯定维基百科页面上 matrixChainOrder 的 Java 实现，Matrix Chain Multiplication ， 是不正确的。我会改变它，但我不是一个合格的数学家，并且在没有首先审查我的观察的情况下做出改变是不舒服的。我想我要问的是——我的说法是否正确？ k 应该改为 k + 1，因为这个版本是用基于零的索引编写的，这与在同一页面上首次引入的伪代码版本不同。

protected int[][]m;
protected int[][]s;
public void matrixChainOrder(int[] p) {
    int n = p.length - 1;
    m = new int[n][n];
    s = new int[n][n];

    for (int ii = 1; ii < n; ii++) {
        for (int i = 0; i < n - ii; i++) {
            int j = i + ii;
            m[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k + 1; // <-- this is the necessary change 
                }
            }
        }
    }
}

编辑

我快要回答我自己的问题了，但这里有一个例子可以解释将算法转换为从零开始的索引所产生的问题:

给定数组 = [3,2,4,3,2]，这些是上面生成的成本表:

m:
0   24  42  48  
0   0   24  36  
0   0   0   24  
0   0   0   0   

s:
0   0   0   0   
0   0   1   2   
0   0   0   2   
0   0   0   0

如果不将 1 加到 k(因为零索引偏移)，您会得到错误的矩阵链接位置。对于初学者，您不能将矩阵括在 0 处。 s 的正确输出应该是:

s:
0   1   1   1   
0   0   2   3   
0   0   0   3   
0   0   0   0

s[0][3] = 1 表示在 A(BCD) 处拆分 ABCD
s[1][3] = 3 表示在 A((BC)D) 处拆分 A(BCD)

就是这样 - 最优成本计算。

最佳答案

不，实现是正确的。将 s[i][j] = k; 更改为 s[i][j] = k + 1; 会破坏程序。

您可以通过将代码复制到一个名为 MatrixOrderOptimization.java 的文件并添加一个 main 函数来对此进行测试:

public static void main(String[] args) {
  MatrixOrderOptimization moo = new MatrixOrderOptimization();
  moo.matrixChainOrder(new int[]{ 3, 2, 4, 3, 2 });
  moo.printOptimalParenthesizations();
}

尝试在有或没有您建议的更改的情况下编译和运行程序。您会看到进行建议的更改会导致无效的索引值。

这是为什么？那么，解决方案值 s[i][j] 被定义为“达到最优成本的指标”。这就是它在伪代码中的名称，也是 Java 实现处理它的方式。

您指出，在伪代码中，索引从 1 开始，而在 Java 实现中，它们从 0 开始。但是，在这两种情况下，s[i][j] 的含义是实现最优成本的索引。

如果您通过添加一个来修改索引，您将放弃程序的其余部分。这样想:不是将 s[i][j] = k; 更改为 s[i][j] = k + 1;，而是更改数组在 printOptimalParenthesizations 中访问。在代码引用 s[i][j] 的每一行中，将其更改为 s[i][j]+1。

换句话说，替换

printOptimalParenthesizations(s, i, s[i][j], inAResult);
printOptimalParenthesizations(s, s[i][j] + 1, j, inAResult);

与

printOptimalParenthesizations(s, i, s[i][j]+1, inAResult);
printOptimalParenthesizations(s, s[i][j]+1 + 1, j, inAResult);

这些更改的效果与您提议的更改完全相同。在这里，当我们将其从数组中拉出时，我们将其添加到最佳索引，而您建议将其插入数组时将其添加到最佳索引。

在这两种情况下，值都会变得不正确并且程序会崩溃。那是因为s[i][j]的意义不是最优索引加一。它只是最佳索引。

Java 程序期望 s 包含最佳索引，因为它理解最佳索引，这意味着它们从零开始。如果通过加一来更改这些值，就会违反索引的含义并破坏程序。

关于java - 我认为维基百科上的 Java 矩阵链乘法算法不正确，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29665594/

维基不正codeprintOptimalParenthesizationssectionjavaalgorithmwikipediamatrix-multiplication

有关java - 我认为维基百科上的 Java 矩阵链乘法算法不正确的更多相关文章

  1. ruby-on-rails - 如果为空或不验证数值，则使属性默认为 0 - 2

    我希望我的UserPrice模型的属性在它们为空或不验证数值时默认为0。这些属性是tax_rate、shipping_cost和price。classCreateUserPrices8,:scale=>2t.decimal:tax_rate,:precision=>8,:scale=>2t.decimal:shipping_cost,:precision=>8,:scale=>2endendend起初，我将所有3列的:default=>0放在表格中，但我不想要这样，因为它已经填充了字段，我想使用占位符。这是我的UserPrice模型:classUserPrice回答before_val

  2. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  3. ruby-on-rails - date_field_tag，如何设置默认日期？ [ rails 上的 ruby ] - 2

    我想设置一个默认日期，例如实际日期，我该如何设置？还有如何在组合框中设置默认值顺便问一下，date_field_tag和date_field之间有什么区别？ 最佳答案 试试这个:将默认日期作为第二个参数传递。youcorrectlysetthedefaultvalueofcomboboxasshowninyourquestion. 关于ruby-on-rails-date_field_tag，如何设置默认日期？[rails上的ruby]，我们在StackOverflow上找到一个类似的问

  4. ruby-on-rails - openshift 上的 rails 控制台 - 2

    我将我的Rails应用程序部署到OpenShift，它运行良好，但我无法在生产服务器上运行“Rails控制台”。它给了我这个错误。我该如何解决这个问题？我尝试更新ruby​​gems，但它也给出了权限被拒绝的错误，我也无法做到。railsc错误:Warning:You'reusingRubygems1.8.24withSpring.UpgradetoatleastRubygems2.1.0andrun`gempristine--all`forbetterstartupperformance./opt/rh/ruby193/root/usr/share/rubygems/rubygems

  5. ruby-on-rails - 相关表上的范围为 "WHERE ... LIKE" - 2

    我正在尝试从Postgresql表(table1)中获取数据，该表由另一个相关表(property)的字段(table2)过滤。在纯SQL中，我会这样编写查询:SELECT*FROMtable1JOINtable2USING(table2_id)WHEREtable2.propertyLIKE'query%'这工作正常:scope:my_scope,->(query){includes(:table2).where("table2.property":query)}但我真正需要的是使用LIKE运算符进行过滤，而不是严格相等。然而，这是行不通的:scope:my_scope,->(que

  6. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  7. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  8. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  9. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  10. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

随机推荐