MTE3104 Matematik Keputusan
Algoritma Heuristik
Latihan Algoritma Heuristik
1. Dengan menggunakan kertas graf dan kertas berwarna, tunjukkan penyelesaian kepada masalah bin-packing pada m.s. 8 hingga 9 dalam buku D1 berdasarkan algoritma berikut:
(a) first-fit
(b) first-fit decreasing
(c) full bins
2. Dengan merujuk kepada m.s. 8 hingga 10 dalam buku D1, tentukan keberkesanan relatif algoritma first-fit, first-fit decreasing dan full bins untuk masalah berikut:
(a) bin-packing problem
(b) plumbing problem
(c) ferry loading problem
(d) disc storage problem
Nyatakan kelebihan/kelemahan setiap algoritma heuristik di atas.
3. Jadual berikut menunjukkan tempoh beberapa aktiviti dalam satu projek.
Aktiviti
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
Tempoh (hari)
|
8
|
7
|
5
|
6
|
5
|
6
|
9
|
4
|
7
|
9
|
8
|
6
|
Dengan menggunakan satu algoritma packing yang sesuai, tentukan bilangan pekerja yang diperlukan untuk menyempunakan tugas dalam 12 hari.
4. Dalam perjalanan balik dari Kuala Lumpur, Mazura dan keluarganya ingin membawa bilangan beg bagasi yang seminima mungkin. Setiap beg bagasi mestilah mempunyai jisim kurang daripada 22 kg. Mereka telah membungkuskan barang-barang mereka dalam 12 bungkusan.
Bungkusan
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
Jisim (kg)
|
8
|
12
|
14
|
6
|
6
|
6
|
6
|
14
|
8
|
4
|
8
|
4
|
Berapakah beg bagasi yang diperlukan?
5. Chong ingin merakamkan program telesisyen berikut. Dia mempunyai empat pita video yang setiap satunya dapat merakam program selama180 minit. Tempoh program adalah seperti dalam jadual berikut.
Program
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
Jisim (kg)
|
90
|
35
|
105
|
90
|
120
|
45
|
60
|
100
|
Adakah semua program dapat dirakamkan? Bagaimana ia dilakukan?
Jawapan:
1. Rujuk buku D1 4. 5 beg bagasi
2. Rujuk buku D1 5. Ya. Full bin/first-fit decreasing
3. 8 orang pekerja
