数学建模练习小标题

标题A

有三名贩子各带一名仆役过河，船最多能载两人。在河的任何一岸，若仆役数超 过贩子数，仆役会杀贩子越货。怎样搭船由贩子决定，问是否有安全过河方案，如有，最少须要几步?
界说变量

贩子和仆役的状态：利用状态 (M, S) 来表现某一岸上的贩子数和仆役数。
船的状态：由于船只能在两岸之间移动，利用一个二元变量来表现船的位置，1 表现船在左岸（起始岸）,0 表现船在右岸（目标岸）。
因此，体系的一个状态可以表现为三元组 (M, S, B)，此中，M 表现左岸的贩子数，S 表现左岸的仆役数，B 表现船的位置（左岸或右岸），界说初始状态为 (3, 3, 1)，目标状态为 (0, 0, 0)，即全部人都在右岸。
状态转换

在题目标办理过程中，船一次可以带1或2人过河，因此答应的利用包罗一名贩子和一名仆役一起过河 (1, 1)，两名贩子一起过河 (2, 0)，两名仆役一起过河 (0, 2)，一名贩子过河 (1, 0)，一名仆役过河 (0, 1)。
基于当前船地点的位置，贩子和仆役要么从左岸到右岸（如果船在左岸），要么从右岸到左岸（如果船在右岸）。
合法状态条件：
如果左岸有贩子和仆役，必须满足左岸的贩子数 >= 左岸的仆役数。
如果右岸有贩子和仆役，也必须满足右岸的贩子数 >= 右岸的仆役数。
如果某岸没有贩子，则无需思量仆役数目。
目标函数

题目标目标是找到一种安全的过河战略，使得全部贩子和仆役安全过河，而且最少步数完成过河过程。步数是须要最小化的目标函数。
束缚条件

•         每次船的载重不能高出两人。
  
•         每次过河之后，任何一岸的仆役数不能高出贩子数。
  
•         贩子决定搭船方案，仆役不能独立决定过河。
  

BFS求解

广度优先搜刮（BFS）是一种常用来探求最短路径的算法，恰当用来办理这种题目。
详细步调如下：

•         从初始状态 (3, 3, 1) 开始，参加队列。
  
•         对于队列中的每个状态，实验全部大概的合法过河方式，天生新状态。
  
•         如果新状态满足安全条件而且没有被访问过，将其参加队列。
  
•         当某个状态到达目标状态 (0, 0, 0) 时，制止搜刮，返回路径。
  
•         如果全部状态都搜刮完毕还没有找到解，则分析题目无解。
  

2. from collections import deque
3. ​
4. # 定义初始状态 (左岸商人数量, 左岸仆人数量, 船所在岸 1表示左岸, 0表示右岸)
5. initial_state = (3, 3, 1)
6. goal_state = (0, 0, 0)
7. ​
8. # 检查状态是否合法
9. def is_valid(state):
10.    left_m, left_s, _ = state
11.    right_m = 3 - left_m
12.    right_s = 3 - left_s
13.    # 检查两岸的商人数和仆人数比例
14.    if (left_m >= 0 and left_s >= 0 and left_m >= left_s) or left_m == 0:
15.        if (right_m >= 0 and right_s >= 0 and right_m >= right_s) or right_m == 0:
16.            return True
17.    return False
18. ​
19. # 使用BFS算法来搜索最优解
20. def bfs():
21.    queue = deque([(initial_state, [])])  # 队列保存当前状态和走过的路径
22.    visited = set()  # 记录已经访问过的状态
23.    visited.add(initial_state)
24.    
25.    while queue:
26.        current_state, path = queue.popleft()
27.        
28.        # 如果到达目标状态，返回路径
29.        if current_state[:2] == goal_state[:2] and current_state[2] == goal_state[2]:
30.            return path + [current_state]
31.        
32.        left_m, left_s, boat = current_state
33.        new_boat = 1 - boat  # 切换船所在的岸
34.        
35.        # 定义所有可能的船的移动情况
36.        moves = [
37.            (1, 0), (0, 1), (1, 1), (2, 0), (0, 2)  # (商人移动数量, 仆人移动数量)
38.        ]
39.        
40.        for move_m, move_s in moves:
41.            if boat == 1:  # 如果船在左岸
42.                new_state = (left_m - move_m, left_s - move_s, new_boat)
43.            else:  # 如果船在右岸
44.                new_state = (left_m + move_m, left_s + move_s, new_boat)
45.            
46.            # 检查新状态是否合法
47.            if is_valid(new_state) and new_state not in visited:
48.                visited.add(new_state)
49.                queue.append((new_state, path + [current_state]))
50. ​
51.    return None
52. ​
53. # 运行BFS算法
54. result = bfs()
55. ​
56. if result:
57.    print("找到安全过河方案，最少步骤为：", len(result) - 1)
58.    for step in result:
59.        print(step)
60. else:
61.    print("没有找到安全过河方案。")

