FSM (FINITE STATE MACHINE)
Finite State Machine adalah metode perancangan sistem kontrol yang menggambarkan prinsip kerja sistem dengan menggunakan 3 hal, yaitu : State (keadaan) , Event (kejadian) , Action (aksi).
Representasi FSM:
Diagram Keadaan
Tabel Transisi Keadaan
Bagan Algorithmic State Machines
Hardware Description Language
VHDL
Verilog
ABEL
Dalam Bahasa Pemrograman biasa digunakan if-then atau switch case.
Stateflow Representasi
Diagram stateflow adalah representasi dari sebuah FSM secara grafis, dimana keadaan dan transisi-transisi dari rancangan dasar yang mem-blok sistemnya. Stateflow menmbuat representasi dari hirarky dan parallelism
A* (A STAR)
Algoritma A* adalah salah satu algorima pencarian yang cukup populer di kalangan pemrogram. Algoritma ini memberikan solusi yang cukup mangkus bagi proses pathfinding (pencarian jalan), sehingga sering digunakan dalam pembuatan perangkat lunak berjenis permainan (game).
Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list, closed list, harga (cost), halangan (unwalkable). Starting point adalah sebuah terminologi untuk posisi awal sebuah benda. A adalah simpul yang sedang dijalankan dalam algortima pencarian jalan terpendek. Simpul adalah petak-petak kecil sebagai representasi dari area pathfinding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga. open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan. Closed list adalah tempat menyimpan data simpul sebelum A yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan. Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.
Diawali dengan menempatkan A pada starting point, kemudian memasukkan seluruh simpul yang bertetangga dan tidak memilik atribut rintangan dengan A ke dalam open list. Kemudian mencari nilai H terkecil dari simpul-simpul dalam open list tersebut. Kemudian memindahkan A ke simpul yang memiliki nilai H terkecil. Simpul sebelum A disimpan sebagai parent dari A dan dimasukkan ke dalam closed list. Jika terdapat simpul lain yang bertetangga dengan A (yang sudah berpindah) namun belum termasuk kedalam anggota open list, maka masukkan simpul-simpul tersebut ke dalam open list. Simpul yang pernah dicoba dimasukkan ke dalam closed list. Hal terebut dilakukan berulangulang hingga
terdapat solusi atau tidaka ada lagi simpul lain yang berada pada open list.
Efisiensi waktu Algoritma A*
Dengan digunakannya fungsi heuristic H(n), algoritma A* dapat memfokuskan pencarian pada arah yang mendekati node tujuan. Kemudian pencarian dapat diterminasikan pada waktu node tujuan diperiksa. Hal ini dapat meminimalisasikan jumlah node yang harus diperiksa dan karena waktu yang diperlukan untuk mendapatkan jalur berbanding lurus dengan jumlah node yang diperiksa, maka waktu pencarian dapat diminimalisasikan.
Walaupun jumlah node yang diperiksa dapat diminimalisasikan, algoritma A* kasus terburuk. Pada kasus ini, sebagian besar ataupun keseluruhan node pada peta diperiksa, sehingga algoritma A* bekerja seperti algoritma Dijkstra. Ada dua hal yang dapat menyebabkan keadaan terburuk ini, yaitu keadaan sepadan dan jika jalur yang dicari tidak ditemukan.
Keadaan Sepadan Pada Algoritma A*
Jika dua atau lebih node yang diperiksa mempunyai harga f(n) yang sama, maka keadaan sepadan (He). Hal ini sangat dimungkinkan karena f(n) bergantung pada dua fungsi, yaitu fungsi G(n) dab H(n). hal ini sangat mungkiin terjadi antara node-node yang letaknya berjatuhan pada peta, dan kemungkinan besar nodde yang satu teerletak dekat node tujuan sedangkan yang lainnya terletak jauh dari node tujuan.
Gambar. Keadaan Sepadan
Karena algoritma A* memberikan prioritas berdasarkan harga F(n), maka jika keadaan sepaadan terjadi, terdapat lebih dari satu node dengan prioritas sama. Akibatnya adalah node-node tersebut akan diperiksa lebih dulu, yang mungkin node tersebut terletak berjauhan dengan node tujuan. Hal ini berakibat turunnya kinerja algoritma A*
