Обо всем > Комбинаторика? 

> brener


кэп, ты конечно извини, но ты и логистика несовместимы.

>  brener [11] (06.10.11 20:48)
> > все он нормально изложил. есть ограничение - в течение суток> вряд ли тебе одного самолета хватитА что значит > посетив все города?Кто их посещать должен? некий коммивояжор, который должен летать на самолетах? Или все-таки задача к задаче коммивояжора отношения не имеет и речь идет просто о том, как минимальным количеством самолетов обеспечить такое расписание, чтобы раз в сутки по каждому ребру графа в обе стороны был рейс?

Самолет !!! да Самолет!!

Я просто подразумевал, что моя задача - частный случай задачи коммивояжера)))

Только не раз в сутки, а в отведенный промежуток времени..ну тут скорее всего надо для простоты принять, что сутки равны - 13 часам))

>  Джимми Нейтрон [10] (06.10.11 20:48)
> > NikolasptANTOR LogisticsMaster вот название проги, которая в логистике используется. Но не знаю сможешь ли ты ее найти в бесплатной версии. А вообще гугли на тему информационные технологии в логистике

Счас буду смотреть, спасибо!)

> кэп, ты конечно извини, но ты и логистика несовместимы.
>


боюсь, что после разъяснений, что речь идет именно о составленом расписания, задача к логистике перестанет иметь хоть какое-то отношение.
В итоге задача по сути сводится к тому, что надо посчитать время, необходимое на облет каждого треугольника, а потом получившиеся 8 чисел разбить на минимальное возможное количество групп так, чтобы сумма чисел в каждой группе не превосходила 13 часов. Остаюсь при своем мнении, что написать программку, которая бы осуществляла полный перебор быстрее, чем рамусоливать все это на форуме

>  brener [11] (06.10.11 20:57)
> > кэп, ты конечно извини, но ты и логистика несовместимы.>боюсь, что после разъяснений, что речь идет именно о составленом расписания, задача к логистике перестанет иметь хоть какое-то отношение.В итоге задача по сути сводится к тому, что надо посчитать время, необходимое на облет каждого треугольника, а потом получившиеся 8 чисел разбить на минимальное возможное количество групп так, чтобы сумма чисел в каждой группе не превосходила 13 часов. Остаюсь при своем мнении, что написать программку, которая бы осуществляла полный перебор быстрее, чем рамусоливать все это на форуме

Ты более менее правильно поняла.
Напиши программу и будет тебе спасибо)

>  Nikolaspt [10] (06.10.11 21:02)
> >  brener [11] (06.10.11 20:57)> > кэп, ты конечно извини, но ты и логистика несовместимы.>боюсь, что после разъяснений, что речь идет именно о составленом расписания, задача к логистике перестанет иметь хоть какое-то отношение.В итоге задача по сути сводится к тому, что надо посчитать время, необходимое на облет каждого треугольника, а потом получившиеся 8 чисел разбить на минимальное возможное количество групп так, чтобы сумма чисел в каждой группе не превосходила 13 часов. Остаюсь при своем мнении, что написать программку, которая бы осуществляла полный перебор быстрее, чем рамусоливать все это на форумеТы более менее правильно поняла.Напиши программу и будет тебе спасибо)

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

1 самолет за указанный промежуток времени пролетает только 5 городов.
2 самолета пролетают все 8, но остается еще 5 часов(например) и могу на ряде направлений сделать не 1 перелет туда-обратно, а 2?
То есть в данной группе городов, надо получить максимальный налет.

> Напиши программу и будет тебе спасибо)


максимум могу придумать алгоритм.
типа
берем самое большое число. Потом максимальное из оставшихся так, чтобы сумма не превзошла 13 часов (на самом деле, кстати, 14, а не 13, но это мелочи) и так далее. Потом с невостребованными делаем то же самое. Получили какое-то число самолетов.
Возвращаемся назад до первой ситуации, когда кроме максимального числа были другие на выбор. Берем в этом месте второе из возможных, далее продолжаем как раньше. Ну и так далее, пока все возможное дерево не облазием. Не знаю, оптимально это или нет, но писаться код должен за полчаса, а так как сложность задачи. если не ошибаюсь, квадратична по количеству городов, то особо заморачиваться оптимизацией алгоритма не стоит.

>  brener [11] (06.10.11 21:08)
> > Напиши программу и будет тебе спасибо)максимум могу придумать алгоритм.типаберем самое большое число. Потом максимальное из оставшихся так, чтобы сумма не превзошла 13 часов (на самом деле, кстати, 14, а не 13, но это мелочи) и так далее. Потом с невостребованными делаем то же самое. Получили какое-то число самолетов.Возвращаемся назад до первой ситуации, когда кроме максимального числа были другие на выбор. Берем в этом месте второе из возможных, далее продолжаем как раньше. Ну и так далее, пока все возможное дерево не облазием. Не знаю, оптимально это или нет, но писаться код должен за полчаса, а так как сложность задачи. если не ошибаюсь, квадратична по количеству городов, то особо заморачиваться оптимизацией алгоритма не стоит.

Хм..."берем самоле большое число" - какое число?
Ты можешь написать алгоритм , ну скажем так более нагляднее?

> Хм..."берем самоле большое число" - какое число?



> потом получившиеся 8 чисел разбить на минимальное возможное
> количество групп так, чтобы сумма чисел в каждой группе
> не превосходила 13 часов.

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

>  Vinny the Pooh [10] (06.10.11 21:16)
> Проще перебором, компьютеры быстро считают.Просчитать все варианты разбивки городов по самолетам и отсечь которые не укладываются в условия.

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

http://lib.custis.ru/Задача_коммивояжера

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

> Nikolaspt

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

>  Vinny the Pooh [10] (06.10.11 21:31)
> > NikolasptПеребор тебе всегда даст самое эффективное решение, вопрос только что может много времени занять. Но если число городов не много тысяч, то просчитается достаточно быстро

Ну хз.
Лана завтра буду искать ченить еще, может найду готовую прогу.