用於解決與重疊選項衝突的算法

我有一個計算問題，其中有一組標籤可以只給出一次，還有一些項目每個都有一組他們可以接受的標籤。我需要以這樣的方式分配標籤，即每當遇到問題的解決方案時，每個項目都會獲得標籤。用於解決與重疊選項衝突的算法

舉一個具體的例子，如果我有這樣的詞典：

options = { 
    'a': [1], 
    'b': [2, 3], 
    'c': [1, 2] 
}

..then的解決辦法是：

{'a': 1, 'b': 3, 'c': 2}

我還需要能夠擴大問題來處理多個約束，例如

[1], ['A', 'B']   # -> (1, A) or (1, B) 
[1, 2, 3], ['A', 'C'] # -> (3, C) 
[1, 2], ['A', 'C']  # -> (2, A) or (2, B)

我試圖拿出基於對簡單的情況下，優先級隊列可行的解決方案，但完全有多個約束分崩離析。我可以蠻力使用itertools.permutations解決方案，但我更喜歡有效的實現。有沒有可能適用於這個問題的已知算法？

來源

2014-03-19 lyschoening

如果有多個解決方案，就像如果你有選項= {'a'：[1,2]，'b'：[2,3]，'c'：[1,2]）是解決方案，則{'a'：[1,2] ，'b'：3，'c'：[1,2]}還是你想得到一組解決方案？ – MaSp

只是一個解決方案。這個問題的範圍是避免不完整的解決方案，而不是列舉所有的可能性。 – lyschoening

形式上，必須在本例中是什麼簡單的約束滿足問題有三個變量['a', 'b', 'c']，每一個有限整數域和「全部不同」約束。

回溯搜索與適當的啓發式方法可以在實踐中相當快地解決這類問題。例如。

def backtracking(domains): 
    if any(len(dom) == 0 for var, dom in domains.iteritems()): 
     return None 
    if all(len(dom) == 1 for var, dom in domains.iteritems()): 
     return domains 

    # minimum remaining values heuristic: process variables with few possible 
    # values first (fail-first strategy) 
    order = sorted(domains.iteritems(), key=lambda (var, dom): len(dom)) 
    for var, dom in order: 
     if len(dom) == 1: 
      continue 

     for value in list(dom): 
      doms = {v: d - {value} for v, d in domains.iteritems() 
            if v != var} 
      doms[var] = {value} 

      solution = backtracking(doms) 
      if solution is not None: 
       return solution 

print(backtracking({v: set(d) for v, d in options.iteritems()}))

來源

2014-03-19 15:50:39

這看起來好像是爲了簡單的情況而工作，我相信如果成本更高，它可以擴展到複雜的情況。 – lyschoening

更詳細地查看解決方案後，您只需注意一些問題：如果原始案例已出現故障狀態，則此解決方案將失敗如果'選項= {'a'：[1，2]，'b'：[3]，'c'：[3]}'。否則，可以通過將'd - {value}'（_aka拒絕step_）更改爲更合適的方法來輕鬆擴展該解決方案。 – lyschoening

我會用回溯來解決這個問題。根據約束條件，如果貪心算法可以實現，選擇1個標籤在同一時間實現全球最佳

來源

2014-03-19 15:50:18 ctutte

你不必爲了解決這個問題而實現一個完整的回溯系統。許多研究人員已經建立了系統和建模語言來促進這類問題的解決。

你的問題是一個非常經典的約束滿足問題，我們有所有不同的約束。我建議你使用像minizinc這樣的高級建模語言（http://www.minizinc.org/），你會看到自己的區別。這裏寫在這個格式的簡單模型（你的問題）：

include "globals.mzn"; 
var {1} : a; 
var {2,3} : b; 
var {1,2} : c; 
constraint alldifferent([a,b,c]); 

solve satisfy; 

output ["a : ", show(a), "\n" , 
     "b : ", show(b), "\n" , 
     "c : ", show(c), "\n" ];

如果這是使用minizinc你的第一次，你可以用最新的教程here開始。

來源

2014-03-20 00:10:49 Med

這真的是一個非常基本的不同約束。如果Python感興趣，使用 https://pypi.python.org/pypi/python-constraint

problem = Problem() 
problem.addVariable("a", [1, 2]) 
problem.addVariable("b", [2, 3]) 
problem.addVariable("c", [1, 2]) 
problem.addConstraint(AllDifferentConstraint()) 
print problem.getSolution()

（會給你發現是否存在或

print sorted(sorted(x.items()) for x in problem.getSolutions())

會給所有的解決方案第一個）

來源

2014-08-11 11:27:29

用於解決與重疊選項衝突的算法

回答

相關問題