gds
19.03.2013 11:14 umodniA63A5C27
Посоны, помогите с задачкой. Я совсем разучился в графы. Наговнокодить могу, но должно быть красивое решение (скорее всего, ещё и более быстрое, чем наивный говнокод).
Есть направленный ациклический граф: https://docs.google.com/drawings/d/1OPIv...
Задана вершина, из которой не выходит рёбер (тут — Z). Пометим её.
Хочется пройти по графу так, чтобы на каждом следующем шаге прохода были помечены только те узлы, у которых все дети помечены тоже. (пофиг, все из таких узлов, или ровно один на каждом шаге.)
Граф может быть немаленьким, но часто будет оказываться так, что более нескольких шагов алгоритма делать не нужно. То есть, вполне приемлем ленивый алгоритм такого обхода.
17 comments
recommend
bookmark
subscribe
смотри банальные алгоритмы закраски области. Это именно оно.
Судя по описанию и иллюстрации, должно помочь что-то типа модификации поиска в ширину (например, с запоминанием того, во всех ли детях вершины мы побывали).
в общем случае — не оно. А вот какой-то специфичный алгоритм закраски может и подойдёт.
банально пихаем в очередь те точки ,которые видим из текущей точки.
текущую выбираем из очереди.
вот что-то такое и хотел наговнокодить, да вот не знаю, как-то не очень красиво. Но, если других идей не будет, то придётся.
из Z мы видим D, но её пихать раньше, чем пихнём H и F, не можем.
то есть, пихать можно только того, от кого все выходы оприходованы?
A* ?
таки да: "чтобы на каждом следующем шаге прохода были помечены только те узлы, у которых все дети помечены тоже"
ппц у тебя аватарка модная теперь
Мне это очень напомнило поиск в ширину, только по стрелочкам надо в другую сторону ходить.
Т.е. не поиск в ширину, а топологическую сортировку.
тогда модифицируем алгоритм так:
при вынимании из очереди проверяем возможность закраски.
при невозможности пихаем обратно в хвост очереди.
если добавлений в очередь извне не было на протяжении 1 круга по очереди, то мы встали раком.
в нём надо стоимость узлов расставлять хитро, чтобы проход был в нужном мне порядке. Сходу не соображу, как.
вот, тоже напомнило. Но что-то пробовал на бамажке, не получалось. Попробую ещё.
А стрелочки — фигня, у меня есть и обратные стрелочки для этих целей.
да, вот что-то такое и думал, но, может, есть покрасивше что.
хз..