Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Замкнутый путь на графе

62K
23 августа 2010 года
bonesbones
1 / / 23.08.2010
Товарищи, нужна помощь!
Сколько сам ни бился, не осилил:


Сразу смотрите пикчу:


Есть решетка X на Y (пофиг какой размерности, пусть 12х14, как в пикче).
В узлах решетки некоторым образом расставлены точки (пикча).
надо определить, существует ли замкнутый путь на игровом поле.
Условие замкнутости - смежные узлы решетки по горизонтали, вертикали, диагонали.
(пикча: условие выполняется для черных точек, зеленым показан путь, но не выполняется для красных)

Люди добрые, хотя бы на пальцах, как это сделать (или как по-умному называется то, что мне надо искать).
Ежели есть кодеры на VB, то это ваапще шик!
5
23 августа 2010 года
hardcase
4.5K / / 09.08.2005
Задача похожа на построение выпуклой оболочки (с означенными ограничениями).
2.1K
23 августа 2010 года
Norgat
452 / / 12.08.2009
Цитата: bonesbones

Есть решетка X на Y (пофиг какой размерности, пусть 12х14, как в пикче).
В узлах решетки некоторым образом расставлены точки (пикча).
надо определить, существует ли замкнутый путь на игровом поле.
Условие замкнутости - смежные узлы решетки по горизонтали, вертикали, диагонали.
(пикча: условие выполняется для черных точек, зеленым показан путь, но не выполняется для красных)



хм... если нету никаких условий кроме этого, то это просто поиск цикла в графе...
всё что нужно - правильно построить граф:

вершины графа - все точки решётки входной.
а условие существования ребра между 2-мя вершинами:
1) вершины смежны(по вертикали, горизонтали или диагонали)
2) обе вершины помечены одинаковым цветом

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

так можно решить эту задачу, если не налагается никаких доп. условий на искомый цикл(т.е. если не учитывать выпуклость полученного кольца, его длину и т.п.)

5
23 августа 2010 года
hardcase
4.5K / / 09.08.2005
Цитата: Norgat
хм... если нету никаких условий кроме этого, то это просто поиск цикла в графе...
всё что нужно - правильно построить граф:

вершины графа - все точки решётки входной.
а условие существования ребра между 2-мя вершинами:
1) вершины смежны(по вертикали, горизонтали или диагонали)
2) обе вершины помечены одинаковым цветом

Да, похоже на верное решение. :)

444
24 августа 2010 года
patison
323 / / 15.03.2007
Похоже на игру "Точки" )) Сам совсем недавно писал её, и в частности этот алгоритм.

Если поле не большого размера - то можно рекурсивно обходить точку за точкой (отмеченные).
Суть такая: берём исходную точку (под точками подразумеваем отмеченые точки на поле), и рекурсивно передвигаемся к соседним точкам (лево, право, низ, верх и диагонали). Делаем это до тех пор пока не достигнем исходной точки (из которой начался обход). если не дошли в неё - значит область не замкнута.

Как-то так.
1.8K
25 августа 2010 года
LM(AL/M)
332 / / 20.12.2005
по-моему рекурсия тут не рулит, так вы получите обход в глубину, в ширину побыстрее должно быть
444
30 августа 2010 года
patison
323 / / 15.03.2007
Цитата: LM(AL/M)
по-моему рекурсия тут не рулит, так вы получите обход в глубину, в ширину побыстрее должно быть


ну я не зря отметил, что алгоритм годен для поля, относительно небольшого размера.

Может приведёте пример алгоритма для поиска в ширину?

1.8K
30 августа 2010 года
LM(AL/M)
332 / / 20.12.2005
ладно уговорил) хотя в нете таких приеров должно быть полно
 
Код:
# поиск цикла в графе, псевдокод
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)

