Например TDA7294

 Форум РадиоКот • Просмотр темы - Заливка матрицы 6х6
Форум РадиоКот
Здесь можно немножко помяукать :)



Текущее время: Сб ноя 18, 2017 17:02:58



Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
Не в сети
 Заголовок сообщения: Заливка матрицы 6х6
СообщениеДобавлено: Сб сен 09, 2017 16:43:15 
Прорезались зубы
Аватар пользователя

Зарегистрирован: Чт фев 28, 2013 15:16:10
Сообщений: 209
Рейтинг сообщения: 0
Добрый день, уважаемые Коты!

На нетематическом форуме на днях возник вопрос. Есть квадрат 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 тыс. лет.

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


Вернуться наверх
 Профиль  
 
Не в сети
 Заголовок сообщения: Re: Заливка матрицы 6х6
СообщениеДобавлено: Вт сен 12, 2017 23:15:46 
Родился

Зарегистрирован: Вт авг 08, 2017 00:05:44
Сообщений: 3
Рейтинг сообщения: 0
По моим прикидкам, на каком-нибудь дорогущем Stratix IV перебор всех вариантов займет не меньше нескольких месяцев.


Вернуться наверх
 Профиль  
 
JLCPCB Prototype, $2 за 10 печатных плат (2 слоя, 100×100мм).

Крупнейший производитель печатных плат в Китае, 290,000+ заказчиков, 8,000+ он-лайн заказов в день.

Узнать цену прямо сейчас!

LCSC Parts: Экономия до 50%, большой выбор компонентов в наличии, отправка заказа в день оплаты.

Не в сети
 Заголовок сообщения: Re: Заливка матрицы 6х6
СообщениеДобавлено: Ср сен 13, 2017 00:27:50 
Друг Кота

Карма: 45
Зарегистрирован: Вт фев 21, 2012 14:51:55
Сообщений: 4875
Откуда: Начинающий
Рейтинг сообщения: 0
Общественность может предложить повторить на п.л.и.с. известный японский проект PROLOG-компьютера и на нём попытаться таки решить задачку не простым перебором.
( Можно сразу доработать проект до "FUZZYPARLOG" что sело упростит и ускорит на пару порядков. )

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

_________________
< виртуальная "кнопочка" >--( WWW ) <- Убедительная просьба интересующимся старыми компьютерами типа РК86 - не пишите в теме в барахолке, пишите Ваши вопросы в ( лс ) пожалуйста


Вернуться наверх
 Профиль WWW  
 

Показать сообщения за:  Сортировать по:  Вернуться наверх
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 



Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB
Extended by Karma MOD © 2007—2012 m157y
Extended by Topic Tags MOD © 2012 m157y