Недетерминированное программирование

Недетерминированный язык программирования — это язык , который может определять в определенных точках программы ( называемых «точками выбора») различные альтернативы ходу программы . В отличие от оператора if-then , метод выбора между этими альтернативами не задается программистом напрямую; программа должна во время выполнения выбирать между альтернативами с помощью некоторого общего метода, применяемого ко всем точкам выбора. Программист указывает ограниченное количество альтернатив, но программа должна позже выбрать между ними. («Выбрать» - это, по сути, типичное название недетерминированного оператора.) Может быть сформирована иерархия точек выбора, в которой выбор более высокого уровня ведет к ветвям, содержащим внутри себя варианты выбора более низкого уровня.

Один из методов выбора реализован в системах обратного отслеживания (таких как Amb , ^[1]или унификация в Прологе ), при которой некоторые альтернативы могут «потерпеть неудачу», заставляя программу вернуться и попробовать другие альтернативы. Если все альтернативы терпят неудачу в определенной точке выбора, то вся ветвь терпит неудачу, и программа возвращается дальше, к более старой точке выбора. Одна из сложностей заключается в том, что, поскольку любой выбор является предварительным и может быть изменен, система должна иметь возможность восстанавливать старые состояния программы, устраняя побочные эффекты, вызванные частичным выполнением ветки, которая в конечном итоге завершилась неудачно.

Другой метод выбора — обучение с подкреплением , воплощенное в таких системах, как Alisp . ^[2]В таких системах вместо того, чтобы возвращаться назад, система отслеживает некоторую степень успеха и изучает, какой выбор часто приводит к успеху и в каких ситуациях (как внутреннее состояние программы, так и влияние окружающей среды могут повлиять на выбор). Эти системы подходят для приложений в робототехнике и других областях, в которых возврат назад предполагает попытку отменить действия, выполненные в динамической среде, что может быть трудным или непрактичным.

См. также [ править ]

Ссылки [ править ]

^ «Структура и интерпретация компьютерных программ» . ^{[ мертвая ссылка ]}
^ Дэвид Андре; Стюарт Дж. Рассел (июль 2002 г.). «Абстракция состояний для программируемых агентов обучения с подкреплением» . Восемнадцатая национальная конференция по искусственному интеллекту : 119–125.

[1] «Структура и интерпретация компьютерных программ» . ^{[ мертвая ссылка ]}

[2] Дэвид Андре; Стюарт Дж. Рассел (июль 2002 г.). «Абстракция состояний для программируемых агентов обучения с подкреплением» . Восемнадцатая национальная конференция по искусственному интеллекту : 119–125.

[1]

[2]