Инквизитор Опубликовано 15 декабря, 2015 Жалоба Поделиться Опубликовано 15 декабря, 2015 Хау, народ) Имею задачу, которую не знаю как решить. Гуглеж заводит или не туда, или в такие дикие дебри, что у меня отказывают пониматоры. Собственно, воть она: Дано: N пар объектов вида X->Y. Объекты в парах могут повторяться. Пример этих пар:A->С B->A C->E D->E E->B F->A G->C Требуется:1. Построить цепь из этих объектов таким образом, что: а) Второй объект в каждой паре является первым объектом в следующей б) Объекты не повторяются в) Направление стрелок предпочтительно слева направо, но в целом не имеет значения г) Цепь должна быть максимальной длины Цепь может иметь ответвления (когда в нескольких парах один и тот же одинаковый второй объект) и кольца.Пример цепи, построенной из вышенаписанных пар: F | V D->E->B->A->С<-G ^ | |________| Собственно, прошу ткнуть меня носом в подходящий алгоритм или их комбинацию. Или еще как-то наставить на путь истинный... Цитата - Что они хотят? - Ку они хотят… Ссылка на комментарий Поделиться на другие сайты Поделиться
Rumlin Опубликовано 15 декабря, 2015 Жалоба Поделиться Опубликовано 15 декабря, 2015 видимо графы Цитата Я детей вообще то боюсь, милостивый мой государь, - шумливы, жестоки и себялюбивы, а коли дети правят державой? ©Юлиан Семёнов Ничего не делается к лучшему © Борис РаушенбахЛюди, люди — это самое главное. Люди дороже даже денег. © Ф.М. Достоевский Ссылка на комментарий Поделиться на другие сайты Поделиться
Инквизитор Опубликовано 15 декабря, 2015 Автор Жалоба Поделиться Опубликовано 15 декабря, 2015 видимо графыПерекопал википедию... из того, что понял - все не то ( Цитата - Что они хотят? - Ку они хотят… Ссылка на комментарий Поделиться на другие сайты Поделиться
Rumlin Опубликовано 15 декабря, 2015 Жалоба Поделиться Опубликовано 15 декабря, 2015 но что- то явно из тех степей. В принципе похоже на генерацию лабиринтов m.habrahabr.ru/post/176671/ Цитата Я детей вообще то боюсь, милостивый мой государь, - шумливы, жестоки и себялюбивы, а коли дети правят державой? ©Юлиан Семёнов Ничего не делается к лучшему © Борис РаушенбахЛюди, люди — это самое главное. Люди дороже даже денег. © Ф.М. Достоевский Ссылка на комментарий Поделиться на другие сайты Поделиться
ravemassacre Опубликовано 15 декабря, 2015 Жалоба Поделиться Опубликовано 15 декабря, 2015 Вначале убрать дубликаты, если входные данные это позволяют.Потом каждой такой паре перехода назначить уникальный ID, т.е. в данном случае это будет обыкновенный массив ['a->b', 'd->f'] где номер значения и есть id.Потом создать массивы для каждого a, b, c из ID возможных переходов.Затем для каждого a, b, c придумать аглоритм поиска цепочек, и находить самые длинные, если цепочка достигла длинны массива возможных переходов - получили замкнутую цепь с кротчайшим путем.А так конечно нужно думать, много нюансов вылезет наверняка, на бумажке такое не придумаешь... Цитата Ссылка на комментарий Поделиться на другие сайты Поделиться
Mim Опубликовано 15 декабря, 2015 Жалоба Поделиться Опубликовано 15 декабря, 2015 Возможно стоит построить обобщенный граф последовательно добавляя в него правила. Потом искать самую длинную цепочку. Надо учесть, что может быть набор несвязанных графов, например для случая A->B, C->D. Цитата Ссылка на комментарий Поделиться на другие сайты Поделиться
Местный Сусанин Опубликовано 15 декабря, 2015 Жалоба Поделиться Опубликовано 15 декабря, 2015 Я очень дико извиняюсь конечно... Но не могу пройти мимо данной темы.. Ээээммм, о чем вообще речь идет то? Цитата Ссылка на комментарий Поделиться на другие сайты Поделиться
SlavaD Опубликовано 15 декабря, 2015 Жалоба Поделиться Опубликовано 15 декабря, 2015 DOTdigraph SI{ A->С; B->A; C->E; D->E; E->B; F->A; G->C; } Цитата Ссылка на комментарий Поделиться на другие сайты Поделиться
SlavaD Опубликовано 16 декабря, 2015 Жалоба Поделиться Опубликовано 16 декабря, 2015 И на сколько я понял, у вас в задании ошибка, в строке "A->С", "С" - русская, собственно DOT все правильно построил, если заменить на лат. будет так: Цитата Ссылка на комментарий Поделиться на другие сайты Поделиться
Инквизитор Опубликовано 16 декабря, 2015 Автор Жалоба Поделиться Опубликовано 16 декабря, 2015 И на сколько я понял, у вас в задании ошибка, в строке "A->С", "С" - русская, собственно DOT все правильно построил, если заменить на лат. будет так:Возможно, русская.DOT - есть либы под жабкоскрипт? Цитата - Что они хотят? - Ку они хотят… Ссылка на комментарий Поделиться на другие сайты Поделиться
SlavaD Опубликовано 16 декабря, 2015 Жалоба Поделиться Опубликовано 16 декабря, 2015 DOT - есть либы под жабкоскрипт? Javascript не увлекаюсь, не скажу, для всяких perl, php, python - точно есть. Цитата Ссылка на комментарий Поделиться на другие сайты Поделиться
Рекомендуемые сообщения
Присоединяйтесь к обсуждению
Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.
Примечание: Ваш пост будет проверен модератором, прежде чем станет видимым.