Решение задач на тему: Работа алгоритма поиска в ширину. Неформальное описание. Формальное описание

Введение

Алгоритм - набор инструкций <https://ru.wikipedia.org/wiki/%D0%9Е%D0%ВF%D0%В5%D1%80%D0%В0%D1%82%D0%ВЕ%D1%80_%28%D0%ВF%D1%80%D0%ВЕ%D0%В3%D1%80%D0%В0%D0%ВС%D0%ВС%D0%В8%D1%80%D0%ВЕ%D0%В2%D0%В0%D0%ВD%D0%В8%D0%В5%29>, описывающих порядок действий исполнителя для достижения результата решения задачи <https://ru.wikipedia.org/wiki/%D0%А0%D0%В5%D1%88%D0%В5%D0%ВD%D0%В8%D0%B5_%D0%В7%D0%В0%D0%В4%D0%В0%D1%87> за конечное число действий. В старой трактовке вместо слова "порядок" использовалось слово "последовательность", но по мере развития параллельности в работе компьютеров слово "последовательность" стали заменять более общим словом "порядок". Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Ранее часто писали "алгорифм", сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм <https://ru.wikipedia.org/wiki/%D0%9D%D0%ВЕ%D1%80%D0%ВС%D0%В0%D0%ВВ%D1%8С%D0%ВD%D1%8В%D0%B9_%D0%В0%D0%ВВ%D0%В3%D0%ВЕ%D1%80%D0%В8%D1%84%D0%ВС> Маркова <https://ru.wikipedia.org/wiki/%D0%9С%D0%В0%D1%80%D0%ВА%D0%ВЕ%D0%В2,_%D0%90%D0%ВD%D0%В4%D1%80%D0%В5%D0%B9_%D0%90%D0%ВD%D0%В4%D1%80%D0%В5%D0%В5%D0%В2%D0%В8%D1%87_%28%D0%ВС%D0%ВВ%D0%В0%D0%В4%D1%88%D0%В8%D0%В9%29>).

Часто в качестве исполнителя выступает некоторый механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма необязательно относится к компьютерным программам <https://ru.wikipedia.org/wiki/%D0%9А%D0%ВЕ%D0%ВС%D0%ВF%D1%8С%D1%8Е%D1%82%D0%В5%D1%80%D0%ВD%D0%В0%D1%8F_%D0%ВF%D1%80%D0%ВЕ%D0%В3%D1%80%D0%В0%D0%ВС%D0%ВС%D0%В0>, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.

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

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

Рисунок 1 - Поиск в ширину

Оглавление

- Введение

- Работа алгоритма поиска в ширину

- Неформальное описание

- Формальное описание

- Схема алгоритма поиска в ширину

- Примеры реализации Заключение

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

Заключение

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

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

- Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Энергоатомиздат, 1988. - 480 с.

- Коршунов Ю.М. Математические основы кибернетики: Учеб. Пособие для вузов. - 3-е изд. перераб. и доп. - М.: Энергоатомиздат, 1987. - 496 с.: ил.

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

- Яблонский С.В. Введение в дискретную математику: Учебное пособие для Вузов/ Под ред.В.А. Садовничего - 3-е изд. стер. - М.: Высш. шк., 2001. - 384 с.

- Липский В. Комбинаторика для программистов. М.: Мир, 1988. - 213 С.

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