Спрямований (орієнтований) ациклічний граф (англ. directed acyclic graph, DAG) — випадок орієнтованого графа, в якому відсутні орієнтовані цикли, тобто шляхи, що починаються і закінчуються в одній і тій самій вершині. Орієнтований ациклічний граф є узагальненням дерева (точніше, їх об'єднання — лісу).
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekF6TDBScGNtVmpkR1ZrWDJGamVXTnNhV05mWjNKaGNHaGZNaTV6ZG1jdk1qVXdjSGd0UkdseVpXTjBaV1JmWVdONVkyeHBZMTluY21Gd2FGOHlMbk4yWnk1d2JtYz0ucG5n.png)
Застосування
- Компілятори машинних мов;
- Клас штучних нейронних мереж без зворотного зв'язку (Нейронна мережа прямого поширення);
- Статистика: Баєсова мережа довіри.
Оптимізація префіксного дерева
DAWG (англ. directed acyclic word graph) — компактна форма збереження префіксного дерева, списку слів, оптимізована для з'ясування, чи входить деяке слово в цей список чи ні. Сам список отримати нескладно рекурсивним проходом дерева. З точки зору програми, що провадить обхід чи пошук, орієнтований ациклічний граф нічим не відрізняється від дерева, просто однакові піддерева зберігаються в одиничному екземплярі.
Сам спосіб перетворення очевидний: пошук однакових піддерев і перепідключення посилань, одиничний екземпляр. В дійсності окрім букви в вершинах зберігається прапорець, що вказує, чи є дана буква останньою. Через це для пошуку слів, що не повторюються перетворення в DAWG і назад відбувається без втрат (з точністю до порядку слів).
Інші застосування
Вважається, що у Вікіпедії не повинна включати циклів.
Посилання
- Weisstein, Eric W. Орієнтований ациклічний граф(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Spryamovanij oriyentovanij aciklichnij graf angl directed acyclic graph DAG vipadok oriyentovanogo grafa v yakomu vidsutni oriyentovani cikli tobto shlyahi sho pochinayutsya i zakinchuyutsya v odnij i tij samij vershini Oriyentovanij aciklichnij graf ye uzagalnennyam dereva tochnishe yih ob yednannya lisu Priklad oriyentovanogo aciklichnogo grafaZastosuvannyaKompilyatori mashinnih mov Klas shtuchnih nejronnih merezh bez zvorotnogo zv yazku Nejronna merezha pryamogo poshirennya Statistika Bayesova merezha doviri Optimizaciya prefiksnogo dereva DAWG angl directed acyclic word graph kompaktna forma zberezhennya prefiksnogo dereva spisku sliv optimizovana dlya z yasuvannya chi vhodit deyake slovo v cej spisok chi ni Sam spisok otrimati neskladno rekursivnim prohodom dereva Z tochki zoru programi sho provadit obhid chi poshuk oriyentovanij aciklichnij graf nichim ne vidriznyayetsya vid dereva prosto odnakovi piddereva zberigayutsya v odinichnomu ekzemplyari Sam sposib peretvorennya ochevidnij poshuk odnakovih pidderev i perepidklyuchennya posilan odinichnij ekzemplyar V dijsnosti okrim bukvi v vershinah zberigayetsya praporec sho vkazuye chi ye dana bukva ostannoyu Cherez ce dlya poshuku sliv sho ne povtoryuyutsya peretvorennya v DAWG i nazad vidbuvayetsya bez vtrat z tochnistyu do poryadku sliv Inshi zastosuvannya Vvazhayetsya sho sistema kategorij u Vikipediyi ne povinna vklyuchati cikliv PosilannyaWeisstein Eric W Oriyentovanij aciklichnij graf angl na sajti Wolfram MathWorld