Читать онлайн «Большие системы. Ситуационное управление»

На каждом шаге поиска ЭВМ в соответствии с заложенной в нее программой производят локальную оценку возможного продолжения путей и выбирает на основании этой оценки один или не- 7 сколько путей дальнейшего перемещения по лабиринту. Программы такого типа часто называют эвристическими, подразумевая под эвристикой методы сокращения перебора. Наиболее полно принципы лабиринтной теории были воплощены в программе «Общий Решатель Проблем» (ОРП), в создании которой принимали участие видные американские ученые А. Ньюэлл и Г. Саймон. Эта программа «выросла» из программы «Логик—Теоретик» тех же авторов, сохранив те основные принципы, которые были заложены в начальную программу. В чем же состояли эти принципы? Программа «Логик — Теоретик» была предназначена для доказательства теорем исчисления высказываний. В качестве исходной, информации программе сообщалось некоторое соотношение вида F = Я, в котором справа и слева стояли некоторые сложные высказывания, построенные из элементарных переменных (букв) и логических операций. Требовалось либо доказать, либо опровергнуть заданное соотношение. Для этого программа располагала набором операторов, применение которых позволяло получать из них эквивалентные высказывания. Если после конечного применения операторов к F в результате получалось Я, то теорема считалась доказанной. В противном случае поиск надо было продолжать. Читатель, по-видимому, легко усмотрит в этой программе и методе решения задачи все ту же лабиринтную модель. Начальная площадка лабиринта соответствует F,- а конечная — Н. От каждой площадки идет столько путей, сколько операторов можно применить к тому высказыванию, которое получилось на данном шаге. Если вместо F и Н рассматривать слова табор и торба, а в качестве операторов — операторы попарной перестановки соседних букв в слове, то лабиринтная модель, описанная выше, в точности совпадает с моделью, лежащей в. основе программы «Логик — Теоретик». Однако авторы программы сделали еще один существенный шаг. Они ввели понятие различия между F и Н и установили шкалу таких различий. После этого на каждом шаге они стремились использовать тот оператор, который максимально уменьшал различие между получаемым высказыванием и Н. Проиллюстрируем этот принцип на нашем примере. В качестве меры различия между двумя словами мы будем рассматривать суммарное число инверсий букв одного слова относительно другого. Подсчет производится следующим образом. Перенумеруем слева направо все пози- 8 ции букв в словах. Для нашего примера таких позиций пять по числу букв в словах. Зафиксируем некоторую букву в одном слове и отметим номер ее позиции. После этого определим номер позиции этой же буквы, в другом слове. Абсолютная разность номеров этих позиций определит инверсию, даваемую рассматриваемой буквой. Суммируя эти инверсии для всех букв, входящих в слово, мы получим меру различия двух слов. Пусть нам даны два слова табор и торба. Сравнивая последовательно оба слова побуквенно, мы обнаружим, что буква т инверсий не дает, буква а дает три инверсии, буква б — одну, буква о — две и, наконец, буква р — две инверсии.