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

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

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

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

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

 

 

 

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

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

 

 

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

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

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

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

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

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

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

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

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

Списки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

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

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

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

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

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

 

domains=integer*

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

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

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

(a,a,F,Q).

 

(a,b,1,1).(a,b,2,1).(a,c,3,1).(a,c,4,1).(c,d,5,1).(a,d,6,1).(b,d,7,1).

(T,I,Q,E):-findall(K,most(_,_,K,_),L),dlina(L,R),put(T,I,E,Q),dlina(E,R).(X,Y,L,Q):-vput(X,Y,L,[],Q).(X,Y,[N],P,Q):-smost(X,Y,N,Q),not(prin(N,P)).(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.(P,T,H,N):-most(P,T,H,N).(P,T,H,N):-most(T,P,H,N).(X,[X|_]):-!.(X,[_|L]):-prin(X,L).([],0).([_|B],K):-dlina(B,K1),K=K1+1.

 

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

 

 

 

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

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

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

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

("Богота", «Москва"). ves("Москва",1).("Москва", «Лондон"). ves("Богота",1).("Москва", «Токио"). ves("Лондон",1).("Токио", «Богота"). ves("Токио",1).("Рим", «Лондон"). ves("Рим",1).("Лондон", «Вашингтон"). ves("Вашингтон",1).("Вашингтон", «Нью-Йорк"). ves("Нью-Йорк",1).("Нью-Йорк", «Мехико"). ves("Мехико",1).("Мехико", «Богота").("Рим", «Мехико").

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Самоанализ

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

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

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

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

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

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

Заключение

 

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложение 1

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

 

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

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

 

 

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

 

Domains=integer*=symbol*

цепь (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)

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

дуга(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=integer*

путь (symbol, symbol, spisok)

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

дуга (symbol, symbol, integer)

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

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

длина (spisok, integer)

цикл (symbol, symbol, spisok)

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

дуга (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