Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
dima-dima
1 / 1 / 3
Регистрация: 27.11.2012
Сообщений: 146
1

Поиск всех маршрутов

18.02.2018, 15:32. Просмотров 332. Ответов 6
Метки нет (Все метки)

Добрый день. Нужна теоретическая помощь по следующей задаче.
Дано квадратное поле. Найти количество существующих маршрутов из левого верхнего угла в правый нижний.
Ограничения:
1. Заданы некоторые координаты на поле, на которые заходить нельзя.
2. Двигаться можно либо вниз, либо направо. Влево и вверх нельзя.
3. Использовать, например, списки.

Какие известные алгоритмы можно использовать для решения этой задачи? Нужна ли тут рекурсия и как её применить?
Спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2018, 15:32
Ответы с готовыми решениями:

Хранение маршрутов (путей графа) в БД
Что-то без поллитры не соображу как хранить маршруты в базе данных. Маршрут -динамическая...

поиск всех цепочек фирм
День добрый, знатоки! :) Недавно встретился вот с такой задачей: Есть несколько фирм,...

Алгоритм нахождения маршрутов общественного транспорта
Идея следующая: есть город, у города есть дороги, на которых стоят остановки. В городе существует...

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

Двоичный поиск в массиве ВСЕХ вхождений искомого элемента
У Вики есть такой чудесный код: def check(x, m): return x < m def binSearch(lst, x): #...

6
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
18.02.2018, 18:11 2
Эта классическая задача динамического программирования.

Исходно дана таблица, в каждой ячейке которого булева величина, указывающая на наличие или отсутствие препятствия.
Создадим другую таблицу того же размера, в каждой ячейке которой (по окончанию алгоритма) будет количество маршрутов из этой точки в правый нижний угол. Ответом к задаче будет число в первой строке первого столбца. Задачу сведём к задаче заполнения этой таблицы.
Заметим, что правый нижный элемент имеет значение 1.
Заметим, что на нижней строке и правом столбце все значений <1 ввиду ограничения (2). Если на нижней строке или правом столбце есть препятствия, то часть будет заполнена 0 (не расписываю детально, это очевидно).
Заметим, что в любой другой точке (i,j) количество маршрутов равно a+b, где
a=0, если ячейка снизу (i,j+1) занята препятствием,
a равно значению в (i,j+1) ячейке иначе,
b=0, если ячейка справа (i+1,j) занята препятствием,
b равно значению в (i+1,j) иначе.

Как это положить в код, рекурсией или циклом, вопрос реализации.
0
ROS88
Нарушитель
130 / 129 / 99
Регистрация: 10.03.2015
Сообщений: 533
18.02.2018, 18:11 3
Я бы для задачи такого типа пробовал применить алгоритм обхода графа в глубину. Исходя из того, что в Вашем случае двигаться можно только по указанным направлениям, то и рассматриваемый граф должен быть ориентированным.
0
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
18.02.2018, 18:32 4
ROS88, жаль, что я написал чуть раньше. Нетерпеливый.

Дополню мною сказанное.
Вот пример заведомо неэффективной реализации, которая использует рекурсию.
https://ideone.com/hFzcYM
Код
Haskell
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
pathCount :: [[Bool]] -> Int
pathCount matrix = count (0,0)
  where
    n = length matrix - 1 -- максимальный индекс
    count (i,j) = if i == n && j == n then 1 else a + b
      where
        a = if j == n || ((matrix !! i) !! (j+1)) then 0 else count (i, j + 1)
        b = if i == n || ((matrix !! (i+1)) !! j) then 0 else count (i + 1, j)
 
testMatrix1 :: [[Bool]]
-- ...
-- .#.
-- ...
testMatrix1 = [[ False, False, False ],[ False, True, False ],[ False, False, False ]]
testMatrix2 = map (map (== '#')) [
  ".#..",
  "...#",
  ".#..",
  "...."
  ]
testMatrix3 = map (map (== '#')) [
  "..#.",
  "..#.",
  "....",
  ".##."
  ]
 
main = do
  print (pathCount testMatrix1) -- 2
  print (pathCount testMatrix2) -- 3
  print (pathCount testMatrix3) -- 3
0
ROS88
Нарушитель
130 / 129 / 99
Регистрация: 10.03.2015
Сообщений: 533
18.02.2018, 18:40 5
Цитата Сообщение от Mysterious Light Посмотреть сообщение
ROS88, жаль, что я написал чуть раньше. Нетерпеливый.
Не совсем понимаю о чем ты.
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,428
19.02.2018, 10:27 6
Логическая задача на количество путей
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,428
19.02.2018, 10:29 7
Цитата Сообщение от ROS88 Посмотреть сообщение
Я бы для задачи такого типа пробовал применить алгоритм обхода графа в глубину.
Плохо.
0
19.02.2018, 10:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.02.2018, 10:29

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

Список всех маршрутов, отправляются утром до 10 часов
- Список всех маршрутов, отправляются утром до 10 часов; - Список перевозчиков, чьи маршруты позже...

Выведение всех возможных маршрутов в неориентированном графе
Помогите пожалуйста составить программу для выведения всех возможных маршрутов в неориентированном...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru