Что то тут народ совсем далекие от программинга задачки разбирает. Попробую поближе к теме

Значит так — есть некий список сервисов, которые нужно проинициализировать. Для некоторых из сервисов важен порядок инициализации, так как одни сервисы при инициализации могут использовать другие. Для этого каждый сервер может нести несколько меток (атрибутов).
Атрибут №1 — Зависимость(сервис). Указывает на то что этот сервис использует другой(указанный) сервис.
Атрибут №2 — Требует инициализации для работы. Этот атрибут указывается для тех сервисов, которые способны работать только после инициализации.

Требуется:
придумать самый эффективный алгоритм переупорядочивания списка сервисов таким образом чтобы
1) Зависимые сервисы, если возможно, шли после тех, от которых они зависят.
2) Если сервисы зависят друг от друга и ни один из них не имеет атрибута №2 то порядок следования любой
3) Если один из сервисов имеет второй атрибутом, а второй нет и при этом они зависят друг от друга, то первым должен идти тот, который с атрибутом
4) Если оба сервиса имеют второй атрибут и зависят друг от друга должна выдаваться ошибка.

Исходный список сервисов представляет собой хеш-таблицу. При этом у каждого сервиса есть уникальный ключ.

Здравствуйте, AndrewVK, Вы писали:

AVK>Что то тут народ совсем далекие от программинга задачки разбирает. Попробую поближе к теме

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

Ты будешь смеяться, но почти точь-в-точь эта задача была позавчера у нас на олимпиаде школьников

Решение, в общем, элементарное — первым инициализируем то, что не требует других. И так далее.

Если надо быстро — помним, сколько у сервиса "пап" и декрементируем всех "детей" добавляемого в список.

Тогда сложность равна кол-во сервисов + кол-во зависимостей.

Здравствуйте, AndrewVK, Вы писали:

AVK>Что то тут народ совсем далекие от программинга задачки разбирает. Попробую поближе к теме

AVK>Значит так — есть некий список сервисов, которые нужно проинициализировать. Для некоторых из сервисов важен порядок инициализации, так как одни сервисы при инициализации могут использовать другие. Для этого каждый сервер может нести несколько меток (атрибутов).
AVK>Атрибут №1 — Зависимость(сервис). Указывает на то что этот сервис использует другой(указанный) сервис.
AVK>Атрибут №2 — Требует инициализации для работы. Этот атрибут указывается для тех сервисов, которые способны работать только после инициализации.

AVK>Требуется:
AVK>придумать самый эффективный алгоритм переупорядочивания списка сервисов таким образом чтобы
AVK>1) Зависимые сервисы, если возможно, шли после тех, от которых они зависят.
AVK>2) Если сервисы зависят друг от друга и ни один из них не имеет атрибута №2 то порядок следования любой

AVK>3) Если один из сервисов имеет второй атрибутом, а второй нет и при этом они зависят друг от друга, то первым должен идти тот, который с атрибутом
????? какой аттрибут? как зависит, если не имеет аттрибуте?

AVK>4) Если оба сервиса имеют второй атрибут и зависят друг от друга должна выдаваться ошибка.

AVK>Исходный список сервисов представляет собой хеш-таблицу. При этом у каждого сервиса есть уникальный ключ.

Короче когда то писал такое:
Смысл в том чтобы пронумеровать все сервисы..
причём номер каждого зависимого должен быть минимум на 1 больше того, от которого он зависит..
В общем как то так:

1. задаёшь всем сервисам вес 0, и значение флага пройдено=0
2. для всех независимых ни от кого сервисов x выполнять фффф(x,o)
4. пока о не пустой
{
для всех x из o выполнять фффф(x,o1)
o= o1
почистить o1
}
3. сортируем сервисы по весу и в таком порядке инициализируем..

процедура фффф(x:сервис,o: список сервисов)
если (x требует инициализации )
x.пройдено= 1
для всех зависимых от x сервисов y
если y.пройдено ошибка-цикл!!!!
y.вес = max(y.вес,x.вес + 1)
добавить y в o

Здравствуйте, mihoshi, Вы писали:

M>Ты будешь смеяться, но почти точь-в-точь эта задача была позавчера у нас на олимпиаде школьников

Не, это честная задачка, из реальной софтинки. Точнее из второго януса.

