Алгоритм соответствия - PullRequest
Новая
       50

Алгоритм соответствия

2 голосов
/ 14 июня 2009

Странный вопрос, здесь не код, а логика, надеюсь, можно разместить его здесь, вот он

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

Я хочу найти максимальную стоимость для графика.

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

Для уточнения: 

Global variable = T
many nodes N each have E,X,Y,L
L is the max number of links each node can have.
cost of link A,B = Sqrt(  min([a].e | [b].e)  ) x 
     ( 1 + Sqrt( sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10 )


total cost =sum all links.....and we wish to maximize this.

среднее значение для узлов 40-50 может варьироваться до (20..600) средний коэффициент привязки узла составляет 3 диапазона 0-10.

Ответы [ 6 ]

2 голосов
/ 15 июня 2009

Ради полноты для всех, кто смотрит на эту статью, я бы предложил пересмотреть ваши алгоритмы теории графов:

  • Дейкстр
  • Астар
  • жадный
  • Глубина / Ширина вначале
  • Даже динамическое программирование (в некоторых ситуациях)
  • ЭСТ. ЭСТ.

Там где-то есть правильное решение вашей проблемы. Я бы посоветовал сначала посмотреть на Дейкстру.

Надеюсь, это кому-нибудь поможет.

1 голос
/ 15 июня 2009
1 голос
/ 15 июня 2009

Это эквивалентно проблеме коммивояжера (и, следовательно, NP-Complete), поскольку, если бы вы могли эффективно решить эту проблему, вы могли бы решить TSP, просто заменив каждую цену на обратную.

Это означает, что вы не можете решить точно. С другой стороны, это означает, что вы можете сделать именно так, как я сказал (заменить каждую цену на ее взаимную), а затем использовать любой из известных методов аппроксимации TSP по этой проблеме.

1 голос
/ 15 июня 2009

Если я правильно понимаю проблему, скорее всего, нет полиномиального решения. Поэтому я бы реализовал следующий алгоритм:

  1. Найдите решение от Бенг жадный . Для этого вы сортируете все ребра по стоимости, а затем просматриваете их, начиная с самого высокого, добавляя ребро к вашему графику, когда это возможно, и пропуская, когда узел не может принять больше ребер.
  2. Посмотрите на свои ребра и попробуйте изменить их, чтобы архивировать более высокую стоимость, используя эвристику . Первое, что приходит мне в голову: вы перебираете все 4 набора узлов (A, B, C, D), и если у вашего текущего графа есть ребра AB, CD, но AC, BD будет лучше, тогда вы вносите изменения.
  3. Опционально то же самое с 6-ю кортежами или другими генетическими алгоритмами (они называются так, потому что работают мутациями).
0 голосов
/ 14 июня 2009

Используйте генетические алгоритмы. Они предназначены для быстрого решения проблемы, о которой вы говорите, сокращая сложность времени. Проверьте библиотеку ИИ на вашем языке.

0 голосов
/ 14 июня 2009

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

...