2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Модифицированный поиск в ширину для взвешенного графа
Сообщение16.12.2020, 21:54 
Аватара пользователя


26/05/12
1534
приходит весна?
mihaild в сообщении #1496805 писал(а):
Так а вы понимаете, как именно это посчитать?

Да, понимаю. Завести отдельную карту и от каждой позиции тащить за поиском индекс этой позиции, отмечая его на карте. Расход памяти, за то все данные на лицо. Если в отсев элементов очереди ещё добавить немного кода, то можно будет отрисовать границы этих областей. Это, конечно, интересная задача, но на данный момент мной не востребована.

У меня тут другая беда: А-Стар на карте с манхэттонским расстоянием на прямоугольной сетке оказывается не лучше, чем поиск в ширину. То есть он, конечно, по прямой путь находит сразу, но если надо по диагонали идти, то он, видимо, просматривает весь прямоугольник. Сложность поиска пути получается пропорциональна произведению модулей разности координат. И это без препятствий. Бред какой-то.

код: [ скачать ] [ спрятать ]
Используется синтаксис Text
..........................#####.
......#..#..........########....
....##.###........######.....#..
...#.#.............###......##..
...........................##...
....................X+....###...
...####.............+++..##.#...
..#..#.#............+.++#.##....
..##..####.#........+..+##......
........#######..++++..++#++++o.
.#####..o+++++++++....##+++.....
#.#######.+............#..+.....
########.++#............#.+.....
o++##+++++..##............+++...
..++++.......#......########+o..
.............##..........#######
..............##..######.....###
.................##########.....
...................###.....###..
.........................####...

492
209
 


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

 Профиль  
                  
 
 Re: Модифицированный поиск в ширину для взвешенного графа
Сообщение16.12.2020, 22:05 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
B@R5uk в сообщении #1496825 писал(а):
Это, конечно, интересная задача, но на данный момент мной не востребована
Так вам нужно
B@R5uk в сообщении #1496107 писал(а):
реализовать алгоритм пересчёта карты расстояний, чтобы не рассчитывать её заново целиком?
или нет?
B@R5uk в сообщении #1496825 писал(а):
но если надо по диагонали идти, то он, видимо, просматривает весь прямоугольник
Я не очень понимаю, что на вашей карте нарисовано, но так быть не должно. Если эвристическая функция точно оценивает расстояние (а без препятствий так и есть), то A* должен просмотреть ровно кратчайший путь и соседние с ним вершины.

 Профиль  
                  
 
 Re: Модифицированный поиск в ширину для взвешенного графа
Сообщение16.12.2020, 22:13 
Аватара пользователя


26/05/12
1534
приходит весна?
mihaild в сообщении #1496831 писал(а):
или нет?

Это была рабочая идея. Ну и вообще интересная задача. Просто сейчас приоритет резко изменился. Временно, надеюсь.

mihaild в сообщении #1496831 писал(а):
Я не очень понимаю, что на вашей карте нарисовано

Точки — это проходимые клетки, диезы — непроходимые. Плюсиками помечены пути от начала (крестик) до конечных точек (кружочки). Хотя бы сами пути алгоритм находит правильно.
mihaild в сообщении #1496831 писал(а):
но так быть не должно

Где-то косяк, видимо. Хотя кроме как забыть выйти, когда все пути найдены, тут трудно где-то ошибиться. Работать просто не будет.

-- 16.12.2020, 22:26 --

Хотя стоп, сортировать элементы в очереди надо не полному расстоянию, а по оценке оставшегося, верно? Не, тогда неправильно расстояния ищутся. Что-то я туплю сегодня нереально. Видимо переутомление в последние полмесяца сказываются.

-- 16.12.2020, 22:47 --

А ларчик то просто открывался! В дополнение к сортировке по полному расстоянию (пройдено + оценка), в случае совпадения значений (такое происходит очень часто) надо сортировать по величине оценки (в первую очередь брать меньше) или по величине пройденного расстояния (брать больше). Вот тогда будет быстро работать, потому что из очереди будет в первую очередь тянутся ближайший к цели элемент, а не какой-нибудь с правильным минимальным расстоянием, коих при манхэттенском способе замера расстояний будет много.

 Профиль  
                  
 
 Re: Модифицированный поиск в ширину для взвешенного графа
Сообщение17.12.2020, 09:26 
Аватара пользователя


26/05/12
1534
приходит весна?
B@R5uk в сообщении #1496832 писал(а):
В дополнение к сортировке по полному расстоянию (пройдено + оценка), в случае совпадения значений (такое происходит очень часто) надо сортировать по величине оценки (в первую очередь брать меньше) или по величине пройденного расстояния (брать больше).

