Bagaimana cara menerapkan algoritma AO *?

16

Saya telah memperhatikan bahwa struktur data yang berbeda digunakan ketika kita menerapkan algoritma pencarian. Sebagai contoh, kami menggunakan antrian untuk melaksanakan luasnya pertama pencarian, tumpukan untuk melaksanakan pencarian mendalam-pertama dan min-tumpukan untuk menerapkan A * algoritma . Dalam kasus ini, kita tidak perlu membangun pohon pencarian secara eksplisit.

Tapi saya tidak dapat menemukan struktur data sederhana untuk mensimulasikan proses pencarian dari AO * algoritma . Saya ingin tahu apakah membangun pohon pencarian eksplisit adalah satu-satunya cara untuk menerapkan AO * algoritma? Ada yang bisa memberikan saya implementasi yang efisien?

algorithms graphs data-structures search-algorithms Zhang
sumber
3
Selamat datang! Harap ingat untuk menyertakan referensi ke materi non-standar yang Anda gunakan. Sebagai AO * belum ada artikel Wikipedia, link tentu dalam rangka. Saya harap saya menemukan yang baik, silakan cek.
Raphael
1
Bukan hanya grafik (dengan fungsi yang memungkinkan seseorang untuk pindah ke node "berikutnya")?
soandos
itu akan membantu jika seseorang hanya menggambarkan bagaimana AO * berbeda dari algoritma A *. tidak bisa mengetahuinya dari tautan. untuk implementasi, struktur apa pun untuk pohon tampaknya masuk akal .... itu melintasi pohon, kan?
vzn

Jawaban:

1

Mengenai ini artikel setiap kali Anda memperluas node di AO * algoritma Anda harus pergi ke belakang untuk memperbarui semua perkiraan biaya pendahulunya.

Bila Anda menggunakan struktur data linear mengandung kelenjar Anda harus melintasi elemen data secara berurutan dan hanya satu elemen data bisa langsung diambil (stack, queue, prioritas antrian ...).

Dalam AO * setiap kali node diambil untuk ekspansi berdasarkan biaya memperkirakan iterates algoritma di atas semua node yang pendahulunya (untuk memperbarui perkiraan biaya mereka). Itu berarti bahwa kadang-kadang Anda harus mengambil elemen berdasarkan biaya estimasi dan kadang-kadang berdasarkan penggantinya. Tidak ada urutan urutan yang dapat memenuhi kedua kondisi ini dalam kasus umum. Mungkin ada cara untuk menggunakan "bersarang" struktur data linear, tetapi hanya harus meniru struktur pohon, dan akan lebih baik untuk membangun pohon pencarian sebagai gantinya.

Anton
sumber
0

Aku hanya pergi deskripsi Anda terhubung ke, tapi bagaimana BST? Anda mungkin bisa membangun itu untuk mengimbangi node yang belum terpecahkan. Itu bisa menghemat waktu pada langkah 2, dan akan membantu menjaga waktu keseluruhan turun tergantung pada jumlah traversals. Tentu saja, jika Anda seimbang / diurutkan pohon Anda sesuai dengan node yang belum terpecahkan, Anda mungkin akan setidaknya lebih baik dari struktur data yang lebih sederhana, berpotensi tetap / waktu sekitar logaritmik.

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Univ426
sumber
2
Dan dapat Anda lakukan ini?
Raphael
yang tidak begitu jelas kepada saya bagaimana BST yang akan digunakan karena BSTs memiliki indeks numerik untuk setiap node & digunakan untuk menempatkan mereka. apa adalah indeks numerik digunakan?
vzn