M>Решение, в общем, элементарное — первым инициализируем то, что не требует других. И так далее.

Это неполное решение, только для дерева. А в реальности там сеть, со всеми вытекающими. Вся фишка то именно в циркулярных ссылках. Особливо если кольцо не из двух сервисов, а из трех и более. В этом и проблема. А если бы было простое дерево я бы и не спрашивал.

Здравствуйте, AndrewVK, Вы писали:

AVK>Что то тут народ совсем далекие от программинга задачки разбирает. Попробую поближе к теме

AVK>Значит так — есть некий список сервисов, которые нужно проинициализировать. Для некоторых из сервисов важен порядок инициализации, так как одни сервисы при инициализации могут использовать другие. Для этого каждый сервер может нести несколько меток (атрибутов).
AVK>Атрибут №1 — Зависимость(сервис). Указывает на то что этот сервис использует другой(указанный) сервис.
AVK>Атрибут №2 — Требует инициализации для работы. Этот атрибут указывается для тех сервисов, которые способны работать только после инициализации.

AVK>Требуется:
AVK>придумать самый эффективный алгоритм переупорядочивания списка сервисов таким образом чтобы
AVK>1) Зависимые сервисы, если возможно, шли после тех, от которых они зависят.
AVK>2) Если сервисы зависят друг от друга и ни один из них не имеет атрибута №2 то порядок следования любой
AVK>3) Если один из сервисов имеет второй атрибутом, а второй нет и при этом они зависят друг от друга, то первым должен идти тот, который с атрибутом
AVK>4) Если оба сервиса имеют второй атрибут и зависят друг от друга должна выдаваться ошибка.

AVK>Исходный список сервисов представляет собой хеш-таблицу. При этом у каждого сервиса есть уникальный ключ.

Есть такой довольно известный алгоритм: нахождение замкнутого пути в направленном графе. Его же с успехом используют для упорядочивания зависимостей, равно как и в алгоритмах обнаружения/избежания deadlock'ов.
Один из вариантов называется топологическая сортировка Это то, что нужно. (Ну или стоило сразу с топологичестой сортировки начать? Не суть важно).

Алгоритм такой.

Сортируем

Если удалось — нет круговой зависимости — бай-бай

Если нет — значит есть как минимум один круг (и у нас есть все узлы этого/этих кругов).

Ищем узел, который может стартовать

Выкидываем, продолжаем сначала.

Если не смогли избавиться от кругов, удаляем узел с наиметьшим количеством входящих дуг.

Сначала

Как вариант — изначально выкинуть все узлы, которые могут стартовать независимо, тогда алгоритм заметно упростится:

Сортируем

Если удалось — нет круговой зависимости — бай-бай

Если не смогли избавиться от кругов, удаляем узел с наиметьшим количеством входящих дуг.

Сначала

Sorry..
Наверно лучше отформатировать так

{
  задаёшь всем сервисам вес 0, и значение флага пройдено=0 
  для всех независимых ни от кого сервисов x выполнять фффф(x,o) 
  пока о не пустой 
  {
     для всех x из o выполнять фффф(x,o1) 
     o= o1 
     почистить o1 
  }
  сортируем сервисы по весу и в таком порядке инициализируем.. 
}

процедура фффф(x:сервис,o: список сервисов) 
{
   если (x требует инициализации ) 
   {
     x.пройдено= 1 
     для всех зависимых от x сервисов y 
     {
        если y.пройдено ошибка-цикл!!!! 
        y.вес = max(y.вес,x.вес + 1) 
        добавить y в o 
     }
   }
}

Здравствуйте, vvaizh, Вы писали:

AVK>>3) Если один из сервисов имеет второй атрибутом, а второй нет и при этом они зависят друг от друга, то первым должен идти тот, который с атрибутом
V>????? какой аттрибут? как зависит, если не имеет аттрибуте?

Если есть два сервиса, зависящих друг от друга и один из них помечен атрибутом №2, т.е. может использоваться только если проинициализирован то такой сервис должен инициализироваться первым.

Здравствуйте, fAX, Вы писали:


fAX>Есть такой довольно известный алгоритм: нахождение замкнутого пути в направленном графе. Его же с успехом используют для упорядочивания зависимостей, равно как и в алгоритмах обнаружения/избежания deadlock'ов.
fAX>Один из вариантов называется топологическая сортировка Это то, что нужно. (Ну или стоило сразу с топологичестой сортировки начать? Не суть важно).

