Модифицированный поиск в ширину для взвешенного графа

[B@R5uk]

Имеется плоская карта (типа клетчатой бумаги или шестиугольничков на плоскости, где каждая ячейка соседствует с несколькими), для которой проходимость из ячейки в ячейку варьируется. Существует ли модификация алгоритма поиска в ширину для графа, соответствующей этой карте?

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

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

[mihaild]

B@R5uk в сообщении #1495856 писал(а):

Попытка прикрутить к нему очередь с приоритетом натыкается на сложность: вершины постоянно меняют значения расстояний до них.

У вас граф меняется что ли?
Если граф фиксированный. то алгоритм Дейксрты с очередью с приоритетом работает за $O((|V| + |E|)\log |V|)$ (можно улучшить до $O(|V| \log |V| + |E|)$, если использовать фибоначчиеву кучу; в вашем случае неважно, т.к. $|E| = O(|V|)$).
Если проходимость какая-то разумная - нам надо идти примерно в сторону цели - то еще может помочь алгоритм $A^*$.

[B@R5uk]

mihaild в сообщении #1495861 писал(а):

У вас граф меняется что ли?

Граф постоянный. Просто сам алгоритм в процессе работы меняет оценки для соседних вершин.

mihaild в сообщении #1495861 писал(а):

алгоритм Дейксрты с очередью с приоритетом работает за $O((|V| + |E|)\log |V|)$ (можно улучшить до $O(|V| \log |V| + |E|)$)

А можете накидать ссылочек на описание рабочего алгоритма?

А-стар не нужен. Задача стоит "взвесить" проходимость всей карты и использовать это для расчёта других оценок.

[mihaild]

B@R5uk в сообщении #1495863 писал(а):

А можете накидать ссылочек на описание рабочего алгоритма?

Да где угодно есть - на e-maxx, в википедии и т.д.

[B@R5uk]

mihaild, спасибо. Вы не представляете, как конкретные ссылки помогают, когда интернет тормозит и странички грузятся по пять-десять минут (если вообще грузятся)!

Вариант с использованием фибоначчиевой кучи мне пока переварить не под силу. В Java нет для неё готовой реализации, а самому такие вещи писать или разбираться в чужом коде — та ещё морока. Так что откладывается для будущего изучения. Там ещё вопросы с производительностью: куча имеет большой временной множитель и на малых графах проигрывает.

Разобрался вроде бы с алгоритмом и-макс. Реализовал вариант с упорядоченным множеством. Не уверен, что повторил дословно, потому что про стандартную библиотеку плюсов знаю только по наслышке. Но код, вроде, работает:

Используется синтаксис Java

import java.util.*;

public class Study_Modified_BFS_Dijkstra {
    
    private static final int spaceStepTime = 1;
    private static final int dotStepTime = 3;
    
    private static final String [] sourceMap = {
            "                          ..... ",
            "      .  .          ........    ",
            "    .. ...        ......     .  ",
            "   . .             ...      ..  ",
            "                           ..   ",
            "                          ...   ",
            "   ....                  .. .   ",
            "  .  . .                . ..    ",
            "  ..  .... .            ..      ",
            "        .......          .      ",
            " .....                ..        ",
            ". .......              .        ",
            "........   .            .       ",
            "   ..       ..                  ",
            "             .      ........    ",
            "             ..          .......",
            "              ..  ......     ...",
            "                 ..........     ",
            "                   ...     ...  ",
            "                         ....   "
    };
    
    private static int width, height;
    private static int [] [] stepTimeMap;
    private static int [] [] travelTimeMap;
    
    private static int iterationsCount;
    private static int comparisonsCount;
    
    public static void main (String [] args) {
        
        initializeMaps ();
        
        iterationsCount = 0;
        comparisonsCount = 0;
        
        performDijkstraSearch (new Position (0, 0));
        
        displayTravelMap ();
        
        System .out .println ("Iterations Count  = " + iterationsCount);
        System .out .println ("Comparisons Count = " + comparisonsCount);
    }
    
