|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[123] Мысля абстрактно, мы можем представить, что выполнение выражения amb заставляет время разветвиться, и на каждой ветке оно продолжается с одним из возможных значений выбора. Мы говорим, что amb представляет собой точку недетерминистского выбора (nondeterministic choice point). Если бы у нас была машина с достаточным числом процессоров, которые можно было бы динамически выделять, то поиск можно было бы реализовать напрямую. Выполнение происходило бы, как в последовательной машине, пока не встретится выражение amb. В этот момент выделялись и инициализировались бы дополнительные процессоры, которые продолжали бы все параллельные потоки выполнения, обусловленные выбором. Каждый процессор продолжал бы последовательное выполнение одного из потоков, как если бы он был единственным, пока поток не оборвется, потерпев неудачу, не разделится сам или не завер- 45 шится. С другой стороны, если у нас есть машина, которая способна выполнять только один процесс (или небольшое число параллельных процессов), альтернативы приходится рассматривать последовательно. Можно представить себе интерпретатор, который в каждой точке выбора произвольным образом выбирает, по какой ветке продолжить выполнение. Однако случайный выбор может легко привести к неудачам. Можно было бы запускать такой интерпретатор многократно, делая случайный выбор и надеясь, что в конце концов мы получим требуемое значение, но лучше проводить систематический поиск (systematic search) среди всех возможных путей выполнения. Amb-интерпретатор, который мы разработаем в этом разделе, реализует систематический поиск следующим образом: когда интерпретатор встречает выражение amb, он сначала выбирает первый вариант. Такой выбор может в дальнейшем привести к другим точкам выбора. В каждой точке выбора интерпретатор сначала будет выбирать первый вариант. Если выбор приводит к неудаче, интерпретатор автомагически46 возвращается (backtracks) к последней точке выбора и пробует следующий вариант. Если в какой-то точке выбора варианты исчерпаны, интерпретатор возвращается к предыдущей точке выбора и продолжает оттуда. Такой процесс реализует стратегию поиска, которую называют поиск в глубину (depth-first search) или хронологический поиск с возвратом (chronological backtracking).47 45Можно возразить, что этот механизм безнадежно неэффективен. Чтобы решить какую-нибудь просто сформулированную задачу таким образом, могут потребоваться миллионы процессоров, и большую часть времени большая часть этих процессоров будет ничем не занята. Это возражение нужно воспринимать в контексте истории. Память раньше точно так же считалась дорогим ресурсом. В 1964 году мегабайт памяти стоил 400 000 долларов. Сейчас в каждом персональном компьютере имеется много мегабайтов памяти, и большую часть времени большая часть этой памяти не используется. Трудно недооценить стоимость электроники при массовом производстве. 46Автомагически: «Автоматически, но при этом таким способом, который говорящий почему-либо (обычно либо из-за его сложности, либо уродливости, или даже тривиальности) не склонен объяснять». (Steele 1983; Raymond 1993) 47У встраивания стратегий автоматического поиска в языки программирования долгая и пестрая история. Первые предположения, что недетерминистские алгоритмы можно изящно реализовать в языке программирования с поиском и автоматическим возвратом, высказывались Робертом Флойдом (Floyd 1967). Карл Хьюитт (Hewitt 1969) изобрел язык программирования Плэнер (Planner), который явным образом поддерживал автоматический хронологический поиск в возвратом, обеспечивая встроенную стратегию поиска в глубину. Сассман, Виноград и Чарняк (Sussman, Winograd, and Charniak 1971) реализовали подмножество этого языка, названное ими МикроПлэнер (MicroPlanner), которое использовалось в работе по автоматическому решению задач и планированию действий роботов. Похожие идеи, основанные на логике и доказательстве теорем, привели к созданию в Эдинбурге и Марселе изящного языка Пролог (Prolog) (который мы обсудим в разделе 4.4). Разочаровавшись в автоматическом поиске, Макдермот и Сассман (McDermott and Управляющий цикл Управляющий цикл amb-интерпретатора не совсем обычен. Он считывает выражение и печатает значение первого успешного вычисления, как в примере с prime-sum-pair в начале раздела. Если нам хочется увидеть значение следующего успешного выполнения, мы можем попросить интерпретатор вернуться и попробовать породить значение следующего успешного выполнения. Для этого нужно ввести символ try-again. Если вводится какое-то другое выражение, а не try-again, интерпретатор начнет решать новую задачу, отбрасывая неисследованные варианты предыдущей. Вот пример работы с интерпретатором: ;;; Ввод Amb-Eval: (prime-sum-pair (1358) (20 35 110)) ;;; Начало новой задачи ;;; Значение Amb-Eval: (3 20) ;;; Ввод Amb-Eval: try-again ;;; Значение Amb-Eval: (3 110) ;;; Ввод Amb-Eval: try-again ;;; Значение Amb-Eval: (8 35) ;;; Ввод Amb-Eval: try-again ;;; Нет больше значений (prime-sum-pair (quote (13 5 8)) (quote (20 35 110))) ;;; Ввод Amb-Eval: (prime-sum-pair (19 27 30) (11 36 58)) ;;; Начало новой задачи ;;; Значение Amb-Eval: (30 11) Sussman 1972) разработали язык Коннивер (Conniver), в котором имелись механизмы, позволявшие программисту управлять стратегией поиска. Однако это оказалось слишком громоздким, и Сассман и Столлман (Sussman and Stallman 1975) нашли более удобный в обращении подход, когда исследовали методы символьного анализа электрических цепей. Они разработали схему нехронологического поиска с возвратом, которая была основана на отслеживании логических зависимостей, связывающих факты, и стала известна как метод поиска с возвратом, управляемого зависимостями (dependency-directed backtracking). При всей своей сложности, их метод позволял строить достаточно эффективные программы, так как почти не проводилось излишнего поиска. Дойл (Doyle 1979) и Макаллестер (McAllester 1978; McAllester 1980) обобщили и сделали более ясными идеи Столлмана и Сассмана, разработав новую парадигму для формулирования поиска, называемую сейчас поддержание истины (truth maintenance). Все современные системы решения задач основаны на какой-либо форме поддержания истины. У Форбуса и де Клеера (Forbus and deKleer 1993) можно найти обсуждение изящных способов строить системы с поддержанием истины и приложения, в которых используется поддержание истины. Заби, Макаллестер и Чепман (Zabih, McAllester, and Chapman 1987) описывают недетерминистское расширение Scheme, основанное на amb; оно похоже на интерпретатор, обсуждаемый в этом разделе, но более сложно, поскольку использует поиск с возвратом, управляемый зависимостями, а не хронологический. Уинстон (Winston 1992) дает введение в обе разновидности поиска с возвратом. Упражнение 4.35. Напишите процедуру an-integer-between, которая возвращает целое число, лежащее между двумя заданными границами. С ее помощью можно следующим образом реализовать процедуру для поиска Пифагоровых троек, то есть троек чисел (i, j, k) между заданными границами, таких, что i < j и i2 + j2 = k2: (define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high))) (let ((j (an-integer-between i high))) (let ((k (an-integer-between j high))) (require (= (+ (* i i) (* j j)) (* k k))) (list i j k))))) Упражнение 4.36. В упражнении 3.69 рассматривалась задача порождения потока всех Пифагоровых троек, без всякой верхней границы диапазона целых чисел, в котором надо искать. Объясните, почему простая замена an-integer-between на an-integer-startingfrom в процедуре из упражнения 4.35 не является адекватным способом порождения произвольных Пифагоровых троек. Напишите процедуру, которая решает эту задачу. (Это значит, что Вам нужно написать процедуру, для которой многократный запрос try-again в принципе способен породить все Пифагоровы тройки.) Упражнение 4.37. Бен Битобор утверждает, что следующий метод порождения Пифагоровых троек эффективнее, чем приведенный в упражнении 4.35. Прав ли он? (Подсказка: найдите, сколько вариантов требуется рассмотреть.) (define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high)) (hsq (* high high))) (let ((j (an-integer-between i high))) (let ((ksq (+ (* i i) (* j j)))) (require (>= hsq ksq)) (let ((k (sqrt ksq))) (require (integer? k)) (list i j k)))))) 4.3.2 Примеры недетерминистских программ В разделе 4.3.3 описывается реализация amb-интерпретатора. Однако для начала мы приведем несколько примеров его использования. Преимущество недетерминистского программирования состоит в том, что можно отвлечься от деталей процесса поиска, а следовательно, выражать программы на более высоком уровне абстракции. Логические загадки Следующая задача (взятая из Dinesman 1968) - типичный представитель большого класса простых логических загадок. Бейкер, Купер, Флетчер, Миллер и Смит живут на разных этажах пятиэтажного дома. Бейкер живет не на верхнем этаже. Купер живет не на первом этаже. Флетчер не живет ни на верхнем, ни на |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||