Нет, это приводит к неправильному поиску. Скорее всего это происходит из-за того, что позиции исключаются из поиска раньше, чем до них находится кратчайший путь. Видимо, надо ещё раз всё перепроверить.

 Профиль  
                  
 
 Re: Модифицированный поиск в ширину для взвешенного графа
Сообщение17.12.2020, 11:20 
Аватара пользователя


26/05/12
1534
приходит весна?
B@R5uk в сообщении #1496898 писал(а):
Скорее всего это происходит из-за того, что позиции исключаются из поиска раньше, чем до них находится кратчайший путь.

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

 Профиль  
                  
 
 Re: Модифицированный поиск в ширину для взвешенного графа
Сообщение19.12.2020, 16:48 
Аватара пользователя


26/05/12
1534
приходит весна?
B@R5uk в сообщении #1496107 писал(а):
Тем не менее, надо будет попробовать реализовать тот же код, но с приоритетной очередью

Реализовал:

код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class Study_Modified_BFS_Dijkstra_Queue {
   
    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 [] [] stepCostMap;
    private static int [] [] distanceMap;
   
    private static int iterationsCount;
    private static int comparisonsCount;
   
    public static void main(String[] args) {
       
        initializeMaps ();
       
        iterationsCount = 0;
        comparisonsCount = 0;
       
        performDijkstraSearch (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 ();
        stepCostMap = new int [height] [width];
        distanceMap = new int [height] [width];
       
        for (k = 0; height > k; ++k) {
            for (l = 0; width > l; ++l) {
                switch (sourceMap [k] .charAt (l)) {
                case '.':
                    stepCostMap [k] [l] = dotStepTime;
                    break;
                default:
                    stepCostMap [k] [l] = spaceStepTime;
                }
                distanceMap [k] [l] = Integer .MAX_VALUE;
            }
        }
    }
   
    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", distanceMap [k] [l]));
            }
            System .out .println ();
        }
        System .out .println ();
    }
   
    private static void performDijkstraSearch (int x0, int y0) {
        int k, x, y;
        final int [] dx = {0, -1, 1, 0};
        final int [] dy = {-1, 0, 0, 1};
        Queue <QueueRecordClass> queue;
        QueueRecordClass queueRecord, newQueueRecord;
       
        queue = new PriorityQueue <> ();
        newQueueRecord = new QueueRecordClass (x0, y0, 0);
        newQueueRecord .setMapValue (distanceMap);
        queue .add (newQueueRecord);
       
        while (!queue .isEmpty ()) {
            ++iterationsCount;
            queueRecord = queue .poll ();
//            System .out .println (iterationsCount + " " + queueRecord .x + " " + queueRecord .y + " " + queueRecord .distance);
            if (queueRecord .getMapValue (distanceMap) < queueRecord .distance) {
                continue;
            }
            for (k = 0; 4 > k; ++k) {
                x = queueRecord .x + dx [k];
                y = queueRecord .y + dy [k];
                if (0 > x || 0 > y || width <= x || height <= y) {
                    continue;
                }
                newQueueRecord = new QueueRecordClass (x, y, 0);
                newQueueRecord .distance =
                        queueRecord .distance +
                        newQueueRecord .getMapValue (stepCostMap);
                if (newQueueRecord .getMapValue (distanceMap) <= newQueueRecord .distance) {
                    continue;
                }
                newQueueRecord .setMapValue (distanceMap);
                queue .add (newQueueRecord);
            }
        }
    }
   
    private static class QueueRecordClass implements Comparable <QueueRecordClass> {
       
        int x, y, distance;
       
        public QueueRecordClass (int x, int y, int distance) {
            this .x = x;
            this .y = y;
            this .distance = distance;
        }
       
        public int getMapValue (int [] [] map) {
            return map [y] [x];
        }

        public void setMapValue (int [] [] map) {
            map [y] [x] = distance;
        }

        @Override
        public int compareTo(QueueRecordClass arg) {
            ++comparisonsCount;
            return distance - arg .distance;
        }
    }
}
 


Результаты вроде те же самые:

код: [ скачать ] [ спрятать ]
Используется синтаксис 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 = 4694
 


Только число сравнений в 2 раза меньше. Это ещё, конечно, не решённый вопрос быстродействия. Надо покрутить разные размеры карт и положения препятствий на них. Но вывод можно сделать: очередь работает быстрее.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group