約束規劃求解邏輯謎題

約束規劃在解決複雜邏輯謎題方面展現出強大的能力。本文以「SEND MORE MONEY」和「女士或老虎」兩個經典謎題為例，示範如何利用約束規劃技術，將邏輯推理轉化為數學模型，並使用 OR-Tools 進行求解。首先，針對每個謎題，定義關鍵變數，例如字母對應的數字或房間的狀態。接著，根據謎題規則建立約束條件，例如 SEND MORE MONEY 中字母與數字的一一對應關係，以及 女士或老虎 中房間狀態與門上標語真偽的邏輯關係。最後，利用 OR-Tools 提供的求解器，找到滿足所有約束條件的解，並驗證其正確性。 程式碼實作部分，詳細展示瞭如何使用 OR-Tools 宣告整數變數、建立約束條件以及求解模型。同時，也解析了程式碼中的關鍵部分，例如 reify 函式的使用、指標變數的應用以及 k_out_of_n 約束的設定。

進階技術：約束規劃與邏輯謎題求解

邏輯謎題的建模與求解技術

在處理複雜的邏輯謎題時，約束規劃（Constraint Programming）提供了一種強大的建模和求解框架。本章節將透過兩個經典的邏輯謎題：「SEND MORE MONEY」與「女士或老虎」，來展示如何使用約束規劃技術進行建模和求解。

7.5.3 SEND MORE MONEY 謎題

問題描述

「SEND MORE MONEY」是一個經典的密碼算術謎題，要求將不同的字母對映到不同的數字，使得以下等式成立：

  SEND
+ MORE
---
---
 MONEY

建模方法

1. 變數定義：為每個字母定義整數變數，範圍在0到9之間。
2. 全不同約束：使用all_different約束確保所有字母對映到不同的數字。
3. 數值約束：將字母組合成數值表示式，並建立等式約束。
4. 前導零約束：對S和M新增非零約束。

實作程式碼

def solve_smm():
    s = newSolver('Sendumoreumoney', True)
    ALL = [S, E, N, D, M, O, R, Y] = [newIntVar(s, 0, 9) for _ in range(8)]
    s.Add(1000*S[0] + 100*E[0] + 10*N[0] + D[0] +
          1000*M[0] + 100*O[0] + 10*R[0] + E[0] ==
          10000*M[0] + 1000*O[0] + 100*N[0] + 10*E[0] + Y[0])
    all_different(s, ALL)
    neq(s, S, 0)
    neq(s, M, 0)
    rc = s.Solve()
    return rc, SolVal([a[0] for a in ALL])

解題結果

S E N D M O R Y
9 5 6 7 1 0 8 2

驗證結果：9567 + 1085 = 10652，等式成立。

7.5.4 女士或老虎謎題

邏輯建模關鍵技術

1. 變數設計

   • 使用R[i]表示房間i的狀態（1：空、2：女士、3：老虎）
   • 使用S[i]表示房間i的門上陳述的真假

2. 核心約束

   • 女士存在性約束：恰好有一個房間包含女士
   • 陳述邏輯約束：
     • 若房間有老虎，則陳述為假
     • 若房間有女士，則陳述為真
     • 各房間的特殊邏輯陳述

程式碼實作重點解析

def solve_lady_or_tiger():
    s = newSolver('Ladyuorutiger', True)
    Rooms = range(1, 10)
    R = [None] + [newIntVar(s, 0, 2) for _ in Rooms]
    S = [None] + [s.IntVar(0, 1, "") for _ in Rooms]
    
    # 確保恰好有一位女士
    k_out_of_n(s, 1, [R[i][i_lady] for i in Rooms])
    
    # 設定老虎房間的陳述為假
    for i in Rooms:
        reify_force(s, [1], [R[i][i_tiger]], 0, S[i], '<=')
    
    # 設定女士房間的陳述為真
    for i in Rooms:
        reify_raise(s, [1], [R[i][i_lady]], 1, S[i], '>=')
    
    # 各房間的特殊邏輯約束
    # 例如：1號門的陳述「女士在奇數房間」
    v = [1]*5
    reify(s, v, [R[i][i_lady] for i in range(1, 10, 2)], 1, S[1], '>=')
    
    rc = s.Solve()
    return rc, [SolVal(S[i]) for i in Rooms], [SolVal(R[i]) for i in Rooms]

#### 邏輯實作解析：

1. 使用reify函式將邏輯陳述轉換為數值約束
2. 透過指標變數實作複雜邏輯關係
3. k_out_of_n確保唯一解的存在

「女士或老虎」難題的約束規劃與實作解析

「女士或老虎」謎題是一個經典的邏輯問題，涉及多個房間的狀態判斷以及對門上標語真偽的分析。本篇文章將透過 OR-Tools 的約束規劃技術，逐步拆解並實作該謎題的求解過程。

難題描述與建模考量

該謎題包含九個房間，每個房間可能包含「女士」或「老虎」，並且每個房間門上的標語代表著特定的邏輯陳述。我們的目標是根據這些標語的真偽條件，找出「女士」所在的房間。

變數定義與資料結構

首先，我們需要定義用於表示房間狀態和標語真偽的變數：

• R[i][j]：二維矩陣，其中 i 表示房間編號（1-9），j 表示狀態（0:空, 1:女士, 2:老虎）
• S[k]：一維陣列，用於表示第 k 個標語的真偽狀態

程式碼實作：變數宣告

R = [[s.IntVar(0, 2, f"R{i}_{j}") for j in range(3)] for i in range(10)]
S = [s.IntVar(0, 1, f"S{k}") for k in range(10)]

內容解密：

1. s.IntVar(0, 2, f"R{i}_{j}") 用於宣告整數變數，範圍在 0 到 2 之間，分別代表房間狀態。
2. R 矩陣用於儲存每個房間的狀態，而 S 陣列儲存每個標語的真偽。
3. 使用 IntVar 是因為這是一個整數規劃問題，需要精確的整數解。

約束條件設定

每個房間有且僅有一個狀態，因此需要對每個房間新增恰好一個狀態的約束條件：

for i in range(1, 10):
    s.Add(R[i][0] + R[i][1] + R[i][2] == 1)

內容解密：

1. 該迴圈確保每個房間只能有一種狀態（空、女士或老虎）。
2. R[i][0] + R[i][1] + R[i][2] == 1 代表三種狀態的指標變數總和為 1。

邏輯條件轉化與實作

第一個條件：「A room with a lady has a true statement on its door.」

# 在正確方向上的約束提升布林值
# 已於程式碼第10行實作對應邏輯

第二個條件：「The lady is in an odd-numbered room.」

s.Add(R[1][1] + R[3][1] + R[5][1] + R[7][1] + R[9][1] >= 1)
s.Add(S[1] == (R[1][1] + R[3][1] + R[5][1] + R[7][1] + R[9][1] >= 1))

內容解密：

1. 將奇數房間的女士狀態相加，若總和大於等於 1，表示至少有一個奇數房間有女士。
2. 將此條件重新化為 S[1] 的布林約束。

其他條件轉化範例

s.Add(S[2] == (R[2][0] >= 1))  # 「This room is empty.」
s.Add(S[5] - S[7] >= 0)        # 「Either sign 5 is right or sign 7 is wrong.」

內容解密：

1. 將每個標語的邏輯陳述轉化為對應的布林運算。
2. 例如，S[5] - S[7] >= 0 表示第五個標語為真或第七個標語為假的邏輯析取。

多重解的尋找與分析

在找到第一組解後，若要尋找其他可能的解，可以新增額外的約束條件排除已知的解。例如，若第一組解中女士在房間 1，則新增約束 s.Add(R[1][1] == 0) 以排除該情況。

