Сегодня мы разберём мою бакалавровскую дипломную работу о построении кратчайшего вершинно несамопересекающегося пути, проходящего через обязательные вершины (задача NP‑трудна).Текст диплома довольно сложный, поэтому я постараюсь изложить его попроще и уберу доказательства вспомогательных утверждений.Давайте же пройдём путь от рассмотрения ограничений задачи и её полиномиальных аналогов до ускоренного переборного алгоритма, который добьём метаэвристиками. Читать далее
Волновой алгоритм — это алгоритм поиска пути, который использует волновое распространение для определения кратчайшего пути от начальной вершины до целевой вершины. В этой статье мы не будем рассматривать основной принцип данного алгоритма (поиск кратчайшего пути), а лишь обратимся к идее волнового алгоритма. Название алгоритма происходит от способа распространения, напоминающего распространение волн. Читать далее
Проанализируем поиск кратчайшего пути в некотором лабиринте. Из каждой клетки этого лабиринта можно ходить в соседние по горизонтали, по вертикали и по диагонали. Стоимость прохода по горизонтали или по вертикали равна единице. Стоимость прохода по диагонали равна корню квадратному из двух.При поиске будем использовать только целочисленный тип данных и не допускать никаких погрешностей в вычислениях. Для поиска кратчайшего пути будет использоваться алгоритм Дейкстры. Читать далее
При поиске кратчайшего пути на графах большого размера плохо работает традиционная оценка стоимости т.к. данные заведомо не помещаются в памяти и общая стоимость больше зависит от числа обращений к диску нежели от числа просмотренных рёбер. А число дисковых операций — весьма…