Нить Ариадны (логика) - Ariadne's thread (logic)

Нить Ариадны , названная в честь легенды об Ариадне , решает проблему несколькими способами, такими как физический лабиринт , логическая головоломка или этическая дилемма, посредством исчерпывающего применения логики ко всем доступным маршрутам. Это особый используемый метод, который позволяет полностью проследить шаги или по пунктам выполнить серию найденных истин в условном, упорядоченном поиске, который достигает конечной позиции. Этот процесс может принимать форму мысленных записей, физических отметок или даже философских дебатов; имя получает сам процесс.

Реализация

Ключевым элементом применения потока Ариадны к проблеме является создание и поддержание записи - физической или иной - о доступных проблемах и исчерпанных вариантах в любое время. Эта запись называется «потоком», независимо от ее фактического носителя. Цель записи состоит в том, чтобы разрешить возврат, то есть отменить предыдущие решения и попробовать альтернативы. Учитывая запись, применить алгоритм просто:

• В любой момент, когда необходимо сделать выбор, сделайте его произвольно из тех, которые еще не отмечены как отказы, и следуйте ему, насколько это возможно, логически.
• Если возникает противоречие, вернитесь к последнему принятому решению, отметьте его как неудачное и попробуйте другое решение в той же точке. Если там нет других вариантов, вернитесь к последнему месту в записи, которое есть, отметьте сбой на этом уровне и продолжайте.

Этот алгоритм завершится либо при нахождении решения, либо при пометке всех начальных вариантов как неудачных; в последнем случае решения нет. Если требуется тщательное изучение, даже если решение было найдено, можно вернуться к предыдущему решению, отметить успех и продолжить, как если бы решение никогда не было найдено; алгоритм исчерпает все решения и найдет все решения.

Отличие от проб и ошибок

Термины «нить Ариадны» и « метод проб и ошибок » часто используются как синонимы, что не обязательно правильно. У них есть два отличительных отличия:

• «Метод проб и ошибок» подразумевает, что каждое «испытание» дает определенную ценность, которую необходимо изучить и улучшить, удаляя «ошибки» из каждой итерации, чтобы повысить качество будущих испытаний. В нити Ариадны такого механизма нет, поэтому все решения принимаются произвольно. Например, научный метод - это метод проб и ошибок; решение головоломок - это нить Ариадны.
• Подходы, основанные на пробах и ошибках, редко касаются того, сколько решений может существовать для проблемы, и часто предполагают, что существует только одно правильное решение. Нить Ариадны не делает такого предположения и способна найти все возможные решения чисто логической проблемы.

Короче говоря, метод проб и ошибок приближает желаемое решение; Нить Ариадны слепо исчерпывает пространство поиска полностью, находя любые без исключения решения. У каждого есть свое собственное применение. Их можно использовать в тандеме - например, хотя редактирование статьи в Википедии, возможно, является процессом проб и ошибок (учитывая то, как теоретически оно приближается к идеальному состоянию), истории статей предоставляют запись, для которой может быть применена ветка Ариадны. , отменить вредные изменения и восстановить статью до самой последней безошибочной версии, из которой можно попробовать другие варианты.

Приложения

Очевидно, что нить Ариадны может быть применена к решению лабиринтов таким же образом, как и легенда; в качестве записи можно использовать настоящую нить, или нанести мелом или аналогичным маркером места для этикеток. Если лабиринт на бумаге, нить вполне может быть карандаш.

Логические проблемы любой природы могут быть решены через нить Ариадны, лабиринт является лишь примером. В настоящее время он наиболее широко применяется к головоломкам судоку , используемым для определения значений для еще не решенных ячеек. Нити для решения головоломок могут быть самыми разными: от карандаша до пронумерованных карточек и компьютерной программы, но все они решают одну и ту же задачу. Обратите внимание, что, поскольку компиляция потока Ариадны является индуктивным процессом и из-за его полноты не оставляет места для фактического изучения, он в значительной степени не одобряется как метод решения, который следует использовать только в крайнем случае, когда дедуктивные методы терпят неудачу.

Искусственный интеллект сильно зависит от нити Ариадны, когда дело доходит до игры, особенно в программах, играющих в шахматы ; возможные ходы - это решения, выигрышные состояния - решения, а проигрышные - провалы. Из-за огромной глубины многих игр большинство алгоритмов не могут позволить себе применять поток Ариадны полностью на каждом ходу из-за ограничений по времени, и поэтому работают в тандеме с эвристикой, которая оценивает игровые состояния и ограничивает поиск в ширину только теми, которые скорее всего, принесет пользу, метод проб и ошибок.

Даже в обстоятельствах, когда понятие «решение» не так четко определено, к ним применялась нить Ариадны, например, навигация по всемирной паутине , понимание патентного права и философия; «Нить Ариадны» - это популярное название для веб-сайтов, предназначенных для многих целей, но в первую очередь для тех, которые посвящены философским или этическим дебатам.

Смотрите также

• Поиск грубой силы
• Поиск в глубину
• Лабиринт
• Дедуктивное мышление
• Компьютерные шахматы
• Дж. Хиллис Миллер
• Гордиев узел

использованная литература