Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
frutty
1 / 1 / 3
Регистрация: 11.05.2013
Сообщений: 31
#1

Нахождение пути от одной ячейки к другой в массиве - C++

30.10.2013, 19:49. Просмотров 510. Ответов 13
Метки нет (Все метки)

Дан массив NxM, изначально все элементы нули, кроме препятствий. Препятствия обозначаются -1. Указываем ячейку A и ячейку B. Нужно проложить путь от A до B с минимальным количеством изгибов, так же нельзя прокладывать по диагонали. Если это невозможно то вывод соответствующего сообщения. Путь прописывается единицами.

Прошу помочь с алгоритмом, если будет код это будет замечательно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2013, 19:49     Нахождение пути от одной ячейки к другой в массиве
Посмотрите здесь:

Нахождение критического пути C++
Нахождение кратчайшего пути от одной вершины графа до другой C++
Нахождение эйлерова пути C++
нахождение времени, потраченного на прохождение путником половины пути C++
Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней C++
Найти возможные пути для шахматной фигуры «слон» от одной клетки до другой C++
Графы. Нахождение максимального пути C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
31.10.2013, 06:50     Нахождение пути от одной ячейки к другой в массиве #2
Цитата Сообщение от frutty Посмотреть сообщение
Прошу помочь с алгоритмом
дейкстра
Цитата Сообщение от frutty Посмотреть сообщение
если будет код это будет замечательно
бесплатно я такое писать не буду, т.к. время дорого да и в задаче не всё так просто. но могу подкинуть хитрых тестов.
выкладывайте свой код, посмотрим как вы поняли задачу
frutty
1 / 1 / 3
Регистрация: 11.05.2013
Сообщений: 31
31.10.2013, 17:54  [ТС]     Нахождение пути от одной ячейки к другой в массиве #3
Спасибо за идею, но не знаете ли вы как быстро будет работать такой алгоритм при размерности массива например 1000x1000???
ТОрчОК
Заблокирован
31.10.2013, 18:52     Нахождение пути от одной ячейки к другой в массиве #4
алгоритм где все элементы - 0, с препятствиями(-1) сам додумай
C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
struct pos
{
    int a;
    int b;
    friend std::istream& operator>>(std::istream& is, pos& ob)
    {
        is >> ob.a >> ob.b;
        return is;
    }
};
 
int main()
{
    std::vector<std::vector<int>> vec(20, 20);
    pos A, B;
    for(int i = 0; i < 20; i++)
        for(int j = 0; j < 20; j++)
            vec[i][j] = 0;
    std::cin >> A >> B;
    while(A.a != B.a)
    {
        vec[A.a][A.b] = 1;
        if(A.a != B.a && A.a < B.a)
            A.a++;
        if(A.a != B.a && A.a > B.a)
            A.a--;
        if(A.b != B.b && A.b < B.b)
            A.b++;
        if(A.b != B.b && A.b > B.b)
            A.b--;
    }
 
    for(int i = 0; i < 20; i++)
    {
        for(int j = 0; j < 20; j++)
        {
            std::cout << vec[i][j] << ' ';
        }
        std::cout << std::endl;
    }
    system("pause");
    return 0;
}
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
31.10.2013, 19:03     Нахождение пути от одной ячейки к другой в массиве #5
знаю.
если реализовать алгоритм дейкстры с использованием очереди по приоритетам, то сложность E*logV операций, где V - кол-во вершин (в вашем случае 1000), а E - кол-во ребер (путем несложных расчетов получаем для вашего случая E=4000, т.е. у каждой вершины может быть по 4 связи(слева/справа/сверху/снизу)).
для вашего примера получаем 4000 * log2(1000) = 40000 (очень быстро).
если же реализовывать дейкстру просто с помощью циклов, то сложность V*V = миллион, что чуть чуть медленнее чем первый вариант, но зато реализовать легче.

Добавлено через 7 минут
ТОрчОК, вы не поняли суть задачи. там надо минимизировать количество поворотов.
Цитата Сообщение от ТОрчОК Посмотреть сообщение
с препятствиями(-1) сам додумай
а это условие перечеркивает всю вашу задумку
ТОрчОК
Заблокирован
31.10.2013, 19:07     Нахождение пути от одной ячейки к другой в массиве #6
ну так изгиб и есть поворот. только с препятствиями алгоритм будет намного сложнее.

