4817
правок
Поддерево максимального соответствия: различия между версиями
Материал из WEGA
Поддерево максимального соответствия (посмотреть исходный код)
Версия от 09:48, 22 сентября 2015
, 22 сентября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
Финден и Гордон [ ] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем исполнения O( | Финден и Гордон [8] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем исполнения <math>O(n^5) \;</math>, не гарантирующий оптимального решения. Кубицка, Кубицкий и Макморрис [13] предложили алгоритм с временем <math>O(n^{(.5 + \epsilon) log \; n)}</math> для той же задачи. Первый алгоритм решения этой задачи за полиномиальное время разработали Стил и Уорноу [15]; время его исполнения составляло <math>O(n^2) \;</math>. Стил и Уорноу также рассматривали случай небинарных и некорневых деревьев. Этот алгоритм требует <math>O(n^2) \;</math> времени для корневых и некорневых деревьев с фиксированной степенью и <math>O(n^{4.5 \; log \; n} )</math> для корневых и некорневых деревьев произвольной степени. Кроме того, они предложили линейную редукцию от корневого дерева к некорневому. Фарак и Торуп предложили алгоритм с временем исполнения <math>O(nc^{\sqrt{log \; n}})</math> для решения задачи MAST на бинарных деревьях; здесь c – константа величиной больше 1. Для деревьев с произвольной степенью этот алгоритм требует <math>O(n^2 c^{\sqrt{log \; n}}) \;</math> времени для некорневого случая [ ] и O(n1:5 log n) – для корневого [7]. Фарак, Пжытычка и Торуп получили алгоритм с временем исполнения O(nlog3 n) для решения задачи MAST на бинарных деревьях. Као [ ] удалось получить алгоритм для этой же задачи с временем исполнения O(nlog2 n). Для деревьев степени n он выполняется за время O(minfnd2 logdlog n, nd32log и}). | ||
Также была исследована задача MAST для более чем двух деревьев. Амир и Кеселман [ ] показали, что проблема является NP-полной даже для трех деревьев с неограниченной степенью. Однако для трех или более деревьев с ограниченной степенью известны полиномиальные алгоритмы [1 , 5]. | Также была исследована задача MAST для более чем двух деревьев. Амир и Кеселман [ ] показали, что проблема является NP-полной даже для трех деревьев с неограниченной степенью. Однако для трех или более деревьев с ограниченной степенью известны полиномиальные алгоритмы [1 , 5]. | ||
| Строка 45: | Строка 45: | ||
Эту технику можно обобщить на случаи более высоких степеней d > 2, за счет сочетания ее с техниками из ([6, глава 2]) для неограниченных степеней. Полученный алгоритм теоретически должен выполняться за время O(minfnpd log2 n; nd log n logdg); однако на деле время его исполнения составляет O(npd log n). | Эту технику можно обобщить на случаи более высоких степеней d > 2, за счет сочетания ее с техниками из ([6, глава 2]) для неограниченных степеней. Полученный алгоритм теоретически должен выполняться за время O(minfnpd log2 n; nd log n logdg); однако на деле время его исполнения составляет O(npd log n). | ||
== Применение == | == Применение == | ||
