Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.141.30.162] |
|
Страницы: (3) [1] 2 3 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Постараюсь предельно лаконично описать задачу и проблемы (а их не мало тут накопилось). Все схемы, рисунки показаны на общем изображении. Дан лабиринт квадратной формы. Заданы препятствия, начальная и конечная ячейка. 1. Найти кратчайший путь между стартом и концом (используя BFS + планарный граф). Движение робота по принципу фон Неймана (вверх, вправо, вниз, влево). 2. Построить граф видимости ===================================================== С 1-й подзадачей справился особенно легко. Сформировал матрицу смежности планарного графа (ведь у графа нет ни одной пары пересекающихся ребер) из сетки/лабиринта, запустил поиск в ширину из старт.вершины и в итоге получил наикратчайший путь. Здесь проблем НЕТ! Со 2-й подзадачей не сложилось: не сразу, ни через какое-то время... Поискал в сети информацию о получении графа видимости. Я бы не сказал, что описательной информации этого алгоритма предостаточно (в отличие, например, от BFS, DFS и др.классических алгоритмов) + я не смог выкупить все равно тонкости построения графа видимости. Как я понял, оптимальный путь будет представлять кусочно-линейная ломаная, проходящая через вершины препятствий. Но дело в том, что тут смешиваются информационные модели и геометрические. Т е оказывается важна геометрия физически исходного лабиринта. Ну, допустим! Но когда я получал планарный граф за вершину принимался ЦЕНТР ЯЧЕЙКИ, а не ее вершины, коих 4-ре штуки к слову... Т е придется полностью менять граф что ли для создания его видимости)? Я вот этот момент не очень выкупаю. Также непонятно, что брать за отправную точку движения? Центр исходной ячейки или можно сместиться в какую-то ее вершину? Также, как я понимаю, для построения графа видимости робот, перемещающийся по лабиринту вырождается в ТОЧКУ, т е не обладает ни шириной, ни высотой и вообще не обладает габаритами? Я правильно выкупаю, что нужно ввести систему координат и раздать координаты тем ячейкам сетки, которые выражают препятствия? Потом нужно получить новый взвешенный граф и запустить алг. Дейкстры, для нахождения кратчайшего пути? Или достаточно все делать на одном графе? Ну, и последнее) мне бы просто шоб работало. Мне не нужен оптимальный, высокопроизводительный алгоритм, т к он будет сложен для моего понимания. Хотелось бы топорный, максимально простой и тупой алгоритм, который пусть имеет сложность (n^5), но который бы был понятен) Главное чтоб работало да и все... Прикреплённая картинка
|
Сообщ.
#2
,
|
|
|
По-моему граф видимости надо строить по тем же точками, что вы искали кратчайший путь, т.е. центр клеточки лабиринта.
Тогда граф видимости будет такой граф, у которого две вершины будут связаны (видимы), если ребро их связывающее не пересекает препятствие. Соответственно нужно построить отрезки всех препятствий и для всех пар вершин исходного графа проверить видимость: пересекается или нет отрезок из двух вершин какой-то отрезок препятствий. Прикреплённая картинка
|
Сообщ.
#3
,
|
|
|
Что-то я как-то не понимаю, какое движение в графе видимости? Формально граф видимости есть обычный ненаправленный граф, где ребро означает, что связанные им вершины достижимы без смены направления движения. Всего-то лишь... т.е. построение сводится к перебору вершин и для каждой - перебору находящихся в прямой видимости вершин, т.е. движение в одном из 4 возможных направлений до ближайшего препятствия (включая границы). Например, на исходном рисунке для ячейки (row-col) 12 такой перебор даст следующие рёбра графа видимости: 12-13, 12-14, 12-22, 12-32, 12-42, 12-52, причём первые 2 ребра получены движением вправо до препятствия, остальные движением вниз до границы, а движение вверх или влево невозможны, ибо граница - вот она... для ячейки 13 набор рёбер будет 13-12, 13-14. Для исключения дубликатов (граф-то ненаправленный) достаточно для каждой ячейки обрабатывать только два (перпендикулярные) из 4 направлений, т.е. после обработки ячейки 12 и получения 7 рёбер графа видимости обработка ячейки 13 добавит в граф только одно ребро 13-14. И чего тут сложного...
|
Сообщ.
#4
,
|
|
|
Кстати, в общем случае граф видимости не планарный.
|
Сообщ.
#5
,
|
|
|
вот с одной стороны вроде все понятно, а с другой стороны не выкупаю тонкости некоторые, которые не позволяют осознать все окончательно...
мне ведь еще нужно показать эту видимость (ломаную линию) на самом лабиринте, используя технологию GDI+, которую я вроде норм. знаю и что-либо отрисовать нет проблем, если ПОНИМАТЬ, что и где чертить.... я прав или нет в том, что: вот эта "видимость" будет пролегать через вершины/ячейки лабиринта, которые входят в состав кратчайшего пути (они желтого цвета на картинке)? Если да, то тогда ведь можно оптимизировать построение, проверяя только эти "желтые" ячейки или нет? они у меня все лежат в стеке и я всегда к ним могу получить доступ... Цитата grgdvo @ По-моему граф видимости надо строить по тем же точками, что вы искали кратчайший путь, т.е. центр клеточки лабиринта. ок, это не потребует формирование нового графа, хотя в описании алгоритма постоянно твердят, мол видимость проходит через вершины препятствий, а любая стенка имеет 4-ре вершины (правда всегда их можно рассчитать, зная координаты центра стенки) Цитата Akina @ Например, на исходном рисунке для ячейки (row-col) 12 такой перебор даст следующие рёбра графа видимости: 12-13, 12-14, 12-22, 12-32, 12-42, 12-52, причём первые 2 ребра получены движением вправо до препятствия, остальные движением вниз до границы, а движение вверх или влево невозможны, ибо граница - вот она... для ячейки 13 набор рёбер будет 13-12, 13-14 вроде я понимаю это, но твое движение предполагает строго по вертикали и по горизонтали, а ломаная линейная может проходить и под углом и не всегда вроде даже под 45 градусов... Цитата amk @ Кстати, в общем случае граф видимости не планарный. да, согласен, но у меня ведь частный случай, поэтому граф образуется строго планарный и никак иначе... |
Сообщ.
#6
,
|
|
|
Цитата FasterHarder @ ок, это не потребует формирование нового графа, хотя в описании алгоритма постоянно твердят, мол видимость проходит через вершины препятствий, а любая стенка имеет 4-ре вершины (правда всегда их можно рассчитать, зная координаты центра стенки) Я был не прав (смутило определение в википедии). Граф видимости похоже действительно строится по вершинам препятствий. Соответственно, да, потребуется построение второго графа со своими вершинами и определением ребер видимости. |
Сообщ.
#7
,
|
|
|
Цитата FasterHarder @ мне ведь еще нужно показать эту видимость (ломаную линию) Видимости. Ломаная. Ага... не, ну бред же, али сам не видишь? оно, конечно, пушка по параболе стреляет, и ежели её на бок положить, так можно из-за угла стрелять... Не смешивай граф видимости и построение пути по нему. Как строится сам граф - я выше говорил... Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша). И построение выполняется стандартными методами - хоть поиском в ширину, хоть ещё как... |
Сообщ.
#8
,
|
|
|
Цитата Akina @ Формально граф видимости есть обычный ненаправленный граф, где ребро означает, что связанные им вершины достижимы без смены направления движения. кажется я понял о чем речь! Прикреплённая картинка
это визуально, а так будем в памяти матрица смежности соот-щая. Т е, получив такой граф можно говорить, что сформирована структура графа видимости, да? Добавлено Цитата Akina @ Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша). что ты понимаешь здесь под ПАРАЛЛЕЛЬНЫМИ ребрами? я могу предположить, что || ребра - как || ходы в лабиринте, если смотреть на лабиринт, как на физ.объект, а не информационный. Возможно, я не прав, разумеется) Добавлено Цитата Akina @ параллельных ребра как я понял, в т.графов, под параллельными ребрами понимают ребра, имеющие одинаковые концевые вершины. хотелось бы глубоко понять смысл этой фразы: Цитата Akina @ Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша). вот тут ты говоришь про ДВА || ребра, но, если я правильно построил граф видимости, то у него вообще нет ни одной пары || ребер или я чего-то не выкупаю конкретно...?... |
Сообщ.
#9
,
|
|
|
Цитата FasterHarder @ получив такой граф можно говорить, что сформирована структура графа видимости, да? Угу. Цитата FasterHarder @ что ты понимаешь здесь под ПАРАЛЛЕЛЬНЫМИ ребрами? Параллельны рёбра, если у них при переходе меняется одна и та же координата. Ну или если они лежат на параллельных прямых (с учётом общей вершины-клетки - на одной прямой). Школьная геометрия, не надо искать какого-то особенного смысла. Скажем, ребру (в нотации row,col) 2,3-2,4 параллельны рёбра 2,3-2,5 и 2,3-2,1, ибо у них всех изменяется только координата col. Цитата FasterHarder @ как я понял, в т.графов Я использовал этот термин чисто в геометрическом смысле, рассматривая ребро как отрезок, соединяющей точки центров клеток. Цитата FasterHarder @ если я правильно построил граф видимости, то у него вообще нет ни одной пары || ребер С учётом вышенаписанного - нет. Скажем, параллельны рёбра 2-3 и 3-4, они же в нотации (row,col) рёбра 1,2-1,3 и 1,3-1,4. PS. Конечно, рёбра 2-3 и 18-20 (они же 1,2-1,3 и 4,3-4,5) тоже параллельны - но они лежат на разных прямых, не имеют общей вершины, а потому в свете вышеописанного выбрасывания нам неинтересны. |
Сообщ.
#10
,
|
|
|
Akina, ох, сколько тут тонкостей, хм...
отбрасывать нужно, когда именно РОВНО ДВА || ребра, а, допустим, не 3 или 17, ну ладно... Посмотри, плиз картинку, я правильно понЯл твою идею или совсем не то Прикреплённая картинка
Добавлено и давай еще закрепим понятие параллельных ребер, а то у меня есть сомнения. что не на 100% я правильно понял! Ребра считаем параллельными, если они лежат на одной прямой в геом.смысле конфигурации лабиринта (горизонтальной или вертикальной) и имеют строго одну общую вершину Исключения для ребер, исходящих/входящих в старт. и конеч. вершины. |
Сообщ.
#11
,
|
|
|
Цитата FasterHarder @ Посмотри, плиз картинку, я правильно понЯл твою идею или совсем не то Неправильно. Впрочем, я неаккуратно сформулировал условие. Цитата Akina @ Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша). Должно быть: Для построения пути из графа предварительно выбрасываются все узлы, имеющие только два, причём параллельных, ребра к соседним вершинам (проходные), а также все узлы, имеющие только одно ребро к соседним вершинам (тупики), за исключением узлов старта и финиша, и все исходящие из выброшенных узлов рёбра. На картинке ты нарисовал два ребра 2-3 и 2-4. И забыл нарисовать третье ребро 3-4. А также пометить, что у узлов 2 и 4 есть ещё рёбра. В соответствии с тем, что я сказал, ни узел 2, ни узел 4 не подходят под описание, ибо у них более чем 2 ребра к соседям. А вот узел 3 подходит, из него выходят 2 ребра 2-3 и 3-4, и они параллельны. Поэтому мы выбрасываем узел 3 и оба выходящих из него ребра, и оставляем только ребро 2-4. Аналогично на второй картинке. Узел 16 не является кандидатом на выбрасывание, это начало. Узел 17 тоже не является кандидатом, потому что у него есть как рёбра горизонтальные (17-16 и 17-18), так и вертикальные (17-12 и 17-22). Узел 18 - кандидат, у него 2 ребра к соседним вершинам (18-17 и 18-19) и они параллельны, т.е. выбрасывается вершина 18 и оба ребра этой вершины. Узел 19 тоже не является кандидатом, потому что у него есть как рёбра горизонтальные (19-18 и 19-20), так и вертикальные (19-14 и 19-24). Узел 20 - не кандидат, хотя у него всего 2 ребра (20-19 и 20-15), но они непараллельны. Суммарно при построении пути по матрице видимости в ходе предобработки из матрицы будут выброшены узлы 3, 18 (оба - проходные), 6 и 24 (тупиковые), а также все исходящие из них рёбра (6 штук). PS. При выбрасывании одного узла количество выбрасываемых рёбер может быть и более 2, потому что рассматриваем мы только рёбра к "соседям", а выбрасываем вообще все. Добавлено Цитата FasterHarder @ давай еще закрепим понятие параллельных ребер Давай будем проще. Рёбра видимости А-Б и Б-В считаются параллельными, если существует ребро видимости А-В. |
Сообщ.
#12
,
|
|
|
Akina, во, теперь стало гораздо понятнее)
вот более "сложный" случай, посмотри, плиз Прикреплённая картинка
И очень важные уточняющие вопросы: 1. начальная и конечная ячейка/вершина НЕ учитываются в принципе в анализе, как будто их нет, а также не учитываются все ребра им инцидентные? 2. насколько важен порядок нахождения проходных и тупиковых вершин? или без разницы? такое чувство, что если сначала удалить тупиковые, то тогда некоторые "тройки" с проходной вершиной уже не будут найдены... 3. вот этот коэффициент равный 2 продиктован ТОЛЩИНОЙ препятствий. Если бы стенки были двойной толщины, тогда коэффициент бы стал равен 3 или там бы этот учет усложнился..? Добавлено 4. все эти поиски и удаления узлов и ребер производится на построенном на 1-й стадии графом видимости? 5. что делать дальше?) |
Сообщ.
#13
,
|
|
|
Цитата FasterHarder @ вот более "сложный" случай, посмотри, плиз Тупиковые определены верно. Проходные - пропущены 8, 14, 15, 22, 30, 32, 36, 43, 47. Например, у 8-й есть только два соседа 1 и 15, и существует ребро 1-15. Цитата FasterHarder @ 1. начальная и конечная ячейка/вершина НЕ учитываются в принципе в анализе, как будто их нет, а также не учитываются все ребра им инцидентные? На стадии "избавления" от лишних рёбер графа достижимости - да. Цитата FasterHarder @ 2. насколько важен порядок нахождения проходных и тупиковых вершин? Абсолютно неважен. Цитата FasterHarder @ 3. вот этот коэффициент равный 2 продиктован ТОЛЩИНОЙ препятствий. Какой коэффициент??? Добавлено Цитата FasterHarder @ 4. все эти поиски и удаления узлов и ребер производится на построенном на 1-й стадии графом видимости? Угу. Цитата FasterHarder @ 5. что делать дальше?) А всё, потом поиск (в ширину, в глубину, в длину или куда там надо). |
Сообщ.
#14
,
|
|
|
Цитата Akina @ Абсолютно неважен. а как насчет этого случая Прикреплённая картинка
способ №1: если сначала обработать №1 - тупиковая - удаляем. потом №8 - тупиковая - удаляем. потом №15 - аналогично и потом №22 - она по твоей классификации не является ни тупиковой ни проходной, а по сути - изолированная. способ №2: если встать на №8 - проходная - удаляем. потом №15 - проходная - удаляем. №22 - тупиковая - удаляем. №1 - изолированная. хотя вроде, да, неважно какой способ, остается по 1 изолированной вершине. ну и как бы плевать на нее) наверное... Вот мы еще не обговорили кол-во компонент связности графа видимости. Их ведь очевидно, что может быть больше 1! Наверное, нужно взять только ту КС, в состав которой входят начальная и конечная вершины, а остальные вообще не учитывать при анализе?, т к через те вершины путь теоретически даже не может проходить... Добавлено Цитата Akina @ Какой коэффициент??? Цитата Akina @ существует только два параллельных ребра Добавлено Цитата Akina @ Проходные - пропущены 8, 14, 15, 22, 30, 32, 36, 43, 47. важнейшее для меня уточнение! говоришь, что №14 - проходная, но ведь мы обсудили, что: Цитата FasterHarder @ начальная и конечная ячейка/вершина НЕ учитываются в принципе в анализе поэтому она вроде должна быть ТУПИКОВОЙ, т к у нее нет верхнего соседа, точнее он есть - конечная вершина, но мы же ее НЕ учитываем! или как? |
Сообщ.
#15
,
|
|
|
Цитата Akina @ А всё, потом поиск (в ширину, в глубину, в длину или куда там надо). а дальше самое страшное для меня... нужно ГРАФИЧЕСКИ, средствами GDI+ (ну я типа на C# делаю) НА ПОВЕРХНОСТИ ЛАБИРИНТА (который представлен элементом управления "сетка") показать кратчайшую траекторию. т е граф видимости построен - 1 стадия отсекли лишние вершины+ребра - 2 стадия как я понимаю, вершина соот-ет как бы ЦЕНТРУ ячейки грида, но я вот в упор не понимаю, как наклонять линию при рисовании ломаной. еще описывал в 1-ом сообщении, что нужно вводить систему координат, раздавать координаты. Но теперь мне непонятно, стенка характеризуется только своим центром или нужно задавать координаты ее 4-рех вершин... тут ведь такой нюанс есть, что это ломаная может проходить не только по горизонтальным/вертикальным осям симметрии ячейки, но и касаться вершин препятствий, а там вроде не только угол в 45 градусов может быть и пр... +нужно еще рассчитать длину этой траектории, а это приводит к Дейкстра какому-нибудь. По умолчанию можно взять габариты ячейки 1 на 1 уе. вот на этой стадии совсем не выкупаю к чему стремиться, хотя поверхностно понятно... |