Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
flambo
27 / 27 / 7
Регистрация: 03.10.2009
Сообщений: 122
1

Нахождение количества кратчайших путей

07.12.2010, 23:36. Просмотров 1355. Ответов 1
Метки нет (Все метки)

собственно, то задачка:
Шпиону требуется пробраться из одной клетки лабиринта в другую. У шпиона есть карта лабиринта, поэтому он всегда идет по кратчайшему пути. Если кратчайших путей несколько, то он с равной вероятностью может выбрать любой из них. В лабиринте размещено несколько мин. Шпион не знает, где они расположены. Известно только, что в начальной и конечной клетках мин нет. Если на пути, выбранном шпионом, есть хотя бы одна мина, то он погибнет. Требуется найти вероятность того, что он все же доберется из начальной клетки в конечную.

описание лабиринта (что по сути вопроса - неважный фактор):
'#' - стена, '.' - пустая клетка, 'm' - клетка с миной, 's' - начальная клетка, 'f' - конечная клетка

подскажите какой-нибудь алгоритм поиска количества кратчайших путей, плиз;

с помощью волнового, к примеру, можно достаточно просто найти один кратчайший путь, но нужно найти все, с модификацией этого алгоритма тоже пока что ничего действующего не придумал;

реализовывать буду на C++
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2010, 23:36
Ответы с готовыми решениями:

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

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой...

Просчёт путей
Нужен просчёт путей в трехмерном пространстве. Препятствия делятся на два...

Алгоритм поиска путей
Привет. Ребята, такая тема, у меня есть граф, взвешенный, неориентированный, у...

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых...

1
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
08.12.2010, 00:25 2
Запустим сначала обычный поиск в ширину из начальной клетки. Пусть теперь d[i][j] - расстояние от старта до клетки (i,j).

Найдем для каждой клетки количество способов, которыми можно в нее попасть, идя по кратчайшему пути.
Для стартовой клетки ответ 1. Пусть известен ответ для клеток, находящихся на насстоянии не более s от старта. Тогда количество путей для любой клетки с расстоянием s+1 равно сумме количеств путей соседних с ней клеткок с расстоянием s.

Найдем теперь для каждой клетки количество "плохих" - заминированных кратчайших путей от старта до нее.
Для стартовой клетки ответ 0. Пусть известен ответ для клеток, находящихся на насстоянии не более s от старта. Рассматриваем клетки с расстоянием s+1. Если клетка заминирована, то любой кратчайших путь через нее плох; ответ - просто количество путей к ней. Если не заминирована, то ответ - сумма количеств плохих путей по соседним клеткам с расстоянием s.

Осталось поделить два числа.

И да, эти веселые числа наверняка быстро вылезут за пределы инта.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2010, 00:25

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому...

Экономное представление путей в графе
Есть приведенное бинарное дерево (изоморфные подграфы сливаются, в узла может...

Логическая задача на количество путей
Робот может двигаться только вправо и вниз на одну клетку. В клетки,...


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

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

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