程式碼實作：多重解尋找

s.Add(R[1][1] == 0)  # 新增約束以排除第一組解

內容解密：

1. 該步驟透過排除特定變數的取值，強制求解器尋找其他可能的解。
2. 若無其他解，則求解器將傳回無可行解的結果。

使用OR-Tools進行整數決策變數宣告與模型建立

在最佳化問題中，宣告整數決策變數是建模的第一步。Google的OR-Tools提供了方便的介面來宣告和使用這些變數。本章節將介紹如何使用OR-Tools宣告整數決策變數、建立約束條件以及定義目標函式。

整數決策變數宣告

宣告整數決策變數的基本語法如下：

VAR = s.IntVar(LOW, HIGH, NAME)

其中，LOW和HIGH分別代表變數的下限和上限，NAME是變數的名稱。

內容解密：

• s.IntVar是用於宣告整數變數的函式。
• LOW和HIGH確保變數的值在指定的範圍內。
• NAME用於識別變數，在除錯和輸出結果時非常有用。

建立決策變數陣列

建立一維陣列的決策變數可以使用列表推導式，如下所示：

x = [s.IntVar(LOW, HIGH, f"x_{i}") for i in range(N)]

這裡，N是陣列中元素的數量。

內容解密：

• 列表推導式用於快速生成包含N個元素的陣列。
• 每個元素都是一個整數決策變數，具有相同的上下限。

對於高維陣列，例如一個M行N列的矩陣，可以使用巢狀的列表推導式：

m = [[s.IntVar(LOW, HIGH, f"m_{i}_{j}") for j in range(N)] for i in range(M)]

內容解密：

• 巢狀列表推導式用於建立二維陣列。
• 每個元素m[i][j]都是一個具有指定上下限的整數決策變數。

約束條件宣告

約束條件是模型中的關鍵部分，用於限制決策變數的取值。基本的約束條件宣告語法如下：

s.Add(REL)

其中，REL是一個線性代數關係，可以使用決策變數、數字、算術運算子（+、-、*、/）以及等式和不等式關係運算子。

內容解密：

• s.Add用於向模型中新增約束條件。
• REL應該是一個有效的線性代數表示式，例如2 * x[12] + 30 * x[13] <= 100。

範例：

s.Add(2 * x[12] + 30 * x[13] <= 100)
s.Add(25 == x[100] - x[101])
s.Add(x[99] >= x[100])

內容解密：

• 第一個約束條件限制了兩個決策變數的線性組合不得超過100。
• 第二個約束條件強制兩個決策變數之間的差值等於25。
• 第三個約束條件確保一個決策變數大於或等於另一個。

總和運算子

OR-Tools提供了s.Sum()函式，用於計算一組決策變數的總和。

s.Add(s.Sum(x) <= 100)
s.Add(s.Sum(m[i][j] for i in range(M) for j in range(N)) <= 100)

內容解密：

• 第一個範例限制了陣列x中所有元素的總和不得超過100。
• 第二個範例對二維陣列m中的所有元素進行求和，並限制其總和不得超過100。

目標函式宣告

目標函式定義了最佳化的方向，可以是最大化或最小化某個線性表示式。

s.Maximize(EXPR)
s.Minimize(EXPR)

其中，EXPR是任何線性的代數表示式。

內容解密：

• s.Maximize用於最大化目標函式。
• s.Minimize用於最小化目標函式。
• EXPR應該是決策變數的線性函式。

求解模型

使用OR-Tools求解模型非常簡單，只需呼叫s.Solve()方法。

rc = s.Solve()

傳回值rc表示求解的狀態，可以是最佳（OPTIMAL）、可行（FEASIBLE）、不可行（INFEASIBLE）、無界（UNBOUNDED）等。

內容解密：

• s.Solve()啟動求解過程。
• 傳回值rc可用於檢查求解是否成功。

取得最優解和目標函式值

