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

[Инквизитор]

Хау, народ)

 

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

 

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

 

Дано:

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]

видимо графы

[Инквизитор]

видимо графы

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

[Rumlin]

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

[ravemassacre]

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

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

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

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

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

[Mim]

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

[Местный Сусанин]

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

[SlavaD]

DOT

digraph SI{
   A->С;
   B->A;
   C->E;
   D->E;
   E->B;
   F->A;
   G->C;
}

[SlavaD]

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

[Инквизитор]

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

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

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

[SlavaD]

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

 

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