Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 13
Текст из файла (страница 13)
Несмотря69на то, что найденный путь совпадает с путем, найденным с помощьюпредыдущей реализацией программы, и результаты работы функции test2совпадают для первого и второго прототипов.» (breadth 'n1 'nil)search level=0current visited list:(n4 n2 n1)current search list:((n1 n1 n4 162.2621335986927) (n1 n1 n292.5418824100742))search level=1 currentvisited list:(n3 n8 n4 n2 n1)current search list:((n1 n1 n2 n3 349.64108505372303) (n1 n1 n4 n8292.53108615454926))search level=2current visited list:(n6 n5 n3 n8 n4 n2 n1)current search list:((n1 n1 n2 n3 n6 500.49200483878764) (n1 n1 n2 n3 n5529.4298499974759))search level=3 current visited list: (n10n6 n5 n3 n8 n4 n2 n1) current search list:((n1 n1 n2 n3 n6 n10 655.2692641503545))search level=4 current visited list: (n9 nl0n6 n5 n3 n8 n4 n2 nl) current search list:((n1 n1 n2 n3 n6 nl0 n9 814.9721132169882))search level=5 currentvisited list:(n7 n9 nl0 n6 n5 n3 n8 n4 n2 n1)current search list:((n1 n1 n2 n3 n6 nl0 n9 n7 874.6378487776934))search level=6 currentvisited list:(n11 n7 n9 nl0 n6 n5 n3 n8 n4 n2 nl)current search list:((n1 n1 n2 n3 n6 nl0 n9 n7 n11 1026.0181645390235))Found a good path:(nl nl n2 n3 n6 nl0 n9 n7 n111026.0181645390235)Глава 4Постановка задач и методические указанияЗадание практикума состоит из двух частей: разработки библиотеки(генетического алгоритма или работы с графами) и решения с помощьюбиблиотеки одной из предложенных задач.Разработка библиотеки предполагает создание повторно используемыхкомпонент.
Обладая достаточно сложной функциональностью, библиотекаможет иметь очень простой внешний (пользовательский) интерфейс. Припроектировании сложных библиотек не менее важен внутреннийинтерфейс, определяющий структуру, модульность самой библиотеки. Вчастности, хорошо продуманная внутренняя структура должна позволятьлегко заменять (перегружать) внутренние функции, допускающиеразличную реализацию (например, различные модели естественногоотбора).Решение конкретной задачи - это пример создания собственногонебольшого приложения, демонстрирующего функциональность, гибкостьи удобство использования библиотеки.
В соответствии со «спиральной»моделью жизненного цикла программы, проектирование приложенияцелесообразно осуществлять поэтапно по мере уточнения (усложнения)задачи. При этом на каждом шаге создается работающий прототиппрограммы, который затем может быть расширен. Постановкапредлагаемых задач уже включает элементы последовательногоуточнения.Генетический алгоритмЗадание - написать библиотеку генетического алгоритма (ГА) и с еепомощью решить поставленную задачу.Для реализации предлагается простейшая модель генетическогоалгоритма. Хромосомы кодируются с помощью 0 и 1.
Методырепродукции включают одноточечное скрещивание и мутацию хромосом.Размер популяции при смене поколений не изменяется. Длина хромосомтакже остается постоянной. Вероятность мутации задается как параметргенетического эксперимента.Решение об окончании работы генетического алгоритма принимаетсялибо при достижении заданной точности, либо алгоритм осуществляетзаданное число итераций и останавливается. В качестве окончательного71решения выбирается «лучшая» хромосома в последней популяции.
Приэтом предполагается возможность просмотра всего процесса пошаговогорешения (т.е. для каждой промежуточной популяции выводится «лучшая»хромосома и ее пригодность). Просмотр пошагового решения может такжевключать визуализацию процесса решения (например, диаграммупригодности).Реализация библиотеки ГА включает спецификацию, код и набор тестовдля демонстрации работоспособности библиотеки. Решение задачивключает отображение задачи на понятия ГА, наличие нескольких,последовательно уточняемых прототипов программы и визуализациюрезультатов и процесса пошагового решения.Список задач1. Нахождение максимума функции.Найти экстремум функции на заданном промежутке.1-ый прототип: функция и промежуток заданы:f(x) = х+ |sin (32 х)|,х∈ [0, pi).2-ой прототип: произвольная функция от двух переменных.2.
Построение треугольника по трем отрезкам.Отрезки произвольной длины перемещаются на экране, пока не получитсятреугольник.1-ый прототип: две точки фиксированы в системе координат, однасвободно перемещается на плоскости.2-ой прототип: все три точки свободно перемещаются (ориентациятреугольника на плоскости произвольна).3. Составное число.Задано положительное целое число N. Существуют ли такие целые числа ти n (т, п > 1), что N = т*n?1-ый прототип: числа т, n, N представимы с помощью разряднойсетки машины.2-ой прототип: числа т, п, N. не представимы с помощью разряднойсетки машины (иными словами встроенные арифметическиефункции не могут быть использованы).4. Линейная делимость.Даны целые положительные числа а, с.
Существует ли такое целое х, что сделится нацело на a -x + 1?1-ый прототип: числа а, с представимы с помощью разрядной сеткимашины.722-ой прототип: числа а, с не представимы с помощью разряднойсетки машины (иными словами встроенные арифметическиефункции не могут быть использованы).5. Упаковка в контейнеры.Заданы конечное множество U предметов, размер s(u) ∈ Z+ каждогопредмета и ∈ U, положительное целое число К, и положительные целыечисло B 1, ..., B k - вместимости контейнеров.
Существует ли такоеразбиение множества U на непересекающиеся подмножества U1, U2,… , Uk,что сумма размеров предметов из каждого подмножества м, не превосходитBj?1-ый прототип: все контейнеры одинаковой вместимости (Bi - Bj ∀ i,j) .2-ой прототип: контейнеры разной вместимости.6.
Рюкзак.Заданы конечное множество U предметов, размер s(u) ∈ Z+ и стоимостьv(u) ∈ Z+ каждого и ∈ U , положительные целые числа В и К.Существует ли N таких различных подмножеств U' ⊆ U, что £ „ £ у s(u)< В и £ „ е у v(u)>Kl1-ый прототип: нахождение одного такого подмножества.2-ой прототип: нахождение N таких различных подмножеств.7. Подпоследовательность чисел.Даны натуральные числа т, а;, ..., а„. В последовательности а,, ..,, а„выбрать такую подпоследовательность a,j, а,2, ..., aik (0 <= И < (2 < ... < ik <п), что ац + ... ч- а& = т.1-ый прототип: нахождение одной такой подпоследовательности.2-ойпрототип:нахождениеNтакихразличныхподпоследовательностей.8. Раскрашиваемость графа в k цветов.Задан граф G = (V, Е).
Можно ли G раскрасить в k цветов? Другимисловами, существует функция/ У -> { 1, 2, ..., k}, такая, что f(u) ?f(v),если {и, v} ∈ Е?1 -ый прототип: k = 2.2-ой прототип: k > 4.9. Группы предметов.Имеется п предметов, веса которых равны а 1 , . . . , аn. Разделить этипредметы на т групп так, чтобы общие веса групп были максимальноблизки.1-ый прототип: т = 2.2-ой прототип: т > 2.10. Доминирующее множество.Заданы граф G = (V, E) и целое число К, К < |V|. Существует ли такоеподмножество V' ⊆ V, что |V| ≤ К и каждая вершина v ∈ V \ V' соединенаребром по крайней мере с одной вершиной из V'?1-ый прототип: нахождение одного подмножества.2-ой прототип: нахождение N таких различных подмножеств.11.
Гамильтонов цикл (путь).Задан граф G = (V, Е). Имеется ли в G гамилътонов цикл (путь)?1-ый прототип: гамильтонов цикл (необходимо пройти через всевершины).2-ой прототип: гамильтонов путь (необходимо пройти через всеребра).12. Поиск пути в графе.Задан граф G = (V, Е) с двумя выделенными вершинами s, t ∈ V, длина1(е) ∈ Z+ каждого ребра е ∈ Е и положительные целые числа B и K.Существует ли в G К различных путей от s до t, веса которых непревосходят В?1-ой прототип: нахождение одного пути, вес которого непревосходит В.2-ий прототип: нахождение в G К различных путей от s до t, весакоторых не превосходят В.13. Сельский почтальон.Заданы граф G = (V, Е), длина l(e) ∈ Z+ каждого ребра е ∈ Е,подмножество Е' ⊆ Е и граница В ∈ Z* .
Существует ли в G цикл,включающий каждое ребро из E' и имеющий длину не более В?1-ый прототип: нахождение цикла, включающего каждое ребро из E'.2-ой прототип: нахождение цикла, включающего каждое ребро из Е'и имеющий длину не более В.Обработка графовЗадание - написать библиотеку работы с графом, решить поставленнуюзадачу и визуализировать результат решения.На первом этапе задание практикума предполагает создание библиотекиработы с графами, включающей процедуру преобразования графа извнешнего формата во внутреннее представление и обратно. Внешнийформат будем считать фиксированным.Формат описания графа:74Graph ::=StartGraphNodesGraphEdgesFinishStart : : =[ORIENTED][COLORED][WEIGHTED][WITH CONDITIONS]#GRAPH DESCRIPTIONOptNameOptName ::= Name |GraphNodes ::=iNODESStartNode[Node}*StartNode ::= #START NODE Name [COLOR ColorName]Node ::= Name [COLOR ColorName]GraphEdges ::=#EDGES{Edge}*Edge :=EdgeName ':' Name Name[WEIGHT NaturalNumber][CONDITION Input][COLOR ColorName]EdgeName := OptNameInput ::= NameFinish ::= #END GRAPH DESCRIPTIONOptName, Name - последовательность из букв и цифрNaturalNumber - последовательность из цифрColorName - один из цветов 16-цветной палитрыПример описания графа:ORIENTEDCOLOREDWITH CONDITIONS#GRAPH DESCRIPTION ExampleGraph#NODES#START NODE A COLOR RED75В COLOR WHITE СCOLOR MAGENTA D EQQ COLOR BLACK#EDGESEl : А В CONDITION siE2 : D E CONDITION s2: D QQ CONDITION si#END GRAPH DESCRIPTIONЭтот пример описывает ориентированный раскрашенный граф сдействиями.
Первые два ребра поименованы: E 1 и Е2. Приориентированности графа порядок вершин в описании ребра существенен:ребро ориентировано от первой вершины ко второй. Если графраскрашенный, то вершины без явного указания цвета имеют цвет поумолчанию (WHITE). Граф с действиями используется для представленияавтомата с конечным числом состояний. В этом случае вершинасоответствует состоянию автомата, ребро - переходу в другое состояние, аусловие - текущему значению из управляющей входнойпоследовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
