Программа должна удовлетворять следующим требованиям:
· операционная система: Windows XP, Windows Vista, Windows 7.
· установленный пакет Microsoft. Net Framework 3.0.
Требования к гарантийному периоду
Гарантийный период (срок предоставления гарантии качества работ) на аппаратное обеспечение и другие работы, выполняемые в соответствии с настоящим контрактом составляет 24 месяцев с момента утверждения акта сдачи-приемки работ.
В случае выявления в течение этого срока недостатков в программах для ЭВМ или иных разработках, составляющих результаты работ, Исполнитель обязуется по требованию Заказчика незамедлительно устранять такие недостатки за свой счет. При этом гарантийный срок продлевается на период устранения недостатков.
Требования к программной документации
Программная документация должна включать следующие документы:
· техническое задание;
· рабочий проект;
· приложение (листинг исходных текстов программного изделия).
Требования к транспортированию, хранению, маркировке и упаковке
Требования не предъявляются.
Специальные требования
Специальных требований к временным характеристикам программы не предъявляется. Специальных требований к емкостным характеристикам программы не предъявляется.
ТЕХНИКО-ЭКОНОМИЧЕСКИЕ ПОКАЗАТЕЛИ
Ориентировочная экономическая эффективность не рассчитываются.
Предполагаемая годовая потребность продукта - 100 сеансов в год.
Зарубежные и отечественные аналоги не рассматриваются.
СТАДИИ И ЭТАПЫРАЗРАБОТКИ
Компьютерная программа поиска пути в лабиринте должна разрабатываться в следующем порядке:
· анализ предметной области (изучение алгоритма поиска в глубину);
· разработка технического задания;
· проектирование приложения;
· реализация приложения;
· тестирование законченной программы.
ПОРЯДОК КОНТРОЛЯ И ПРИЕМКИ
Сдача-приемка работ
Создаваемое в рамках настоящей работы программное изделие передаются Заказчику, как в виде готового модуля, так и в виде исходных кодов, представляемых в электронной форме на стандартном машинном носителе (например, записываемом компакт-диске CD-R).
Испытания
При сдаче-приёмке работ проводятся испытания с целью подтверждения работоспособности доработанных функций и соответствия требованиям ТЗ. Предварительные испытания должны проводиться Головным исполнителем в присутствии представителей Заказчика по программе и методике испытаний, составленной Головным исполнителем и согласованной с Заказчиком.
По результатам испытаний оформляются:
· протокол испытаний;
· перечень выявленных недостатков и замечаний (при их наличии);
По итогам испытаний по мере необходимости Головным исполнителем проводится корректировка документации и устранение выявленных недостатков программного обеспечения.
С целью принятия результатов работ по проекту Заказчик имеет право создать приемочную комиссию.
ПРИЛОЖЕНИЕ
Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
При поиске в глубину всегда развертывается самый глубокий узел в текущей периферии дерева поиска. Поиск непосредственно переходит на самый глубокий уровень дерева поиска, на котором узлы не имеют преемников. По мере того как эти узлы развертываются, они удаляются из периферии, поэтому в дальнейшем поиск «возобновляется» со следующего самого поверхностного узла, который все еще имеет неисследованных преемников.
Поиск в глубину имеет очень скромные потребности в памяти. Он требует хранения только единственного пути от корня до листового узла, наряду с оставшимися неразвернутыми сестринскими узлами для каждого узла пути. После того как был развернут некоторый узел, он может быть удален из памяти, коль скоро будут полностью исследованы все его потомки.
В качестве схемы работы алгоритма целесообразнее рассмотреть не блок-схему алгоритма, а выполнение его на конкретном примере, из которого станет ясна схема его работы.
 |
Рис. Схема работы алгоритма
Рассмотрим граф, и на его примере покажем схему работы алгоритма. Каждый шаг обхода графа представлен в таблице.
Таблица
Алгоритм поиска пути
| 1-й шаг | Идем от первой вершины в «глубь» графа. Пометим её второй вершиной. |
| 2-й шаг | То же самое со второй вершиной. Так появится третья вершина. |
| 3-й шаг | Аналогично появилась четвертая вершина. |
| 4-й шаг | Из четвертой вершины некуда идти, так что возвращаемся в третью. Нам есть куда идти. Появилась пятая вершина. |
| 5-й шаг | Из пятой некуда идти, из третьей - тоже. Возвращаемся во вторую. Идем в шестую вершину. |
| 6-й шаг | Теперь возвращаемся во вторую, а затем и в первую вершину. |
| 7-й шаг | Теперь пытаемся пойти в другую вершину из первой. В седьмую. |
| 8-й шаг | Из неё идем в восьмую вершину. |
| 9-й шаг | Теперь нам некуда идти. Возвращаемся в седьмую. И теперь идем в девятую. На этом обход вершин закончен. |
Применительно к нашей задаче, обход происходит следующим образом. Сначала выбирается исходная клетка. Потом выбирается клетка, стоящая слева от данной. И так далее рекурсивно происходит поиск вглубь. Если эта ветка не дала результата, то выбирается ячейка, которая расположена справа от исходной. Для нее вышеописанные операции повторяются. Затем выбирается клетка сверху и снизу, пока путь не будет найден, или пока не будут рассмотрены все варианты, и поиск не даст никаких результатов. В этом случае будет выведено сообщение о том, что путь не может быть найден.