haskell - 在 Haskell 中解决 Google Code Jam 的 "Minimum Scalar Product"

Question

为了准备即将到来的 Google Code Jam，我已经开始着手解决一些问题。这是我尝试过的练习题之一:

http://code.google.com/codejam/contest/32016/dashboard#s=p0

这是我当前的 Haskell 解决方案的要点:

{-
- Problem URL: http://code.google.com/codejam/contest/32016/dashboard#s=p0
-
- solve takes as input a list of strings for a particular case
- and returns a string representation of its solution.
-}

import Data.List    

solve :: [String] -> String
solve input = show $ minimum options
    where (l1:l2:l3:_) = input
          n = read l1 :: Int
          v1 = parseVector l2 n
          v2 = parseVector l3 n
          pairs = [(a,b) | a <- permutations v1, b <- permutations v2]
          options = map scalar pairs

parseVector :: String -> Int -> [Int]
parseVector line n = map read $ take n $ (words line) :: [Int]

scalar :: ([Int],[Int]) -> Int
scalar (v1,v2) = sum $ zipWith (*) v1 v2

这适用于提供的示例输入，但会因内存不足错误的小输入而死。增加最大堆大小似乎无济于事，只是让它无限期地运行。

我的主要问题是如何进行优化，以便它实际上返回一个解决方案，而不是将 -O 标志传递给我已经完成的 ghc。

Answer 1

改进你的算法是最重要的。目前，您对这两个列表进行置换，总共得到 (n!)^2要检查的选项。您只需要置换其中一个列表。这不仅应该降低时间复杂度，还应该大大降低空间使用量。
并确保 minimum被严格的最小值取代(因为它应该通过优化，因为你正在获取 Int s 列表中的最小值，所以使用 -ddump-rule-firings 编译并检查“minimumInt”)。如果不是，请使用 foldl1' min而不是最小值。

我刚刚检查过:

Large dataset

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

为此，您需要一个更好的算法。 100!大约是 9.3 * 10157，在您检查 100 个元素的所有排列的可测量部分之前，宇宙将早已不复存在。您必须通过查看数据来构建求解排列。要找出解决方案的样子，请调查一些小的输入以及实现这些最小标量积的排列(看看 Cauchy-Bun'akovskiy-Schwarz 不等式也不会受到伤害)。