Логические задачи → Очень трудная задача

11 ноября 2009 | Добавил: atlakatl

В 90-ые столкнулся с проблемой. Решил её не оптимально. А как найти приемлемое решение, так и не знаю.
Итак, имеется протяжённое сопротивление. В некоторых его частях выведены N клемм. Нужно расположить их на сопротивлении так, чтобы при последовательном присоединении к каждой паре получался наиболее равномерное распределение по сопротивлению. Не понятно? – конечно, лучше не получается. Понятнее будет на примерах:

Пример 1:
Длина сопротивления 3. Первая клемма на 0, вторая на 1, третья на 3. Соединяя каждую пару, получаем: кл1-кл2=1, кл2-кл3=2, кл1-кл3=3
Пример 2:
Длина сопротивления 6. Первая клемма на 0, вторая на 1, третья на 4, четвёртая на 6. кл1-кл2=1, кл3-кл4=2, кл2-кл3=3, кл1-кл3=4, кл2-кл4=5, кл1-кл4=6
Абсолютно равномерное распределение! При 5 клеммах должны получаться числа от 1 до 10 и т.д. Но не получается!
Потому зададимся каким-нибудь критерием. Например, чтобы максимальное отклонение от натурального ряда было минимально. Или был бы минимален квадрат отклонения. Что удобнее. Какой должна быть процедура поиска? Кроме случайного перебора ничего не вырисовывается.

(голосов: 2, оценка: 3 из 5)

Loading ...

Версия для печати.
RSS комментариев записи.

Метки → физические

Комментариев: 4

SoVictor пишет:
11 ноября 2009 в 09:09

Задача знаменита и не нова, обычно она даётся так:
Сделать минимальное количество засечек на линейке длиной N, чтобы этой линейкой можно было измерить любое расстояние от 1 до N
Сущесвтуют вариации этой задачи... должен сказать, что для произвольного N её не встречал
atlakatl пишет:
11 ноября 2009 в 16:43

Задача в формулировке SoVictor-а решается для конкретных N довольно просто. Так для измерения целых длин от 1 до 10 требуется линейка длиной 10 с насечками на 1, 5, 6, 8, - один из минимальных вариантов. В этом варианте есть и дублирующиеся пары. Так, 2=10-8=8-6 и т.д.

Уточняю мою формулировку. Если на сопротивлении имеется N клемм, то возможно измерить K=N*(N-1)/2 значений. Например, при 5 клеммах возможно измерить 10 значений. Нужно найти такое расположение клемм, чтобы разности всевозможных пар обеспечивали минимальное отклонение от целого ряда чисел от 1 до K. Формулировку минимальности не конкретизирую: она может зависеть от метода решения.

В случае численного решения имеем классическую многоэкстремальную задачу, где число минимумов пропорционально (K-1)! – в смысле факториал. Без дополнительных соображений для больших K найти глобальный минимум перебором невозможно за приемлемое время.
Kot пишет:
20 февраля 2010 в 03:36

а можно так соеденять?
__П__П_П__ т.е. вторую с третьей,четветую с 7й, т.е. что бы сопротивление было 1-2 + 3-4 + 7-Н??
atlakatl пишет:
21 февраля 2010 в 10:39

что бы сопротивление было 1-2 + 3-4 + 7-Н
Действительно, так можно получить дополнительные варианты значений сопротивления. Но меня интересуют соображения по нахождению именно простейших пар, создаваемых подключением по двум клеммам.