Ищем кратчайшие пути: Алгоритм Шимбелла

Данная статья о сложном алгоритме поиска маршрута в графах. К слову, графы не только труднее для понимания, но и необычны для визуального восприятия. Правда, только сначала. А речь пойдет сегодня об алгоритме Шимбелла.

Нашей главной задачей будет найти кратчайший путь. Но сам путь уже будет другим. Вот так (см. рис) выглядит ориентированный граф.

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

На основе графы строится матрица. Эта матрица отображает расстояния между доступными вершинами графа. Она называется матрицей весов.

На графе по стрелкам направлений видно, что мы можем попасть из четвертой вершины графа в пятую и обратно тоже. А вот из второй вершины можно попасть в пятую, а обратно — никак. Соответственно, заполняются и поля матрицы. Если прохода нет, мы пишем 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

 

Алгоритм кажется несколько сложным, но на самом деле это очень примитивная арифметика. А уж программируется она и вовсе несколькими строчками, если не «рисовать» визуальный интерфейс. Но… крепко подумать при этом всё же придется, если подзабыты правила работы с двумерными матрицами.

Я решил не напрягать вас и разработал элементарное решение. В первом приближении нам нужно в двойном цикле пройти все элементы двумерного массива. Нужен и третий цикл внутри двух первых, который будет на каждом шаге складывать элемент искомых строки и столбца. 

При этом нужно создать простейший набор условий, который поможет нам отбросить операции, где фигурирует хоть один ноль, и операции с одинаковыми номерами строки и столбца (см. пример: элемент с адресом 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, который обеспечивает поиск кратчайших путей из двух и трех ребер графа. Код работает, его можно использовать для создания собственных методов, классов и решения лабораторных работ.

public class Shim {
            public static void main(String[] args) {
                        // TODO Auto-generated method stub
 
                        int n = 5;
                        int v = 0;
                        int i = 0;
                        int l = 0;
                        int f = 0;
                        int j = 0;
                        int w = j;
                        int [][] MatricaVesov = {{0,10,0,0,0},{0,0,12,6,8},{0,0,0,8,0},{0,0,0,0,3},{0,3,0,3,0}};
                                  
                                   int [][] Matrix2Top = new int [n][n];
                                    int [][] Matrix3Top = new int [n][n];
                                                                      
                                   System.out.println("Матрица весов первой степени степени");
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           System.out.printf("%3d", MatricaVesov[i][j]);
                                               }
                                               System.out.println();
                                   }                                             
           
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           f = i;
                                               w = j;
                                                           for (l = 0; l < n; l++)    {
                                                                                                                     
            v = MatricaVesov[i][l] + MatricaVesov[l][j];
if(MatricaVesov[i][l] != 0 && MatricaVesov[l][j] != 0&&MatricaVesov[i][l]!=MatricaVesov[l][j]) {
                                                                       Matrix2Top[i][j] = v;
                                                           }
                                               }
                                   }
                                   }
                                   System.out.println();
                                   System.out.println("Матрица весов второй степени");
                                   System.out.println();
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           System.out.printf("%3d", Matrix2Top[i][j]);
                                               }
                                               System.out.println();
                                   }                     
                                  
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           f = i;
                                               w = j;
                                                           for (l = 0; l < n; l++)    {
                                                          
                                                                      
            v = MatricaVesov[i][l] + Matrix2Top[l][j];
if(MatricaVesov[i][l] != 0 && Matrix2Top[l][j] != 0&&MatricaVesov[i][l]!=Matrix2Top[l][j]) {
                                                                       Matrix3Top[i][j] = v;
                                                                      
                                                                       }
                                               }
                                   }
                                   }
                                   System.out.println();
                                   System.out.println("Матрица весов третьей степени");
                                   System.out.println();
                                                                       for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           System.out.printf("%3d", Matrix3Top[i][j]);
                                               }
                                               System.out.println();
                                   }                     
            }
 

Эдуард Трошин

Версия для печатиВерсия для печати

Рубрики: 

  • 1
  • 2
  • 3
  • 4
  • 5
Всего голосов: 0
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!

Комментарии

Страницы

Аватар пользователя Al

"Никто из тех, кому я это показываю, включая действующих программистов, ничего не понял" - Ээээ... извините, а зачем тогда писать так непонятно?

Аватар пользователя Petro45

 Ээээ... извините, а зачем тогда писать так непонятно?

А что именно непонятно, как в циклах пройти двумерный массив?:-) 

