Реализация алгоритмов поиска Курсовая работа (проект)

Теория графов представляет собой один из наиболее важных и интересных, но в то же время один из самых сложных и непонятных разделов в информатике. Круг задач, решаемый при помощи теории графов, очень обширный, что делает актуальным применение алгоритмов на графах по сей день. В частности, если требуется рассчитать какие-либо параметры маршрутов, то теория графов с её богатым математическим аппаратом оказывает помощь при решении поставленных задач. Часто бывает полезно и наглядно изображать некоторую ситуацию в виде рисунка, состоящего из точек вершин, представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графов. Благодаря своему широкому применению теория графов в последние годы интенсивно развивается. В большой мере этому способствует также прогресс в области развития больших быстродействующих вычислительных машин. Непосредственное и детальное представление практических систем, таких, как распределительные сети и системы связи, приводит к графам большого размера успешный анализ которых зависит в равной степени как от существования "хороших" алгоритмов, так и от возможности использования быстродействующих вычислительных машин.

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