GADDAG - GADDAG

A GADDAG a ma'lumotlar tuzilishi Stiven Gordon tomonidan 1994 yilda harakatlarni ishlab chiqarishda foydalanish uchun taqdim etilgan Scrabble va boshqa so'zlarni yaratish o'yinlari, bu erda bunday harakatlar mavjud so'zlarga "bog'langan" so'zlarni talab qiladi. Bu ko'pincha a-dan foydalanib harakatlanishni yaratish algoritmlaridan farq qiladi yo'naltirilgan asiklik so'zlar grafigi (DAWG) tomonidan ishlatilgan Maven. Odatda an'anaviy DAWG algoritmlaridan ikki baravar tezroq, ammo tartibga solish uchun taxminan 5 barobar ko'proq joy oladi Scrabble lug'atlari.[1]

Quackle, ochiq manbali Scrabble dasturi, harakatlarni yaratish uchun GADDAG dan foydalanadi.[2]

Tavsif

GADDAG nomi DAG uchun keladi yo'naltirilgan asiklik grafik, o'zining teskari tomoni bilan prefiks qilingan.[1]

GADDAG - bu a ixtisoslashuvi Trie, boshqa GADDAGlarga davlatlar va filiallarni o'z ichiga olgan. Lug'atda har bir so'zning teskari prefiksini saqlashi bilan ajralib turadi. Bu shuni anglatadiki, har bir so'zda harflar kabi ko'p tasavvurlar mavjud; aksariyat Scrabble tartibga soluvchi lug'atlarda o'rtacha so'z 5 harfdan iborat bo'lganligi sababli, bu GADDAGni oddiy DAWG dan 5 baravar katta qiladi.

Ta'rif

Bo'sh bo'lmagan prefiks tomonidan yaratilgan lug'atdagi har qanday so'z uchun x va qo'shimchani y, GADDAG har qanday mag'lubiyat uchun to'g'ridan-to'g'ri, deterministik yo'lni o'z ichiga oladi REV(x)+y, bu erda + biriktirish operatori.

Masalan, "so'zi uchuntushuntiring, "a GADDAG qatorlarga to'g'ridan-to'g'ri yo'llarni o'z ichiga oladi

e + xplainxe + plainpxe + lainlpxe + ainalpxe + inialpxe + nnialpxe

Ushbu sozlash, unda paydo bo'lgan har qanday harf berilgan so'zni izlashga imkon beradi.

Harakatlanishda foydalaning

Har qanday harakatni yaratish algoritmi uch turdagi cheklovlarga rioya qilishi kerak:

  • Kengash cheklovlari: faqat taxtaning mavjud harflariga "ilmoq" bilan qurish mumkin, va faqat bo'sh kvadratlarga plitkalar qo'yish mumkin.
  • Raf cheklovlari: bitta javonga faqat harflar bilan plitka qo'yish mumkin.
  • Lug'at cheklovi: plitkalarni joylashtirishdan kelib chiqadigan barcha so'zlar o'yin lug'atida mavjud.

DAWG-ga asoslangan algoritmlar ikkinchi va uchinchi cheklovlardan foydalanadi: DAWG lug'at atrofida qurilgan va javondagi plitkalar yordamida o'tib ketadi. Biroq, birinchi cheklovni hal qilish muvaffaqiyatsiz tugadi: kimdir xatni "bog'lashni" xohlaydi P yilda HARPYva taxtada P dan oldin ikkita bo'sh joy mavjud, lug'atda uchinchi harf joylashgan tokchadan harflar bo'lgan barcha so'zlarni qidirish kerak. P. DAWG orqali qidirish paytida bu samarasiz, chunki uchlik orqali ko'plab qidiruvlar samarasiz bo'ladi.

Bunga GADDAG-ning prefikslarini saqlash orqali murojaat qilish kerak P GADDAG filiali, a ga tegishli barcha so'zlarni ko'radi P ularning tarkibidagi biron bir joyda va prefiksni "yuqoriga ko'tarib", rafdagi plitkalar bilan so'z hosil qilishi mumkin. Misolidan foydalanish uchun § Ta'rif bo'limini qidirib toping P chiqadi "pxe + lain". Orasidagi harflar P va + ni yuqoridan yuqoriga qo'yish mumkin P taxtada, qolganlari esa uning ostidadir (agar taxtada bo'sh joy bo'lsa).

Shuningdek qarang

Adabiyotlar

  1. ^ a b Gordon, Stiven A. (1994). "Tezroq Scrabble harakatini yaratish algoritmi" (PDF). Dasturiy ta'minot: Amaliyot va tajriba. 24 (2): 219–232. doi:10.1002 / spe.4380240205.
  2. ^ Jeyson Kats-Braun; Jon O'Laflin. "Qanday qilib Quackle Scrabble o'ynaydi". Olingan 2018-07-02.