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

17

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

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

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

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

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

    
задан Jon 12.05.2009 в 04:16
источник
  • Это помогло бы, если бы вы описали свой однопоточный алгоритм немного больше. –  Bob Cross 12.05.2009 в 04:28
  • на самом деле, это почти то, что вы опубликовали :) Я считаю, что это работает очень хорошо и очень легко кодировать ... –  Jon 12.05.2009 в 04:40
  • Хорошо, см. мою дополнительную заметку ниже с простым обоснованием для многопоточности. –  Bob Cross 12.05.2009 в 04:44
  • Почему бы просто не разбить каждую строку и / или столбцы на собственный поток? –  Aaron 12.05.2009 в 04:47
  • @Aaron, это намного больше, чем строки и столбцы, вам нужно обработать мини-сетки 3x3 и перекрестный разговор между всеми этими элементами в действительно эффективном решении. –  paxdiablo 12.05.2009 в 04:54
Показать остальные комментарии

13 ответов

17

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

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

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

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

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

    
ответ дан Tom Leys 12.05.2009 в 04:47
источник
  • +1 хорошее предложение –  ninesided 12.05.2009 в 04:52
  • много отличных советов от всех, это выглядит как наилучшим образом подходящим для моей конкретной ситуации. Еще раз спасибо всем :) –  Jon 12.05.2009 в 05:22
  • Методы параллелизма Java имеют различные исполнители, которые допускают ограниченный пул потоков. Изучите их - это упростит вашу синхронизацию. –  Thorbjørn Ravn Andersen 12.05.2009 в 08:32
  • На самом деле нереста n + 1 потоков очень быстро исчерпывает все ваши системные ресурсы. Вместо этого вам нужно использовать пул потоков фиксированного размера - и даже это столкнется с другими проблемами с большим деревом игр. –  Nick Johnson 12.05.2009 в 10:22
  • Исполнители java также сделают тривиальным создание ограниченного пула потоков. –  Bill Michell 12.05.2009 в 10:29
9

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

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

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

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

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

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

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

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

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

Update:

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

  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
ответ дан paxdiablo 12.05.2009 в 04:32
источник
  • +1 место, хотя в зависимости от количества правил или их эффективности на разных этапах головоломки, возможно, стоит посмотреть на правила группировки, а не на поток для каждого правила. –  ninesided 12.05.2009 в 04:49
  • Если домашнее задание состоит в том, чтобы сделать его многопоточным, вы можете просто разделить правила на два набора и передать их двум потокам. Но вы также можете пройти весь путь и выделить одно правило для потока. Кажется, я помню, что мое решение работало только с 12 правилами (у меня было одно правило для всех столбцов, а не для каждого столбца и т. Д.), Которые должны быть довольно легкими для потоковой передачи. –  paxdiablo 12.05.2009 в 04:57
  • Pax - ваш алгоритм, который вы набросал, вероятно, будет работать только в том случае, если есть одно уникальное решение. Когда есть два возможных варианта, нет никаких «очевидных» шагов. Именно так, что разделение на два потока, чтобы попробовать оба выбора, становится целесообразным. Поскольку все эти ветви и петли кода требуют времени, они также могут разбивать их на несколько ядер - большая причина использовать параллелизм. Гораздо эффективнее, чем если ваша программа была связана с вводом / выводом (память, hdd) –  Tom Leys 12.05.2009 в 04:58
  • Btw, имея два потока, которые оценивают одно и то же состояние платы (то есть правила разделения на две части), является полной потерей времени, вы хотите, чтобы потоки продолжались дольше, чем это - несколько состояний. –  Tom Leys 12.05.2009 в 04:59
  • Том, это мое утверждение, что у судоку есть только одно решение, так как это логическая головоломка (другие могут не согласиться, но они ошибаются :-). –  paxdiablo 12.05.2009 в 05:04
Показать остальные комментарии
5

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

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

ответ дан Tal Pressman 12.05.2009 в 04:28
источник
4

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

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

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

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

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

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

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

    
ответ дан Bob Cross 12.05.2009 в 04:37
источник
  • Если ваши 9 рабочих потоков не могут порождать новые потоки самостоятельно, есть хороший шанс, что у большинства из них сразу закончится работа, и вы оставите только 1 или 2 потока. Вам нужно повторить разветвление на нескольких уровнях, чтобы получить решение, которое будет масштабироваться для многих процессоров. –  Tom Leys 12.05.2009 в 04:54
  • На самом деле, для действительно патологических случаев, вы не обязательно быстро найдете тупики. Тем не менее, это правда, что сложный многопоточный решатель должен был бы поддерживать пул потоков, снабженный частичными решениями для работы. Однако это не моя домашняя работа .... ;-) –  Bob Cross 12.05.2009 в 05:20
  • Например, см. сайт Гордона Ройла, где он создает минимальные проблемы: people.csse.uwa.edu.au/gordon/sudokumin.php Очень противно даже при многопоточности. –  Bob Cross 12.05.2009 в 05:23
2

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

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

ответ дан DrStalker 12.05.2009 в 04:25
источник
2

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

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

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

    
ответ дан ninesided 12.05.2009 в 04:23
источник
  • Я думаю, что головоломка Sudoku может иметь несколько решений. Вы можете добраться до точки, где у вас есть 4 ячейки, которые могут иметь 1 из 2 чисел, либо номер будет работать до тех пор, пока другие ячейки будут согласованы. Я нашел это при написании Excel solver / hinter. –  geofftnz 12.05.2009 в 04:27
  • , если это так, то это не настоящая судоку, иначе многие передовые методы, которые полагаются на этот принцип, бесполезны –  ninesided 12.05.2009 в 04:30
  • Я думаю, что вы правы на «истинной судоку». –  geofftnz 12.05.2009 в 04:32
  • Судоку должен иметь только одно решение. Это данность. –  paxdiablo 12.05.2009 в 04:33
  • Если клиент дает многопользовательские головоломки судоку, вы можете либо настаивать на том, что они не являются правильными проблемами судоку, и спрашивают, что данные, предоставляемые вашему приложению, изменены, либо вы можете написать приложение, которое решает эти «неправильные» судоку головоломки, как хочет клиент. Угадайте, какой подход, скорее всего, поможет вам в реальном мире? :-) –  DrStalker 12.05.2009 в 04:39
Показать остальные комментарии
1

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

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

    
ответ дан Justin Niessner 12.05.2009 в 04:24
источник
1

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

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

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

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

ответ дан Precipitous 12.05.2009 в 04:33
источник
  • Suduku имеет очень маленькое пространство для поиска, что мало чем помогает в итеративном углублении, которое вы описываете. Возможно, на мнимой доске 15 * 15 или 25 * 25. –  Tom Leys 12.05.2009 в 05:28
1

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

ответ дан Ali Hmer 12.05.2009 в 04:45
источник
0

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

    
ответ дан Marc Charbonneau 12.05.2009 в 04:25
источник
0

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

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

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

    
ответ дан luca 28.10.2009 в 23:21
источник
0

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

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

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

    
ответ дан Kevin Coulombe 10.08.2010 в 00:33
источник
0

Вот моя копейка. Надеюсь, что это поможет.

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

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

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

    
ответ дан d2alphame 03.05.2014 в 02:31
источник