Модель дерева рішень
З Вікіпедії, безкоштовно encyclopedia
У теорії складності обчислень та теорії складності комунікації[en] модель дерева рішень являє собою модель обчислення або зв'язку, в якій алгоритм або процес комунікації вважаються, по суті, деревом рішень, тобто послідовністю операцій розгалуження на основі порівняння деяких величин, зіставленню присвоюється обчислювальна вартість одиниці.
Операції розгалуження називаються «тестами» або «запитами». У цьому параметрі даний алгоритм можна розглядати як обчислення булевої функції , де вхідний рядок запитів і висновок є остаточним рішенням. Кожен наступний запит залежить від попередніх.
Було запроваджено декілька варіантів моделей дерева рішень, в залежності від складності операцій, дозволених при обчисленні єдиного порівняння та способу розгалуження.
Моделі дерев рішень допомагають встановлювати нижні межі для обчислювальної складності для деяких класів обчислювальних задач та алгоритмів: нижня межа складності для найгірших випадків[en] пропорційна найбільшій глибині серед дерев рішень для всіх можливих входів даної обчислювальної задачі. Обчислювальна складність задачі або алгоритму виражається в термінах моделі дерева рішень як «складність дерева рішень» або «складність запитів».