一个农夫带着一头狼、一头羊、一颗白菜过河。他面前只有一条船,只能容纳他和一件物品,只有农夫会划船。如果农夫不在场,狼会吃羊、羊会吃白菜,农夫在场则不会。求将所有物品运到对岸的方案。

图论-安全过河的最短路径问题

原博客

农夫过河问题

问题描述

一个农夫带着一头狼、一头羊、一颗白菜过河。他面前只有一条船,只能容纳他和一件物品,只有农夫会划船。如果农夫不在场,狼会吃羊、羊会吃白菜,农夫在场则不会。求将所有物品运到对岸的方案。

解题思路

根据物品的位置定义状态,若在左岸记为1,右岸记为0,于是最终方案就是(1,1,1,1)–>(0,0,0,0)所经过的路径。

1、定义状态

2、列举所有状态(人、狼、羊、菜)

3、删除不合理的状态(狼和羊、羊和菜)

4、连边(模拟一次渡河)

5、寻找路径

寻找(1111)–>(0000)的边,可以用寻路算法如bfs、dfs,如果要求最短路可以用最短路算法如bfs、Dijsktra等,当然这里图很简单,可直接观察出来。

1
2
3
4
5
6
7
8
9
10
(1111)-->(0101)-->(1101)-->(0001)-->(1011)-->(0010)-->(1010)-->(0000)(两条最短路之一)
左岸 右岸
1、人 狼 羊 花 空
2、狼 花 人 羊
3、人 狼 花 羊
4、花 人 狼 羊
5、人 羊 花 狼
6、羊 人 花 狼
7、人 羊 狼 花
8、空 狼 花 人 羊

传教士与吃人恶魔的问题

问题描述

有三个传教士和三个吃人恶魔要渡过一条河,河中有一条船,只能装下两个人。在任何地方(无论是岸边还是船上),如果吃人恶魔数量多于传教士数量,吃人恶魔就会吃掉传教士。问:怎么才能让这些都安全过河?

解题思路

1、定义状态

2、列举所有状态

3、删除不合理状态

4、连边(模拟依次渡河变化)

5、寻找路径

寻找(33 L 00)–>(00 R 33)的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
其中一条路径
(33 L 00)-->(31 R 01)-->(32 L 01)-->(30 R 03)-->(31 L 02)-->(11 R 22)-->(22 L 01)-->(02 R 31)-->(03 L 30)-->(01 R 32)-->(02 L 31)-->(00 R 33)
1、两个吃人恶魔过河
2、一个吃人恶魔回来
3、两个吃人恶魔过河
4、一个吃人恶魔回来
5、两个传教士过河
6、一个传教士和一个吃人恶魔回来
7、两个传教士回来
8、一个吃人恶魔回去
9、两个吃人恶魔过河
10、一个吃人恶魔回去
11、两个吃人恶魔过河

四人过桥问题

问题描述

在一个漆黑的夜里,四位旅游者来到一座狭窄而没有护栏的桥边,如果不借助手电筒的话,大家是无论也不敢过去。不幸的是四个人中只有一只手电筒,而桥窄得只够两个人同时通过。如果各自单独过桥得话,四个人所需要的时间分别是1、2、5、10分钟,如果两个人同时过桥,所需要的时间是较慢的那个人单独行动时的时间。问:如何设计一个方案,让四个人尽快过桥。

解题思路

与前面两个相比,这次不仅要求方案,同时要求时间最短。

同样需要定义状态,四个人+手电筒的位置

1、定义状态

2、建图

分为每次通过一个人和每次两个人,都是带权无向边。

(下面只连接了与(01111)的边)

3、寻找最短路

寻找(L 1111)–>(R 0000)的最短路,即最短路算法中(01111)–>(10000)的最短路,以下是利用Dijstra算法的解决方法。

最终答案为(2 + 1 + 10 + 2 + 2) = 17.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<stdio.h>
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

//定义图中结点
struct Node
{
int u, d; //该节点的编号与距离
bool operator < (const Node x) const
{
return d > x.d;
}
};

//边结构体的定义
struct Edge
{
int to;
int w;
int next;
};

const int INF = 0x3f3f3f3f;
const int V = 32 + 10;
const int E = 32 * 32 + 10;
int dis[V]; //源到各顶点的最短距离
int vis[V]; //记录是否被收录,用来代替集合S
int head[V]; //head[i]表示顶点i的第一条边的数组下标,"-1"表示顶点i没有边
Edge edge[E];

inline void AddEdge(int a, int b, int w, int id)
{
edge[id].to = b;
edge[id].w = w;
edge[id].next = head[a];
head[a] = id;
return;
}

//s为起点
void Dijsktra(int s)
{
priority_queue<Node>q; //取出集合T中的最小值
memset(vis, 0, sizeof(vis));
memset(dis, INF, sizeof(dis));

dis[s] = 0;
q.push(Node{ s, dis[s] });
while (!q.empty())
{
Node x = q.top(); q.pop();
int u = x.u;

if (vis[u]) continue;

vis[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) //松弛与u直接相邻的顶点
{
int v = edge[i].to;
int w = edge[i].w;
if (!vis[v] && dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
q.push(Node{ v,dis[v] });
}
}
}
}

const int score[] = { 1,2,5,10 }; //每个人单独行动的时间

int main()
{
//建图
memset(head, -1, sizeof(head));
int id = 0;
for (int i = 0; i < (1 << 4); i++)
{
int bits[4];
for (int j = 0; j < 4; j++) bits[j] = (i >> j) & 1;
//一次走一个人
for (int j = 0; j < 4; j++) if (bits[j])
{
int tmp = i - (1 << j) + 16;
int w = score[j];
AddEdge(i, tmp, w, id++);
AddEdge(tmp, i, w, id++);
}
//一次走两个人
for(int j = 0;j < 3;j++)
for (int k = j + 1; k < 4; k++) if (bits[j] && bits[k])
{
int tmp = i - (1 << j) - (1 << k) + 16;
int w = max(score[j],score[k]);
AddEdge(i, tmp, w, id++);
AddEdge(tmp, i, w, id++);
}
}
Dijsktra(15);
printf("%d\n", dis[16]);

return 0;
}

留言

⬆︎TOP