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

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

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

Предлагаем разбить каждую из задач на 3 подзадачи.

Для первой задачи предлагаем следующее разбиение на подзадачи:

1) Некоторая авиакомпания обеспечивает прямые рейсы между n городами. Определить есть ли возможность перелета из одного города в другой (рейсы считаем однонаправленными).

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

2) Некоторая авиакомпания обеспечивает прямые рейсы между n городами (рейсы считаем двунаправленными). Проверяем, существует ли путь из одного города в другой, при этом запоминая посещенные города. Зная, расстояние между города, найти длину данного пути.

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

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

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

Разбиение задачи про прораба ДРСУ будет следующим:

1) В некотором районе ДРСУ проводит ремонт дорог между населенными пунктами. Выяснить, имеет ли возможность прораб попасть из одного населенного пункта в другой, если по дорогам установлено одностороннее движение.

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

2) В некотором районе ДРСУ проводит ремонт дорог между населенными пунктами. Выяснить, существует ли возможность попасть из одного населенного пункта в другой, если считать дороги двунаправленными. При этом проезжая каждую из дорог прораб фиксирует себе, что данная дорога уже пройдена.

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

3) В некотором районе ДРСУ проводит ремонт дорог между населенными пунктами. Выяснить, существует ли возможность, выехав из некоторого населенного пункта, проехать по всем дорогам по одному разу и вернуться в начальный пункт. В качестве доказательства этого пути прорабу необходимо представить список посещенных дорог.

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

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

Задача № 1: Пусть конь стоит на любом поле шахматной доски. Определите хотя бы одну непрерывную траекторию, вдоль которой должен перемещаться конь, чтобы, побывав по одному разу в каждой клетке доски, вернуться последним ходом в исходную позицию [16].

Одон из вариантов решения этой задачи изображен в таблице.

63	22	15	40	1	42	59	18
14	39	64	21	60	17	2	43
37	62	23	16	41	4	19	58
24	13	38	61	20	57	44	3
11	36	25	52	29	46	5	56
26	51	12	33	8	55	30	45
35	10	49	28	53	32	47	6
50	27	34	9	48	7	54	31

Задача №2: Можно ли прогуляться по парку и его окрестностям (см. рис.) так, чтобы перелезть через каждый забор ровно один раз?

1

Размещено на http://www.allbest.ru/

Задача №3: На рисунке 5 план подземелья (слева), в одной из комнат которого скрыты богатства сеньора. После смерти его наследники нашли завещание, в котором было сказано, что для отыскания сокровищ достаточно войти в одну из крайних комнат подземелья, пройти через все двери, причем в точности по одному разу через каждую; сокровища скрыты за той дверью, которая будет последней [4].



1

Размещено на http://www.allbest.ru/

Задача №4: Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается [17].

1

Размещено на http://www.allbest.ru/

Факультативное занятие «Решение классических задач теории графов на Прологе».

Была проведена апробация, предложенной нами методики изложения данных задач в форме факультативного занятия для дисциплины программирования раздела «Языки программирования ИИ». Условия эксперимента - предварительное знакомство студентов с языком программирования Пролог. В апробации принимали участие 20% студентов третьего курса, обучающиеся по специальности "математика - информатика". 50% из них хорошей успеваемости, 50% - отличной успеваемости. Ниже приведен конспект проведенного занятия.

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

Тема: Решение классических задач теории графов на Прологе

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

1

Размещено на http://www.allbest.ru/

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

Для начала решим более простую задачу.

1

Размещено на http://www.allbest.ru/

Будем считать, что движение по дорогам возможно только в одном направлении. И пусть у прораба есть возможность переночевать в другом населенном пункте, т.е. не возвращаться домой.

Как мы должны поступить с графом, который соответствует начальным условиям задачи?

- Мы нашим дорогам должны задать направление.

Как теперь будем решать эту задачу?

