如何枚舉蠻力算法的所有可能性？

Question

可能未指定此問題，但我認爲這非常重要。當你想解決一個優化問題，並且你不熟悉dynamic programming方法時，這是你想到的第一個想法。

我可以舉一些簡單的例子：

• 獲取列表（很簡單）
• 列表中選擇一個集合的所有排列
• 列表中選擇一個集合的所有子集的最小元素

這些問題都有成熟的方法。但也有問題，不是很清楚：

• 列表中的兩個字符串的所有edit distance（我的意思是不是編輯操作中最短的一個）
• 列表common subsequence兩個控制順序
• 所有列表圓括號matrix chain multiplication
的所有可能性

我不知道用蠻力法解決這些問題。我的問題是：

是否有一個系統的通用方法列出蠻力算法的所有可能性？

Answer 1

Backtracking是查找問題的所有解決方案的最通用方法之一。每維基百科，

回溯查找所有（或部分）的解決方案，一些計算問題的通用算法，即逐步儘快建立考生的解決方案，並放棄每個部分候選人C（「回溯」），因爲它確定c不可能完成到一個有效的解決方案。

使用回溯的經典教科書示例是八個皇后拼圖，它要求在標準棋盤上安排八個國際象棋皇后，以免皇后攻擊任何其他棋王。

你提到的兩個問題，
•列表中有兩個序列
•列表圓括號矩陣鏈乘積
的所有可能性可以是所有公共子容易使用回溯處理。我不確定編輯距離問題。