heuristic suite

Suite heuristik

Catatan penting

Proyek ini tidak lagi dalam pemeliharaan. Silakan kunjungi Linq ke* untuk versi terbaru.

Ringkasan

Heuristic Suite adalah implementasi eksperimental dari serangkaian algoritma heuristik dalam pemrograman generik. Proyek ini bertujuan untuk menyediakan infrastruktur yang dapat diterapkan pada teka -teki apa pun - selama teka -teki dapat diselesaikan dengan algoritma.

Algoritma yang diimplementasikan:

• A*
• Inerative mendalam A* (Ida*)
• Pencarian Pertama Terbaik
• Pencarian Pertama Terbaik Rekursif (RBFS)

Implementasi ini sepenuhnya berorientasi pada objek dan mengambil keuntungan dari mekanisme perbandingan kerangka kerja .NET built-in seperti Icomparer (T) dan IequalityComparer (T) untuk menciptakan kompatibilitas yang hebat dengan standar .NET dan seluruh ekosistem .NET. Kode sumber dapat dengan mudah dibawa ke platform lain seperti Unity dan Xamarin.

Memecahkan teka -teki dengan algoritma

Untuk menerapkan algoritma ke teka -teki, diperlukan implementasi berikut:

1. Definisi Langkah Jenis yang mendefinisikan langkah teka -teki akan diperlukan untuk mengimplementasikan antarmuka ISTEP (TKEY). Properti Key melayani dua tujuan:

   • Untuk menguji apakah dua langkah setara. Misalnya: Posisi yang sama di papan tulis.
   • Untuk membandingkan dua langkah untuk menentukan skor mana yang lebih baik. Misalnya: Jarak antara posisi A dan tujuan, dan jarak antara posisi B dan sasaran, semakin dekat skor lebih baik.

2. Langkah perbandingan langkah dibandingkan satu sama lain berdasarkan properti Key untuk menentukan skor mana yang lebih baik. Perbandingan dapat dilakukan dengan salah satu cara berikut:

   • Implementasi Icomparable (TKey).
   • Instance icomparer (tkey) yang disesuaikan.
   • Fungsi h (n) yang diberikan secara eksplisit di mana parameter n adalah Key .

3. Langkah -langkah yang tersedia dari langkah saat ini, Informasi Langkah Berikutnya dapat disediakan dengan mengimplementasikan antarmuka INextStepFactory(TKey, TStep) , atau menyediakan delegasi NextStepFactory .

Setelah itu, algoritma dapat dijalankan dengan memohon metode FindSolution dengan from dan langkah -langkah goal sebagai parameter. Jika solusinya ada, masing -masing langkah dapat diperoleh dengan memanggil metode Enumerate . Langkah -langkah dapat menjadi Reverse sebelum enumerasi dimulai.

Perbandingan heuristik dan perbandingan heuristik yang terpisah

Proyek ini menyediakan HeuristicComparer dan DiscreteHeuristicComparer untuk berbagai skenario perbandingan langkah.

• Jika properti Key dapat secara langsung dibandingkan satu sama lain tanpa fungsi H (n) eksplisit, secara default, DiscreteHeuristicComparer akan digunakan untuk perbandingan langkah yang lebih cepat.
• Jika fungsi h (n) secara eksplisit diperlukan untuk membandingkan masing -masing langkah, HeuristicComparer akan digunakan untuk melakukan estimasi tradisional f (n) = g (n) + h (n) .

Preferensi fungsi heuristik

Pencacahan HeuristicFunctionPreference memungkinkan pengguna untuk mengubah keseimbangan estimasi f (n) = g (n) + h (n) . Ketika dua langkah dievaluasi skor yang sama, enumerasi memutuskan fungsi mana, g (n) atau h (n) , akan dipertimbangkan terlebih dahulu. Keseimbangan yang berubah dapat mempengaruhi perilaku algoritma heuristik.

Contoh

• Path Find (Algorithmforce.example.pathfinding)

  Contohnya menunjukkan teka -teki paling umum dan tradisional yang menggunakan algoritma heuristik untuk dipecahkan.

• 8-Puzzle (Algorithmforce.example.eightpuzzle)

  Contohnya menunjukkan cara menyelesaikan 8-puzzle dengan algoritma heuristik. Langkah -langkah awal dan sasaran teka -teki ditunjukkan di bawah ini:

• Koin membalik puzzle (algorithmforce.example.plipping)

  Contoh ini menunjukkan bagaimana game AI memecahkan koin membalik teka -teki. Dalam teka -teki, hanya sepasang koin yang berdekatan yang dibiarkan terbalik pada saat yang sama. Semua sepuluh koin yang merupakan kepala adalah tujuannya. Teka -teki ini terinspirasi oleh brilliant.org.

Lebih banyak contoh akan ditambahkan di masa depan.

Platform

Proyek saat ini menargetkan .NET Core dan .NET Framework 4.5 atau di atas.