Например TDA7294

Форум РадиоКот :: Просмотр темы - Заливка матрицы 6х6
Форум РадиоКот
http://radiokot.ru/forum/

Заливка матрицы 6х6
http://radiokot.ru/forum/viewtopic.php?f=60&t=148203
Страница 1 из 1

Автор:  ks0 [ Сб сен 09, 2017 15:43:15 ]
Заголовок сообщения:  Заливка матрицы 6х6

Добрый день, уважаемые Коты!

На нетематическом форуме на днях возник вопрос. Есть квадрат 4х4 (16 комнат). Между комнатами двери (24 штуки), которые могут быть в открытом или закрытом состоянии (с вероятностью 50%). Найти: 1) Вероятность с которой можно попасть из любой (для определенности верхней левой) в любую другую комнату. Задача решалась аналитически и на компьютере. Было ли найдено аналитическое решение мне не известно, а вот компьютер дал вероятность 3,3%.
Затем задачу расширили. Нужно найти полное количество любых состояний дверей, при которых путь во всем комнаты будет открыт. Т.е. всего состояний дверей 2^24 = примерно 16 млн. Полным перебором программа нашла решение за 1,7 сек - 555195 перестановок (те же 3,3%).
Программу оптимизировали как могли и вышли на такую скорость. Но!
Дальше возникла задача найти количество решений для квадрата 5х5. Дверей в данном случае уже 40, т.е. это сложность возрастает в 2^16 раз. Плюс комнат больше в 1,56 раз, т.е. больше проверок в циклах. Примерная сложность решения будет в 100 тыс. раз больше. Ожидаемое время решения на одном ядре не самого свежего компьютера порядка 50 часов.

Теперь смотри в будущее. Каким образом решить эту задачу для квадрата 6х6? Дверей будет 60, это еще в 2^20 раз больше, комнат больше в 1,5. Ожидаемое время решения, мммм... 8 тыс. лет.

Что может предложить в данных условиях общественность?

Автор:  prx [ Вт сен 12, 2017 22:15:46 ]
Заголовок сообщения:  Re: Заливка матрицы 6х6

По моим прикидкам, на каком-нибудь дорогущем Stratix IV перебор всех вариантов займет не меньше нескольких месяцев.

Автор:  petrenko [ Вт сен 12, 2017 23:27:50 ]
Заголовок сообщения:  Re: Заливка матрицы 6х6

Общественность может предложить повторить на п.л.и.с. известный японский проект PROLOG-компьютера и на нём попытаться таки решить задачку не простым перебором.
( Можно сразу доработать проект до "FUZZYPARLOG" что sело упростит и ускорит на пару порядков. )

Остаётся только оценить затраты на оборудование и человеко-часы проектирования и программирования.

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/