Perpustakaan Digital ITB

Huruf kanji adalah sistem huruf yang digunakan dalam bahasa Jepang. Salah satu pembeda huruf kanji dibandingkan huruf alfabet adalah huruf kanji dapat tersusun atas radikal, atau bagian kanji yang lebih kecil. Misalnya, kanji ?(rest; retire) disusun oleh radikal ?(person) dan ?(tree). Susunan ini juga membentuk suatu cerita bahwa salah satu bentuk istirahat adalah orang yang tertidur di pohon. Keterkaitan antara satu kanji, radikalnya, dan kanji yang lainnya ini dapat direpresentasikan dengan knowledge graph. Untuk memanfaatkan keterkaitan kanji dan radikal ini, algoritma pencarian rute diperlukan untuk mencari rute pembelajaran kanji. Kami menguji 3 algoritma pencarian rute, yaitu D?kstra, A*, dan Steiner Tree. Algoritma Steiner Tree memiliki waktu tempuh yang lebih cepat di antara ketiganya karena memiliki time complexity yang lebih baik. Algoritma Steiner Tree memiliki time complexity O((|MOrig|+|MDest|) ? |VerticesG|2), sementara algoritma D?kstra dan A* memiliki time complexity O((|MOrig| ? |MDest|) ? (|VerticesG|+|EdgesG|) log |VerticesG|)). Ditemukan juga bahwa optimasi Steiner Tree dengan teknik mengekstraksi langkah pembangkitan metricClosure dan dilakukan memoisasi mempercepat kinerja dari Algoritma Steiner Tree. Algoritma Steiner Tree juga memiliki jumlah simpul hasil yang lebih sedikit dibandingkan D?kstra maupun A*. Hal ini karena graf hasil Algoritma Steiner Tree dipastikan berbentuk tree atau graf tanpa cycle, sedangkan algoritma D?kstra dan A* mungkin menghasilkan graf dengan cycle.