хотя да, проглядел, что нельзя по диагонали.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
31.10.2013, 19:25     Нахождение пути от одной ячейки к другой в массиве #7
Цитата Сообщение от ya_noob Посмотреть сообщение
если реализовать алгоритм дейкстры с использованием очереди по приоритетам, то сложность E*logV операций, где V - кол-во вершин (в вашем случае 1000), а E - кол-во ребер (путем несложных расчетов получаем для вашего случая E=4000, т.е. у каждой вершины может быть по 4 связи(слева/справа/сверху/снизу)).
для вашего примера получаем 4000 * log2(1000) = 40000 (очень быстро).
если же реализовывать дейкстру просто с помощью циклов, то сложность V*V = миллион, что чуть чуть медленнее чем первый вариант, но зато реализовать легче.
ох наврал я, жестко наврал (исходную матрицу представил как матрицу смежности, что неверно). правильно будет так: V = 1000000, E = 4000000. тогда для первого варианта E*logV = 4000000 * log2(1000000) = 800 миллионов с копейками (секунд 10 точно считать будет в худшем случае). второй вариант отпадает, т.к. не дождетесь окончания работы алгоритма, если только у вас не суперкомпьютер.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
31.10.2013, 19:33     Нахождение пути от одной ячейки к другой в массиве #8
задача решается bfs-ом за линию относительно числа клеток.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
31.10.2013, 19:45     Нахождение пути от одной ячейки к другой в массиве #9
Цитата Сообщение от salam Посмотреть сообщение
задача решается bfs-ом за линию относительно числа клеток.
наверное надо жирным выделить вот это:
Цитата Сообщение от frutty Посмотреть сообщение
с минимальным количеством изгибов
не пройдет здесь bfs никаким боком.

а я между тем опять в расчетах ошибся (видимо день был сегодня тяжелый): сложность не 800 млн, а только 80 млн и считать будет в худшем случае 1 секунду
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
31.10.2013, 21:03     Нахождение пути от одной ячейки к другой в массиве #10
Цитата Сообщение от ya_noob Посмотреть сообщение
не пройдет здесь bfs никаким боком.
все же это решается bfs-ом на 0-1 графе.

Добавлено через 3 минуты
каждый изгиб равносилен переходу по ребру веса 1, каждый проход в прежнем направлении равносилен переходу по ребру веса 0.

Добавлено через 1 минуту
ну очевидно, код модифицируется так. состояние, в которое пришли по нулевому ребру пихаем в начало, состояние, в которое пришли по 1-ребру в конец.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.11.2013, 07:04     Нахождение пути от одной ячейки к другой в массиве #11
salam, отличная идея! и правда дек поможет избавиться от логарифма в оценке сложности для таких графов. но думаю некорректно такой обход называть bfs'ом
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.11.2013, 10:12     Нахождение пути от одной ячейки к другой в массиве #12
идея, к сожалению, не моя. Название тоже. Но, по-моему, это самый настоящий бфс.
scotty
28 / 28 / 1
Регистрация: 09.09.2012
Сообщений: 131
01.11.2013, 11:08     Нахождение пути от одной ячейки к другой в массиве #13
Видел несколько видов реализации алгоритмов Дейкстра, волнового и А*. То чесно скажу что меня не впечатлили скорость работы алгоритма А* когда его проверяли в спиралеобразной "карте". Но для других вариантов очень даже хорошо..это так к слову) Автору могу посоветовать создать временную матрицу в которую он занесет маску на стоимость "ребра" в его случае ячейки матрицы исходя из стартовой точки с увеличением каждого подхода на +1. После чего получим на финальную точку сумму минимальных количества шагов , останется выбрать сам путь.
Изображения
 
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2013, 14:08     Нахождение пути от одной ячейки к другой в массиве
Еще ссылки по теме:

Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
C++ Нахождение кратчайшего пути, поиск с возвратом
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
C++ Нахождение кратчайшего пути
C++ Нахождение пути к папке с файлом

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.11.2013, 14:08     Нахождение пути от одной ячейки к другой в массиве #14
Цитата Сообщение от salam Посмотреть сообщение
идея, к сожалению, не моя.
да это не важно . самое главное, что я теперь знаю хоть какое-то практическое применение деков.
Цитата Сообщение от salam Посмотреть сообщение
Но, по-моему, это самый настоящий бфс.
bfs реализуется с помощью очереди FIFO. Вы же не будете называть поиск bfs'ом, если в нем используется стек LIFO, т.к. это dfs. а тут вообще дек.
Цитата Сообщение от scotty Посмотреть сообщение
Автору могу посоветовать создать временную матрицу в которую он занесет маску на стоимость "ребра" в его случае ячейки матрицы исходя из стартовой точки с увеличением каждого подхода на +1. После чего получим на финальную точку сумму минимальных количества шагов, останется выбрать сам путь.
на предыдущей странице уже давали такие советы, но к сожалению они не верны (читайте внимательнее условие задачи)
Yandex
Объявления
01.11.2013, 14:08     Нахождение пути от одной ячейки к другой в массиве
Ответ Создать тему
Опции темы

Текущее время: 17:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru