c++ - 在 C++ 中通过网格/矩阵找到成本优化路径

Question

我遇到了一个问题，在网上找不到太多帮助。我需要从多个数字 vector 中找到数字的最小成本组合。所有 vector 的 vector 大小相同。 例如，考虑以下内容:

row [0]:  a  b  c  d   
row [1]:  e  f  g  h  
row [2]:  i  j  k  l  

现在我需要通过从每一行中取一个元素来找到数字的组合，即 vector ，例如:aei
在此之后，我需要找到其他三个不相交的组合，例如:bfj、cgk、dhl。我根据选择的这四种组合计算成本。目标是找到成本最低的组合。另一种可能的组合可以是:afj、bei、chk、dgl。如果总列数为 d，行数为 k，则可能的总组合为 d^k。这些行存储为 vector 。我被困在这里，我发现很难为上述过程编写算法。如果有人可以提供帮助，我将不胜感激。
谢谢。

// I am still working on the algorithm. I just have the vectors and the cost function.  

//Cost Function  , it also depends on the path chosen
float cost(int a, int b, PATH to_a) {  
float costValue;  
...  
...  
return costValue;  
}  

vector< vector < int > > row;  
//populate row  
...   
...
//Suppose  

//    row [0]:  a  b  c  d   
//    row [1]:  e  f  g  h  
//    row [2]:  i  j  k  l   

// If a is chosen from row[0] and e is chosen from row[1] then,  
float subCost1 = cost(a,e, path_to_a);  

// If i is chosen from row[2] ,  
float subCost2 = cost(e,i,path_to_e);  

// Cost for selecting aei combination is  
float cost1 = subCost1 + subCost2;  

//similarly other three costs need to be calculated by selecting other remaining elements  
//The elements should not intersect with each other eg. combinations aei and bej cannot exist on the same set.  

//Suppose the other combinations chosen are bfj with cost cost2, cgk with cost cost3   and dhl with cost cost4  
float totalCost = cost1 + cost2 + cost3 + cost4;   

//This is the cost got from one combination. All the other possible combinations should be enumerated to get the minimum cost combination. 

Answer 1

Posting more utility code

see github: https://gist.github.com/1233012#file_new.cpp

This is basically an much better approach to generating all possible permutations based on much simpler approach (therefore I had no real reason to post it before: As it stands right now, it doesn't do anything more than the python code).

I decided to share it anyways, as you might be able to get some profit out of this as the basis for an eventual solution.

Pro:

• much faster
  • smarter algorithm (leverages STL and maths :))
  • instruction optimization
  • storage optimization
• generic problem model
• model and algorithmic ideas can be used as basis for proper algorithm
• basis for a good OpenMP parallelization (n-way, for n rows) designed-in (but not fleshed out)

Contra:

• The code is much more efficient at the cost of flexibility: adapting the code to build in logic about the constraints and cost heuristics would be much easier with the more step-by-step Python approach

All in all I feel that my C++ code could be a big win IFF it turns out that Simulated Annealing is appropriate given the cost function(s); The approach taken in the code would give

• a highly efficient storage model
• a highly efficient way to generate random / closely related new grid configurations
• convenient display functions

---

Mandatory (abritrary...) benchmark data point (comparison to the python version:)

  a  b  c  d e
  f  g  h  i j
  k  l  m  n o
  p  q  r  s t

Result: 207360000

real  0m13.016s
user  0m13.000s
sys   0m0.010s

这是我们到现在为止的:

• 从描述中，我了解到您有一个基本图表，例如 。

• 必须构造一条访问网格中所有节点的路径 ( Hamiltonian cycle )。

• 额外的限制是后续节点必须从下一个rank(a-d、e-h、i-l 是三个rank em>；一旦访问了最后一个 rank 的节点，路径必须与来自第一个 rank

的任何未访问节点继续

• 边缘是加权的，因为它们具有相关的成本。然而，权重函数对于图算法来说并不是传统的，因为成本取决于完整路径，而不仅仅是每条边的端点。

鉴于此，我相信我们处于“全覆盖”问题的领域(需要 A* 算法，最著名的是 Knuths Dancing Links 论文)。

具体来说如果没有进一步的信息(路径的等价性，成本函数的特定属性)，获得满足约束的“最便宜”汉密尔顿路径的最知名算法将是

• 生成所有可能的这样的路径
• 计算每个的实际成本函数
• 选择成本最低的路径

这就是为什么我开始编写一个非常愚蠢的蛮力生成器，它可以在 NxM 的通用网格中生成所有可能的唯一路径。

宇宙的尽头

3×4 样本网格的输出为 4!³ = 13824 条可能的路径...外推到 6×48 列，得到 6!⁴⁸ = 1.4×10¹³⁷ 种可能性。很明显 如果不进一步优化，问题就难以解决(NP Hard 之类的——我不记得很微妙的定义)。

运行时的爆炸声震耳欲聋:

• 3×4(实测)大约需要 0.175 秒
• 4×5(实测)大约需要 6 分 5 秒(在快速机器上在 PyPy 1.6 下无输出运行)
• 5×6 大约需要 10 年零 9 个月以上...

在 48x6 时，我们会看到...什么... 8.3x10¹⁰⁷ 年(仔细阅读)

现场观看:http://ideone.com/YsVRE

无论如何，这里是 python 代码(所有预设为 2×3 网格)

#!/usr/bin/python
ROWS = 2
COLS = 3

## different cell representations
def cell(r,c): 
    ## exercise for the reader: _gues_ which of the following is the fastest
    ## ...
    ## then profile it :)
    index = COLS*(r) + c
    # return [ r,c ]
    # return ( r,c )
    # return index
    # return "(%i,%i)" % (r,c)

    def baseN(num,b,numerals="abcdefghijklmnopqrstuvwxyz"):
        return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

    return baseN(index, 26)

ORIGIN = cell(0,0)

def debug(t): pass; #print t
def dump(grid): print("\n".join(map(str, grid)))

def print_path(path):
    ## Note: to 'normalize' to start at (1,1) node:
    # while ORIGIN != path[0]: path = path[1:] + path[:1] 
    print " -> ".join(map(str, path))

def bruteforce_hamiltonians(grid, whenfound):
    def inner(grid, whenfound, partial):

        cols = len(grid[-1]) # number of columns remaining in last rank
        if cols<1:
            # assert 1 == len(set([ len(r) for r in grid ])) # for debug only
            whenfound(partial)                             # disable when benchmarking
            pass
        else:
            #debug(" ------ cols: %i ------- " % cols)

            for i,rank in enumerate(grid):
                if len(rank)<cols: continue
                #debug("debug: %i, %s (partial: %s%s)" % (i,rank, "... " if len(partial)>3 else "", partial[-3:]))
                for ci,cell in enumerate(rank):
                    partial.append(cell)
                    grid[i] = rank[:ci]+rank[ci+1:] # modify grid in-place, keeps rank

                    inner(grid, whenfound, partial)

                    grid[i] = rank # restore in-place
                    partial.pop()
                break
        pass
    # start of recursion
    inner(grid, whenfound, [])

grid = [ [ cell(c,r) for r in range(COLS) ] for c in range(ROWS) ]

dump(grid)

bruteforce_hamiltonians(grid, print_path)