Да зачем им, вообще, это читать, они знать должны. А для новичков у меня всё понятно написано: простые действия, простые условия. Кто захочет вникнуть - легко вникнет. 

Аватар пользователя mike

Никто из тех, кому я это показываю, включая действующих программистов, ничего не понял. Возможно, такие "специалисты".

А возможно, от вас просто отмахивались.

Вставлю и я свои обычные в случае Петра 5 копеек.

"По адресу http://qiao.github.com/PathFinding.js/visual есть онлайн-демо с симпатичной визуализацией выполнения алгоритмов. Здесь скорость искусственно занижена (для красоты)."

javascript - симпатичной визуализацией - вот почему я ратую, Пётр, на переход к javascript - ВИЗУАЛИЗАЦИЯ!!!!

Сейчас поддерживается 11 алгоритмов:

  • AStarFinder *
  • BreadthFirstFinder *
  • BestFirstFinder
  • DijkstraFinder *
  • BiAStarFinder
  • BiBestFirstFinder
  • BiDijkstraFinder *
  • BiBreadthFirstFinder *
  • JumpPointFinder *
  • OrthogonalJumpPointFinder *
  • Trace


Для алгоритмов реализованы три эвристики расчёта расстояния: Manhattan (расстояние городских кварталов), евклидова метрика и расстояние Чебышёва. Каждая из них использует эвристический анализ, чтобы определить перспективность возможного направления дальнейшего пути, то есть каково расстояние от соседних квадратов до цели, в соответствии с определением расстояния.

Аватар пользователя Petro45

А возможно, от вас просто отмахивались.

Не исключено. Но даже просто "знаю" никто сказать не решился. 

Сейчас поддерживается 11 алгоритмов:

Да, я читал эту статью Ализара. 

...реализованы три эвристики расчёта расстояния

У меня будет статья об эвристике в алгоритме А*. По-крайней мере, я её планирую. Фишка в том, что механизм работы алгоритма не всегда можно понять, даже по такой классной визуализации. Лучше просто запомнить, как он реализуется. 

К слову, следующий материал я специально посвящу алгоритму, который очень прост в программировании но практически невозможен для интуитивного понимания. Естественно, обычному человеку. Может, какой Каспаров и поймет...

petro45 > Фишка в том, что механизм работы алгоритма не всегда можно понять, даже по такой классной визуализации.

Это так. Но фишка в том, что если есть вообще визуализация, то можно допиливать (меняя) саму визуализацию также.

Аватар пользователя Petro45

Это так. Но фишка в том, что если есть вообще визуализация, то можно допиливать (меняя) саму визуализацию также.

Не понял, зачем там что-то допиливать? Вот это вы предлагали допиливать? Это ещё года два разбираться надо....

var parseMap = require('./parse_map').parse;
var parseScen = require('./parse_scen').parse;
var testCases = require('./test_cases');
+var path = require('path');
function profile(callback) {
var startTime = Date.now();
@@ -54,17 +55,13 @@ function map2grid(map) {
return new PF.Grid(map.width, map.height, map.grid);
}
-
testCases.forEach(function(test) {
-
- var grid = map2grid(parseMap(test.map));
- var scens = parseScen(test.scen).scenarios;
+ var grid = map2grid(parseMap(path.join(__dirname, test.map)));
+ var scens = parseScen(path.join(__dirname, test.scen)).scenarios;
var select = test.select;
select.forEach(function(id) {
-
var scen = scens[id];
-
var result = benchmark({
header: 'AStarFinder',
finder: new PF.AStarFinder({allowDiagonal: true}),
@@ -75,7 +72,5 @@ testCases.forEach(function(test) {
endY: scen.endY,
footer: '(optimal: '.grey + (''+scen.length).green + ')'.grey
});
-
});
-
});

>Это ещё года два разбираться надо....

Surprised

Ну, меньше, гораздо меньше. Smile

Аватар пользователя Petro45

Ну, меньше, гораздо меньше. Smile

Ну, теоретизировать-то гораздо проще. :-) Попробуйте вы, а мы - подтянемся. 

petro45 > Попробуйте вы, а мы - подтянемся.

Вот смотрите, вы можете и дальше развивать алгоритмы решения разных интересных математических задач на Java, но упрётесь в тупик - нет визуализации, не считать же визуализацией вызов методов типа:

System.out.println(...);



Javascript в операторах и функциях работы с массивами ли и прочим - он не хуже Java и аналогичен.

Но Javascript даст вам возможно понемногу, но с каждым разом всё больше и больше возможность визуализировать ваше решение! А иначе то как? Иначе тупик. Имхо.

Страницы