Bài giảng Thuật toán ứng dụng - Bài 2: Knapsac - Đỗ Tuấn Anh
TAXI
KNAPSAC
BCA
Thuật toán ứng dụng
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung
TA: Trần Thanh Tùng
Viện Công Nghệ Thông Tin và Truyền Thông
Trường Đại học Bách Khoa Hà Nội
Tháng 3, năm 2020
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
1 / 23
TAXI
KNAPSAC
BCA
Mục lục
1
2
3
TAXI
KNAPSAC
BCA
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
2 / 23
TAXI
KNAPSAC
BCA
Lịch sử
Nêu ra lần đầu tiên năm 1930 về tối ưu hóa
Dưới dạng bài toán “The Saleman Problem”
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
3 / 23
TAXI
KNAPSAC
BCA
Phát biểu bài toán
Một tài xế Taxi xuất phát từ điểm 0, và nếu khoảng
cách giữa hai điểm bất kỳ được biết thì đâu là đường
đi ngắn nhất mà người Taxi có thể thực hiện sao cho đi
hết tất cả các điểm mỗi điểm một lần để quay về lại
điểm A.
Đầu vào : khoảng cách giữa các điểm, tài xế Taxi xuất
phát từ điểm 0, và có n điểm từ 1, 2, 3, ..n cần đi qua.
Đầu ra : đường đi ngắn nhất 0 → i → j. . . → 0
Dưới dạng đồ thị : bài toán người lái taxi được mô hình
hóa như một đồ thị vô hướng có trọng số, trong đó mỗi
điểm đến là một đỉnh của đồ thị, đường đi từ một điểm
đến điểm khác là khoảng cách hay chính là độ dài
cạnh.
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
4 / 23
TAXI
KNAPSAC
BCA
Tổng quãng đường đi từ
0 → 2 → 4 → 1 → 3 → 0 = 8 + 4 + 15 + 10 + 4 = 51
Tổng quãng đường đi từ
0 → 1 → 4 → 2 → 3 → 0 = 9 + 15 + 4 + 8 + 4 = 40
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
5 / 23
TAXI
KNAPSAC
BCA
Ứng dụng
Lập kế hoạch như bài toán Taxi là tối ưu trong quãng
đường phục vụ, bài toán Người bán hàng,. . .
Thiết kế vi mạch → Tối ưu về đường nối, điểm hàn
Trong lĩnh vực phân tích gen sinh học
Trong lĩnh vực du lịch
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
6 / 23
TAXI
KNAPSAC
BCA
TAXI
Có n hành khách được đánh số từ 1 tới n.
Có 2n + 1 địa điểm được đánh số từ 0 tới 2n
Hành khách thứ i muốn đi từ địa điểm thứ i đến địa
điểm thứ i + n
Taxi xuất phát ở địa điểm thứ 0 và phải phục vụ n hành
khách và quay lại địa điểm thứ 0 sao cho không điểm
nào được đi lại 2 lần và tại một thời điểm chỉ có 1 hành
khách được phục vụ.
Cho khoảng cách giữa các địa điểm. Tính quãng
đường nhỏ nhất mà tài xế Taxi phải đi.
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
7 / 23
TAXI
KNAPSAC
BCA
Thuật toán
Nhận xét với mỗi cách chọn đường đi ta sẽ ánh xạ về
được một hoán vị từ 1 đến n.
Ta duyệt hết n! hoán vị.
Với mỗi hoán vị tính toán khoảng cách phải di chuyển.
Độ phức tạp thuật toán O(n! ∗ n), có thể cải tiến xuống
O(n!) hoặc thậm chí O(2n ∗ n2).
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
8 / 23
TAXI
KNAPSAC
BCA
Công thức
Gọi c[i][j] là khoảng cách di chuyển từ địa điểm i đến
địa điểm j
Gọi một hoán vị có dạng a1, a2, ..., an
P
P
c[ai][ai + n] + n−1 c[ai + n][ai+1] +
n
Công thức :
i=1
i=1
c[0][a1] + c[an + n][0]
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
9 / 23
TAXI
KNAPSAC
BCA
Code
1
2
3
int calc(int a[]) {
// tra ve chi phi di chuyen cua hoan vi
// tinh theo cong thuc da neu
a
4
5
}
6
7
8
int main ()
Nhap
{
9
n
10
11
12
13
14
15
16
17
18
19
20
21
Nhap ma tran c[i][j]
Khoi tao hoan vi a[]
=
{1, 2, ... , n}
answer
=
INF
{
=
while (1)
cost
calc(a)
if (a == {n, n - 1, ... , 1}) {
break;
}
a
=
next_permutation (a)
}
In ra answer
}
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
10 / 23
TAXI
KNAPSAC
BCA
KNAPSAC
Một nhà thám hiểm cần đem theo một cái túi có trọng
lượng không quá m.
Có n đồ vật có thể đem theo.
Đồ vật thứ i có trọng lượng ai và giá trị sử dụng ci.
Hỏi nhà thám hiểm cần đem theo những đồ vật nào để
cho tổng giá trị sử dụng là lớn nhất mà tổng trọng
lượng đồ vật mang theo cái túi không vượt quá m ?
Ghi ra duy nhất một số là tổng giá trị lớn nhất tìm được
của các đồ vật cho vào túi.
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
11 / 23
TAXI
KNAPSAC
BCA
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
12 / 23
TAXI
KNAPSAC
BCA
Ứng dụng
Xếp đồ đi du lịch
Xếp hàng trong lĩnh vực vận chuyển hàng hóa
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
13 / 23
TAXI
KNAPSAC
BCA
Thuật toán 1
Mỗi cách chọn lấy các đồ vật tương ứng với một dãy
nhị phân độ dài n. bit thứ i là 0/1 tương ứng là không
lấy/có lấy đồ vật thứ i.
Duyệt hết các xâu nhị phân độ dài n và tìm nghiệm tốt
nhất.
Để xét hết các xâu nhị phân độ dài n, có thể dùng đệ
quy - quay lui hoặc chuyển đổi giữa thập phân với nhị
phân.
Độ phức tạp O(2n × n)
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
14 / 23
TAXI
KNAPSAC
BCA
Code 1
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
main (){
Nhap n,
Nhap mang a,
answer 0;
for (int mask
int sum_weight
for (int 0;
if (mask >>
m
c
=
=
1
<< n; mask --;
=
)
0, sum_value
{
=
// mask
0;
= 0..2^n
i
=
i
i
<
&
n; ++i)
1){ // bit thu
i
= 1
sum_weight += a[i];
sum_value += c[i];
}
if ( sum_weight <= m)
ans max(ans , sum_value );
=
}
In ra answer
}
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
15 / 23
TAXI
KNAPSAC
BCA
Thuật toán 2
Chia tập đồ vật làm hai phần A và B. Mỗi cách chọn
lấy các đồ vật tương ứng với một cách lấy bên A kết
hợp với một cách lấy bên B.
Ý tưởng chính ở đây là lưu trữ hết các cách lấy bên B
và sắp xếp trước theo một thứ tự. Sau đó với mỗi cách
lấy bên A, ta có thể tìm kiếm nghiệm tối ưu bên B một
cách nhanh chóng.
Giả sử cách lấy tối ưu là lấy mA bên A và mB bên B, ta
sẽ xét tuần tự từng mA một và tìm kiếm nhị phân mB.
Độ phức tạp O(2A × log(2B) + 2B) = O(2n/2 × n) nếu
chọn |A| = |B| = n / 2
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
16 / 23
TAXI
KNAPSAC
BCA
Code 2
S1, S2 là tập các cách lấy bên A, bên B có 2 tham số
là khối lượng (w), giá trị (v) và đã được sort lại theo
tham số khối lượng (w).
maxValue[j] = max{S2[0].w, S2[1].w, ..., S2[j].w}
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
17 / 23
TAXI
KNAPSAC
BCA
Code 2
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int get_position (int S2[], int max_weight )
// tra ve vi tri cuoi cung cua S2 ma co S2.w <= max_weight
{
// tra ve -1 trong truong hop S2 [0]. w
>
max_weight
}
int main
Nhap n,
Nhap mang a,
Tinh S1 , S2 theo code
{
m
c
1
answer
for(int
=
-INF;
0;
i
=
i
<
S1. size (); i++){
// lay vi tri lon nhat co the
get_position (S2 , S1[i].w)
if (j != -1){
answer
j
=
m -
=
max(answer , S1[i].v
+
max_value[j]);
}
}
In ra answer
}
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
18 / 23
TAXI
KNAPSAC
BCA
BCA (Balanced Academic Curriculum)
Mỗi đầu học kỳ các bộ môn phải thực hiện phân công
giảng dạy đều cho các giảng viên.
Có n khóa học và m giáo viên, mỗi giáo viên có danh
sách các khóa có thể dạy.
Có danh sách các khóa học không thể để cùng một
giáo viên dạy do trùng giờ.
Load của một giáo viên là số khóa học phải dạy của
giáo viên đó.
Yêu cầu : Tìm cách xếp lịch cho giáo viên sao cho
Load tối đa của các giáo viên là tối thiểu.
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
19 / 23
TAXI
KNAPSAC
BCA
Giảng viên : Đỗ Tuấn Anh, Lê Quốc Trung TA: Trần ThThuật toán ứng dụng
Tháng 3, năm 2020
20 / 23
Tải về để xem bản đầy đủ
23 trang
15540
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thuật toán ứng dụng - Bài 2: Knapsac - Đỗ Tuấn Anh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thuat_toan_ung_dung_bai_2_knapsac_do_tuan_anh.pdf
