Многопоточный алгоритм решения судоку?

Ответ 1

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

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

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

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

Каждая процедура, которая вызывает несколько потоков для выполнения работы, должна вызывать n-1 потоков, когда есть n частей работы, выполнить n-й кусок работы и затем ждать с объектом syncronisation, пока все остальные потоки не будут завершены. Затем вы оцениваете их результаты - у вас есть n системных состояний, возвратите одно с наименьшим количеством ходов.

Ответ 2

Многопоточность полезна в любой ситуации, когда одному потоку приходится ждать ресурса, и вы можете запустить еще один поток. Это включает поток, ожидающий запроса ввода-вывода или доступа к базе данных, в то время как другой поток продолжает работать с ЦП.

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

Я не вижу причин, по которым многопоточный решатель Sudoku будет более эффективным, чем однопоточный, просто потому, что не ждет ресурсов. Все будет сделано в памяти.

Но я помню некоторые домашние задания, которые я делал в Uni, и это было так же бесполезно (код Fortran, чтобы увидеть, насколько глубок туннель, когда вы откопали до 30 градусов на одну милю, а затем 15 градусов за еще одну милю - да, я 'm довольно старый:-). Дело в том, чтобы показать, что вы можете это сделать, а не что это полезно.

В соответствии с алгоритмом.

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

Были одинаковые правила для всех строк, всех столбцов, всех мини-сеток 3x3. Были также правила, которые проверяли пересечение строк/столбцов (например, если данный квадрат мог содержать только 3 или 4 из-за строки и 4 или 7 из-за столбца, то это было 4). Были более сложные правила, которые я не буду здесь описывать, но они в основном так же, как вы его решаете вручную.

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

Что бы я предложил, это распределить каждое правило в поток и поделиться им сетью. Каждый поток выполнил бы это правило и только это правило.

Update:

Джон, на основе вашего редактирования:

[edit] Я забыл упомянуть, что количество потоков, которые будут использоваться, указывается в качестве аргумента для программы, так как я могу сказать, что это никак не связано с состоянием головоломки...

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

Похоже, ваш учитель не хочет, чтобы вы делились на основе правил, а вместо этого на fork-points (где могли применяться несколько правил).

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

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

Я бы предположил, что у вас есть рабочая очередь и N потоков. Рабочая очередь изначально пуста, когда ваш основной поток запускает все рабочие потоки. Затем основной поток помещает начальное состояние головоломки в рабочую очередь.

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

Итак, скажем, есть только одно решение (правда Sudoku:-). Первый рабочий поток удалит решение, не найдя никаких вилок, и это будет точно так же, как в вашей текущей ситуации.

Но с двумя возможностями при перемещении 27 (скажем, 3 или 4 могут попасть в верхнюю левую ячейку), ваш поток создаст другую плату с первой возможностью (поместите 3 в эту ячейку) и поместите ее в рабочую очередь. Затем он поместит 4 в свою собственную копию и продолжит.

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

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

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

Когда все потоки простаивают, а рабочая очередь пуста, главная или будет или не будет иметь решение. Он также будет иметь количество решений.

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

Ответ 3

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

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

Ответ 4

Вот жадный алгоритм однопоточной утилиты грубой силы:

• Выберите следующую пустую ячейку. Если нет более пустых ячеек, победа!
• Возможное значение ячейки = 1
• Проверьте недопустимое частичное решение (дубликаты в блоке строки, столбца или 3x3).
• Если частичное решение недействительно, увеличьте значение ячейки и вернитесь к шагу 3. В противном случае перейдите к шагу 1.

Если вы посмотрите на приведенный выше план, комбинация шагов 2 и 3 является очевидным кандидатом на многопоточность. Более амбициозные решения включают создание рекурсивного исследования, которое порождает задачи, которые отправляются в пул потоков.

EDIT, чтобы ответить на этот вопрос: "Я не понимаю, как вы можете найти разные решения одной и той же проблемы одновременно, не поддерживая несколько копий головоломки".

Вы не можете. Это все. Однако конкретный пример из 9 нитей может сделать преимущества более понятными:

• Начните с примера проблемы.
• Найдите первую пустую ячейку.
• Создайте 9 потоков, где каждый поток имеет свою собственную копию проблемы со своим собственным индексом в качестве значения кандидата в пустой ячейке.
• В каждом потоке запускайте свой оригинальный однопоточный алгоритм в этой локальной локально модифицированной копии проблемы.
• Если один из потоков находит ответ, остановите все остальные потоки.

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

Ответ 5

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

Для первого, либо подход на основе правил Pax, или Tom Leys возьмет многопоточность существующего алгоритма обратного отслеживания может быть, путь.

Если последний, вы можете реализовать какой-то алгоритм ветвления, который запускает новый поток (с его собственной копией головоломки) для каждого возможного движения на каждом этапе головоломки.

Ответ 6

Нужно ли использовать многопоточность или просто использовать многопоточность, чтобы вы могли узнать о назначении?

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

Ответ 7

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

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

Ответ 8

Некоторые общие моменты: я не запускаю процессы параллельно, если 1) легко разделить проблему. 2) Я знаю, что я получу преимущество для этого. Я не буду бить еще одно узкое место. Я полностью избегаю совместного использования изменяемых значений между потоками - или минимизации. Некоторые люди достаточно умны, чтобы безопасно работать с мьютексами. Я не.

