Интелектуальные ИС

Искусственный интеллект (ИИ) как научное направление. Фундаментальное направление в ИИ.

Иску́сственный интелле́кт — наука и технология создания интеллектуальных машин, особенно интеллектуальных компьютерных программ. ИИ связан со сходной задачей использования компьютеров для понимания человеческого интеллекта, но не обязательно ограничивается биологически правдоподобными методами.

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

Участники Российской ассоциации искусственного интеллекта дают следующие определения искусственного интеллекта:

1. Научное направление, в рамках которого ставятся и решаются задачи аппаратного или программного моделирования тех видов человеческой деятельности, которые традиционно считаются интеллектуальными^[4].

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

3. Наука под названием «Искусственный интеллект» входит в комплекс компьютерных наук, а создаваемые на её основе технологии к информационным технологиям. Задачей этой науки является воссоздание с помощью вычислительных систем и иных искусственных устройств разумных рассуждений и действий^[5].

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

Стандартная интерпретация этого теста звучит следующим образом: «Человек взаимодействует с одним компьютером и одним человеком. На основании ответов на вопросы он должен определить, с кем он разговаривает: с человеком или компьютерной программой. Задача компьютерной программы — ввести человека в заблуждение, заставив сделать неверный выбор».

Все участники теста не видят друг друга. Если судья не может сказать определенно, кто из собеседников является человеком, то считается, что машина прошла тест. Чтобы протестировать именно интеллект машины, а не её возможность распознавать устную речь, беседа ведется в режиме «только текст», например, с помощью клавиатуры и экрана (компьютера-посредника). Переписка должна производиться через контролируемые промежутки времени, чтобы судья не мог делать заключения, исходя из скорости ответов. Во времена Тьюринга компьютеры реагировали медленнее человека. Сейчас это правило необходимо, потому что они реагируют гораздо быстрее, чем человек.

Основные подходы к проблеме искусственного интеллекта.

Проведенный нами анализ показал, что в настоящее время выражение "искусственный интеллект" используется в двояком смысле: • как техническая или кибернетическая модель естественного интеллекта, • как научное направление, лежащее на стыке разнообразных научных дисциплин. Таким образом, аналогично, целесообразно выделить два основных подхода к проблеме искусственного интеллекта. На основании этих двух подходов принято выделять два направления исследований в этой научной области: 1) прикладное направление развития области искусственного интеллекта, 2) фундаментальное направление развития области искусственного интеллекта. Фундаментальное направление развития области искусственного интеллекта.

Одним из сторонников этого, более общего, "философского", подхода является С. М. Шалютин. В своей работе С. М. Шалютин подчеркивает, что глубокая связь гносеологии и проблемы искусственного интеллекта имеет и такой важный аспект, как включение технических систем в познавательный процесс. Это означает, что человек как субъект познавательного процесса использует создаваемые им специальные орудия познавательной деятельности. Познание человека ограничивается психофизиологическими особенностями его организма и, здесь, ему на помощь приходит кибернетическая, информационно-вычислительная техника.

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

2) кибернетическое моделирование мыслительных процессов;

3) общетеоретические исследования.

1. Проблема искусственного интеллекта. Исследователи, конструирующие ИИ, с самого начала ставят своей целью создание технических систем, осуществляющих функции, которые обычно выполняет человек, естественный интеллект. Конструкторы таких систем ориентируются на получение определенного результата: решение машинами некоторого класса задач, которые до сих пор решал человек. При этом не имеет существенного значения, подобны ли процессы, происходящие в машине, процессам, происходящим в нервной системе человека. Таким образом, конечная цель заключается в том, чтобы получить определенный результат, аналогичный тому, который получает человек в результате размышлений. В действительности, перед системой ИИ ставится цель: решение задач высокого уровня сложности, а не только получение каких-либо результатов.

2. Моделирование процессов мышления. При моделировании процессов мышления сущность проблемы иная. Важен не результат сам по себе, а процесс, который приводил бы к результату. Моделирование мышления представляет собой применение метода моделей к познанию определенного объекта: мышления. В рассматриваемой области ученые пытаются упростить сложнейшую задачу познания мышления путем применения различных моделей. Развитие ЭВМ создает предпосылки для технического моделирования мыслительных процессов. Таким образом, постановка проблем и задач при моделировании мышления по сравнению с конструированием ИИ существенно различна. Возможно, что те или иные задачи, связанные с созданием искусственного интеллекта, могут быть решены только при условии воспроизведения в нем определенных черт познавательного процесса. Гипотеза С. М. Шалютина в том и заключается, что ряд выявленных гносеологией исторически сложившихся орудий познавательной деятельности (язык, категории и т.п.) Обязательны для всякой системы, которая была бы способна выполнить весь объем интеллектуальных функций, осуществляемых человеком. Чем в большей степени эти орудия будут воплощены в системах искусственного интеллекта, тем более "разумными", "интеллектуальными" будут эти системы.

3. Общетеоретическое направление области искусственного интеллекта. Для этого направления актуальным является вопрос: "может ли машина мыслить?". Сущность этого направления состоит в следующем. Если бы модель была тождественна оригиналу, то ее исследование не давало бы познавательного выигрыша. Тем не менее, очень важен вопрос о возможности создания модели, столь адекватной оригиналу, что различие между нею и классом объектов, составляющих оригинал, по основным, конституирующим характеристикам, было бы не большим, чем различие внутри этого класса. Ответ на поставленный вопрос требует анализа мышления как целостной системы и сопоставления с ним созданных моделей.

Итак, сделаем вывод о том, что задача создания мыслящей машины не совпадает с задачей моделирования мышления. Другими словами, сущностью этого направления является теоретическое, фундаментальное изучение и познание мышления, с точки зрения кибернетики, математики и информатики. Результатом развития этого направления, по всей видимости, будет создание абстрактной теории мышления, с точки зрения процессов генерации и обработки знаний, информации.

Прикладное направление в ИИ.

Иску́сственный интелле́кт — наука и технология создания интеллектуальных машин, особенно интеллектуальных компьютерных программ. ИИ связан со сходной задачей использования компьютеров для понимания человеческого интеллекта, но не обязательно ограничивается биологически правдоподобными методами.

При таком подходе, основные исследования, которые ведутся в области искусственного интеллекта, можно свести к следующим 4 направлениям.

1. Представление знаний и работа с ними, т.е. создание специализированных моделей и языков для представления знаний в ЭВМ, а также программных и аппаратных средств для их преобразования; исследования по созданию специальных логик, позволяющих пополнять и обобщать знания, хранимые в машине.

2. Планирование целесообразного поведения, т.е. исследования по созданию методов формирования целей и решения задач планирования действий автоматического устройства, функционирующего в сложной внешней среде.

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

4. Распознавание образов и обучение, т.е. исследования по восприятию зрительной, слуховой и других видов информации, методам ее обработки, формированию ответных реакций на воздействия внешней среды и способам адаптации искусственных систем к среде путем обучения.

Считается, что такой подход непосредственно связан с техникой, с существующими и перспективными ЭВМ, а также с программированием. Поэтому, такой подход можно назвать (определить) "прикладным подходом в области ИИ". При таком подходе под системами искусственного интеллекта (или под искусственным интеллектом) понимают системы, выполняющие функции, которые принято считать интеллектуальными. Таким образом, основоположники прикладного подхода и их последователи сразу же сужают область ИИ, сводя ее лишь к прикладным, чисто практическим целям. Это тоже важно, но путем создания таких искусственных систем вряд ли можно создать нечто "мыслящее", разумное. Ибо, при таком подходе изучаются лишь отдельные функции и способности мозга, следовательно, происходит упрощение задачи. Конечно же, одну из функций моделировать и исследовать проще, но нельзя забывать о том, что мозг - это динамическая саморегулирующаяся система, в которой все функции взаимосвязаны и взаимозависимы.

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

Попробуем определить свойством какой системы является интеллект. Предположим, что это свойство любого человеческого мозга. Тогда можно провести следующий мысленный эксперимент. Берем некий человеческий мозг и изолируем его от всех внешних воздействий, кроме жизнеобеспечивающих, питающих мозг. Для такого эксперимента можно взять известную "голову профессора Доуэла" и накрыть ее звуконепроницаемым, черным ящиком. Итак, если в мозг не будут поступать сигналы от органов чувств, то в мозг перестанет поступать информация, и интеллекту нечего будет перерабатывать и обдумывать. В таком случае, интеллект не сможет развиваться, а, скорее всего, он просто "засохнет", испортится, "сойдет с ума". Таким образом, без органов чувств, без поступления новой информации мышление не может развиваться (даже, не сможет появиться), а вероятнее всего, мышление просто не может существовать без этого. Следовательно, система "обладающая" интеллектом должна содержать помимо "мозга" еще и подсистему органов чувств, т.е. подсистему приема информации. По нашему глубокому убеждению, интеллект - это свойство, как минимум, всего человека, а не только человеческого мозга.

Рассмотрим другой, "литературный" опыт, например, жизнь человека на необитаемом острове, т.е. случай с Робинзоном Крузо. Интеллектом Робинзон обладал, но почему и откуда появилось у него это свойство? Интеллект - это свойство личности, отдельного человека? Робинзон был на острове единственным разумным существом и у него не было ни какой связи с другими людьми. Но от этого он не утратил свой "интеллект", ведь до этого Робинзон жил среди людей и общался с ними, получил определенные знания и навыки. Общение с людьми как с носителями "интеллекта" послужило причиной интеллектуальности Робинзона. Следовательно, кроме того, что некоторая система должна быть способной к интеллектуальной деятельности, эта система должна еще пройти курс обучения "интеллектуальности", т.е. научиться мыслить и рассуждать, а, кроме того, она еще должна накопить внутри себя, "в себе", некоторый определенный запас знаний.

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

Можем сделать такой вывод, что конкретный человек - это лишь определенный материальный носитель интеллекта, который, в свою очередь, является свойством общественного явления - мышления или, даже, сознания. Остается процитировать известную поговорку: "Для того, чтобы быть Человеком мало родиться человеком, надо еще и стать Человеком".

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

1. Непрерывное движение, внутреннее изменение системы.

2. Постоянное отражение, связь, взаимодействие с внешним миром.

3. Активность системы, т.е. наличие у нее собственной внутренней модели, (самосознания, самоотношения), существование и действие комплекса целей.

4. Закрепление опыта, накопление и обработка информации.

5. Необходимый уровень сложности самой системы, т.е. система должна быть "физически" способна к интеллектуальной деятельности.

6. Наличие некоторого количества таких систем, образование некоторой популяции систем.

7. Наличие взаимодействия, взаимопомощи с подобными себе системами внутри определенной популяции.

8. "Размножение", порождение новых подобных себе систем, отличающихся от уже существующих и "умирание", исчезновение старых и не приспособленных систем.

9. Благоприятные, удовлетворительные условия окружающей среды, существование необходимых ресурсов для реализации системами своих целей.

Прежде всего, надо создать, разработать такую систему, которая была бы способна к интеллектуальной деятельности, а уж затем из такой "заготовки", путем обучения и самообучения, создавать систему искусственного интеллекта.

Сетевые модели представления знаний. Представление знаний в виде набора продукционных правил.

Наиболее полно (в явном виде) отразить семантику предметной области позволяют сетевые модели. С этой формой связано понятие семантической сети как струтуры, отображающей совокупность предметной области. При этом объектам соответствуют узлы сети, а отношениям – дуги между ними. Объектами могут быть обобщенные понятия, события, действия; свойства указанных объектов также представляются вершинами. Совокупность объектов, включаемых в сеть, определяется содержанием предметной области и рассматриваемым кругом задач.

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

• Быть элементом класса

• Обладать свойством

• Являться следствием

• Иметь значение

Вершины могут иметь свою внутреннюю сетевую структуру. Тогда сеть называют сетью иерархического типа. Как разновидность сетевых моделей рассматривают иерархические структуры фреймов. Фрейм (термин введен М.Минским) – структура для описания стереотипной ситуации, состоящая из характеристик этой ситуации (слотов) и их значений (заполнителей слотов).

Совокупность фреймов, моделирующая определенную предметную область, имеет иерархическую структуру. Каждый фрейм соответствует некоторому объекту предметной области. Слоты сожержат описывающие этот объект данные. На верхнем уровне иерархии находится фрейм, отражающий наиболее общую информацию, присущую фреймам более низкого уровня. В качестве заполнителей слотов могут указываться:

- одно значение

- несколько значений

- фасет (диапозон или перечень)

- правило, согласно которому определяется заполнитель слота

- имя процедуры, реализующей алгоритм заполнения слота

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

Различают статические системы фреймов (не меняющиеся в процессе задачи) и динамические.

К достоинствам сетевых, в частности фреймовых, моделей знаний следует отнести:

• Явное представление иерархических связей

• Представление слотов в единственном экземпляре

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

Недостатки: сложность их реализации и сложность внесения изменений в базу знаний.

Анализ действий экспертов, связанных с диагностикой состояний сложных объектов и систем, показывает, что профессионал проводит экспертизу вполне целенаправленно, придерживаясь определённой стратегии. При этом он руководствуется множеством правил (эвристик), которые могут быть представлены в форме «ЕСЛИ посылка, ТО заключение» - эта форма называется продукционным правилом или продукцией.

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

Правило может быть задано с коэффициентом уверенности, определяющим положительным значением от 0 до 1 степень адекватности (достоверности) или достоверности вывода (консеквента) правила условием его срабатывания (антецедентом). Другими словами, этот коэффициент определяет степень близости его к точной логической конструкции, для которой его значение принимается равным 1. Коэффициент уверенности это не то же самое, что и коэффициент вероятности!

С коэффициентами уверенности так же могут задаваться конкретные факты со стороны пользователя при описании текущей ситуации, в достоверности которых существует определённая доля сомнения. С коэффициентом уверенности могут задаваться факты экспертом в антецедентах правил.

Пример: машина не заводится

ЕСЛИ <есть искра>(1) ТО <виновата не система зажигания>

При организации базы знаний (БЗ) антецеденты и консеквенты продукционных правил могут представляться совокупностью пар «атрибут-занчение» или троек «атрибут-объект-значение». Это сокращает число задействованных переменных, однако использование троек усложняет процесс формирования правил и усложняет алгоритм вывода.

Представление знаний продукционных правил обладает преимуществами:

• Модульность (легко изменяем структуру)

• Единообразие структуры создаваемых на их основе СОЗ и, как следствие, возможность построения и использования оболочек

• Естественность такой формы представления знаний - имитация рассуждений человека-эксперта

• Гибкость иерархии понятий с точки зрения внесения изменений.

Недостатки:

• Громоздкость процесса вывода, связанная с проверкой применимости правил

• Сложность управления процессом вывода

• Отсутствие наглядности представления иерархии понятий

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

В продукционной системе для этого удобно использовать дерево решений (граф решений), которое к тому же существенно компенсирует недостаток продукционных правил, связанный с отсуствием наглядности представления иерархиии понятий.

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

В пользу продукционной модели представления знаний говорит так же то, что она хорошо согласуется с представлением задач в пространстве состояний, характерном для целевого назначения многих ИС.

Нейромодельный подход к построению интеллектуальных информационных систем. Биологические основы нейромодельного подхода.

Кибернетический подход.

Попытки построить машины, способные к разумному поведению, в значительной мере вдохновлены идеями профессора МТИ Норберта Винера,.

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

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

В дальнейшем Винер разработал на принципе обратной связи теории как машинного так и человеческого разума. Он доказывал, что именно благодаря обратной связи все живое приспосабливается к окружающей среде и добивается своих целей. «Все машины, претендующие на «разумность», писал он, должны обладать способность преследовать определенные цели и приспосабливаться, т.е. обучаться». Созданной им науке Винер дает название кибернетика, что в переводе с греческого означает рулевой.(2)

Нейронный подход.

Многие ученые стали понимать, что создателям вычислительных машин есть чему поучиться у биологии. Среди них был нейрофизиолог и поэтлюбитель Уоррен Маккалох. Он разработал теорию деятельности головного мозга. Эта теория и являлась той основой, на которой сформировалось широко распространенное мнение, что функции компьютера и мозга в значительной мере сходны.

Исходя отчасти из предшествующих исследований нейронов (основных активных клеток, составляющих нервную систему животных), проведенных Маккаллохом, они с Питтсом выдвинули гипотезу, что нейроны можно упрощенно рассматривать как устройства, оперирующие двоичными числами. Двоичные числа, состоящие из цифр единица и нуль, рабочий инструмент одной из систем математической логики.

Английский математик XIXв. Джордж Буль, предложивший эту остроумную систему, показал, что логические утверждения можно закодировать в виде единиц и нулей, где единица соответствует истинному выссказыванию а нуль ложному, после чего этим можно оперировать как обычными числами.

В 30е годы XX в. пионеры информатики, в особенности американский ученый Клод Шеннон, поняли, что двоичные единица и нуль вполне соответствуют двум состояниям электрической цепи (включено/выключено), поэтому двоичная система идеально подходит для электронновычислительных устройств.

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

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

Биологические основы нейромодельного подхода

Первые исследования по анатомической организации мозга связаны с работами испанского гистолога Сантьяго Рамон-и-Кахаля, датируемыми 1911 годом. Именно он, используя предложенный итальянским гистологом Камилло Гольджи метод окраски нейронов (нервных клеток) солями серебра (серебро избирательно проникает только в нейроны), выявил клеточную (нейронную) структуру мозга.

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

Головной мозг человека содержит порядка 20 млрд нейронов и 300 млрд межнейронных соединений. Он состоит из левого и правого полушарий, на поверхности которых находится тонкий слой серого вещества. Это кора головного мозга (кортекс), состоящая в основном из нейронов. Кортекс ответствен за интеллектуальные, творческие процессы (мышление), протекающие в человеческом мозге.

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

Правое полушарие реализует синтетический способ обработки информации, соединяя разрозненные сведения в единый образ. Оно действует как аналоговый компьютер, охватывая всю ситуацию сразу и реализуя существенный параллелизм. Правое полушарие мыслит на «языке» образов, структур. Происходит это значительно быстрее описания ситуации словами (аналитическим способом). Например, знакомое лицо человек распознает за 100–120 мс, цифровой компьютер тратит на это минуты и даже десятки минут (при наличии существенных помех).

Нейрон состоит из тела (сомы) и отходящих от него отростков – дендритов и аксона. Сома содержит обычные для большинства клеток внутриклеточные компоненты: ядро и клеточные части, реализующие обмен веществ и синтез белков. Дендриты представляют собой сравнительно короткие ветвистые входные (афферентные) отростки. Они воспринимают идущие к нейрону по многочисленным волокнам импульсы (возбуждения). Аксон – это длинный, тонкий, мало ветвящийся (имеет концевые разветвления) выходной (эфферентный) отросток нейрона. Он передает нервные импульсы от нейрона к другим нервным клеткам, мышцам, железам. Пучки аксонов образуют нервные волокна.

Типичная структура нейрона представлена на рис. 10 (в верхней его части).

Выявлено широкое разнообразие нейронов, различающихся формой тела, разветвленностью дендритной части и длиной аксона. Различают нейроны трех классов:

·  сенсорные (чувствительные, афферентные, рецепторные) нейроны, получающие информацию из внешней среды или от рецепторных клеток (фоторецепторов, механорецепторов и т. д.);

·  связующие (вставочные, ассоциативные) нейроны (интернейроны), которые связывают один нейрон с другим;

·  моторные (эффекторные, эфферентные) нейроны, посылающие свои импульсы к исполнительным органам (мышцам, железам).

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

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

Каждый синапс в отдельности лишь незначительно влияет на активность нейрона. Для установки интенсивности формирования нервного импульса нейрон должен непрерывно интегрировать до 1000 синаптических входов.

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

Стратегии поиска в глубину.

Стратегии поиска в ширину

В зависимости от преследуемых целей может применяться прямой или обратный вывод. В случае прямого вывода по известным фактам отыскивается заключение следующие из этих фактов. Найденное заключение заносится в рабочую память, и если оно представляет собой некоторый промежуточный (неокончательный) вывод, то процесс продолжается. Такой вывод называют управляемым данными (управляемым антецедентами). При обратном выводе выдвигается некоторая гипотеза и среди фактов ищутся те, которые её подтверждают. Если гипотеза правильная, то может быть выдвинута следующая гипотеза, детализирующая первую и т.д. Такой вывод называется управляемым целями (управляемым консеквентами). Он применяется когда цели известны и их немного.

Иногда применяют так называемый циклический (комбинированный) метод, использующий обратный и ограниченный прямой вывод.

Как при прямом, так и при обратном выводе возможны две стратегии поиска решений – стратегия поиска в ширину и стратегия поиска в глубину.

При поиске в ширину сначала просмотриваются все узлы очередного уровня (уровня отстояния от исходных) пространства состояний, и только затем осуществляется переход к узлам следующего уровня. Таким образом отслеживаются все возможные заключения, которые могут быть получены в условиях возникшей ситуации.

