pro.algorithms
Всем привет! Подскажите, пожалуйста, по представлению лабиринта в виде графа. Вот
на этом изображении, я верно понимаю, что вершинами (vertexes) графа будут не все клетки в лабиринте, а лишь те, в которых имеются переходы (перекрёстки)?
5 ответов
Перекрёстки и тупики
Iskander
R
Автор вопроса
Перекрёстки и тупики
Понял, спасибо!
Iskander
R
Автор вопроса
В продолжение моего вопроса. Когда мы представляем лабиринт в виде графа, как на картинке выше, то учитываем лишь перекрёстки и тупики, так как несколько клеток, которые собираются в ребро между узлами, например, M и J и ребро между ними - там нет никакой полезной информации, поэтому мы эти клетки "исключаем" из представления графа, верно? Тогда вытекающий вопрос. Если у нас лабиринт с некой "стоимостью" хода по клетке, что эквивалентно весам рёбер. Например, клетки между M и J, их 4 штуки и на каждой клетке свой вес, допустим { 3, 2, 2, 4 }. Если мы пытаемся найти не только выход из лабиринта, но и учитываем, что у нас имеется ограниченное число ходов, то в этом случае представление лабиринта в виде графа будет: а) таким же графом, как и без весов, просто на ребра накладываем веса? Вес ребра MJ = 3 + 2 + 2 + 4 = 11. б) новый граф, где каждая клетка становится узлом с весом X, то есть будут новые узлы на каждую клетку между M и J со своим весом?
В продолжение моего вопроса. Когда мы представляе...
без разницы. в варианте б просто будет дольше алгоритм поиска путей работать
В продолжение моего вопроса. Когда мы представляе...
Собственное как сделаешь, так и будет представляться. Какого-то каноничного представления, насколько я знаю, нет. В зависимости от задачи может быть удобно по-разному
Похожие вопросы
Обсуждают сегодня