Аналіз завдання про хід коня - Problem Solving with Algorithms and Data Structures
Це остання тема, присвячена задачі про перебіг коня; далі ми перейдемо до загальної версії пошуку у глибину. Тут же поговоримо про продуктивність. Зокрема, knightTour дуже чутливий до того, як ви вибираєте наступну вершину для відвідування. Наприклад, для дошки п'ять на п'ять на досить швидкому комп'ютері можна прокласти шлях протягом близько 1,5 секунд. Але що станеться, якщо взяти дошку вісім на вісім? У цьому випадку (залежно від швидкості комп'ютера) ви можете до півгодини чекати на отримання результату! Причина цього в тому, що наша реалізація задачі - експоненційний алгоритм розміром (O(k^N)), де N - число клітин на дошці, а k - якась мала константа. Рисунок 12 допоможе візуалізувати причину, через яку так відбувається. Корінь дерева є початковою точкою пошуку. З неї алгоритм генерує та перевіряє кожен із можливих ходів, які може зробити кінь. Як ми помітили раніше, їх кількість може залежати від позиції фігури на дошці. У кутах у неї є лише два можливі ходи, у клітинах, суміжних з кутовими, – три, а в середині дошки – вісім. Кількість можливих ходів для кожної позиції на дошці показано малюнку 13. На наступному рівні дерева з досліджуваного положення знову існує від двох до восьми можливих ходів. Число позицій дослідження пов'язані з кількістю вузлів у дереві пошуку.
Малюнок 12: Дерево пошуку для завдання про хід коня
Малюнок 13: Кількість можливих ходів кожної клітини
Ми вже бачили, що кількість вузлів у двійковому дереві заввишки N дорівнює \(2^-1\). Для дерева, чиї вершини можуть мати до восьми нащадків замість двох, кількість вузлів набагато більша. Оскільки фактор розгалуження – змінна для кожного вузла, кількість останніхможна оцінити, використовуючи середнє значення фактора. Важливо, що це алгоритм експоненціальний: \(k^-1\) , де \(k\) - середній чинник розгалуження для дошки. Давайте подивимося, як швидко він росте. Для дошки 5х5 дерево буде 25 рівнів глибиною або N = 24, якщо вважати перший рівень нульовим. Середній чинник розгалуження дорівнює (k = 3.8). Таким чином, кількість вузлів у дереві пошуку дорівнює \(3.8^-1\) або \(3.12 \times 10^\). Для дошки 6х6 \ (k = 4.4 \), число вузлів - \ (1.5 \ times 10 ^ \). Для звичайної ж дошки 8х8 (k = 5.25), а кількість вузлів (1.3 times 10). Звичайно, оскільки існує кілька рішень завдання, ми не будемо досліджувати кожен конкретний вузол, але дрібна частина виразу для кількості вузлів, які нам необхідно вивчити, - лише постійний множник, що не змінює експоненційний характер проблеми. Ми залишаємо вам як вправу спробу висловити \(k\) у вигляді функції від розміру дошки.
На щастя є спосіб прискорити випадок 8х8, щоб він працював приблизно одну секунду. У нижченаведеному лістингу можна знайти код, що прискорює knightTour . Ця функція (див. список 4) називається orderbyAvail і буде використовуватися замість виклику u.getConnections з коду вище. Вирішальний рядок в ордерБыАваил - десятий. Вона гарантує, що обрана для подальшого просування вершина має найменшу кількість доступних ходів. Ви можете подумати, що насправді це контрпродуктивно: чому не вибрати вузол, з якого можна зробити максимальну кількість переміщень? Такий підхід легко випробувати, запустивши програму та вставивши рядок resList.reverse() одразу після сортування.