Поиск в ширину предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться больше в ширину. При поиске в ширину приходится сохранять все множество альтернативных вершин (а не одну вершину как при поиске в глубину). Хранятся не только вершины, но и множество путей, которые хранятся в виде списка.

Общие принципы построения поиска в ширину: 1) Если первый элемент (вершина) первого пути (в списке путей) - это целевая вершина то взять этот путь в качестве решения. 2) Иначе удалить первый путь и породить множество продолжений этого пути на один шаг.

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

Стратегии поиска в глубину.

В зависимости от преследуемых целей может применяться прямой или обратный вывод. В случае прямого вывода по известным фактам отыскивается заключение следующие из этих фактов. Найденное заключение заносится в рабочую память, и если оно представляет собой некоторый промежуточный (неокончательный) вывод, то процесс продолжается. Такой вывод называют управляемым данными (управляемым антецедентами). При обратном выводе выдвигается некоторая гипотеза и среди фактов ищутся те, которые её подтверждают. Если гипотеза правильная, то может быть выдвинута следующая гипотеза, детализирующая первую и т.д. Такой вывод называется управляемым целями (управляемым консеквентами). Он применяется когда цели известны и их немного.

Иногда применяют так называемый циклический (комбинированный) метод, использующий обратный и ограниченный прямой вывод.

Как при прямом, так и при обратном выводе возможны две стратегии поиска решений – стратегия поиска в ширину и стратегия поиска в глубину.

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

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

Стратегия поиска в глубину основана на тщательном исследовании последовательности одного варианта выбора до изучения других вариантов. Первоначально исследуется самая первая левая ветвь дерева, когда процесс поиска заходит в тупик. Интерпретатор возвращается вверх, в последний пункт выбора. Где имеются неизученные альтернативные варианты движения. Поиск в глубину наиболее адекватен рекурсивному стилю программирования.

Важно! Действие, вызванное срабатыванием правила, может быть связано не только с переходом процесса вывода в следующие состояние, фиксируемое содержимым рабочей памяти. Оно может состоять и в модификации (изменении, удалении или добавлении новых правил) или замене критерия выбора активизуруемого правила при разрешении конфликтных ситуаций.

Поиск в глубину

[править | править вики-текст]

Материал из Википедии — свободной энциклопедии

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 9 января 2015; проверки требует 1 правка.

Порядок обхода дерева в глубину

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин^[1].

Содержание

  [убрать] 

• 1 Алгоритм поиска в глубину

  • 1.1 Нерекурсивные варианты

• 2 Поиск в глубину с метками времени. Классификация рёбер

• 3 Применение

• 4 См. также

• 5 Примечания

• 6 Литература

• 7 Ссылки

Алгоритм поиска в глубину[править | править вики-текст]

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

1. Пройдём по всем вершинам .

• Если вершина  белая, выполним для неё DFS(v).

Процедура DFS (параметр — вершина )

1. Перекрашиваем вершину  в серый цвет.

2. Для всякой вершины , смежной с вершиной  и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w)^[2].

3. Перекрашиваем вершину  в чёрный цвет.

Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.

Нерекурсивные варианты[править | править вики-текст]

На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.

Первый вариант: можно сэмулировать стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер  и номер текущей смежной вершины .

Процедура DFS (параметр — вершина )

1. Кладём на стек пару . Перекрашиваем вершину  в серый цвет.

2. Пока стек не пуст…

   1. Берём верхнюю пару , не извлекая её из стека.

   2. Находим вершину , смежную с  и следующую за .

      1. Если таковой нет, извлекаем  из стека, перекрашиваем вершину  в чёрный цвет.

      2. В противном случае присваиваем , прямо в стеке.

• Если к тому же вершина  белая, кладём на стек пару , перекрашиваем  в серый цвет.

Второй вариант: можно в каждой из «серых» вершин держать текущее  и указатель на предыдущую (ту, из которой пришли).

Третий вариант работает, если хватает двухцветных меток.

Процедура DFS (параметр — вершина )

1. Кладём на стек вершину .

2. Пока стек не пуст…

   1. Берём верхнюю вершину .

   2. Если она белая…

      1. Перекрашиваем её в чёрный цвет.

      2. Кладём в стек все смежные с  белые вершины.