    private static void initializeMaps () {
        int k, l;
        
        height = sourceMap .length;
        width = sourceMap [0] .length ();
        stepTimeMap = new int [height] [width];
        travelTimeMap = new int [height] [width];
        
        for (k = 0; height > k; ++k) {
            for (l = 0; width > l; ++l) {
                switch (sourceMap [k] .charAt (l)) {
                case '.':
                    stepTimeMap [k] [l] = dotStepTime;
                    break;
                default:
                    stepTimeMap [k] [l] = spaceStepTime;
                }
                travelTimeMap [k] [l] = Integer .MAX_VALUE;
            }
        }
    }
    
    private static void performDijkstraSearch (Position startPosition) {
        int k, time;
        SortedSet <Position> positionsSet;
        Position [] neighbors;
        Position currentPosition, newPosition;
        
        positionsSet = new TreeSet <> ();
        startPosition .setTravelTime (0);
        positionsSet .add (startPosition);
        
        while (!positionsSet .isEmpty ()) {
            currentPosition = positionsSet .first ();
            positionsSet .remove (currentPosition);
            neighbors = currentPosition .getNeighbors ();
            for (k = 0; neighbors .length > k; ++k) {
                newPosition = neighbors [k];
                time = currentPosition .getTravelTime () + newPosition .getStepTime ();
                if (newPosition .getTravelTime () > time) {
                    positionsSet .remove (newPosition);
                    newPosition .setTravelTime (time);
                    positionsSet .add (newPosition);
                }
            }
            ++iterationsCount;
        }
    }
    
    private static void displayTravelMap () {
        int k, l;
        
        for (k = 0; height > k; ++k) {
            for (l = 0; width > l; ++l) {
                System .out .print (String .format ("%3d", travelTimeMap [k] [l]));
            }
            System .out .println ();
        }
        System .out .println ();
    }
    
    private static class Position implements Comparable <Position> {
        
        private int x, y;
        
        public Position (int arg_x, int arg_y) {
            x = arg_x;
            y = arg_y;
        }
        
        public int getStepTime () {
            return stepTimeMap [y] [x];
        }
        
        public int getTravelTime () {
            return travelTimeMap [y] [x];
        }
        
        public void setTravelTime (int value) {
            travelTimeMap [y] [x] = value;
        }
        
        public Position [] getNeighbors () {
            int count;
            Position [] result;
            
            count = 4;
            
            if (0 == x || width == x + 1) {
                --count;
            }
            if (0 == y || height == y + 1) {
                --count;
            }
            
            result = new Position [count];
            
            count = 0;
            
            if (0 < y) {
                result [count] = new Position (x, y - 1);
                ++count;
            }
            if (0 < x) {
                result [count] = new Position (x - 1, y);
                ++count;
            }
            if (width > x + 1) {
                result [count] = new Position (x + 1, y);
                ++count;
            }
            if (height > y + 1) {
                result [count] = new Position (x, y + 1);
            }
            
            return result;
        }

        @Override
        public int compareTo (Position arg) {
            int value;
            
            ++comparisonsCount;
            
            value = travelTimeMap [y] [x] - travelTimeMap [arg .y] [arg .x];
            if (0 != value) {
                return value;
            }
            value = y - arg .y;
            if (0 != value) {
                return value;
            }
            return x - arg .x;
        }
    }
}
 

Результат работы:

