Лекция
Привет, Вы узнаете о том , что такое алгоритм шимбелла, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое алгоритм шимбелла , настоятельно рекомендую прочитать все из категории Физические основы механики.
Данная статья о сложном алгоритме поиска маршрута в графах. К слову, графы не только труднее для понимания, но и необычны для визуального восприятия. Правда, только сначала. А речь пойдет сегодня об алгоритме Шимбелла.
Нашей главной задачей будет найти кратчайший путь. Но сам путь уже будет другим. Вот так (см. рис) выглядит ориентированный граф.
Очевидно, что маршруты здесь более запутанные, так как вершины имеют разные расстояния между собой. Кстати, разным может быть не только расстояние, а допустим и стоимость поездки тоже. Вообще, критерий для выбора маршрута может быть любым. Но на его основании нужно создать граф.
На основе графы строится матрица. Эта матрица отображает расстояния между доступными вершинами графа. Она называется матрицей весов.
На графе по стрелкам направлений видно, что мы можем попасть из четвертой вершины графа в пятую и обратно тоже. А вот из второй вершины можно попасть в пятую, а обратно — никак. Соответственно, заполняются и поля матрицы. Если прохода нет, мы пишем 0.
Матрица весов
|
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
10 |
0 |
0 |
0 |
|
2 |
0 |
0 |
12 |
0 |
8 |
|
3 |
0 |
0 |
0 |
8 |
0 |
|
4 |
0 |
6 |
8 |
0 |
3 |
|
5 |
0 |
0 |
0 |
3 |
0 |
Одно из математических решений таких задач — алгоритм шимбелла , основанный на хитром сложении матриц. В чем его хитрость? Чтобы узнать путь кратчайший путь от одной вершины к другой из двух ребер, мы складываем поочередно каждый элемент соответствующей номерам вершин строки и столбца. Причем операции, где фигурирует хотя бы один ноль, мы игнорируем. А из получившихся при сложении пар элементов кратчайших цифр выбираем наименьшую. Представить граф очень просто — вообразите себе сеть дорог с блок-постами, где-нибудь на Донбассе или в Сирии. Вполне могут сложиться ситуации, когда одни посты будут закрыты, другие получат приказ пропускать беженцев только в одну сторону, а с третьих их охрана, вообще, сбежит, оставив свободный путь. Вот вам и ориентированный граф. Матрица весов будет основным инструментом, с которым нам предстоит работать.
Итак, путь от элемента 3 к элементу 2.
0+10 (0)
0+ 0 (0)
0 +0 (0)
8+6 (14)
0+0 (0)
Единственная операция, которая удовлетворяет нашим условиям, дает 14. Теперь посмотрите на рисунок в самом верху – единственный кратчайший путь из двух ребер от вершины 3 к вершине 2, через 4-ю имеет вес 14. На матрице для кратчайших путей из двух ребер, изображенной ниже.
Матрица для кратчайших путей из двух ребер
|
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
0 |
22 |
0 |
18 |
|
2 |
0 |
0 |
0 |
11 |
0 |
|
3 |
0 |
14 |
0 |
0 |
11 |
|
4 |
0 |
0 |
18 |
0 |
14 |
|
5 |
0 |
9 |
11 |
0 |
0 |
Алгоритм кажется несколько сложным, но на самом деле это очень примитивная арифметика. Об этом говорит сайт https://intellect.icu . А уж программируется она и вовсе несколькими строчками, если не «рисовать» визуальный интерфейс. Но… крепко подумать при этом все же придется, если подзабыты правила работы с двумерными матрицами.
Я решил не напрягать вас и разработал элементарное решение. В первом приближении нам нужно в двойном цикле пройти все элементы двумерного массива. Нужен и третий цикл внутри двух первых, который будет на каждом шаге складывать элемент искомых строки и столбца.
При этом нужно создать простейший набор условий, который поможет нам отбросить операции, где фигурирует хоть один ноль, и операции с одинаковыми номерами строки и столбца (см. пример: элемент с адресом 3.4 просчитать можно, а вот 3.3 – это вершина 3. А из вершины 3 мы не можем пройти в вершину 3, мы уже там находимся).
При вычислении матрицы для путей из трех ребер необходимо будет складывать элементы строки и столбца первой и второй полученной матриц. В самом алгоритме изменятся только слагаемые. Переписывать его уже не потребуется.
|
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
0 |
0 |
21 |
0 |
|
2 |
0 |
17 |
19 |
0 |
23 |
|
3 |
0 |
0 |
26 |
0 |
22 |
|
4 |
0 |
12 |
14 |
17 |
19 |
|
5 |
0 |
0 |
21 |
0 |
17 |
Блок-схема алгоритма нахождения кратчайших путей в графе методом Шимбелла
Алгоритм Шимбелла — далеко не самый эффективный, с точки зрения расхода памяти и скорости выполнения вид поиска кратчайших граней но он весьма полезен с точки зрения понимания работы циклов и условий. Поэтому, задания с ним очень любят преподаватели вузов.
Итак: небольшой фрагмент кода на языке Java, который обеспечивает поиск кратчайших путей из двух и трех ребер графа. Код работает, его можно использовать для создания собственных методов, классов и решения лабораторных работ.
Исследование, описанное в статье про алгоритм шимбелла, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое алгоритм шимбелла и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Физические основы механики
Из статьи мы узнали кратко, но содержательно про алгоритм шимбелла
Комментарии
Оставить комментарий
Физические основы механики
Термины: Физические основы механики