У мене є район міста (давайте подумаємо про це як про графіквулиць), де всі вулиці мають певну вагу та довжину, пов’язані з ними. Що я хочу зробити, це знайти пов’язаний набір вулиць, розташованих поруч з іншими, з деякою максимальною (або близькою до максимальної) загальною вагою W, враховуючи, що мій максимальний підграф може містити до N вулиць.
Мене особливо не цікавить підграфщо охоплюватиме весь графік, а лише невелику групу вулиць, що має максимальну або близьку до максимальної сумісну вагу і де всі вулиці розташовані "поруч" одна з одною, де "поруч" буде визначено як жодна вулиця не більша за метрів від центру скупчення. Отриманий підграф повинен бути пов’язаний.
Хто-небудь знає, чи назва цього алгоритму передбачає його існування?
Також цікавлять будь-які рішення, точні чи наближені.
Щоб наочно показати це, припустимо, що мій графік - це всесегменти вулиць (перехрестя до перехрестя) на зображенні нижче. Отже, окрема вулиця - це не проспект А, це проспект А між 10-м і 11-м і так далі. Вулиця матиме вагу 1 або 0. Припустимо, що набір вулиць з максимальною вагою знаходиться у вибраному полігоні - що я хочу потрібно знайти цей багатокутник.
Відповіді:
0 для відповіді № 1Ось пропозиція. Розгляньте кожну вершину в графіку вузлів як “центр”, як ви це визначили. Для кожного центру C[i], виконати Алгоритм Дейкстри для побудови дерева найкоротшого шляху з C[i] як походження. Припиніть будувати дерево, коли воно буде включати вершину, що перевищує максимальну, дозволену від центру.
Тоді нехай A[i] - множина всіх ребер, що падають на вершини дерева з центром V[i]. Результатом буде набір A[i] з максимальною вагою.
Час виконання одного виконання алгоритму Дейкстри становить O(|E[i]| + |V[i]| log |V[i]|) для iго центру. Набори тут обмежені за розміром на максимальну відстань від центру. Загальна вартість становить sum_(i in 1..|V|) O(|E[i]| + |V[i]| log |V[i]|). У випадку виродження, коли максимально допустима вага дозволяє включати весь графік з кожного центру, вартість буде O(|V| (|E| + |V| log |V|)).
Я можу придумати деякі можливі оптимізації для покращення часу роботи, але хочу перевірити, чи це стосується проблеми, яку ви маєте на увазі.
0 для відповіді № 2
Ось точне формулювання цілочисельного програмуваннядля проблеми припускаючи, що у вас є кінцева кількість загальної кількості вулиць, S, а "центром" скупчення може бути одна з кінцевої кількості вулиць S. Якщо ви дивитесь на центр скупчення в безперервному евклідовому просторі, це відбувається взяти нас у домен Проблема Вебера. Це все ще може бути здійснено, але нам доведеться поглянути на формулювання генерації колонок.
Цільова функція максимізує вагу вибраних вулиць, проіндексованих j. Обмеження (1) вказує, що потрібно обрати рівно один центр. Обмеження (2) визначає, що для будь-якого потенційного центру i, лише N вулицями вибираються сусідами. Обмеження (3) передбачає, що вулиця вибирається як частина деякого мікрорайону, лише якщо обраний відповідний центр. Решта - це двійкові цілочисельні обмеження.
Якщо вулиця, обрана центром, вважається однією з N вулиць, це легко застосувати, вказавши y_{ii} = x_i
Примітка: Якщо вищевказана формулювання правильна або точно фіксує проблему, [MIP] може бути вирішено тривіально, після встановлення N_i було встановлено.
Розглянемо кожен i по черзі. Від N_i виберіть верх N сусідні вулиці у порядку зменшення ваги. Це ваше діюче рішення. Оновіть діюче рішення, якщо під час перегляду файлу буде знайдено краще рішення iс