# поиск цикла в графе, псевдокод
q = new Queue((initialNode,None)) # 2-й эдемент кортежа -- стэк пути
while not empty(q):
n, path = q.dequeue()
if n == initialNode: break # Нашли!!!
for x in sibling(n): q.enqueue((x, (n, path))) # sibling == мн-во
# связанных вершин
#/while
print_path(path)
Замкнутый путь на графе
Товарищи, нужна помощь!
Сколько сам ни бился, не осилил:
Сразу смотрите пикчу:
Есть решетка X на Y (пофиг какой размерности, пусть 12х14, как в пикче).
В узлах решетки некоторым образом расставлены точки (пикча).
надо определить, существует ли замкнутый путь на игровом поле.
Условие замкнутости - смежные узлы решетки по горизонтали, вертикали, диагонали.
(пикча: условие выполняется для черных точек, зеленым показан путь, но не выполняется для красных)
Люди добрые, хотя бы на пальцах, как это сделать (или как по-умному называется то, что мне надо искать).
Ежели есть кодеры на VB, то это ваапще шик!
Сколько сам ни бился, не осилил:
Сразу смотрите пикчу:
Есть решетка X на Y (пофиг какой размерности, пусть 12х14, как в пикче).
В узлах решетки некоторым образом расставлены точки (пикча).
надо определить, существует ли замкнутый путь на игровом поле.
Условие замкнутости - смежные узлы решетки по горизонтали, вертикали, диагонали.
(пикча: условие выполняется для черных точек, зеленым показан путь, но не выполняется для красных)
Люди добрые, хотя бы на пальцах, как это сделать (или как по-умному называется то, что мне надо искать).
Ежели есть кодеры на VB, то это ваапще шик!
Задача похожа на построение выпуклой оболочки (с означенными ограничениями).
Цитата: bonesbones
Есть решетка X на Y (пофиг какой размерности, пусть 12х14, как в пикче).
В узлах решетки некоторым образом расставлены точки (пикча).
надо определить, существует ли замкнутый путь на игровом поле.
Условие замкнутости - смежные узлы решетки по горизонтали, вертикали, диагонали.
(пикча: условие выполняется для черных точек, зеленым показан путь, но не выполняется для красных)
хм... если нету никаких условий кроме этого, то это просто поиск цикла в графе...
всё что нужно - правильно построить граф:
вершины графа - все точки решётки входной.
а условие существования ребра между 2-мя вершинами:
1) вершины смежны(по вертикали, горизонтали или диагонали)
2) обе вершины помечены одинаковым цветом
дальше скормить этот граф алгоритму поиска цикла в графе, а тема поиска цикла в графе кучу раз пережевана в инете уже...
так можно решить эту задачу, если не налагается никаких доп. условий на искомый цикл(т.е. если не учитывать выпуклость полученного кольца, его длину и т.п.)
Цитата: Norgat
хм... если нету никаких условий кроме этого, то это просто поиск цикла в графе...
всё что нужно - правильно построить граф:
вершины графа - все точки решётки входной.
а условие существования ребра между 2-мя вершинами:
1) вершины смежны(по вертикали, горизонтали или диагонали)
2) обе вершины помечены одинаковым цветом
всё что нужно - правильно построить граф:
вершины графа - все точки решётки входной.
а условие существования ребра между 2-мя вершинами:
1) вершины смежны(по вертикали, горизонтали или диагонали)
2) обе вершины помечены одинаковым цветом
Да, похоже на верное решение. :)
Похоже на игру "Точки" )) Сам совсем недавно писал её, и в частности этот алгоритм.
Если поле не большого размера - то можно рекурсивно обходить точку за точкой (отмеченные).
Суть такая: берём исходную точку (под точками подразумеваем отмеченые точки на поле), и рекурсивно передвигаемся к соседним точкам (лево, право, низ, верх и диагонали). Делаем это до тех пор пока не достигнем исходной точки (из которой начался обход). если не дошли в неё - значит область не замкнута.
Как-то так.
Если поле не большого размера - то можно рекурсивно обходить точку за точкой (отмеченные).
Суть такая: берём исходную точку (под точками подразумеваем отмеченые точки на поле), и рекурсивно передвигаемся к соседним точкам (лево, право, низ, верх и диагонали). Делаем это до тех пор пока не достигнем исходной точки (из которой начался обход). если не дошли в неё - значит область не замкнута.
Как-то так.
по-моему рекурсия тут не рулит, так вы получите обход в глубину, в ширину побыстрее должно быть
Цитата: LM(AL/M)
по-моему рекурсия тут не рулит, так вы получите обход в глубину, в ширину побыстрее должно быть
ну я не зря отметил, что алгоритм годен для поля, относительно небольшого размера.
Может приведёте пример алгоритма для поиска в ширину?
ладно уговорил) хотя в нете таких приеров должно быть полно
на выходе получим циклический путь в перевернутом виде (в виде стэка)
Код:
на выходе получим циклический путь в перевернутом виде (в виде стэка)
Сейчас нашёл багу в предложенном рекурсивном алгоритме.
Если в ситуации на рис.1 поставить точку (красная, на последующих рисунках), то по идее цикл должен быть тот который указан на рис.2, однако на деле - цикл получаем тот что на 3-м рисунке.
Причина ясна - поиск по соседям идёт против часовой стрелки, и таким образом пройдя налево и вернувшись ПОД красную точку, мы упираемся в неё-же, и алгоритм нам сообщает что цикл найден, оставив нетронутыми соседей справа.
Если в ситуации на рис.1 поставить точку (красная, на последующих рисунках), то по идее цикл должен быть тот который указан на рис.2, однако на деле - цикл получаем тот что на 3-м рисунке.
Причина ясна - поиск по соседям идёт против часовой стрелки, и таким образом пройдя налево и вернувшись ПОД красную точку, мы упираемся в неё-же, и алгоритм нам сообщает что цикл найден, оставив нетронутыми соседей справа.
от данной ошибки не застрахован ни рекурсивный алгоритм ни поиск в ширину
нужно видимо находить максимальный цикл а не первый попавшийся
нужно видимо находить максимальный цикл а не первый попавшийся
В том-то и дело. Либо максимальный цикл, либо все циклы и объединение их в один.
В данный момент немного переделал алгоритм, который после нахождения одного цикла - проходится в других направлениях от "красной точки" и ищет другие циклы - объединяя их в один единый массив пути.
Правда это уже очень непроизводительно. Так, костыль на скорую руку.
В данный момент немного переделал алгоритм, который после нахождения одного цикла - проходится в других направлениях от "красной точки" и ищет другие циклы - объединяя их в один единый массив пути.
Правда это уже очень непроизводительно. Так, костыль на скорую руку.
что-то я не понял насчёт объединения... какой смысл? ты нашёл N циклов, один из них с максимальной длиной. Объединение всех циклов всё равно даст в результате этот максимальнй цикл.
Нет, дело в том что все циклы, в моём случае, смежные. Т.е. их можно объединить в один (который будет включать все найденые). Это особенность приложения. Находя все мелкие циклы, пути этих циклов объединяются в один единый массив, который и представляет собой этот целый длинный цикл.
Вот кстати по поводу поиска самого длинного... http://forum.vingrad.ru/act-ST/f-13/t-240912.html
Вот кстати по поводу поиска самого длинного... http://forum.vingrad.ru/act-ST/f-13/t-240912.html
хочешь сказать что исходная точка может оказаться внутри области ограниченной найденным циклом?
Исходная точка является частью этого цикла. Т.е. эта точка - один из узлов графа, через который проходит цикл.
ничего не понимаю с твоим объединением
на рисунке сверху показаны разные варианты циклов, снизу -- макс. цикл
видно что объединение всех циклов не равно максимальному, в этом я был не прав )
но что из укзанного нужно тебе? то что сверху или то что снизу и как это согласуется с исходным вопросом?
на рисунке сверху показаны разные варианты циклов, снизу -- макс. цикл
видно что объединение всех циклов не равно максимальному, в этом я был не прав )
но что из укзанного нужно тебе? то что сверху или то что снизу и как это согласуется с исходным вопросом?
Хм, неужели я так хреново объясняю... ))))
ну я вобщем-то уже решил свою проблему, но я поясню.
По сути да, нужен максимальный цикл. И я не понимаю почему ты утверждаешь что объединение всех циклов не равно максимальному. Давай немного абстрагируемся: я ставлю точку, после которой я могу "захватить" две територии (в одну сторону и в другую). Но в этом случае получается что захватывая ОБЕ територии - они граничат одна с другой, и по сути могут быть обеденены в одну територию.
Таким образом - найдя один цикл, я его не прорисовываю а сохраняю точки (узлы) из которых он состоит, далее я нахожу второй цикл (который начинается из этой-же точки что и предыдущий), и сохраняю его путь туда-же куда был сохранён первый. Таким образом, в этом хранилище у меня будут собраны все узлы обоих циклов, и по сути это будет один большой цикл.
ну я вобщем-то уже решил свою проблему, но я поясню.
По сути да, нужен максимальный цикл. И я не понимаю почему ты утверждаешь что объединение всех циклов не равно максимальному. Давай немного абстрагируемся: я ставлю точку, после которой я могу "захватить" две територии (в одну сторону и в другую). Но в этом случае получается что захватывая ОБЕ територии - они граничат одна с другой, и по сути могут быть обеденены в одну територию.
Таким образом - найдя один цикл, я его не прорисовываю а сохраняю точки (узлы) из которых он состоит, далее я нахожу второй цикл (который начинается из этой-же точки что и предыдущий), и сохраняю его путь туда-же куда был сохранён первый. Таким образом, в этом хранилище у меня будут собраны все узлы обоих циклов, и по сути это будет один большой цикл.
блиин... чувак... когда я говорил что объединение всех циклов равно максимальному (ошибочно) ты заявил что это не то что тебе нужно. теперь же ты утверждаешь что тебе нужен именно максимальный цикл, но чтобы понять что он не равен объединению ВСЕХ циклов достаточно взглянуть на мой рисунок (сравни красный цикл и зелёный например).
сейчас думаю за какой конкретно пост тебе минусануть, поскольку ты ни ни разу не обмолвился что тебе нужен именно максимальный цикл....
сейчас думаю за какой конкретно пост тебе минусануть, поскольку ты ни ни разу не обмолвился что тебе нужен именно максимальный цикл....
Запутался видимо.
Ну в твоём рисунке да, согласен. Тут всё дело в том что зелёный цикл УЖЕ является максимальным. А я имел ввиду объединение всех найденых НЕ максимальных циклов. Всё дело в том, что поиск циклов происходит от одного к другому. Т.е. я нахожу первый цикл (пусть он не максиамльный), дальше нахожу смежный ему цикл (он тоже не максимальный), далее нахожу третий смежный, ну и тд. И в итоге, объединяя их все воедино - получается то что нужно.
Вот на рисунке привёл пример - сначала алгоритм нашёл зелёный цикл, потом нашёл синий (последовательно), и объединяя их получяю таки да - максимальный.
Ну в твоём рисунке да, согласен. Тут всё дело в том что зелёный цикл УЖЕ является максимальным. А я имел ввиду объединение всех найденых НЕ максимальных циклов. Всё дело в том, что поиск циклов происходит от одного к другому. Т.е. я нахожу первый цикл (пусть он не максиамльный), дальше нахожу смежный ему цикл (он тоже не максимальный), далее нахожу третий смежный, ну и тд. И в итоге, объединяя их все воедино - получается то что нужно.
Вот на рисунке привёл пример - сначала алгоритм нашёл зелёный цикл, потом нашёл синий (последовательно), и объединяя их получяю таки да - максимальный.
Цитата:
когда я говорил что объединение всех циклов равно максимальному (ошибочно) ты заявил что это не то что тебе нужно. теперь же ты утверждаешь что тебе нужен именно максимальный цикл
Я этого не утверждал (ну или ты не правильно меня понял). Алгоритм поиска не находит максимальный цикл! А если и находит, то на нём и останавливается и не ищет дальше. В остальных случаях, когда находится мелкий цикл (считай часть максимального цикла), начинается поиск всех смежных (соседних) циклов (при этом максимальный цикл не является соседним(!) циклом моего маленького цилка, т.к. маленький цикл является частью максимального).
Цитата: patison
А я имел ввиду объединение всех найденых НЕ максимальных циклов.
интересно а как ты отличаешь максимальный от немаксимального цикла до того как обойдешь все циклы?
Цитата: patison
Всё дело в том, что поиск циклов происходит от одного к другому. Т.е. я нахожу первый цикл (пусть он не максиамльный), дальше нахожу смежный ему цикл (он тоже не максимальный), далее нахожу третий смежный, ну и тд. И в итоге, объединяя их все воедино - получается то что нужно.
тот же вопрос : ) + как организован перебор именно смежных циклов?
Цитата: patison
Вот на рисунке привёл пример - сначала алгоритм нашёл зелёный цикл, потом нашёл синий (последовательно), и объединяя их получяю таки да - максимальный.
как ты объяснишь что ни один из обозначенных на рисунке циклов не является максимальным (макс. получится если отбросить внутреннюю точку, но как её вычислить?)
и ещё напрашивается вопрос: а какие вообще были основания говорить что в предложенном тебе алгоритме содержится баг? только то что он не очень подошёл к твоей задаче?
Аааа, ну всё, я понял что тебя так задело.. Слово "баг", видимо )))
Во-первых - этот "баг" я обнаружил в своём алгоритме, а не том который "был предложен мне".
Дальше, по твоим вопросам. Собсна я никак не могу определить является найденый цикл максимальным или нет. Поиск происходит следующим образом - после того как на поле появилась очередная точка - из неё начинается поиск цикла. Поиск, как я уже говорил, рекурсивен, и реализуется путём движения влевую сторону по соседям (обходятся все соседи начиная с верхнего, и от него против часовой стрелки). Если цикл был найден (мы вернулись в новую точку, которая последней появилась), осуществляется поиск по другим соседям этой точки (т.е. если цикл начался из этой точки в левый нижний угол, то далее алгоритм пытается найти циклы через других соседей (тех что остались - т.е. нижний сосед, правый нижний, правый, и правый верхний)).
Как-то так.
Во-первых - этот "баг" я обнаружил в своём алгоритме, а не том который "был предложен мне".
Дальше, по твоим вопросам. Собсна я никак не могу определить является найденый цикл максимальным или нет. Поиск происходит следующим образом - после того как на поле появилась очередная точка - из неё начинается поиск цикла. Поиск, как я уже говорил, рекурсивен, и реализуется путём движения влевую сторону по соседям (обходятся все соседи начиная с верхнего, и от него против часовой стрелки). Если цикл был найден (мы вернулись в новую точку, которая последней появилась), осуществляется поиск по другим соседям этой точки (т.е. если цикл начался из этой точки в левый нижний угол, то далее алгоритм пытается найти циклы через других соседей (тех что остались - т.е. нижний сосед, правый нижний, правый, и правый верхний)).
Как-то так.
Цитата: patison
Аааа, ну всё, я понял что тебя так задело..
скорее уж предельная точность выражения мыслей, как-то так...
Цитата: patison
Если цикл был найден (мы вернулись в новую точку, которая последней появилась), осуществляется поиск по другим соседям этой точки (т.е. если цикл начался из этой точки в левый нижний угол, то далее алгоритм пытается найти циклы через других соседей
а если не был?
Ты вообще можешь толком рассказть свой алгоритм?
А если не был - значит цикла в котором состоит новая точка нет.
Я-же выше (несколько раз) описывал алгоритм.
Я-же выше (несколько раз) описывал алгоритм.
Ладно, не хочешь дать нормальное описание -- как хочешь. В любом случае задачу можно было решить проще и красивее...
Да почему-же не хочу, очень даже хочу. Не хочется тему захламлять. Если действительно есть желание - напиши в личку - там продолжим :)
Да почему-же не хочу, очень даже хочу. Не хочется тему захламлять. Если действительно есть желание - напиши в личку - там продолжим :)