algorithm – 矩阵的k个连通元素的最大和

栏目: 编程工具 · 发布时间: 5年前

内容简介:翻译自:https://stackoverflow.com/questions/32824002/maximum-sum-of-k-connected-elements-of-a-matrix

给定具有正整数值和整数K的网格.K连通元素的最大总和是多少?

以下是K值为6的5×5矩阵的示例.

algorithm – 矩阵的k个连通元素的最大和

有人可以帮我识别这个问题吗?我该如何开始解决它?

我知道的唯一方法是对该矩阵的每个单元格进行深度优先搜索.但我认为这不是最好的方法.

不允许重复细胞.

Connected here means only that a cell is adjacent to the other horizontally or vertically

我想你可以蜿蜒前行,随时随地记忆.我使用镜像位集来表示记忆路径,这样它们就可以从构造的任何方向立即识别出来.这是 Python 中的一个版本(哈希长度包括从1到6的路径的计数):

from sets import Set

def f(a,k):
  stack = []
  hash = Set([])
  best = (0,0) # sum, path
  n = len(a)

  for y in range(n):
    for x in range(n):
      stack.append((1 << (n * y + x),y,x,a[y][x],1))

  while len(stack) > 0:
    (path,y,x,s,l) = stack.pop()

    if l == k and path not in hash:
      hash.add(path)
      if s > best[0]:
        best = (s,path)
    elif path not in hash:
      hash.add(path)
      if y < n - 1:
        stack.append((path | (1 << (n * (y + 1) + x)),y + 1,x,s + a[y + 1][x],l + 1))
      if y > 0:
        stack.append((path | (1 << (n * (y - 1) + x)),y - 1,x,s + a[y - 1][x],l + 1))
      if x < n - 1:
        stack.append((path | (1 << (n * y + x + 1)),y,x + 1,s + a[y][x + 1],l + 1))
      if x > 0:
        stack.append((path | (1 << (n * y + x - 1)),y,x - 1,s + a[y][x - 1],l + 1))

  print best
  print len(hash)

输出:

arr = [[31,12,7,1,14]
      ,[23,98,3,87,1]
      ,[5,31,8,2,99]
      ,[12,3,42,17,88]
      ,[120,2,7,5,7]]

f(arr,6) 

""" 
(377, 549312) sum, path
1042 hash length
549312 = 00000
         01110
         11000
         10000 
"""

更新:这个问题类似于这个问题, Whats the fastest way to find biggest sum of M adjacent elements in a matrix ,我意识到我的建议需要修改,以包括从形状的中间部分延伸的构造.这是我修改后的代码,使用集合来散列形状.在我看来,DFS应该保持堆栈大小为O(m)的顺序(尽管搜索空间仍然很大).

from sets import Set

def f(a,m):
  stack = []
  hash = Set([])
  best = (0,[]) # sum, shape
  n = len(a)

  for y in range(n):
    for x in range(n):
      stack.append((a[y][x],Set([(y,x)]),1))

  while len(stack) > 0:
    s,shape,l = stack.pop()

    key = str(sorted(list(shape)))

    if l == m and key not in hash:
      hash.add(key)
      if s > best[0]:
        best = (s,shape)
    elif key not in hash:
      hash.add(key)
      for (y,x) in shape:
        if y < n - 1 and (y + 1,x) not in shape:
          copy = Set(shape)
          copy.add((y + 1,x))
          stack.append((s + a[y + 1][x],copy,l + 1))
        if y > 0 and (y - 1,x) not in shape:
          copy = Set(shape)
          copy.add((y - 1,x))
          stack.append((s + a[y - 1][x],copy,l + 1))
        if x < n - 1 and (y,x + 1) not in shape:
          copy = Set(shape)
          copy.add((y,x + 1))
          stack.append((s + a[y][x + 1],copy,l + 1))
        if x > 0 and (y,x - 1) not in shape:
          copy = Set(shape)
          copy.add((y,x - 1))
          stack.append((s + a[y][x - 1],copy,l + 1))

  print best
  print len(hash)

输出:

arr = [[31,12,7,1,14]
      ,[23,98,3,87,1]
      ,[5,31,8,2,99]
      ,[12,3,42,17,88]
      ,[120,2,7,5,7]]

f(arr,6)

"""
(377, Set([(1, 2), (1, 3), (1, 1), (2, 3), (3, 4), (2, 4)]))
2394 hash length
"""

翻译自:https://stackoverflow.com/questions/32824002/maximum-sum-of-k-connected-elements-of-a-matrix


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

深度学习

深度学习

[美] 伊恩·古德费洛、[加] 约书亚·本吉奥、[加] 亚伦·库维尔 / 赵申剑、黎彧君、符天凡、李凯 / 人民邮电出版社 / 2017-7-1 / 168

《深度学习》由全球知名的三位专家Ian Goodfellow、Yoshua Bengio 和Aaron Courville撰写,是深度学习领域奠基性的经典教材。全书的内容包括3个部分:第1部分介绍基本的数学工具和机器学习的概念,它们是深度学习的预备知识;第2部分系统深入地讲解现今已成熟的深度学习方法和技术;第3部分讨论某些具有前瞻性的方向和想法,它们被公认为是深度学习未来的研究重点。 《深度......一起来看看 《深度学习》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具