Транспортная задача

[danilakh]

Добрые день!

У кого есть идеи по реализации задачи:

"Имеется набор из n количества точек, раскиданных на области, ограниченной двумя эллипсами. Линии, ограниченные по длине параметром p, выходящие из центра, соединяют максимальное количество точек. Линии должны покрыть все точки. Необходимо найти такой набор точек, при котором суммарная длина линий, покрывших все точки, будет максимальной. При этом сам путь должен быть оптимальным, то есть кратчайшим для данного набора точек (минимакс)"


Независимые переменные
W – ширина внутреннего эллипса
H – высота внутреннего эллипса
L – ширина полосы между границами внутреннего и внешнего эллипса
n – количество точек
P – длина линии

Зависимые переменные (что должна находить модель)
N – количество линий
D – суммарная длина всех линий
xi, yj – координаты точек


{x1y1;x2y2;…xnyn} – последовательность точек в линии NX

Задача должна быть решена в VB с возможностью интеграции в макрос Excel.


1) Есть ли люди, готовы взяться за реализацию данной идеи - условия в ЛС

2) У кого какие идеи по работе данного алогитма?

Спасибо!

[was3110]

Интересно, а алгоритм минимизации пути существует (доступен)? Это как бы является исходными данными... Точки надо разбрасывать так, что бы максимально противодействовать алгоритму минимизации. А иначе если поручить такую задачу одному программисту, он будет постоянно бороться сам с собой (поочередно усложняя и совершенствуя, то один алгоритм, то другой ...). Мои контакты в профиле.

[danilakh]

Алгоритм нужно найти

Как вариант -

Т.е. для заданного набора точек. Задаются набор два массива координат X[1 to i] Y[1 to i] и массив названий точек A[1 to i]. Далее алгоритм будет находить самый эффективный способ соединения этих точек с центром линиями заданной длины (т.е. как вариант первый шаг - из всего множества линий ограниченной длины найти ту, которая соединяет максимальное число точек - если таких линий несколько, то выбираем линию наименьшей длины (либо можно брать любую...возможно сделать такое допущение). Затем мы записываем маршрут в виде слова состоящий из точек маршрута (допустим "ahnfgt"), далее мы выкидываем из множества точек точки: a, h, n, f, g, t и повторяем операцию

Т.е. перебирать все точки это не вариант - n*n! операций

Но можно попробовать ограничить длину линии кол-вом точек...т.е. не более 7-ти, тогда уже операций будет меньше - n!/(n-7)! При этом для нахождения всех линий будет примерно (n/7)*(n!/(n-7)!) операций и это все для одного набора точек...ну а затем уже будем генерить случайные наборы точек, для нахождения самого максимального варианта маршрута.

Вариант в лоб - но пока единственное что есть. Задача для применения на практике, так что возможно использовать допущения если это упростит.

[IgorGO]

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

[danilakh]

Сообщение от IgorGO

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

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

Но Вы правы, это не суть задачи...как проще сделать либо два эллипса (т.е. задаются 4 параметра), либо эллипс и полоса одинаковой ширины (т.е. будет три параметра)

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

[IgorGO]

да и задачу Вы ставите

Необходимо найти такой набор точек

может можно так сформулировать:
для существующего набора точек построить ломаные линии так чтобы:
1.каждая линия начинается из цетра и может проходить любое количество точек
2.общая длина каждой линии не должна превышать Р
3.должны быть "пройдены все точки"
4.суммарная длина всех линий должна быть минимальна.

[danilakh]

Сообщение от IgorGO

да и задачу Вы ставите
может можно так сформулировать:
для существующего набора точек построить ломаные линии так чтобы:
1.каждая линия начинается из цетра и может проходить любое количество точек
2.общая длина каждой линии не должна превышать Р
3.должны быть "пройдены все точки"
4.суммарная длина всех линий должна быть минимальна.

согласен, можно так, вот только не уверен на счет 4-ого пункта. Тут первично лисло линий, т.е. чтобы число таких линий было минимальным...

[IgorGO]

я нисколько не давлю на Вас, это Ваша задача и Вам решать как ее ставить. минимизировать количество линий - это то же очень логичная постановка задачи.

я могу это сделать.
но времени уйдет много, это не до конца недели, а скорее всего до конца месяца.

[danilakh]

IgorGo, напишите, пожалуйста Ваши контакты на danilakh@yandex.ru (e-mail, телефон)