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