Что такое хорошая весовая функция?

Question

Я пытаюсь выполнить некоторые вычисления для ненаправленного, циклического, взвешенного графика и ищу хорошую функцию для расчета совокупного веса.

Каждое ребро имеет значение расстояния в диапазоне [1, ∞). Алгоритм должен придавать большее значение меньшим расстояниям (он должен быть монотонно убывающим), и ему следует присвоить значение 0 для расстояния ∞.

Мой первый инстинкт был просто 1 / d, который отвечает обоим этим требованиям. (Ну, технически 1 / ∞ не определено, но программисты склонны упускать этот слайд легче, чем математики.) Проблема с 1 / d состоит в том, что функция гораздо больше заботится о разнице между 1/1 и 1/2 чем разница между 1/34 и 1/35. Я бы хотел еще больше это разгадать. Я мог бы использовать √ (1 / d) или ∛ (1 / d) или даже ∜ (1 / d), но я чувствую, что упускаю целый класс возможностей. Есть предложения?

(я подумал о ln (1 / d), но он переходит в -∞, когда d переходит в ∞, и я не могу придумать, как можно увеличить это значение до 0.)

Позже

Я забыл требование: w (1) должно быть 1. (Это не делает недействительными существующие ответы; мультипликативная константа в порядке.)

Answer 1

возможно:

exp(-d)

edit: что-то вроде

exp(k(1-d)), k real

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

Answer 2

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

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

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

Answer 3

Как насчет 1 / ln (d + k)?

Answer 4

Кажется, что вы действительно ищете линейное уменьшение, что-то вроде бесконечности - d. Очевидно, что это решение является мусором, но поскольку вы, вероятно, не используете тип данных произвольной точности для расстояния, вы можете использовать yourDatatype.MaxValue - d, чтобы получить для этого линейную убывающую функцию.

На самом деле вы можете рассмотреть возможность использования (yourDatatype.MaxValue - d) + 1, когда вы используете double, потому что тогда вы можете присвоить вес 0, если ваше расстояние равно «бесконечности» (поскольку для double фактически есть значение для этого)

Конечно, вы все равно должны учитывать детали реализации, такие как w (d) = double.infinity или w (d) = integer.MaxValue, но их легко заметить, если вы знаете фактические типы данных, которые вы используете;)

Answer 5

Как насчет этого?

ш ( d ) = (1 + k ) / ( d + k ) для некоторых больших k

d = 2 + k будет местом, где w ( d ) = 1 / 2