矩阵连乘问题 给定n个矩阵:A1,A2,,A,其中A与A1是 可乘的。确定一种连乘的顺序,使得矩阵连 乘的计算量为最小 设A和B分别是p×q和q×r的两个矩阵,则乘 积C=AB为p×r的矩阵,计算量为poqr次数乘。 但是对于多于2个以上的矩阵连乘,连乘的顺 序却非常重要,因为不同的顺序的总计算量 将会有很大的差别。 算法设计与分析 2算法设计与分析 2 矩阵连乘问题 ◼ 给定n个矩阵：A1 , A2 , …, An，其中Ai与Ai+1是 可乘的。确定一种连乘的顺序，使得矩阵连 乘的计算量为最小。 ◼ 设A和B分别是p×q和q×r的两个矩阵，则乘 积C=AB为p×r的矩阵，计算量为pqr次数乘。 ◼ 但是对于多于2个以上的矩阵连乘，连乘的顺 序却非常重要，因为不同的顺序的总计算量 将会有很大的差别