Подробнее — например, здесь

Здравствуйте, vvaizh, Вы писали:



Дык я о том же

Здравствуйте, vvaizh, Вы писали:

V>Sorry..
V>Наверно лучше отформатировать так

V>

V>{
V>  задаёшь всем сервисам вес 0, и значение флага пройдено=0 
V>  для всех независимых ни от кого сервисов x выполнять фффф(x,o) 
V>  пока о не пустой 
V>  {
V>     для всех x из o выполнять фффф(x,o1) 
V>     o= o1 
V>     почистить o1 
V>  }
V>  сортируем сервисы по весу и в таком порядке инициализируем.. 
V>}

V>процедура фффф(x:сервис,o: список сервисов) 
V>{
V>   если (x требует инициализации ) 
V>   {
V>     x.пройдено= 1 
V>     для всех зависимых от x сервисов y 
V>     {
V>        если y.пройдено ошибка-цикл!!!! 
V>        y.вес = max(y.вес,x.вес + 1) 
V>        добавить y в o 
V>     }
V>   }
V>}

V>

Проблема в том, что если при кольцевой зависимости, вроде приведённой ниже (на рисунке зависимость по часовой стрелке в каждом круге — 2 зависит от 1, 3 от 2 и т.д.),

  2-3-4   9
 /     \ / \
1       5   10
 \      /\ /
  8-7-6   11

этот код не совсем правилен (с житейской точки зрения), имхо (это я после еды такой добрый):
Ваш код проинициализирует (например):
4,6,8,1,3,7,11,9,10,25, в то время, как можно постараться максимизировать число сервисов от которых непосредственно зависит запускаемый (что, кстати, делает мой псевдокод ).

Пример более правильной (с "житейской" точки зрения ) инициализации:

1 — разрываем кольцо, 2,3,4,9,10,11,5,6,7,8. (и, возможно, снова 1)
Или — сначала "рвём" 5, затем 6,7,8,1,2,3,4,9,10,11. Хотя, возможно, 5 — и есть самый критический сервис...

Здравствуйте, fAX, Вы писали:

fAX>Проблема в том, что если при кольцевой зависимости, вроде приведённой ниже (на рисунке зависимость по часовой стрелке в каждом круге — 2 зависит от 1, 3 от 2 и т.д.),
fAX>

fAX>  2-3-4   9
fAX> /     \ / \
fAX>1       5   10
fAX> \      /\ /
fAX>  8-7-6   11
fAX>

ХЪ

fAX>Пример более правильной (с "житейской" точки зрения ) инициализации:

fAX>1 — разрываем кольцо, 2,3,4,9,10,11,5,6,7,8. (и, возможно, снова 1)
Читать:
1 — разрываем кольцо, 2,3,4,9 — разрываем кольцо, 10,11,5,6,7,8. (и, возможно, снова 1 и 9)

Здравствуйте, fAX, Вы писали:

fAX>Проблема в том, что если при кольцевой зависимости, вроде приведённой ниже (на рисунке зависимость по часовой стрелке в каждом круге — 2 зависит от 1, 3 от 2 и т.д.),
fAX>

fAX>  2-3-4   9
fAX> /     \ / \
fAX>1       5   10
fAX> \      /\ /
fAX>  8-7-6   11
fAX>

fAX>этот код не совсем правилен (с житейской точки зрения), имхо (это я после еды такой добрый):
fAX>Ваш код проинициализирует (например):
fAX>4,6,8,1,3,7,11,9,10,25, в то время, как можно постараться максимизировать число сервисов от которых непосредственно зависит запускаемый (что, кстати, делает мой псевдокод ).

ИМХО, зависимости от сервисов не требующих инициализации можно вообще смело выбросить..
тогда должен получиться строгий ацикличный граф..
и никаких уолец рвать не нужно..
что мой алгоритм успешно и делает..

Здравствуйте, AndrewVK, Вы писали:

Удаляем все зависимости на элементы другого типа и на удаленные элементы
Если остались ссылки то сообщаем этим сервисам что от них зависит данный
Иначе
{
удаляем(вернее перемещаем в список соответвстующего типа)
возвращаемся к просмотру сервисов которые сообщили что зависят от данного
}