Напишем предикат, определяющий можно ли вообще попасть из одного населенного пункта в другой. Проверим, есть ли путь из 2 в 5; укажите, в какие села есть возможность попасть из села 3; из каких сел можно доехать в село 4.

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

Каким образом мы можем поступить, для того чтобы избежать этого?

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

Какая структура Пролога позволяет нам запомнить множество однородных элементов?

- Списки.

Вспомогательный блок

Для решения данной задачи и в дальнейшем нам понадобятся некоторые вспомогательные предикаты для работы со списками:

1) предикат, проверяющий принадлежность элемента списку;

2) предикат, ставящий в соответствие списку его длину;

3) предикат, ставящий в соответствие списку его последний элемент.

Напишем определение для этих предикатов на Прологе.

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

Теперь предложим возможность прорабу проезжать по дорогам в любом направлении.

Каким образом на Прологе мы можем задать двунаправленность дорог?

- Определить новый предикат, который будет истинным и для прямого направления дороги, описанной в базе данных и для обратной дороги, не описанной там.

Посмотрим, существует ли путь из села 1 в село 2. Видим, что таких путей несколько.

Какие это пути? Хотелось бы узнать список пройденных дорог в каждом из путей, тем более это соответствует второму требованию исходной задачи.

Каким образом мы можем добиться нужного нам результата?

- Нужно добавить выводимую переменную - список.

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

Как мы можем проверить прохождения всех дорог, что мы можем использовать?

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

Для этого нам понадобится предикат, ставящий в соответствие списку его длину.

Каким способом будем решать?

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

Более эффективным является второй способ, в котором сравнение длин списков происходит автоматически (нужно использовать предикат findall).

Итак, исходная задача решена? Давайте еще раз просмотрим все этапы решения задачи. Что мы делали на первом этапе, что на втором, на третьем?

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

- На втором этапе: дали возможность двигаться по дорогам в любом направлении; создали список, в котором вывели порядок посещения дорог.

- На третьем этапе: проверили возможность обхода всех дорог, при этом использовали предикат findall.

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



1

Размещено на http://www.allbest.ru/

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

Граф, в котором существует, такой цикл называется эйлеровым графом.

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

Теорема: Для того чтобы граф был эйлеровым необходимо и достаточно четности степеней его вершин.

Программа на Прологе для данной задачи будет выглядеть следующим образом:

domains

spisok=integer*

predicates

put(symbol,symbol,spisok,integer)% откуда-куда-промежуточные

vput(symbol,symbol,spisok,spisok,integer)% откуда-куда-промежут-посещенные

most(symbol,symbol,integer,integer)% откуда-куда-номер моста

smost(symbol,symbol,integer,integer) % двунаправленность мостов

prin(integer,spisok)% принадлежность элемента списку

dlina(spisok,integer) % длину списка

otn(symbol,symbol,integer,spisok) %(i,i,o)

goal

otn(a,a,F,Q).

clauses

most(a,b,1,1).

most(a,b,2,1).

most(a,c,3,1).

most(a,c,4,1).

most(c,d,5,1).

most(a,d,6,1).

most(b,d,7,1).

otn(T,I,Q,E):-findall(K,most(_,_,K,_),L),dlina(L,R),put(T,I,E,Q),dlina(E,R).

put(X,Y,L,Q):-vput(X,Y,L,[],Q).

vput(X,Y,[N],P,Q):-smost(X,Y,N,Q),not(prin(N,P)).

vput(X,Y,[N|R],P,Q):-smost(X,Z,N,Q1),not(prin(N,P)),vput(Z,Y,R,[N|P],Q2), Q=Q1+Q2.

smost(P,T,H,N):-most(P,T,H,N).

smost(P,T,H,N):-most(T,P,H,N).

prin(X,[X|_]):-!.

prin(X,[_|L]):-prin(X,L).

dlina([],0).

dlina([_|B],K):-dlina(B,K1),K=K1+1.

