Nano Hash - криптовалюты, майнинг, программирование

Алгоритм формирования массива неравных стоимостей для оптимизации транспортной задачи

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

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

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

На данный момент я передаю матрицу стоимости через функцию запекания, которая проверяет каждую запись на равенство каждой из других записей и сдвигает ее на фиксированный процент, если она совпадает. Однако этот подход, по-видимому, требует N^2 сравнений, и если все начальные значения одинаковы, последняя стоимость будет на r^N больше. (r — произвольный фиксированный процент). Также существует проблема, заключающаяся в том, что, умножая на процент, вы оказываетесь поверх другого значения. Таким образом, проблема, похоже, имеет элемент рекурсии или, по крайней мере, повторной проверки, которая раздувает код.

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

Пример: {1,1,2,3,4,5} (tol = 0,05) становится {1,1,05,2,3,4,5}

c# optimization algorithm
31.05.2010

  • Я думаю, вы можете пропустить какое-то условие в своей задаче. Почему нельзя использовать весь набор путей с соответствующими коэффициентами балансировки? Если у вас есть ограничение на количество путей, которые вы можете использовать, то оно также должно применяться к вашему набору кратчайших путей. 31.05.2010
  • в основном, это не проблема пути с проходящим потоком. Я ищу минимальный набор, который справится с транспортировкой, и для этого я мог бы убрать все лишнее. Одним из способов устранения избыточности является искусственное увеличение стоимости. 31.05.2010

Ответы:


1

вместо сравнения всех значений друг с другом попробуйте более линейный подход:

Опасность! псевдокод впереди...

seen = {}
for i=0:
  for j=0:
    if cost_matrix[i,j] in seen:
      cost_matrix[i,j] = cost_matrix[i,j]+percentage
    append cost_matrix[i,j] to seen
    j++
  i++
31.05.2010
  • Это улучшение, но я не просто ищу точные совпадения ... поэтому вместо того, чтобы видеть, мне нужна функция внутри элемента в видимой функции. 01.06.2010

    • 2

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

    «Транспортная проблема» в OR — это гораздо более конкретная проблема с одним набором пунктов отправления и одним набором пунктов назначения. В вашей задаче у вас есть пути через несколько точек, но иногда вы получаете два кратчайших пути, потому что затраты в сумме дают одинаковую сумму. Верно?

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

    01.06.2010
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..