Вам нужно найти точки в своем алгоритме, которые создают естественные ветки или большие единицы работы. Как только вы определили устройство для работы, вы бросаете его в очередь для потока, который нужно забрать. В качестве тривиального примера. 10 баз данных для обновления. Запустите обновление async на всех 10 серверах. Подождите, пока все закончится. Я могу легко избежать совместного использования состояний между потоками/процессами и легко агрегировать результаты.

То, что приходит на ум для судоку, заключается в том, что эффективное решение судуко должно сочетать 2-3 (или более) стратегии, которые никогда не пройдут мимо определенной глубины. Когда я делаю Sudoku, очевидно, что в любой момент различные алгоритмы обеспечивают решение с наименьшей работой. Вы могли бы просто запустить несколько стратегий, позволить им исследовать на ограниченной глубине, ждать отчета. Прополощите, повторите. Это позволяет избежать "грубой силы" решения. Каждый алгоритм имеет собственное пространство данных, но вы объединяете ответы.

У Sciam.com была статья об этом год или два назад - похоже, что это не публично.

Ответ 9

Вы сказали, что использовали обратное отслеживание для решения проблемы. Что вы можете сделать, так это разбить пространство поиска на два и обработать каждое пространство в потоке, тогда каждый поток будет делать то же самое до достижения последнего node. Я сделал это решение, которое можно найти www2.cs.uregina.ca/~hmer200a, но с использованием одного потока, но механизм разделения пространства поиска существует с помощью ветвления и привязки.

Ответ 10

TL; DR

Да, решатель судоку, основанный на возврате, может, в зависимости от головоломки, значительно выиграть от распараллеливания! Пространство поиска головоломки может быть смоделировано как древовидная структура данных, и при обратном отслеживании выполняется поиск в глубину (DFS) этого дерева, который по своей природе не распараллеливается. Однако, объединяя DFS с противоположной формой обхода дерева, поиск в ширину (BFS), параллелизм можно разблокировать. Это связано с тем, что BFS позволяет одновременно обнаруживать несколько независимых поддеревьев, которые затем можно искать параллельно.

Поскольку BFS разблокирует параллелизм, его использование гарантирует использование глобальной поточно-ориентированной очереди, в которую/из которой обнаруженные поддеревья могут выталкивать/извлекать все потоки, что влечет за собой значительные издержки производительности по сравнению с DFS. Следовательно, распараллеливание такого решателя требует точной настройки количества BFS, выполняемого таким образом, чтобы выполнялось ровно столько, чтобы обеспечить достаточное распараллеливание обхода дерева, но не слишком много, чтобы накладные расходы на передачу потоков (подталкивание/выталкивание поддеревьев очереди) перевешивает ускорение, которое обеспечивает распараллеливание.

Некоторое время назад я распараллелил решатель судоку на основе обратного отслеживания и реализовал 4 различных варианта параллельного решателя наряду с последовательным (однопоточным) решателем. Все параллельные варианты по-разному и в разной степени комбинировали DFS и BFS, и самый быстрый вариант был в среднем в три раза быстрее, чем однопоточный решатель (см. график внизу).