на выходе получим циклический путь в перевернутом виде (в виде стэка)
444
10 сентября 2010 года
patison
323 / / 15.03.2007
Сейчас нашёл багу в предложенном рекурсивном алгоритме.
Если в ситуации на рис.1 поставить точку (красная, на последующих рисунках), то по идее цикл должен быть тот который указан на рис.2, однако на деле - цикл получаем тот что на 3-м рисунке.
Причина ясна - поиск по соседям идёт против часовой стрелки, и таким образом пройдя налево и вернувшись ПОД красную точку, мы упираемся в неё-же, и алгоритм нам сообщает что цикл найден, оставив нетронутыми соседей справа.
1.8K
10 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
от данной ошибки не застрахован ни рекурсивный алгоритм ни поиск в ширину
нужно видимо находить максимальный цикл а не первый попавшийся
444
10 сентября 2010 года
patison
323 / / 15.03.2007
В том-то и дело. Либо максимальный цикл, либо все циклы и объединение их в один.
В данный момент немного переделал алгоритм, который после нахождения одного цикла - проходится в других направлениях от "красной точки" и ищет другие циклы - объединяя их в один единый массив пути.
Правда это уже очень непроизводительно. Так, костыль на скорую руку.
1.8K
10 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
что-то я не понял насчёт объединения... какой смысл? ты нашёл N циклов, один из них с максимальной длиной. Объединение всех циклов всё равно даст в результате этот максимальнй цикл.
444
10 сентября 2010 года
patison
323 / / 15.03.2007
Нет, дело в том что все циклы, в моём случае, смежные. Т.е. их можно объединить в один (который будет включать все найденые). Это особенность приложения. Находя все мелкие циклы, пути этих циклов объединяются в один единый массив, который и представляет собой этот целый длинный цикл.

Вот кстати по поводу поиска самого длинного... http://forum.vingrad.ru/act-ST/f-13/t-240912.html
1.8K
10 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
хочешь сказать что исходная точка может оказаться внутри области ограниченной найденным циклом?
444
11 сентября 2010 года
patison
323 / / 15.03.2007
Исходная точка является частью этого цикла. Т.е. эта точка - один из узлов графа, через который проходит цикл.
1.8K
11 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
ничего не понимаю с твоим объединением
на рисунке сверху показаны разные варианты циклов, снизу -- макс. цикл
видно что объединение всех циклов не равно максимальному, в этом я был не прав )
но что из укзанного нужно тебе? то что сверху или то что снизу и как это согласуется с исходным вопросом?
444
11 сентября 2010 года
patison
323 / / 15.03.2007
Хм, неужели я так хреново объясняю... ))))

ну я вобщем-то уже решил свою проблему, но я поясню.

По сути да, нужен максимальный цикл. И я не понимаю почему ты утверждаешь что объединение всех циклов не равно максимальному. Давай немного абстрагируемся: я ставлю точку, после которой я могу "захватить" две територии (в одну сторону и в другую). Но в этом случае получается что захватывая ОБЕ територии - они граничат одна с другой, и по сути могут быть обеденены в одну територию.
Таким образом - найдя один цикл, я его не прорисовываю а сохраняю точки (узлы) из которых он состоит, далее я нахожу второй цикл (который начинается из этой-же точки что и предыдущий), и сохраняю его путь туда-же куда был сохранён первый. Таким образом, в этом хранилище у меня будут собраны все узлы обоих циклов, и по сути это будет один большой цикл.
1.8K
12 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
блиин... чувак... когда я говорил что объединение всех циклов равно максимальному (ошибочно) ты заявил что это не то что тебе нужно. теперь же ты утверждаешь что тебе нужен именно максимальный цикл, но чтобы понять что он не равен объединению ВСЕХ циклов достаточно взглянуть на мой рисунок (сравни красный цикл и зелёный например).
сейчас думаю за какой конкретно пост тебе минусануть, поскольку ты ни ни разу не обмолвился что тебе нужен именно максимальный цикл....
444
13 сентября 2010 года
patison
323 / / 15.03.2007
Запутался видимо.

Ну в твоём рисунке да, согласен. Тут всё дело в том что зелёный цикл УЖЕ является максимальным. А я имел ввиду объединение всех найденых НЕ максимальных циклов. Всё дело в том, что поиск циклов происходит от одного к другому. Т.е. я нахожу первый цикл (пусть он не максиамльный), дальше нахожу смежный ему цикл (он тоже не максимальный), далее нахожу третий смежный, ну и тд. И в итоге, объединяя их все воедино - получается то что нужно.

