Мне было интересно, может ли кто-нибудь помочь мне понять эту проблему. Я подготовил небольшую диаграмму, потому что это намного проще объяснить визуально.
альтернативный текст http://img179.imageshack.us/img179/4315/pon.jpg
Проблема, которую я пытаюсь решить:
1. Построение графика зависимости
Учитывая связность графа и метрики, которая определяет, насколько хорошо узел зависит от другого, упорядочите зависимости. Например, я мог бы добавить несколько правил, гласящих, что
- узел 3 зависит от узла 4
- узел 2 зависит от узла 3
- узел 3 зависит от узла 5
Но поскольку последнее правило не является «ценным» (опять же на основе той же метрики), я не буду добавлять правило в свою систему.
2. Оформить заявку на заказ
После того, как я построил граф зависимостей, выполните список в порядке, который максимизирует окончательное соединение. Я не уверен, действительно ли это проблема, но у меня почему-то возникает ощущение, что может существовать более одного заказа, и в этом случае требуется выбрать лучший заказ.
Прежде всего, мне интересно, правильно ли я сконструировал проблему и должен ли я знать о каких-либо угловых случаях. Во-вторых, есть ли тесно связанный алгоритм, на который я могу посмотреть? В настоящее время я думаю о чем-то вроде Набор дуги обратной связи или Секретарская проблема , но сейчас я немного запутался. Есть предложения?
PS: Я сам немного озадачен этой проблемой, поэтому, пожалуйста, не обращайте на меня внимания. Если понадобятся какие-либо разъяснения, я постараюсь обновить вопрос.