если остались сервисы которые требуют инициализации то ошибка

инициализируем в порядке поступления
1)Требующие инициализации
2)Не требующие
3)остаток(циклы нетребующих)

ЗЫ уф надеюсь понятно написал

Здравствуйте, WolfHound, Вы писали:

Для всех не удаленных и не просмотреных
WH>Удаляем все ссылки на элементы другого типа и на удаленные элементы

Здравствуйте, vvaizh, Вы писали:

V>Здравствуйте, fAX, Вы писали:

fAX>>Проблема в том, что если при кольцевой зависимости, вроде приведённой ниже (на рисунке зависимость по часовой стрелке в каждом круге — 2 зависит от 1, 3 от 2 и т.д.),
fAX>>

fAX>>  2-3-4   9
fAX>> /     \ / \
fAX>>1       5   10
fAX>> \      /\ /
fAX>>  8-7-6   11
fAX>>

fAX>>этот код не совсем правилен (с житейской точки зрения), имхо (это я после еды такой добрый):
fAX>>Ваш код проинициализирует (например):
fAX>>4,6,8,1,3,7,11,9,10,25, в то время, как можно постараться максимизировать число сервисов от которых непосредственно зависит запускаемый (что, кстати, делает мой псевдокод ).

V>ИМХО, зависимости от сервисов не требующих инициализации можно вообще смело выбросить..
V>тогда должен получиться строгий ацикличный граф..
V>и никаких колец рвать не нужно..
V>что мой алгоритм успешно и делает..
Зуб за зуб?
На рисунке я имел в виду зависимость: 1-2-3-4-5-6-7-8-9-1. Все зависят от всех. Просто в жизни (ну нравится мне формулировка!) не всегда зависимость — критичная. И поэтому если минимизировать количество инициализированных без прямых "предков" сервисов, шанс живой системы выше, чем просто если инициализировать то, что осталось в кольцах в произвольном порядке (а это то, что получите Вы) в порядре уменьшения ссылок на сервис...

В строго математическом смысел ("если есть решение — вот оно!"), Ваш алгоритм правилен.

Здравствуйте, vvaizh, Вы писали:

V>Sorry..
V>Наверно лучше отформатировать так

V>

V>{
V>  задаёшь всем сервисам вес 0, и значение флага пройдено=0 
V>  для всех независимых ни от кого сервисов x выполнять фффф(x,o) 
V>  пока о не пустой 
V>  {
V>     для всех x из o выполнять фффф(x,o1) 
V>     o= o1 
V>     почистить o1 
V>  }
V>  сортируем сервисы по весу и в таком порядке инициализируем.. 
V>}

V>

Хмм... Сомневаюсь, что это даст оптимальный результат. Вообще задача близка к задаче о числе перестановок в ряде. И можно использовать соответствующие методы.

Основная мысль — если в порядке инициализации поменять идущие подряд сервисы, то меняются только отношения между ними. Соответственно, если n-й сервис использует n+1й, то их нужно менять независимо от веса.

Кстати, лдя упрощения задачи нужно игнорировать лишнюю информацию. Т.е. если А требует Б (или просто находится ниже в иерархии требований), то мы игнорируем факт, что Б использует А. Если А и Б используют друг друга, то мы игнорируем оба факта (в случае если использование имеет вес, вычитаем из обоих весов наименьший).
В итоге мы получаем дерево требований с однонаправленными векторами использования, которые всегда связывают сервисы из разных веток.

Далее отбрасываем пока можем те отношения использования, которые разрешаются "без потерь". Т.е. Если сервис вместе с родителями по дереву требований не использует других сервисов, то его вместе с родителями ставим в начало списка и забиваем. Аналогично с концом.

Кстати, то, что я называл выше деревом на самом деле лес . Впрочем, неважно.

В общем, мы получаем в итоге лес требований с векторами использования крест-накрест. Что с этим делат... Пока неясно Интересная получилась задачка...

В качестве эвристического метода можно использовать, конечно, метод vvaizh с очисткой по mihoshi

Но вполне возможно, что существует алгоритм, находящиц оптимальное решение. Кстати, ен мешало бы ввести меру оценки "хорошести" результата.