窮舉法的方法就是遍歷所有的可能解炫刷。
我用iphone 6 測(cè)試了窮舉法的效率：采用的是幻方（magic square）謎題解法：
試將1~9這9個(gè)不同整數(shù)填入一個(gè)3x3的表格蛙卤，使得每行，每列以及每條對(duì)角線(xiàn)上的數(shù)字之和相同。
| ? | ? | ? |
|---|---|---|
| ? | ? | ? |
| ? | ? | ? |
使用窮舉法，那么可能性有 9! = 362880 種可能。
**測(cè)試結(jié)果： 需要只用76秒珍促。 **
使用的代碼為：
private let MAGIC_SQUARE = 3;
private let beginTime = Date.init().timeIntervalSince1970;
override func viewDidLoad() {
super.viewDidLoad()
let result = Array<Int>.init();
var possibility = Array<Int>.init();
for index in 0..<(MAGIC_SQUARE * MAGIC_SQUARE)
{
possibility.append(index)
}
print("beginTime is \(beginTime)")
methodOfExhuastion(result: result, possibility: possibility)
}
func methodOfExhuastion(result:Array<Int>, possibility:Array<Int>) -> Void {
if 0 >= possibility.count {
print("result is \(result)")
let nowTime = Date.init().timeIntervalSince1970
let usingTime = nowTime - beginTime;
print("usingTime is \(usingTime)")
return;
}
for index in 0..<possibility.count
{
let number = possibility[index];
var tempResult = Array<Int>.init(result);
tempResult.append(number);
var tempPossibility = Array<Int>.init(possibility);
tempPossibility.remove(at: index);
methodOfExhuastion(result: tempResult, possibility: tempPossibility);
}
}
當(dāng)幻方為2 x 2時(shí)，測(cè)試結(jié)果： 0.05秒剩愧。
當(dāng)幻方為4 x 4時(shí)猪叙，測(cè)試結(jié)果： ？仁卷？穴翩？？
執(zhí)行了1189秒時(shí)锦积，才遍歷到了第9位芒帕。
當(dāng)幻方為5 x 5時(shí)，這個(gè)時(shí)候就會(huì)出現(xiàn)計(jì)算機(jī)已經(jīng)無(wú)能為力丰介。
是的你沒(méi)看錯(cuò)背蟆，（（5 x 5）x （5 x 5））鉴分！ = 1.5 x 10000000000000000000000000（25個(gè)0）.如果是每秒計(jì)算100 000億次的計(jì)算機(jī)，需要使用49 000年才能完成這項(xiàng)任務(wù)带膀。你可以計(jì)算下志珍。 當(dāng)我看到這個(gè)結(jié)果時(shí)，我也是被震驚了垛叨。在等待4 x 4的計(jì)算時(shí)碴裙，我也已經(jīng)覺(jué)得數(shù)據(jù)量大的概念是什么了。
16! = 2.0 x 10000000000000(13個(gè)0)点额。
SO， 盡量少用窮舉法莺琳』估猓可以嘗試回溯法（backtracking）。
算法設(shè)計(jì)：
窮舉搜索 -> 回溯法 -> 減而治之 -> 分而治之 -> 變而治之 -> 貪心法 -> 迭代改進(jìn) -> 動(dòng)態(tài)規(guī)劃