求解後，可以透過以下方法取得最優解和目標函式值：

value = s.Objective().Value()
varval = var.SolutionValue()

或者使用包裝函式：

value = ObjVal(s)
xval = SolVal(x)

內容解密：

• s.Objective().Value()傳回目標函式的最優值。
• var.SolutionValue()傳回特定決策變數的最優解。
• ObjVal(s)和SolVal(x)是包裝函式，提供更方便的介面來取得最優值和解。

高階約束條件

OR-Tools提供了多種高階約束條件，如k_out_of_n、sosn、reify_force、reify_raise和reify，這些可以用於實作更複雜的邏輯。

範例：使用k_out_of_n約束

l = k_out_of_n(s, k, x, rel='==')

這裡，k_out_of_n確保列表x中恰好（或至少/至多，取決於rel）有k個變數為非零。

內容解密：

• k_out_of_n是一種特殊的約束，用於控制一組變數中非零元素的數量。
• rel引數決定了比較關係（等於、至少、至多）。

AllDifferent約束

OR-Tools還提供了AllDifferent約束，確保一組整數決策變數具有不同的值。

all_different(s, x)

這裡，x是一組整數決策變數。

內容解密：

• AllDifferent約束強制所有指定的決策變數具有不同的值。
• 這對於需要唯一值的問題非常有用，例如排程或分配問題。

本章介紹了使用OR-Tools進行整數規劃的基本步驟，包括宣告決策變數、建立約束條件、定義目標函式以及求解模型。這些工具和技術可以用於解決廣泛的最佳化問題，從資源分配到生產排程等。透過靈活運用OR-Tools提供的高階功能，可以有效地建模和解決複雜的最佳化挑戰。

最佳化問題與數學模型：從理論到實踐的全面解析

最佳化問題是數學和電腦科學中的核心課題，旨在從多個可行方案中找出最佳解決方案。這些問題廣泛存在於工業生產、物流管理、金融投資等眾多領域，具有重要的理論與實踐價值。本文將探討最佳化問題的基本概念、數學模型及其在實際應用中的表現形式。

線性與非線性最佳化模型

最佳化問題可根據目標函式和約束條件的特性分為線性與非線性兩大類別。線性最佳化模型具有線性目標函式和線性約束條件，其求解方法相對成熟，如單純形法等。非線性最佳化模型則涉及非線性目標函式或約束條件，求解過程更為複雜，通常需要藉助數值最佳化演算法。

線性最佳化例項：飲食問題

飲食問題是線性最佳化的經典案例之一，旨在以最低成本滿足營養需求。給定不同食物的營養成分和價格，模型需確定最優的食物組合。

# 建立求解器例項
solver = pywraplp.Solver.CreateSolver('GLOP')

# 定義決策變數：食物數量
food_vars = [solver.NumVar(0, solver.infinity(), food) for food in foods]

# 目標函式：最小化總成本
objective = solver.Objective()
for i, food in enumerate(foods):
    objective.SetCoefficient(food_vars[i], food_costs[food])
objective.SetMinimization()

# 約束條件：滿足營養需求
for nutrient in nutrients:
    constraint = solver.Constraint(nutrient_min[nutrient], solver.infinity())
    for i, food in enumerate(foods):
        constraint.SetCoefficient(food_vars[i], nutrient_content[food][nutrient])

整數規劃與混合整數規劃

整數規劃（Integer Programming, IP）要求部分或全部決策變數為整數，常見於資源分配、排程等問題。混合整數規劃（Mixed Integer Programming, MIP）則結合了連續變數與整數變數，能夠處理更為複雜的最佳化問題。

案例分析：設施選址問題

設施選址問題旨在確定最佳的設施位置，以最小化總成本（包括建設成本和營運成本）。這是一個典型的MIP問題。

