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

17

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

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

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

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

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

    
задан Jon 12.05.2009 в 04:16
источник

13 ответов

17

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

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

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

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

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

    
ответ дан Tom Leys 12.05.2009 в 04:47
источник
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
источник
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
источник
2

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

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

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

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

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

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

    
ответ дан ninesided 12.05.2009 в 04:23
источник
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
источник
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
источник