Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Здравствуйте! Для консультаций нужен специалист по NP-полным задачам, если точнее, то по судоку. В его задачи будет входить исследование опубликованных научных материалов по судоку, практические рекомендации по составлению, оценке сложности судоку, подбор оптимальных алгоритмов и т. п. Где искать такого спеца? В вузах? На каких кафедрах? Или искать среди прикладников, а не учёных? Заранее спасибо за ответы.
realeugene
Re: Где найти специалиста по теории алгоритмов?
05.07.2021, 12:32
Даже на этом форуме, мне кажется, есть такие спецы. Но вы же не объяснили, что вы им готовы предложить взамен? Вы же хотите нанять исследователя фуллтайм, судя по тексту объявления? Надеюсь, вы догадываетесь, сколько это стоит?
Mihaylo
Re: Где найти специалиста по теории алгоритмов?
01.08.2021, 22:17
Ученый дорого выйдет.) Я практиковался в решении судоку вручную и могу отметить, что сложность решения судоку зависит от кривой ширины перебора. Что такое "кривая ширины перебора"? Судоку решается за n шагов, где n - число незаполненных клеток. Кривая d(i), где шаг i изменяется от 1 до n - минимальная ширина перебора на i-ом шаге. Это инженерный подход, сам придумал. Берем судоку, находим оптимальное решение такое, чтобы на каждом шаге был жадный перебор с минимальной шириной. В итоге получаем кривую, например, 1-1-1-1-1-2-1-1-2-1-1-1-1-1-1-1. Судоку средней сложности. Простейшие судоку имеют значения ширины поиска 1 на каждом шаге. Ширина перебора 1 - это значит, что значение в клетке вычисляется без перебора. Ширина 2 - это перебор двух значений. И так далее. В реальности больше 3-4 минимальная глубина не бывает, хотя все возможно... Может быть вместо кривой есть смысл рассмотреть дерево ширины перебора.
Генерировать судоку можно, взяв разгаданный судоку и удалять в нем цифры, выстраивая кривую ширины перебора или дерево с конца (снизу вверх).