Langsung ke konten utama

PENCARIAN BERBENTUK 




NAMA : SITI CAHYANI (16115603)
KELAS : 3KA10
DOSEN : ESSY MALAYS SARI SAKTI




Best-First Search
Sesuai dengan namanya, best-first search merupakan sebuah metode yang membangkitkan simpul dari sebuah simpul sebelumnya (yang sejauh ini terbaik di antara semua simpul yang pernah dibangkitkan). Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n)[5]. Pada best-first search jika successor digunakan, maka dikatakan algoritma mengembangkan simpul tersebut. Setiap sebuah simpul dikembangkan,
algoritma akan menyimpan setiap successor simpul n sekaligus dengan harga (cost) dan petunjuk pendahulunya yang disebut ―parent‖. Algoritma akan berakhir pada simpul tujuan, dan tidak ada lagi pengembangan simpul. Fungsi evaluasi pada best-first search dapat berupa informasi biaya perkiraan dan suatu simpul menuju ke simpul tujuan atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut. Biaya perkiraan dapat diperoleh dengan menggunakan suatu fungsi yang disebut fungsi heuristic. Pada strategi best-first search, cost
sebenarnya yaitu dari simpul awal ke simpul n, dinotasikan dengan g(n) dan fungsi heuristic
yang digunakan yaitu perkiraan\estimasi nilai dari simpul nke simpul tujuan dinotasikan dengan h(n). Algoritma yang menggunakan metode best-first search, yaitu :
§Greedy Best-First Search
§Algoritma A*Berikut akan diberikan beberapa istilah yang sering digunakan pada metode best-first search:
§Start Node adalah sebuah terminologi untuk posisi awal sebuah pencarian.
§Current Node adalah simpul yang sedang dijalankan (yang sekarang) dalam algoritma pencarian jalan terpendek.
§Kandidat (successor) adalah simpul-simpul yang berbatasan dengan current node, dengan kata lain simpul-simpul yang akan diperiksa berikutnya.
§Simpul (node) merupakan representasi dari area pencarian
§Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan.
§Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
§Goal nodeyaitu simpul tujuan.

Parent adalah current node dari successor/kandidat.

Fungsi Heuristic
Fungsi heuristic h(n)merupakan estimasi cost dari n ke simpul tujuan. Sangat penting untuk memilih fungsi Heuristic yang baik. Misalkan h*(n) merupakan cost sebenarnya dari simpul nke simpul tujuan, maka pada algoritma A* terdapat kemungkinan yang terjadi pada pemilihan fungsi Heuristic yang digunakan yaitu (Amit Gaming):
§Jika h(n)–0, sehingga hanya g(n)yang terlibat maka A* akan bekerja seperti halnya algoritma Djikstra.
§Jika h(n)≤ h*(n), maka A* akan mengembangkan titik dengan nilai paling rendah dan algoritma A* menjamin ditemukannya lintasan terpendek. Nilai h(n)terendah akan membuat algoritma mengembangkan lebih banyak simpul. Jika h(n) ≤ h*(n), maka h(n) dikatakan heuristic yang admissible.
§Jika h(n)= h*(n), maka A* akan mengikuti lintasan terbaik dan tidak akan mengembangkan titik-titik yang lain sehingga akan berjalan cepat. Tetapi hal ini tidak akan terjadi pada semua kasus. Informasi yang baik akan mempercepat kinerja A*.
§Jika h(n)≥ h*(n), maka A* tidak menjamin pencarian rute terpendek, tetapi berjalan dengan cepat.
§Jika h(n) terlalu tinggi relative dengan g(n) sehingga hanya h(n) yang bekerja maka A* berubah jadi Greedy Best First Search.
Algoritma pencarian lokal untuk masalah optimisasi kombinatorik biasanya
digunakan pada pseudopolynomial running time dan algoritma polynomial-time sering tidak dapat menemukan solusi optimum lokal untuk masalah optimisasi NP−hard. Penelitian ini bertujuan mengenalkan konsep optimalitas
-lokal dan menunjukkan bahwa optimum
-lokal dapat diidentifikasi dengan waktu polyno-mial pada masalah ukuran dan bilamana hubungan ketetanggan dapat dicaridengan polynomial time untuk ε >0. Akibatnya, masalah optimisasi kombi-natorial memiliki banyak pola pendekatan polynomial-time jika dan hanya jika
memiliki fully polynomial-time pola tambahan (augmentation).



