SOAL DAN JAWABAN PENGANTAR KECERDASAN BUATAN (PIB)

 SOAL DAN JAWABAN 

Dalam sebuah perusahaan, seorang sales hari itu harus melakukan pengantaran barang ke beberapa kota.  Dalam prakteknya sales tersebut mendapatkan uang transportasi. Untuk menghemat agar terdapat sisa uang transportasi, maka sales tersebut berfikir keras. Bagaimana caranya?

Kota-kota yang harus dikunjungi dan jaraknya seperti terlihat pada gambar berikut :


Lakukan perhitungannya dengan menggunakan metode :

Gambar 1. Lintasan yang harus di kunjungi

1.      Generate And Test
2.      Hill Climbing
3.      Simple Hill Climbing
4.      Steepest Hill Climbing

      Jawaban :

1.      Generate And Test

Gambar 2. Tree Lintasan yang bisa ditempuh 

Dari gambar di atas, maka dapat dibuatkan tabel lintasannya yang dapat dilihat seperti pada Tabel 1.

LINTASAN B						LINTASAN A
Pencarian Ke	Lintasan	Panjang Lintasan	Lintasan Terpilih	Panjang		Pencarian Ke	Lintasan	Panjang Lintasan	Lintasan Terpilih	Panjang
1	ABCD	12	12	ABCD		1	ABCD	10	ABCD	10
2	ABDC	9	9	ABDC		2	ABDC	6	ABDC	6
3	ACBD	6	6	ACBD		3	ACBD	9	ABDC	6
4	ACDB	7	6	ACBD		4	ACDB	8	ABDC	6
5	ADBC	7	6	ACBD		5	ADBC	8	ABDC	6
6	ADCB	11	6	ACBD		6	ADCB	11	ABDC	6
7	BACD	9	6	ACBD		7	BACD	7	ABDC	6
8	BADC	10	6	ACBD		8	BADC	7	ABDC	6
9	BCAD	7	6	ACBD		9	BCAD	10	ABDC	6
10	BCDA	11	6	ACBD		10	BCDA	11	ABDC	6
11	BDAC	4	4	BDAC		11	BDAC	6	ABDC	6
12	BDCA	7	4	BDAC		12	BDCA	8	ABDC	6
13	CABD	5	4	BDAC		13	CABD	5	CABD	5
14	CADB	4	4	BDAC		14	CADB	6	CABD	5
15	CBAD	9	4	BDAC		15	CBAD	8	CABD	5
16	CBDA	7	4	BDAC		16	CBDA	8	CABD	5
17	CDAB	10	4	BDAC		17	CDAB	7	CABD	5
18	CDBA	9	4	BDAC		18	CDBA	6	CABD	5
19	DABC	9	4	BDAC		19	DABC	8	CABD	5
20	DACB	7	4	BDAC		20	DACB	10	CABD	5
21	DBAC	5	4	BDAC		21	DBAC	5	CABD	5
22	DBCA	6	4	BDAC		22	DBCA	9	CABD	5
23	DCAB	9	4	BDAC		23	DCAB	8	CABD	5
24	DCBA	12	4	BDAC		24	DCBA	10	CABD	5

Cek lintasan paling kiri, hitung panjang lintasannya dan masukkan ke dalam tabel. 

Setelah itu hitung lintasan di sebelahnya, apakah lebih kecil, kalau lebih kecil jadikan LINTASAN TERPILIH. 
Ulangi terus untuk lintasan sebelah kananya sampai dengan semua lintasan di cek.

Jadi terlihat bahwa pada Lintasan B, lintasan terpendek untuk melintasi semua kota adalah B - D - A - C, sedangkan pada Lintasan A, yang terpendek adalah rute C- A - B - D


2. Hill Climbing

LINTASAN B

LINTASAN A

Pencarian Ke

LINTASAN

Panjang Lintasan

Pencarian Ke

LINTASAN

Panjang Lintasan

1

A

B

C

D

12

1

A

B

C

D

10

2

A

B

D

C

9

2

A

B

D

C

6

3

A

C

B

D

6

3

A

C

B

D

9

4

A

C

D

B

7

4

A

C

D

B

8

5

A

D

B

C

7

5

A

D

B

C

8

6

A

D

C

B

11

6

A

D

C

B

11

7

B

A

C

D

9

7

B

A

C

D

7

8

B

A

D

C

10

8

B

A

D

C

7

9

B

C

A

D

7

9

B

C

A

D

10

10

B

C

D

A

11

10

B

C

D

A

11

11

B

D

A

C

4

11

B

D

A

C

6

12

B

D

C

A

7

12

B

D

C

A

8

13

C

A

B

D

5

13

C

A

B

D

5

14

C

A

D

B

4

14

C

A

D

B

6

15

C

B

A

D

9

15

C

B

A

D

8

16

C

B

D

A

7

16

C

B

D

A

8

17

C

D

A

B

10

17

C

D

A

B

7

18

C

D

B

A

9

18

C

D

B

A

6

19

D

A

B

C

9

19

D

A

B

C

8

20

D

A

C

B

7

20

D

A

C

B

10

21

D

B

A

C

5

21

D

B

A

C

5

22

D

B

C

A

6

22

D

B

C

A

9

23

D

C

A

B

9

23

D

C

A

B

8

24

D

C

B

A

12

24

D

C

B

A

10

3. Simple Hill Climbing

Gambar 3. Tree Simple Hill Climbing

Langkahnya adalah :
Lakukan penukaran 2 kota yang berdekatan dan tuliskan panjang lintasannya.
Cek panjang lintasan pada ROOT dan bandingkan dengan lintasan terkiri, kalau lintasan terkiri lebih kecil dari lintasan di atasnya, maka gunakan sebagai patokan pencarian berikutnya. Tetapi kalau tidak lebih kecil, cek lintasan dikanannya, apakah ada yang lebih kecil dari lintasan di atasnya ? kalo ada gunakan itu.

Demikian seterusnya sampai dengan lintasan di bawahnya tidak ada yang lebih kecil dari yang dipilih.

Jadi terlihat pada gambar bahwa lintasan terpendek dari Lintasan B yang bisa diambil rutenya adalah dari Kota B - D - A - C , sedangkan lintasan terpendek dari Lintasan A yang bisa diambil rutenya adalah dari Kota D - B - A - C

4.      Steepest Hill Climbing

Gambar 4. Tree Steepest Hill Climbing

Terlihat bahwa lintasan yang harus ditempuh untuk jarak minimalnya untul lintasan B adalah : C à A à D à B, sedangkan untuk lintasan A, rute terpendeknya adalah : D - B - A - C