Максимальное разнообразие: перевод эвристического алгоритма в C (или псевдокод)

У меня есть набор из N предметов, и я знаю их взаимные расстояния. у каждого элемента есть стоимость, и у меня есть бюджет. Я должен выполнить следующую задачу: предположим, я положил предмет в корзину, следующим предметом в корзине будет предмет, расстояние которого максимально от первого (при ограничении бюджета), третьим предметом будет предмет, сумма расстояний из item1 и item2 - это максимум (при ограничениях бюджета), четвертый элемент - это тот, чья сумма расстояний от пунктов 1,2 и 3 является максимальной (всегда бюджет) и т. д. Как мне найти подмножество, чье общее расстояние (вычисляется как указано выше) макс? Знаете ли вы какой-нибудь алгоритм для решения этой проблемы? заранее спасибо

ОБНОВЛЕНИЕ: я провел некоторое исследование, и эта проблема называется проблемой максимального разнообразия. Я не могу перенести эвристический алгоритм (который решит проблему), указанный выше в C или псевдокоде!

Источник

1 ответ

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

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

шаги:

  1. Выберите начальную вершину

  2. Оцените расстояние от начальной точки.

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

  4. Вычислите расстояние между вновь добавленным элементом и остальными как сумму пути, чтобы добраться до элемента + стоимость выбора другого элемента (т.е. первая итерация, скажем, мы получили элемент 1, затем перешли к элементу 2, затем расстояние между элементом 2 и пункт x будет пунктом 1 + пункт 2 + пункт x)

  5. Снова выберите максимум, если бюджет выше, перейдите к следующему максимуму, чтобы получить максимальный уровень, превышающий ваш бюджет.

  6. Повторите, пока бюджет не исчерпан

Надеюсь, что это помогает, не стесняйтесь просить разъяснений, если это имеет смысл. Я предлагаю некоторые справочные материалы по теории графов и связанных с ними алгоритмов

Источник
Другие вопросы по тегам