Используется синтаксис Text

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 28 31 34 37 38 37
  1  2  3  4  5  6  9  8  9 12 11 12 13 14 15 16 17 18 19 20 23 24 25 26 27 28 31 34 33 34 35 36
  2  3  4  5  8  9 10 11 12 15 12 13 14 15 16 17 18 19 22 23 26 27 28 29 28 29 30 31 32 35 36 37
  3  4  5  8  9 12 11 12 13 14 13 14 15 16 17 18 19 20 21 24 27 28 27 28 29 30 31 32 35 38 37 38
  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 33 36 37 38 39
  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 33 36 39 38 39 40
  6  7  8 11 12 13 14 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 33 36 37 40 39 40 41
  7  8 11 12 13 16 15 16 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 33 34 37 40 41 40 41 42
  8  9 12 15 14 15 18 19 18 19 18 21 20 21 22 23 24 25 26 27 28 29 30 31 34 37 38 39 40 41 42 43
  9 10 11 12 13 14 15 16 19 22 21 24 23 24 25 24 25 26 27 28 29 30 31 32 33 36 37 38 39 40 41 42
 10 13 14 15 16 17 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 34 35 34 35 36 37 38 39 40 41
 13 14 17 18 19 20 19 20 21 20 21 22 23 24 25 26 27 28 29 30 31 32 33 36 35 36 37 38 39 40 41 42
 16 17 20 21 22 23 22 23 22 21 22 25 24 25 26 27 28 29 30 31 32 33 34 35 38 37 38 39 40 41 42 43
 17 18 19 22 25 24 23 24 23 22 23 24 27 28 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
 18 19 20 21 22 23 24 25 24 23 24 25 26 29 28 29 30 31 32 33 36 37 38 39 40 41 42 43 42 43 44 45
 19 20 21 22 23 24 25 26 25 24 25 26 27 30 31 30 31 32 33 34 35 36 37 38 39 42 45 46 45 46 47 48
 20 21 22 23 24 25 26 27 26 25 26 27 28 29 32 33 32 33 36 37 38 39 40 41 40 41 42 43 44 47 50 51
 21 22 23 24 25 26 27 28 27 26 27 28 29 30 31 32 33 36 39 40 41 42 43 44 43 44 45 44 45 46 47 48
 22 23 24 25 26 27 28 29 28 27 28 29 30 31 32 33 34 35 36 39 42 43 42 43 44 45 46 47 48 49 48 49
 23 24 25 26 27 28 29 30 29 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 46 49 50 51 50 49 50

Iterations Count  = 640
Comparisons Count = 9099
 

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

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

[mihaild]

B@R5uk в сообщении #1496107 писал(а):

реализовать тот же код, но с приоритетной очередью и кастомарным компаратором, и сравнить быстродействие

По идее очередь должна работать гораздо быстрее. Точнее её нужно очень криво реализовать, чтобы она не обогнала множество в несколько раз.

B@R5uk в сообщении #1496107 писал(а):

Если после расчёта расстояний эти позиции по одной удалять, то можно ли реализовать алгоритм пересчёта карты расстояний, чтобы не рассчитывать её заново целиком?

Можно. Пусть мы удалили одну из стартовых позиций. До каких ячеек кратчайшее расстояние изменится?

[B@R5uk]

mihaild в сообщении #1496110 писал(а):

До каких ячеек кратчайшее расстояние изменится?

До некоторой области, вырастающей из исчезнувшей позиции. Вот только границы этой области я пока даже не представляю как рассчитывать. А ведь чтобы пересчитать расстояния в этой области начинать придётся как раз с её границы.

[B@R5uk]

Похоже, то что мне нужно — это несколько применений Single-Source Multi-Target A* Algorithm с последующим применением Венгерского алгоритма. Сколько всего изучать и разбираться, сколько всего я не знаю!

[mihaild]

B@R5uk в сообщении #1496680 писал(а):

Вот только границы этой области я пока даже не представляю как рассчитывать

Как в данном случае определяется граница? Из приходящего мне в голову определения непосредственно следует способ проверки клетки, принадлежит ли она этой границе.

[B@R5uk]

mihaild в сообщении #1496707 писал(а):

непосредственно следует способ проверки клетки

Не поделитесь?

[mihaild]

B@R5uk в сообщении #1496750 писал(а):

Не поделитесь?

Я думаю что вы можете сами догадаться. Какое определение этой "границе" вы дали бы?

[B@R5uk]

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

[mihaild]

Да, это всё очень сложно. Вы правильно начали

B@R5uk в сообщении #1496680 писал(а):

До некоторой области, вырастающей из исчезнувшей позиции

Уточните на всякий случай - что именно значит "область, вырастающая из исчезнувшей позиции"? (это область для каждой стартовой ячейки можно найти сразу во время поиска в ширину)

[B@R5uk]

mihaild в сообщении #1496794 писал(а):

это область для каждой стартовой ячейки можно найти сразу во время поиска в ширину

Вот это, пожалуй, ключевая идея для пересчёта расстояний при удалении стартовой позиции.

[mihaild]

B@R5uk в сообщении #1496801 писал(а):

Вот это, пожалуй, ключевая идея для пересчёта расстояний при удалении стартовой позиции

Так а вы понимаете, как именно это посчитать? Мы для каждой ячейки хотим посчитать, к какой области (=стартовой ячейке) она относится.