ГАДДАГ
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
ГАДДАГ је структура података презентована од стране Стивена Гордона 1994, да би се користила за генерисање потеза уСцраббле и другим сличним игрицама у којима потези захтевају да се речи уградјују у друге речи. Често је контраст алгоритмима који користе Дирецтед Ацyцлиц Wорд Грапх (ДАWГ), као у игрици Мавен. Генерално је дупло бржи од традиционалних ДАWГ алгоритама, али је потребно 5 пута више простора за регулисање Сцраббле речника.[1]
- Qуацкле користи ГАДДАГ за генерисање потеза.
Опис[уреди | уреди извор]
ГАДДАГ је специјализација дата структуре дрвета, које садржи гране и чворове других ГАДДАГ-ова. Она је различита за складиштење сваког обрнутог префикса сваке речи у речнику. То значи да свака реч има толико репрезентација колико има слова; просечна реч у већини Сцраббле речника је 5 слова дуга, ово чини ГАДДАГ око 5 већим него једноставни ДАWГ.
Дефиниција[уреди | уреди извор]
За сваку реч у речнику која је формирана од непразног префикса x и суфикса y, ГАДДАГ садржи директан, детерминистички пут за сваки стринг РЕВ(x)৳y, где је ৳ оператор за конкатацију.
На пример за реч "еxплаин," ГАДДАГ садржи директну путању до стрингова "е৳xплаин," "xе৳плаин," "пxе৳лаин," "лпxе৳аин," "алпxе৳ин," "иалпxе৳н," и "ниалпxе."
Коришћење у генерисању покрета[уреди | уреди извор]
Сваки алгоритам генерисања покрета мора да садржи 3 врсте ограничења:
- Ограничења табле: Може се градити једино повезивање на већ постојећа слова на табли. Додатно, једино се могу поплочати празни квадрати.
- Ограничења постоља: Можете једино додавати плочице са словима са свог постоља.
- Ограничење речника: Све речи настала смештањем плочица потичу из речника игре.
ДАWГ алгоритма убрзава и користи предности другог и трећег ограничења: ДАWГ је направљен око речника, и пролазите га користећи једино плочице са свог постоља. Не успева да адресира прво ограничење: претпоставимо да желите да надовежете слово П у ХАРПY, и табла има 2 места пре П, морате претражити речник за све речи које садрже слова са вашег постоља где је треће слово П. Ово није детерминистички када претражујемо кроз ДАWГ, јер претраге гроз дрво неће уродити плодом.
Ово је адресирано од ГАДДАГ-овог складишта префикса: док пролазе П грану ГАДДАГ-а, видите све речи које имају П негде у свом саставу, и могу да претраже префиксе за форму од слова са Вашег постоља. Додајете плочице са свог постоља док су одговарајуће, путујући уназад кроз реч док не наиђете на ৳, што значи да сте комплетирали префикс. Комплетирате потез додајући га на почетак речи са суфиксом
Референце[уреди | уреди извор]
- ^ Гордон, Стевен (1994). „А Фастер Сцраббле Мове Генератион Алгоритхм”.