Перейти к содержанию
Симферопольский Форум

Нужна помощь программиста/математика


Инквизитор

Рекомендуемые сообщения

Хау, народ)

 

Имею задачу, которую не знаю как решить. Гуглеж заводит или не туда, или в такие дикие дебри, что у меня отказывают пониматоры.

 

Собственно, воть она:

 

Дано:

N пар объектов вида X->Y. Объекты в парах могут повторяться.

 

Пример этих пар:

A->С
B->A
C->E
D->E
E->B
F->A
G->C

 

Требуется:

1. Построить цепь из этих объектов таким образом, что:

а) Второй объект в каждой паре является первым объектом в следующей

б) Объекты не повторяются

в) Направление стрелок предпочтительно слева направо, но в целом не имеет значения

г) Цепь должна быть максимальной длины

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

Пример цепи, построенной из вышенаписанных пар:

        F
        |
        V
D->E->B->A->С<-G
  ^        |
  |________|

 

 

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

- Что они хотят? 
- Ку они хотят…

Ссылка на комментарий
Поделиться на другие сайты

видимо графы


Я детей вообще то боюсь, милостивый мой государь, - шумливы, жестоки и себялюбивы, а коли дети правят державой? ©Юлиан Семёнов

Ничего не делается к лучшему © Борис Раушенбах

Люди, люди — это самое главное. Люди дороже даже денег. © Ф.М. Достоевский

Ссылка на комментарий
Поделиться на другие сайты

видимо графы

Перекопал википедию... из того, что понял - все не то (

- Что они хотят? 
- Ку они хотят…

Ссылка на комментарий
Поделиться на другие сайты

но что- то явно из тех степей. В принципе похоже на генерацию лабиринтов m.habrahabr.ru/post/176671/


Я детей вообще то боюсь, милостивый мой государь, - шумливы, жестоки и себялюбивы, а коли дети правят державой? ©Юлиан Семёнов

Ничего не делается к лучшему © Борис Раушенбах

Люди, люди — это самое главное. Люди дороже даже денег. © Ф.М. Достоевский

Ссылка на комментарий
Поделиться на другие сайты

Вначале убрать дубликаты, если входные данные это позволяют.

Потом каждой такой паре перехода назначить уникальный ID, т.е. в данном случае это будет обыкновенный массив ['a->b', 'd->f'] где номер значения и есть id.

Потом создать массивы для каждого a, b, c из ID возможных переходов.

Затем для каждого a, b, c придумать аглоритм поиска цепочек, и находить самые длинные, если цепочка достигла длинны массива возможных переходов - получили замкнутую цепь с кротчайшим путем.

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

Ссылка на комментарий
Поделиться на другие сайты

Возможно стоит построить обобщенный граф последовательно добавляя в него правила. Потом искать самую длинную цепочку. Надо учесть, что может быть набор несвязанных графов, например для случая A->B, C->D.
Ссылка на комментарий
Поделиться на другие сайты

Я очень дико извиняюсь конечно... Но не могу пройти мимо данной темы.. Ээээммм, о чем вообще речь идет то?
Ссылка на комментарий
Поделиться на другие сайты

И на сколько я понял, у вас в задании ошибка, в строке "A->С", "С" - русская, собственно DOT все правильно построил, если заменить на лат. будет так:

si2.png

Ссылка на комментарий
Поделиться на другие сайты

И на сколько я понял, у вас в задании ошибка, в строке "A->С", "С" - русская, собственно DOT все правильно построил, если заменить на лат. будет так:

Возможно, русская.

DOT - есть либы под жабкоскрипт?

- Что они хотят? 
- Ку они хотят…

Ссылка на комментарий
Поделиться на другие сайты

DOT - есть либы под жабкоскрипт?

 

Javascript не увлекаюсь, не скажу, для всяких perl, php, python - точно есть.

Ссылка на комментарий
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.
Примечание: Ваш пост будет проверен модератором, прежде чем станет видимым.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

Загрузка...

Чат

Чат

Please enter your display name

×
×
  • Создать...