30.01.2014 10:34 Дата регистрации:
10 лет назад Посты: 4 | наиболее плотная упаковка шаров разных диаметров, или окружностей Помогите пожалуйста решить задачу. Долго бьюсь, но не получается. Даны окружности 4-х размеров, диаметры равны: 30; 15; 7; 3. Количеством: 1; 24; 23; 461 соответственно. Надо их расположить на плоскости так, что бы они занимали наименьшую площадь. В следующем варианте количество каждого вида окружности меняется, но диаметры остаются те же. Можно ли решить ее как задачу закройщика? Не могу поставить задачу. Первоначально задача ставилась так: найти наиболее плотную упаковку шаров с этими же диаметрами и такого же количества. Но найти решение не удалось. Решила попробовать на плоскости, тоже безрезультатно. Может существует уже готовое решение такой задачи, просто я не знаю?
|
30.01.2014 20:30 Дата регистрации:
12 лет назад Посты: 1 575 | // Задача (с шарами, по-крайней мере) - сложнейшая и неоднозначная. До сих пор даже для шаров одного диаметра, имеются, по-моему, только приближенные решения - ограничения "сверху - снизу".. А где это такую задачку задали?.. Не уверен, что существует какой-либо универсальный алгоритм решения, если только диаметры "чудесным" образом не уложатся сразу "по кругу" (в плоскости) или "по шару" (в пространстве)... Редактировалось 1 раз(а). Последний 30.01.2014 20:39.
|
30.01.2014 23:43 Дата регистрации:
12 лет назад Посты: 176 | В таком виде задача сформулирована некорректно. Что значит "чтобы они занимали наименьшую площадь"? Или в каком смысле "наиболее плотная упаковка"? Круги, как ни крути, (если они не пересекаются внутренними областями) занимают одну и ту же площадь. При разных вариантах уточнения задачи различными будут и ответы. Под "занимаемой площадью", в частности, можно понимать: 1. суммарную площадь всех кругов; 2. площадь круга, в котором расположено указанное множество кругов; 3. площадь соответствующего квадрата (аналогично п. 2); 4. площадь выпуклой оболочки заданной системы кругов. Во всех этих случаях решения будут различными: в первом случае тривиальное, в остальных можно получить путем перебора (неизометрических систем кругов). При этом наименее сложным представляется вариант 4. Для системы шаров ситуация аналогична.
|
31.01.2014 10:39 Дата регистрации:
10 лет назад Посты: 4 | наиболее плотная упаковка шаров разных диаметров, или окружностей конечно же не первый вариант. Надо оперделенное количество окружностей или шаров расположить так, чтобы суммарное пустотное пространство между ними было минимальным или хотя бы стремилось к минимальному. При этом не важно, в квадрат укладывать или в окружность. А насчет 4 пункта мне не понятно.
|
31.01.2014 10:42 Дата регистрации:
10 лет назад Посты: 4 | наиболее плотная упаковка шаров разных диаметров, или окружностей Для шаров одинакового диаметра существует модель Слихтера. А это мне препод в институте задал, для курсовой.
|
03.02.2014 23:10 Дата регистрации:
11 лет назад Посты: 37 | оффтоп удален оффтоп удален  Редактировалось 1 раз(а). Последний 03.02.2014 23:30.
|
03.02.2014 23:14 Дата регистрации:
15 лет назад Посты: 13 190 | Еще интереснее тот факт, что "kovtunets" - это новый ник забаненого ранее Григория Пивеня, общеизвестного спамера.
|
03.02.2014 23:29 Дата регистрации:
10 лет назад Посты: 2 | наиболее плотная упаковка шаров разных диаметров, или окружностей Расположить круги в ряд, чтобы центры лежали на одной прямой, и касались друг друга. Тогда площадь пустот будет минимальна - равна нулю.
|
04.02.2014 07:39 Дата регистрации:
12 лет назад Посты: 1 575 | ... Цитата
1q2w3e4r
Расположить круги в ряд, чтобы центры лежали на одной прямой, и касались друг друга. Тогда площадь пустот будет минимальна - равна нулю.
Ничего подобного. Речь идет о площади описанного многогранника (многоугольника). А если располагать вдоль прямой - это будет далеко не самая плотная упаковка. Самую плотную упаковку на плоскости имеет такое расположение окружностей одного диаметра, при котором их количество (когда оно достаточно большое - по-крайней, мере более тривиальных значений - 1, 2 и некоторых других "начальных") равно разности соседних кубов натуральных чисел, и расположены они вокруг одной окружности (без лишних зазоров). В этом случае описанный многоугольник - это всегда равносторонний шестиугольник, внутренние окружности внутри которого имеют по шесть точек соприкосновения с соседними. Именно у него (в общем случае) будет наиболее плотная упаковка (Здесь, кстати, есть некоторое "пересечение" задачи наиболее плотной упаковки с ВТФ, однако, хочу предостеречь, - "выжать" что-то отсюда для ВТФ, того что можно строго доказать, вряд ли получится). Если же число окружностей не равно разности кубов, - тут уже начинается неопределенность - как "лишние" окружности "приспособить" так, чтобы образованный многоугольник имел наименьшую площадь?.. Редактировалось 2 раз(а). Последний 04.02.2014 07:59.
|
06.02.2014 00:36 Дата регистрации:
12 лет назад Посты: 176 | Бред какой-то Цитата
alexo2
[ Ничего подобного. Речь идет о площади описанного многогранника (многоугольника). А если располагать вдоль прямой - это будет далеко не самая плотная упаковка. Самую плотную упаковку на плоскости имеет такое расположение окружностей одного диаметра, при котором их количество (когда оно достаточно большое - по-крайней, мере более тривиальных значений - 1, 2 и некоторых других "начальных") равно разности соседних кубов натуральных чисел, и расположены они вокруг одной окружности (без лишних зазоров).
В этом случае описанный многоугольник - это всегда равносторонний шестиугольник, внутренние окружности внутри которого имеют по шесть точек соприкосновения с соседними. Именно у него (в общем случае) будет наиболее плотная упаковка (Здесь, кстати, есть некоторое "пересечение" задачи наиболее плотной упаковки с ВТФ, однако, хочу предостеречь, - "выжать" что-то отсюда для ВТФ, того что можно строго доказать, вряд ли получится).
Если же число окружностей не равно разности кубов, - тут уже начинается неопределенность - как "лишние" окружности "приспособить" так, чтобы образованный многоугольник имел наименьшую площадь?..
Напишите нормальным языком какая площадь какого описанного многоугольника. Сформулируйте нормальное утверждение или два, но с конкретным результатом.
|
06.02.2014 10:26 Дата регистрации:
12 лет назад Посты: 1 575 | ха.. дают все-таки на работе пятницу! Цитата
yog-urt
Напишите нормальным языком какая площадь какого описанного многоугольника. Сформулируйте нормальное утверждение или два, но с конкретным результатом.
Всем совет - изредка надо "отключать" свой математический склад ума, а то можно превратиться в "злобного карлика". Так уж получилось, что все-таки еду в Домбай на 3 дня. Процитирую свой ответ о домбайских трассах на одном из наших "местных" сайтов: меня заинтересовала так называемая Югославка, кто нибудь катался там?
Если имеется ввиду "дикая" трасса - с самого верха, куда довозит последний подъемник, и вниз, петляя по склону, то я её один раз прошел. Колени потом полдня дрожали.. Пологие склоны перемежаются с обрывистыми, - я ехал за знающим человеком (Далхат - инструктор, может кто знает, - хороший чел и мой знакомец), и он меня предупреждал, что будет дальше. А так, без предупреждений - можно и "улететь" - едешь по пологому месту, вдруг бах! - а дальше очень крутой спуск и т.д. То есть, буквально, - надо расчитать скорость, с которой "влететь воон на тот бугорок" - она должна быть не больше, не меньше, а именно такой-то, так как дальше - обрыв, и по нему уже надо будет закладывать офигенские виражи, чтобы удачно спуститься - если скорость будет меньше чем нужно - до верха бугорка не дотянешь, если больше - то вылетишь как на трамплине, - и метров 30 высоты.. :D
Короче, адреналина выделилось, как при прыжках с парашютом,( коих у меня 3 штуки) Теперь опять тянет покататься - именно спуститься по этой трассе. На лягушатниках мне не интересно - катаюсь я хорошо, и хочется "большего". Зато - кайф неимоверный.. Сродни сами знаете какому... :lol: Да вот в этом году не получилось.. Работа - мать её!
Добавлено спустя 1 час 2 минуты:
Лучше предостеречь - даже тем, кто считает, что он умеет кататься на горных лыжах, но не катался по этой трассе, лучше без "знающего" человека туда не соваться хотя бы первые разы. Да и спускаться первый раз "медленно", - по участкам. Запоминать побольше. Лучше не взобраться слету на какой-нибудь бугор и "корячиться" забираться на него лесенкой, чем не расчитать, и вылететь хрен знает с какой высоты в общем случае... Там и опытных-то спасатели чуть ли не каждый день "поломатых" спускают..Всё.. - отключился до вторника..  Редактировалось 1 раз(а). Последний 06.02.2014 10:38.
|
06.02.2014 17:44 Дата регистрации:
11 лет назад Посты: 715 | Д. Я то думал куда он пропал и почему не отвечает, а он оказывается на саночках катается. Вообще говоря с кругами Ваша мысль правильная. Круги одного диаметра располагают так, чтоб было 6 соседей. Добавлю то, что. Мешать одни круги с другими крайне не эффективно. За исключением тех случаев когда в их промежутки можно кого то запихнуть. Ещё надо стараться, чтоб граница между разными кругами и ихняя внешняя граница была минимальна.
|
17.02.2014 09:11 Дата регистрации:
10 лет назад Посты: 4 | Задача закройщика а можно ли применить сюда задачу закройщика? Ведь им тоже надо расположить детали раскроя так, чтобы был минимальный отход?
|
17.02.2014 15:54 Дата регистрации:
15 лет назад Посты: 3 155 | хм Цитата
valja
а можно ли применить сюда задачу закройщика? Ведь им тоже надо расположить детали раскроя так, чтобы был минимальный отход?
Нельзя. В задаче закройщика заранее известны варианты расположения выкроек на ткани. А в Вашей задача именно это и есть главный вопрос.
|