# 定義決策變數：設施建設狀態（0-1變數）和運輸量
facility_vars = [solver.IntVar(0, 1, f'facility_{i}') for i in range(num_facilities)]
transport_vars = [[solver.NumVar(0, solver.infinity(), f'transport_{i}_{j}') 
                   for j in range(num_customers)] for i in range(num_facilities)]

# 目標函式：最小化總成本
objective = solver.Objective()
for i in range(num_facilities):
    objective.SetCoefficient(facility_vars[i], facility_costs[i])
    for j in range(num_customers):
        objective.SetCoefficient(transport_vars[i][j], transport_costs[i][j])
objective.SetMinimization()

# 約束條件：滿足客戶需求和設施容量限制
for j in range(num_customers):
    constraint = solver.Constraint(demands[j], demands[j])
    for i in range(num_facilities):
        constraint.SetCoefficient(transport_vars[i][j], 1)

for i in range(num_facilities):
    constraint = solver.Constraint(0, capacities[i])
    for j in range(num_customers):
        constraint.SetCoefficient(transport_vars[i][j], 1)

網路最佳化與路徑規劃

網路最佳化涉及在網路結構中尋找最優路徑或流分配方案，常見於交通運輸、物流配送等領域。最短路徑問題和最大流問題是其中的典型代表。

Dijkstra演算法與最短路徑

Dijkstra演算法是一種高效的最短路徑演算法，適用於帶權有向圖或無向圖。其基本思想是逐步擴充套件最短路徑集合，直至到達目標節點。

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# 示例圖結構
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
distances = dijkstra(graph, start_node)
print(distances)

內容解密：

1. 最佳化問題分類別：根據目標函式和約束條件的特性，可分為線性與非線性最佳化。
2. 整數規劃：要求部分或全部決策變數為整數，常見於資源分配和排程問題。
3. 網路最佳化：涉及在網路結構中尋找最優路徑或流分配方案，如最短路徑和最大流問題。
4. Dijkstra演算法：一種高效的最短路徑演算法，適用於帶權圖。
5. 實際應用：最佳化技術廣泛應用於工業生產、物流管理、金融投資等領域。

索引

本索引涵蓋了多個與最佳化問題相關的主題，包括一般引擎、集合包裝、最短路徑、員工排班等。以下將對索引中的關鍵主題進行詳細說明。

一般引擎（General Engine）

一般引擎是一種用於解決最佳化問題的通用框架。它涵蓋了目標函式的定義、供應商和零件的管理，以及多種變化形式，如機組排班問題、消防站設定、電信網路最佳化等。

集合包裝（Set Packing）

集合包裝問題涉及在給定的集合中找到最大的不相交子集集合。它在航空公司機組排班等領域有實際應用。該問題的數學模型包括決策變數的定義、目標函式的建立以及約束條件的設定。

最短路徑（Shortest Paths）

最短路徑問題旨在圖中找到兩個節點之間的最短路徑。Dijkstra’s 演算法和 Floyd-Warshall 演算法是解決此問題的兩種常見方法。此外，還探討了該問題的各種變體，如所有節點對之間的最短路徑、最大化問題轉化為最小化問題等。

員工排班（Staff Scheduling）

員工排班問題涉及為員工安排工作時間表，以滿足組織的需求。它包括定義決策變數、建立目標函式以及設定約束條件，如員工的工作時數、最小滿意度等。

運輸問題（Transshipment）

運輸問題是一個網路流問題，涉及在供應商和需求者之間透過中轉節點運輸商品。它需要滿足流守恆約束，並最小化運輸成本。

旅行商人問題（Travelling Salesman Problem, TSP）

TSP 是一個經典的最佳化問題，涉及找到存取一組城市並傳回起始城市的最短可能路線。它具有多種應用，如電路設計、物流管理等。

索引使用

本索引提供了豐富的最佳化問題相關主題，讀者可以根據自己的需求查詢特定的主題。每個主題都包含了關鍵概念、數學模型和實際應用案例，為讀者提供了深入瞭解和解決實際問題的基礎。