Referensi


Komentar

Postingan populer dari blog ini

KEPERCAYAAN (manusia dan keadilan) Adil kata itu sering kita dengar dikalangan masyarakat dan di kehidupan sehari hari banyak yang mengatakan hidup ini tidak adil ada yang kaya dan ada yang miskin ada yang menindas dan ada yang terdindas, ada yang di sayang dan tidak disayang sering kali kita mendengar kata itu pernahkan kalian merasakan itu, janganlah dipungkiri terkadang kita merasakan itu di dalam keluarga, dulu waktu masih kecil kita mengatakan kenapa kedua orang tua lebih sayang terhadap kakak dari pada adik, sebenarnya tidak seperti itu orang tua tidak pernah membedakan antara kakak dan adik di dalam keluarga, mungkin ada sesuatu yang tidak adik ketahui dan belum mengetahui. Sebenarnya apa sih arti dari keadilan itu Keadilan memberikan kebenaran, ketegasan dan suatu jalan tengah dari berbagai persoalan juga tidak memihak kepada siapapun. Dan bagi yang berbuat adil merupakan orang yang bijaksana. Bukan hal yang sulit untuk memberikan rasa adil ter Kenapa kakak lebih ...

Tugas 1 : Audit Teknologi Sistem Informasi#

Nama : Siti Cahyani NPM : 16115603 Kelas : 4KA10 Dosen : Robby Chandra 1. Apa yang dimaksud dengan teknologi sitem informasi? Apa fungsi dan manfaat dari teknologi sistem informasi? Jelaskan! Jawab : Teknologi Sistem Informasi (tsi)  adalah  technology information system  yaitu teknologi yang tidak terbatas pada penggunaan sarana komputer, tetapi meliputi  pemrosesan data , aspek  keuangan , pelayanan jasa sejak perencanaan, standar dan prosedur, serta  organisasi  dan pengendalian sistem  catatan (informasi) . Teknologi Sistem Informasi sangat mempunyai banyak fungsi dan manfaat seperti dibawah ini: 1. Capture (Menangkap) Proses penyusunan rekord aktifitas yang terperinci. 2. Processing (Mengolah) Mengolah/memproses data masukkan yang diterima untuk menjadi suatu informasi. Pengolahan atau pemrosesan dapat berupa pengubahan data ke bentuk lain (konversi), analisis kondisi (analisis), perhitungan (kalkulasi), pengga...
BOLEHKAH KITA BERPENDAPAT  (manusia dan pandangan hidup) Setiap manusia mempunyai pandangan hidup. Pandangan hidup itu bersifat wajari. Karena itu menentukan masa depan seseorang. Untuk itu perlu dijelaskan pula apa arti pandangan hidup. Pendapat atau pertimbangan yang dijadikan pegangan, pedoman, arahan, petunjuk hidup di dunia. Pendapat atau pertimbangan itu merupakan hasil pemikiran manusia berdasaikan pengalaman sejarah menurut waktu dan tempat hidupnya. Pandangan Hidup merupakan suatu dasar atau landasan untuk membimbing kehidupan jasmani dan rohani. Pandangan hidup ini sangat bermanfaat bagi kehidupan individu, masyarakat, atau negara. Semua manusia pasti mempunyai suatu pandangan hidup sendiri – sendiri dan kemungkinan berbeda antara yang satu dengan yang lainnya. Tak sedikit pula orang yang mempunyai pandangan hidup yang sangat bertentangan dengan pandangan hidup orang yang lainnya, itulah yang sering memicu perdebatan diantara umat manusia dalam kehid...