Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Сортировка маршрута поезда

Автор: Alx 21.3.2011, 17:16

Всем привет. Есть массив, состоящий из перемешанных пар городов (отправление и прибытие) вида [E, C], [B, D], [C, A], [F, E], [A, B] Подскажите, пожалуйста, какой лучше использовать алгоритм сортировки, чтобы отсортировать города по порядку движения поезда (весь маршрут): [F, E] -> [E, C] -> [C, A] -> [A, B] -> [B, D]

Автор: Lipetsk 22.3.2011, 10:39

берете первую пару, пытаетесь к ней присоединить вторую справа или слева, потом третью и т.д. дошли до последней пары, попытались присоединить если остались неприсоединенные пары, пробуем снова присоединить как-то так, например

Автор: Akina 22.3.2011, 10:51

Отсортируй быстрым сортом по отправлению. После чего в один проход пересобери по стыковкам.

Автор: Alx 26.3.2011, 03:32

Lipetsk, а если допустим, у меня получилось к первой паре присоеденить третью, то что я дальше делаю? Пытаюсь присоеденить четвёртую к третьей или к первой? Akina, не понял, отсортировать отправления просто бинарной сортировкой по алфавиту? А как затем я смогу за один проход расставить все по местам? Распиши плз поподробнее, у меня туговато с матчастью  Вообще, я пока сделал так: Беру первую пару (отрезок пути) дальше среди оставшихся ищу следующий отрезок, вырезаю и вставляю за ним. Дальше ищу следующего для него начиная уже с третьего элемента и так далее, пока не дойду до конечного отрезка. После этого меняю направление и ищу среди оставшихся неотсортированными элементов предшествующие отрезки, вырезаю и вставляю их в начало массива. Ничего умнее придумать не смог. Если кто знает, подскажите как можно улучшить и этот алгоритм, просто мне нужно понять как мыслить  Еще, скажите какая алгоритмическая сложность у моего и у ваших примеров. Большое спасибо!

Автор: миг 26.3.2011, 06:24

т.е. хочешь сказать пару [F, E] невозможно присоединить и поэтому эта пара должна быть начальной точкой отправления. Добавлено через 5 минут и 46 секунд Цитата Пытаюсь присоеденить четвёртую к третьей или к первой? присоединяй сразу с двух сторон. так автоматически найдешь начало отправления и конец

Автор: Alx 26.3.2011, 15:44

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

Автор: миг 26.3.2011, 16:10

Цитата(Alx @  21.3.2011,  17:16 ) [E, C], [B, D], [C, A], [F, E], [A, B] Цитата(Akina @  22.3.2011,  10:51 ) Отсортируй быстрым сортом по отправлению. После чего в один проход пересобери по стыковкам  берем первую пару [E,C] пытаемся присоединить со второй парой. если вторую пару нельзя присоединить создаем вторую ленту(список) и третью, четвертую, пятую и т.д. пару будем пытаться присоединить к первой и второй паре,т.е. к той которая  присоединиться.  Если третья пара тоже не сможет присоединиться, то создаем третью ленту(список).  т.е будет работать примерно так:  выбираем элемент [Е,С] -создаем первую ленту в ней пока один элемент ____________________                        [B, D]- создаем вторую, третью и т.д. лент(столько сколько понадобиться) первый шаг    [Е,С] - первая лента ____________________                        [B, D] второй шаг    [Е,С][C, A] - начинаем "наращивать" ленты ___________________________                        [B, D] третий шаг    [F, E][Е,С][C, A] ______________________                           [A, B] [B, D] четвертый шаг [F, E][Е,С][C, A] __________________________ а потом просто соединяем концы полученных лент [F, E][Е,С][C, A][A, B] [B, D]

Автор: Alx 28.3.2011, 04:10

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

Автор: Akina 28.3.2011, 10:26

Цитата(Alx @  28.3.2011,  05:10 ) При большом количестве элементов будет очень много лент с небольшим кол-вом эл-ов, которые потом тоже нужно будет как-то соединять, и я не знаю, как сделать это в один проход. Это не так. Каждый очередной элемент ты пытаешься присоединить к каждой из лент как слева, так и справа. Если он слева стыкуется к одной ленте, а справа к другой - эти ленты вместе с ним объединяются в одну ленту. Т.е. алгоритм миг - однопроходный. И он однозначно лучше предложенного мной.

Автор: миг 28.3.2011, 20:07

Цитата(Alx @  28.3.2011,  04:10 ) При большом количестве элементов будет очень много лент с небольшим кол-вом эл-ов, которые потом тоже нужно будет как-то соединять, и я не знаю, как сделать это в один проход. Или я ошибаюсь? Насколько этот алгоритм быстрее того, что я предложил?  Дополнительные ленты создаются, когда элемент не может состыковаться с текущими лентами.. Если тебя смущает большое количество лент. Можешь на каждом шаге пытаться состыковать ленты между собой. В некоторых случаях стыкование лент на каждом шаге может ускорить работу программы, а может и замедлить.. Все будет зависеть от входных данных тут однозначно сказать нельзя. Добавлено через 2 минуты и 13 секунд но скорей всего в большинстве случаев замедлит работу программы

Автор: ksnk 28.3.2011, 20:24

миг, Правильно ли я понял, что формируются ВООБЩЕ ВСЕ возможные маршруты (ленты). И только потом из всех лент магическим образом выбирается нужная? Imho, при большом количестве маршрутов - эффективнее присоединять от одной из точек с одной стороны. Меньше вариантов для перебора.

Автор: Akina 28.3.2011, 21:12

ksnk, почитайте исходное условие. Имеется ОДИН маршрут, разбитый на участки. И его надо собрать обратно. Поэтому конечное состояние - всегда одна лента, включающая все участки. Если не так - исходные данные неверны. Цитата(миг @  28.3.2011,  21:07 ) Можешь на каждом шаге пытаться состыковать ленты между собой. Зачем? это происходит автоматически: Цитата(Akina @  28.3.2011,  11:26 ) Каждый очередной элемент ты пытаешься присоединить к каждой из лент как слева, так и справа.

Автор: миг 28.3.2011, 21:52

Цитата(ksnk @  28.3.2011,  20:24 ) миг, Правильно ли я понял, что формируются ВООБЩЕ ВСЕ возможные маршруты (ленты). И только потом из всех лент магическим образом выбирается нужная? количество маршрутов будет зависеть от входных данных..  В некоторых задачах будет всего два маршрута. Если данные задать по другому, то возможно  3, 4 и т.д. маршрутов.. Маршруты(ленты) создаются в процессе обработки данных. При большом количестве можно пытаться объединять маршруты(ленты). Для того, чтобы на каждом шаге создавался новый маршрут(лента) последовательность входных данных должна выглядеть крайне не удачно. Вероятность такого сценария довольно низкая, хотя и возможна при задании огромного количества входных данных.. Цитата(Akina @  28.3.2011,  21:12 ) Зачем? это происходит автоматически: кажется вы правы. просто была мысль, что допустим  данные расположены крайне не удачно. например так [Е,С][A, B] [X,Z][M,P][z,M][D,X][F, E][B, D][C, A] то у нас в самом начале получиться четыре не связаные ленты Код [Е,С] [A, B]  [X,Z] [M,P] и на 5 шаге элемент [z,M] нужно сравнить с четырьмя лентами. т.е.  чем больше лент тем больше сравнений.  поэтому и решил, что на каком то этапе логичнее объединять ленты..  вероятность такого неудачного расположения данных на мой взгляд довольно низкая.. Так, что для данного примера в большинстве случаев, при перемешивании входных данных,   будет создаваться меньше 4 лент.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)