Кроме того, , чтобы ответить на ваш вопрос, в моей реализации каждый поток получает копию начальной головоломки (один раз, когда поток порождается), так что требуемая память немного выше, чем последовательный решатель - что не редкость, когда распараллеливание чего-либо. Но это единственная "неэффективность", как вы выразились: как уже упоминалось выше, если количество BFS соответствующим образом точно настроено, достижимое ускорение за счет распараллеливания значительно перевешивает параллельные издержки при обмене потоками, а также более высокий объем занимаемой памяти. Кроме того, в то время как мои решатели предполагали уникальные решения, расширять их, чтобы обрабатывать неправильные головоломки и находить все их решения, было бы просто и не значительно, если вообще уменьшило бы ускорение, из-за характера конструкции решателя. См. полный ответ ниже для получения более подробной информации.

ПОЛНЫЙ ОТВЕТ

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

Как вы, вероятно, уже знаете, пространство поиска Судоку можно смоделировать как древовидную структуру данных: первый уровень из трех представляет первую пустую ячейку, второй уровень - вторую пустую ячейку и т.д. На каждом уровне узлы представляют потенциальные значения этой ячейки, учитывая значения их предковых узлов. Таким образом, поиск в этом пространстве может быть распараллелен путем одновременного поиска независимых поддеревьев. Однопоточный решатель обратного отслеживания должен проходить по всему дереву сам по себе, одно поддерево за другим, но параллельный решатель может пусть каждый поток ищет отдельное поддерево параллельно.

Есть несколько способов реализовать это, но все они основаны на принципе объединения поиска по глубине (DFS) с поиском по ширине (BFS), которые являются двумя (противоположными) формами обхода дерева. Однопоточный решатель обратного отслеживания выполняет DFS только весь поиск, который по своей природе не распараллеливается. Однако, добавив в смесь BFS, параллелизм может быть разблокирован. Это связано с тем, что BFS обходит дерево по уровням (в отличие от ветвления с DFS) и, таким образом, находит все возможные узлы на данном уровне, прежде чем перейти на следующий более низкий уровень, тогда как DFS берет первый возможный узел и полностью ищет свое поддерево, прежде чем перейти к следующему возможному узлу. В результате BFS позволяет сразу обнаруживать несколько независимых поддеревьев, которые затем можно искать по отдельным потокам; DFS ничего не знает о дополнительных независимых поддеревьях с самого начала, потому что она занята поиском первого, которое находит в глубине.

Как обычно бывает с многопоточностью, распараллеливание вашего кода сложно, и первоначальные попытки часто снижают производительность, если вы точно не знаете, что делаете. В этом случае важно понимать, что BFS намного медленнее, чем DFS, поэтому главная задача заключается в настройке количества выполняемых вами DFS и BFS таким образом, чтобы выполнялось достаточно BFS, чтобы разблокировать возможность обнаружения нескольких файлов. поддеревья одновременно, но также минимизируют его, чтобы его медлительность не перевешивала эту способность. Обратите внимание, что BFS по своей природе не медленнее, чем DFS, просто потокам необходим доступ к обнаруженным поддеревьям, чтобы они могли искать их. Таким образом, для BFS требуется глобальная поточно-ориентированная структура данных (например, очередь), в которую/из которой могут быть выдвинуты/извлечены поддеревья отдельными потоками, и это влечет за собой значительные издержки по сравнению с DFS, которая не требует какой-либо связи между потоками. Следовательно, распараллеливание такого решателя - это процесс тонкой настройки, и каждый хочет провести достаточно BFS, чтобы обеспечить все потоки достаточным количеством поддеревьев для поиска (то есть достичь хорошего распределения нагрузки между всеми потоками), одновременно минимизируя обмен данными между потоками ( подталкивание/вставка поддеревьев в/из очереди).

Некоторое время назад я распараллелил решатель судоку на основе обратного отслеживания, реализовал 4 различных варианта параллельного решателя и сравнил их с последовательным (однопоточным) решателем, который я также реализовал. Все они были реализованы в C++. Лучший (самый быстрый) алгоритм параллельного варианта был следующим:

• Начните с DFS дерева головоломки, но делайте это только до определенного уровня или глубины поиска
• На глубине поиска выполните BFS и поместите все поддеревья, обнаруженные на этом уровне, в глобальную очередь
• Затем потоки выталкивают эти поддеревья из очереди и выполняют над ними DFS вплоть до последнего уровня (последней пустой ячейки).

Следующий рисунок (взятый из моего отчета того времени) иллюстрирует эти шаги: Различные цветные треangularьники представляют разные нити и поддеревья, которые они пересекают. Зеленые узлы представляют допустимые значения ячеек на этом уровне. Обратите внимание на одну BFS, выполненную на глубине поиска; Поддеревья, обнаруженные на этом уровне (желтый, фиолетовый и красный), помещаются в глобальную очередь, которая затем параллельно проходит независимо независимо до последнего уровня (последней пустой ячейки) дерева.

Как видите, эта реализация выполняет BFS только одного уровня (на глубине поиска). Эта глубина поиска регулируется, и ее оптимизация представляет собой вышеупомянутый процесс тонкой настройки. Чем глубже глубина поиска, тем больше BFS выполняется, поскольку ширина дерева (# узлов на заданном уровне) естественным образом увеличивается по мере продвижения вниз. Интересно, что оптимальная глубина поиска, как правило, находится на довольно мелком уровне (то есть не очень глубоком уровне в дереве); Это показывает, что проведение даже небольшого количества BFS уже достаточно для генерации достаточного количества поддеревьев и обеспечения хорошего баланса нагрузки между всеми потоками.

Кроме того, благодаря глобальной очереди можно выбрать произвольное количество потоков. Как правило, рекомендуется установить число потоков равным количеству аппаратных потоков (т.е. # Логических ядер); Выбор более обычно не увеличивает производительность. Кроме того, также возможно распараллелить начальную DFS, выполняемую в начале, выполняя BFS первого уровня дерева (первая пустая ячейка): дочерние деревья, обнаруженные на уровне 1, затем проходят параллельно, каждый поток останавливается на заданная глубина поиска. Это то, что сделано на рисунке выше. Однако в этом нет особой необходимости, поскольку оптимальная глубина поиска, как уже упоминалось выше, обычно невелика, поэтому DFS вплоть до глубины поиска все еще очень быстр, даже если он однопоточный.

Я тщательно проверил все решатели на 14 различных головоломках Судоку (в частности, на выбранном наборе головоломок, специально разработанных, чтобы быть трудным для решателя с возвратом), и на рисунке ниже показано среднее время каждого решателя, затрачиваемое на решение всех головоломок, для различного количества потоков (мой Ноутбук имеет четыре аппаратных потока). Параллельный вариант 2 не показан, потому что он фактически достиг значительно худшей производительности, чем последовательный решатель. В параллельном варианте 1 потоки # автоматически определялись во время выполнения и зависели от задачи (в частности, коэффициента ветвления первого уровня); Следовательно, синяя линия представляет его среднее общее время решения независимо от количества потоков.

Все варианты параллельного решателя комбинируют DFS и BFS по-разному и в разной степени. При использовании 4 потоков самый быстрый параллельный решатель (вариант 4) был в среднем в три раза быстрее однопоточного решателя!

Ответ 11

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

Ответ 12

У меня есть идея, что здесь очень весело.. сделайте это с помощью модели Actor! Я бы сказал, используя erlang.. Как? Вы начинаете с оригинальной доски и...

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

Ясно, что каждый выживший актер является решением задачи =)

Ответ 13

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

Во-первых, простые накладные расходы при запуске потока заняли 0,5 миллисекунды, тогда как для всего разрешения потребовалось от 1 до 3 миллисекунд (я использовал Java, другие языки или среды мог давать разные результаты).

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

Ответ 14

Вот мой собственный пенни. Надеюсь, что это поможет.

Помните, что межпроцессорные/межпоточные коммуникации дороги. Не используйте многопоточность, если у вас есть. Если в других потоках не так много работы/вычислений, вы можете просто продолжить один поток.

Попробуйте как можно больше избежать обмена данными между потоками. Используйте их только при необходимости

Используйте SIMD-расширения, где это возможно. С помощью Vector Extensions вы можете выполнять вычисления по нескольким данным одним махом. Это может помочь вам.