Вот на рисунке привёл пример - сначала алгоритм нашёл зелёный цикл, потом нашёл синий (последовательно), и объединяя их получяю таки да - максимальный.

Цитата:
когда я говорил что объединение всех циклов равно максимальному (ошибочно) ты заявил что это не то что тебе нужно. теперь же ты утверждаешь что тебе нужен именно максимальный цикл


Я этого не утверждал (ну или ты не правильно меня понял). Алгоритм поиска не находит максимальный цикл! А если и находит, то на нём и останавливается и не ищет дальше. В остальных случаях, когда находится мелкий цикл (считай часть максимального цикла), начинается поиск всех смежных (соседних) циклов (при этом максимальный цикл не является соседним(!) циклом моего маленького цилка, т.к. маленький цикл является частью максимального).

1.8K
13 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
Цитата: patison
А я имел ввиду объединение всех найденых НЕ максимальных циклов.


интересно а как ты отличаешь максимальный от немаксимального цикла до того как обойдешь все циклы?

Цитата: patison

Всё дело в том, что поиск циклов происходит от одного к другому. Т.е. я нахожу первый цикл (пусть он не максиамльный), дальше нахожу смежный ему цикл (он тоже не максимальный), далее нахожу третий смежный, ну и тд. И в итоге, объединяя их все воедино - получается то что нужно.


тот же вопрос : ) + как организован перебор именно смежных циклов?

Цитата: patison

Вот на рисунке привёл пример - сначала алгоритм нашёл зелёный цикл, потом нашёл синий (последовательно), и объединяя их получяю таки да - максимальный.


как ты объяснишь что ни один из обозначенных на рисунке циклов не является максимальным (макс. получится если отбросить внутреннюю точку, но как её вычислить?)

и ещё напрашивается вопрос: а какие вообще были основания говорить что в предложенном тебе алгоритме содержится баг? только то что он не очень подошёл к твоей задаче?

444
13 сентября 2010 года
patison
323 / / 15.03.2007
Аааа, ну всё, я понял что тебя так задело.. Слово "баг", видимо )))
Во-первых - этот "баг" я обнаружил в своём алгоритме, а не том который "был предложен мне".

Дальше, по твоим вопросам. Собсна я никак не могу определить является найденый цикл максимальным или нет. Поиск происходит следующим образом - после того как на поле появилась очередная точка - из неё начинается поиск цикла. Поиск, как я уже говорил, рекурсивен, и реализуется путём движения влевую сторону по соседям (обходятся все соседи начиная с верхнего, и от него против часовой стрелки). Если цикл был найден (мы вернулись в новую точку, которая последней появилась), осуществляется поиск по другим соседям этой точки (т.е. если цикл начался из этой точки в левый нижний угол, то далее алгоритм пытается найти циклы через других соседей (тех что остались - т.е. нижний сосед, правый нижний, правый, и правый верхний)).

Как-то так.
1.8K
13 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
Цитата: patison
Аааа, ну всё, я понял что тебя так задело..


скорее уж предельная точность выражения мыслей, как-то так...

Цитата: patison
Если цикл был найден (мы вернулись в новую точку, которая последней появилась), осуществляется поиск по другим соседям этой точки (т.е. если цикл начался из этой точки в левый нижний угол, то далее алгоритм пытается найти циклы через других соседей

а если не был?
Ты вообще можешь толком рассказть свой алгоритм?

444
14 сентября 2010 года
patison
323 / / 15.03.2007
А если не был - значит цикла в котором состоит новая точка нет.
Я-же выше (несколько раз) описывал алгоритм.
1.8K
14 сентября 2010 года
LM(AL/M)
332 / / 20.12.2005
Ладно, не хочешь дать нормальное описание -- как хочешь. В любом случае задачу можно было решить проще и красивее...
444
14 сентября 2010 года
patison
323 / / 15.03.2007
Да почему-же не хочу, очень даже хочу. Не хочется тему захламлять. Если действительно есть желание - напиши в личку - там продолжим :)
444
14 сентября 2010 года
patison
323 / / 15.03.2007
Да почему-же не хочу, очень даже хочу. Не хочется тему захламлять. Если действительно есть желание - напиши в личку - там продолжим :)
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог