Командировщик и Карта / Сокращение: Откажитесь от Канала

Question

Это академический, а не практический вопрос. В проблеме коммивояжера или любой другой, которая включает в себя поиск минимальной оптимизации ... если бы кто-то использовал подход «карта / сокращение», кажется, что было бы полезно иметь какие-то средства для передачи текущего минимального результата всем вычислительные узлы в некотором роде, что позволяет им отказаться от вычислений, которые превышают это.

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

Один из подходов, который сразу приходит на ум, - это если бы редуктор имел средства для обратной связи с картографом. Подумайте, есть ли у нас 100 узлов и миллионы путей, передаваемых им картографом. Если редуктор передает лучший результат мапперу, то это значение может быть включено в качестве аргумента вместе с каждым новым путем (подмножество проблем). При таком подходе гранулярность довольно грубая ... каждый из 100 узлов будет продолжать обрабатывать разделение задачи до завершения и получать новый минимум только при следующем запросе от преобразователя. (Для небольшого количества узлов и огромного количества проблемных разделов / подмножеств работать через эту гранулярность было бы несущественно; также вероятно, что можно применить эвристику к последовательности, в которой возможные маршруты или проблемные подмножества подаются к узлам для получить быструю сходимость к оптимальному и, таким образом, минимизировать количество «потраченных впустую» вычислений, выполняемых узлами).

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

Итак, мои вопросы:

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

Answer 1

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

Таким образом, каждый TSP может быть выражен в виде графика, который выглядит, возможно, так: (взят из немецкой Википедии)

Теперь вы можете запустить алгоритм графа на нем.MapReduce вполне может быть использован для обработки графиков, хотя он имеет много накладных расходов.Вам нужна парадигма, которая называется «Передача сообщений».Это было описано в этой статье здесь: Бумага .И я писал об этом с точки зрения исследования графов, он довольно просто рассказывает, как это работает. Мой блогпост

Это способ, которым вы можете сказать мапперу, каков текущий минимальный результат (возможно, только для самой вершины).

Со всеми знаниями вв глубине души должно быть довольно стандартным думать о ветви и связанном алгоритме (который вы описали), чтобы добраться до цели.Как наличие случайной начальной вершины и ветвление к каждой смежной вершине.Это приводит к тому, что сообщение отправляется в каждую из этих смежных областей со стоимостью, которой оно может быть достигнуто из начальной вершины (Шаг карты).Сама вершина обновляет свою стоимость, только если она ниже, чем текущая сохраненная стоимость (шаг уменьшения).Первоначально это должно быть установлено в бесконечность.Вы делаете это снова и снова, пока не достигнете начальной вершины снова (очевидно, после того, как вы посетили все остальные).Таким образом, вы должны каким-то образом отслеживать лучший на данный момент способ достижения вершины, это также может быть сохранено в самой вершине.И время от времени вы должны связывать это ветвление и обрезать слишком дорогие ветки, это можно сделать на этапе сокращения после прочтения сообщений.По сути, это просто смесь графовых алгоритмов в MapReduce и своего рода кратчайшие пути.Обратите внимание, что это не приведет к оптимальному пути между узлами, это все еще эвристическая вещь.И вы просто парализуете NP-сложную проблему.НО еще немного саморекламы, может быть, вы уже читали ее в сообщении в блоге, на которое я ссылался, существует абстракция к MapReduce, у которой намного меньше накладных расходов при такого рода обработке графиков.Он называется BSP (объемная синхронная параллель) .Это более свободно в общении, и это компьютерная модель.Так что я уверен, что это может быть гораздо лучше реализовано с помощью BSP, чем MapReduce.Вы можете лучше понять эти каналы, о которых вы говорили.

В настоящее время я участвую в проекте Summer of Code, который направлен на решение этих проблем SSSP с BSP.Может быть, вы хотите посетить, если вы заинтересованы .Это могло бы быть частичным решением, оно также очень хорошо описано в моем блоге. SSSP в моем блоге

Я рад услышать некоторые отзывы;)

Answer 2

Кажется, что Storm реализует то, о чем я думал.По сути, это вычислительная топология (подумайте, как каждый вычислительный узел может направлять результаты, основанные на функции ключа / хеширования, для конкретных редукторов).

Это не совсем то, что я описал, но может быть полезно, если быспособ с достаточно низкой задержкой для распространения текущего ограничения (т. е. локальной оптимальной информации), который каждый узел в топологии может обновлять / получать, чтобы знать, какие результаты отбрасывать.