复制代码

求解效果

2. 找到安全过河方案，最少步骤为： 11
3. (3, 3, 1)
4. (2, 2, 0)
5. (3, 2, 1)
6. (3, 0, 0)
7. (3, 1, 1)
8. (1, 1, 0)
9. (2, 2, 1)
10. (0, 2, 0)
11. (0, 3, 1)
12. (0, 1, 0)
13. (1, 1, 1)
14. (0, 0, 0)

复制代码

得到方案如下：
贩子和仆役最少颠末11步安全渡河。起首，一名贩子和一名仆役过河，两岸各有2名贩子和2名仆役。接着，一名仆役回到左岸，左岸有3名贩子和2名仆役。然后，两名仆役过河，左岸剩下3名贩子，右岸有3名仆役和2名贩子。接着一名仆役返回左岸，左岸有3名贩子和1名仆役。随后，两名贩子过河，左岸剩下1名贩子和1名仆役。接着一名贩子和一名仆役返回，左右岸再次各有2名贩子和2名仆役。然后两名贩子过河，左岸只剩下仆役，右岸有4名贩子和2名仆役。接着一名仆役回到左岸，左岸有1名仆役，右岸有4名贩子和1名仆役。随后两名仆役过河，右岸全部人到达。末了，一名仆役回到左岸，并带着末了的贩子和仆役安全到达右岸，完玉成部渡河过程。
题目C

四个著名的音乐人受邀成为一场音乐角逐的评委,评委席的座次安排一他们相互忍让,末了组委会不得不让他们投票选出本身心中的座次安排,如果你是组委会拿到了如下的投票效果，叨教你将怎样安排座次?(注:排在最前面的坐首席）
甲:乙丙丁甲
乙:丙甲丁乙
丙:甲丙丁乙
丁:甲丙乙丁
解：根据每个人的投票序次，为每个评委举行排序打分。排名越靠前，得分越高。假设排名第一得 3 分,排名第二得 2 分,排名第三得 1 分,排名第四得 0 分;然后将全部投票效果举行加总，得出每位评委的总分，分数高者安排在靠前的位置。
编写代码如下：

2. # 定义每位评委的投票顺序
3. votes = {
4.    '甲': ['乙', '丙', '丁', '甲'],
5.    '乙': ['丙', '甲', '丁', '乙'],
6.    '丙': ['甲', '丙', '丁', '乙'],
7.    '丁': ['甲', '丙', '乙', '丁']
8. }
9. # 初始化得分表
10. scores = {'甲': 0, '乙': 0, '丙': 0, '丁': 0}
11. # 给每个评委根据投票顺序打分
12. for voter, ranking in votes.items():
13.    # 第一名得3分，第二名得2分，第三名得1分，第四名得0分
14.    for i, candidate in enumerate(ranking):
15.        scores[candidate] += 3 - i
16. # 按得分从高到低排序
17. sorted_scores = sorted(scores.items(), key=lambda x: x[1], reverse=True)
18. # 输出最终座次安排
19. print("最终座次安排：")
20. for i, (name, score) in enumerate(sorted_scores, 1):
21.    print(f"第{i}名: {name}，得分: {score}")

复制代码

求得效果：

2. 最终座次安排：
3. 第1名: 丙，得分: 9
4. 第2名: 甲，得分: 8
5. 第3名: 乙，得分: 4
6. 第4名: 丁，得分: 3

复制代码

故应将座位安排为丙甲乙丁。