Рассмотрим несколько иную задачу: Некоторая авиакомпания обеспечивает прямые рейсы между n городами. Турист желает посетить все n городов по одному разу и вернуться в тот город, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным.

1

Размещено на http://www.allbest.ru/

Решим более простую задачу.

I. Пусть у нас имеется возможность лететь из одного города в другой только в одном направлении (в качестве модели используем взвешенный ориентированный граф). И пусть турист в каждом городе покупает сувенир, который имеет определенный вес.

С чего начнем решение задачи?

База данных для этого графа будет следующей.

reis("Богота", «Москва"). ves("Москва",1).

reis("Москва", «Лондон"). ves("Богота",1).

reis("Москва", «Токио"). ves("Лондон",1).

reis("Токио", «Богота"). ves("Токио",1).

reis("Рим", «Лондон"). ves("Рим",1).

reis("Лондон", «Вашингтон"). ves("Вашингтон",1).

reis("Вашингтон", «Нью-Йорк"). ves("Нью-Йорк",1).

reis("Нью-Йорк", «Мехико"). ves("Мехико",1).

reis("Мехико", «Богота").

reis("Рим", «Мехико").

Давайте, определим вес сувенира, привезенный при одном рейсе, и узнаем:

§ Количество веса при рейсе из Боготы в Москву;

§ В какие города можно попасть из Боготы, зная, что турист может привести не более 20 кг груза;

§ Из каких городов, возможно, попасть в Москву, чтобы конечный груз был равен 12 кг.

Что мы теперь можем сделать? Как усложним задачу?

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

Проверим, существует ли путь из Москвы в Мехико. Видим, что произошло зацикливание.

Что нужно сделать, чтобы этого избежать?

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

Посмотрим, существует ли путь из Лондона в Мехико. Видим, что таких путей много и хотелось бы посмотреть, какие города мы в данном пути посетили.

III. Значит, аналогично предыдущей задаче добавляем в предикат put список посещенных городов.

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

По аналогии с предыдущей задачей пишем предикат itog с двумя аргументами: начальный пункт, список пройденных городов.

Какой еще результат мы должны достичь, чтобы задача была решена полностью? Как мы этого добьемся?

- Нужно минимизировать полученные расстояния.

Что для этого необходимо сделать?

- Используя findall, собираем в список все пути и находим минимум расстояния.

Самоанализ

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

Занятие проходило в форме лабораторной работы. В начале занятия была озвучена проблемная задача (задача о прорабе ДРСУ и задача о туристе), которую они должны разрешить с помощью уже имеющихся у них знаний, далее со студентами была решена классическая задача о Кенигсбергских мостах и задача о Кругосветном путешествии. Для понимания общей стратегии решения задач такого типа, ее решение разбили на 3 этапа. Переход к каждому этапу происходил из-за осознания проблемы и разрешению ее, и поэтому на каждом из этапов задача становилась более общей и усложненной. При объяснении решения каждой из подзадач была показана соответствующая сетевая модель.

В ходе предварительного опроса были выявлены знания студентов и выделены две подгруппы.

1 подгруппа - хорошей успеваемости, поэтому для решения была выбрана лишь одна задача: задача Эйлера. Время, затраченное на решение этой задачи - 2 учебных часа.

2 подгруппа - отличная успеваемость, были решены обе задачи. Время, затраченное на решения двух задач 3,5 учебных часа. Вторая задача была решена несколько быстрее, нежели первая, т.к. стратегии решения этих задач похожи.

Итоги: Все студенты усвоили материал. Контрольное время решения подобной задачи составило 1 учебный час.

Заключение

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

Все поставленные задачи в дипломной работе были выполнены. Получены следующие результаты:

На основе анализа литературы и документов министерства образования РФ выделены основные вопросы, изучаемые в рамках дисциплины «Основы искусственного интеллекта».

Проведен сравнительный анализ дидактических возможностей различных моделей в данной дисциплине.

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

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

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

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

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

Проведено факультативное занятие по теме: «Решение классических задач теории графов на Прологе» со студентами третьего курса, обучающихся по специальности «математика-информатика».

Можно сделать вывод о том, что методика обучения разработке программных систем искусственного интеллекта на основе логического программирования с использованием сетевых моделей допустима в преподавании дисциплины «Основы искусственного интеллекта» для студентов педагогической специальности "информатика".

Список литературы

Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. - М.: Мир, 1990. - 560 с.

Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных. Вводный курс: Учебное пособие. - М.: Гелиос АРВ, 2002. - 368 с.

Дудышева Е.В. Основы логического и функционального программирования: методические материалы для проведения лабораторных работ. - Бийск: НИЦ БиГПИ, 2000. -70 с.

Евстигнеев В.А., Касьянов В.Н. Толковый словарь по теории графов. Часть1,2,3 / Новосибирск, 1996.

Загорулько Ю.А., Телерман В.В., Яхно Т.М. Введение в логическое программирование: методическое пособие. Часть 1. - Новосибирск, 1997. - 91

Залогова Л.А. Язык программирования Пролог // Информатика. - 2004. -№12,16,18,20.

Ильина Т.А. Педагогика: Курс лекций. Учебное пособие для студентов пед. ин-тов. - М.: Просвещение, 1984.- 496с.

Информатика: Учебник/ под ред. проф. Н.В. Макаровой. - М.: Финансы и статистика, 1998. - 768с.

Информатика. Систематический курс. Учебник для 11 класса / С.А. Бешенков, Н.В. Кузьмина, Е.А. Ракитина. - М.: Бином. Лаборатория Знаний, 2002. - 200 с.

Каймин В.А. Информатика: Учебник. - М.: ИНФРА - М, 2001. - 272 с.

Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978

Лапчик М.П., Семакин И.Г., Хеннер Е.К. Методика преподавания информатики

Малпас Дж. Реляционный язык Пролог и его применение: Пер. с англ./ Под ред. В.Н. Соболева - М.: Наука., 1990. - 464 с.

Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: Учеб. пособие для студ. пед. вузов - М.: «Академия», 2001. - 816 с.

Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2003. - 304 с.

Оре О. Теория графов: Пер. с англ./ Под ред. Н.Н. Воробьева - М.: Наука, 1968. - 352 с.

Оре О. Графы и их применение. - М.: Мир, 1965

Педагогика. Учебное пособие для студентов пед. вузов и пед. колледжей / Под ред. П.И. Пидкасистого. - М.: Педагогическое общество России, 1998. - 640 с.

Першников В.И., Савинков В.М. Толковый словарь по информатике. - М.: "Финансы и статистика", 1991. - 497 с.

Столяренко Л.Д., Самыгин С.И. Педагогика. 100 экзаменационных ответов. Экспресс-справочник для студентов вузов. - Ростов н\Д: "МарТ", 2000. -256с.

Хювенен Э., Сеппянен Й. Мир Лиспа, Том 2: Методы и системы программирования. - М.: Мир, 1983.

Приложение 1

«Реализация задачи коммивояжера и задачи китайского почтальона на Прологе».

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

Сетевые модели для каждого шага решения задачи коммивояжера.

Программа на Прологе для задачи коммивояжера:

Domains

spisok=integer*

sp=symbol*

Predicates

цепь (symbol, integer, sp, spisok, integer)

всп_цепь (symbol, integer, sp, sp, spisok, integer)

дуга (symbol, symbol, integer, integer)

ребро (symbol, symbol, integer, integer)

принадлежит (symbol, sp)

количество (spisok, integer, integer)

цикл (symbol, integer, sp, spisok)

итог (symbol, integer, sp, spisok)

минимум (spisok, integer)

последний (sp, symbol)

Goal

итог (a, I, L,Y).

Clauses

дуга(x,v1,1,2).

дуга(v1,v2,2,1).

дуга(v2,v3,3,1).

дуга(v2,v3,4,3).

дуга(v3,v4,5,1).

дуга(v1,v4,6,1).

дуга(v3,v4,7,1).

дуга(v4,y,7,1).

дуга(x,y,7,1).

дуга(x,y,7,4).

итог(X,D,L,P):-findall(K, цикл(_,K,_,_),U), минимум(U,D), цикл(X,D,L,P).

цикл(X,D,L,P):-findall(K, цепь(K,_,_,_,_,_),M), количество (M,R,_), цепь(X,D,L,P,R).

цепь (X,D,L,P,R):- всп_цепь (X,D,L,[],P,R).

всп_цепь (X,D,[X,Y],K,[N],1):-ребро (X,Y,N,D), последний(K,Y).

всп_цепь(X,D,[X|L],K,[N|P],R):- ребро(X,Z,N,D1), not(принадлежит(Z,K)), R1=R-1, всп_цепь (Z,D2,L,[X|K],P,R1), D=D1+D2.

ребро(P,T,H,N):-дуга(P,T,H,N).

ребро(P,T,H,N):-дуга(T,P,H,N).

принадлежит (X,[X|_]):-!.

принадлежит (X,[_|L]):- принадлежит (X,L).

минимум ([X],X).

минимум ([X|T],M):- минимум (T,M),M<=X,!.

минимум ([X|_],X).

последний ([X],X).

последний ([_|T],X):- последний (T,X).

количество ([ ],0,0).

количество ([X|C],D,S):- количество (C,D1,S1),D=D1+1,S=S1+X

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

Сетевые модели для задачи китайского почтальона.

Реализация на Прологе задачи Эйлера.

Domains

spisok=integer*

Predicates

путь (symbol, symbol, spisok)

всп_путь (symbol, symbol, spisok, spisok)

дуга (symbol, symbol, integer)

ребро (symbol, symbol, integer)

принадлежит (integer, spisok)

длина (spisok, integer)

цикл (symbol, symbol, spisok)

Goal

цикл(a,a,P).

Clauses

дуга (a,b,1).

дуга (b,c,2).

дуга (b,c,3).

дуга (d,e,4).

дуга (e,c,5).

дуга (e,b,6).

дуга (e,d,5).

дуга (a,e,6).

цикл(T,I,E):-findall(K,дуга(_,_,K),L),длина(L,R),путь(T,I,E),длина(E,R).

путь(X,Y,L):-всп_путь(X,Y,L,[]).

всп_путь(X,Y,[N],P):-ребро(X,Y,N),not(принадлежит(N,P)).

всп_путь(X,Y,[N|R],P):-ребро(X,Z,N),not(принадлежит(N,P)),всп_путь(Z,Y,R,[N|P]).

ребро(P,T,H):-дуга(P,T,H).

ребро(P,T,H):-дуга(T,P,H).

принадлежит(X,[X|_]):-!.

принадлежит(X,[_|L]):-принадлежит(X,L).

длина([],0).

длина([_|B],K):-длина(B,K1),K=K1+1.

Приложение 2

Этапы разработки прототипа учебной экспертной системы.

1 этап: структурирование и концептуализация знаний.

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

список основных понятий и атрибутов;

отношения между понятиями;

структура входной и выходной информации;

стратегия принятия решений и т.д.

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

2 этап: формализация знаний.

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

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

3 этап: реализация прототипа учебной ЭС.

На данном этапе создается сам прототип учебной ЭС при помощи языка логического программирования, в частности, мы предлагаем использовать язык Пролог.

4 этап: тестирование программ прототипа учебной ЭС.

Тестирование - выявление ошибок в подходе и реализации прототипа.

Прототип проверяется на:

эффективность стратегии управления;

качество проверочных примеров;

корректность базы знаний.

Размещено на Allbest.ru