Зміст:
Визначення - Що означає Backtracking?
Зворотний трек - це алгоритм збору деяких чи всіх рішень заданих обчислювальних питань, особливо для проблем задоволення обмежень. Алгоритм може використовуватися лише для проблем, які можуть прийняти концепцію "часткового рішення кандидата" і дозволяє швидко провести тест, щоб зрозуміти, чи може рішення кандидата бути повноцінним рішенням. Зворотний трек вважається важливою технікою для вирішення проблем та задачок, пов'язаних із задоволенням. Він також вважається чудовою технікою розбору і також складає основу багатьох мов логічного програмування.
Техопедія пояснює зворотний трек
Зворотний трек допомагає вирішити загальну проблему шляхом пошуку рішення першої підпроблеми, а потім рекурсивної спроби вирішити інші підпроблеми на основі вирішення першого питання. Якщо поточну проблему неможливо вирішити, крок відновлюється, і наступне можливе рішення застосовується до попередніх кроків, а потім продовжується далі. Насправді, одна з ключових речей у тому, щоб відслідковувати, - це рекурсія. Він також розглядається як метод вичерпного пошуку з використанням ділення та підкорення. Алгоритм зворотного відстеження закінчується, коли немає більше рішень першої підпроблеми.
Зворотний трек - це алгоритм, який може допомогти досягти впровадження недетермінізму. Потрібен перший поглиблений пошук заданого простору випуску. Він використовується здебільшого в логічних мовах програмування, як Prolog. Де б не було застосовано зворотний трек, він швидший, ніж техніка грубої сили, оскільки він виключає велику кількість кандидатів одним тестом.
