Методические указания по обучению решению задач теории графов.

Одним из методов обучения решению сложных задач является ее разбиение на более простые подзадачи; важным моментом является определение способа разбиения задач по сложности. Заметим, что в разработке реальных программных систем применяются структурные методы «сверху-вниз» и «снизу-вверх» [14]; последний из них означает постепенное укрупнение разрабатываемой системы. Таким образом, при обучении программированию естественно разбить построение исходной системы на ряд этапов, на каждом из которых решается более сложная относительно программирования задача. Конечный этап - построение всей системы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На последнем этапе решения поставленной задачи студентам необходимо рассмотреть встроенный предикат 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: Можно ли прогуляться по парку и его окрестностям (см. рис.) так, чтобы перелезть через каждый забор ровно один раз?

 

 

 

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

 

 

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