Поскольку пока станция крутится ее положение фиксировано +-7 градусов, то имеем не так уж много переменных, только положения панелей. Эта задача скорее всего решается динамическим (memory-cpu trade off) программированием, учитывая что всего 92 шага.
Кстати, вспомнилась одна из задач на ACM где мое решение было самым быстрым/качественным.
Не вспомню точно, что надо было считать, но всего различных вариантов исходных данных было порядка 100 000, из которых только 10 000 не успевало по времени перебором. Решение состояло в таблице для этих 10 000 вариантов, из которой брался правильный ответ, если исходные данные не брались перебором (ограничение по времени на все решения). Таблицу посчитал все тем же перебором где-то за недельку на трех компах, к которым имел доступ.
Алгоритм более быстрый тогда придумать не получилось, а решить хотелось сильно.
Решал достаточно много на ACM (вроде в двухсотке верхних был) в свое время, считается?
Насчет первокурсника и шахмат — Deep Blue, с его всего 200 милионов позиций в секунду победил человека, а там перебор был не на последнем месте.
Теперь если прикинуть, что будем считать с дискретностью 10 градусов станции относительно солнца.
Примерно получается: 36 * 36 * 36 = 46656 положений станции относительно солнца.
Для каждого положения надо найти оптимальное положение солнечных панелей. Это с той же дискретностью
36 * 27 * 27 * 27 * 27 * 9 * 9 * 9 * 9 = 125524238436 вариантов на каждое положение станции.
Всего надо посчитать энергию для 5856458868470016 расположений станции + панелей. Пусть обсчет положения станции равнозначен расчету позиции в шахматах. Это получается что Deep Blue, который явно уже устарел, посчитал бы все это за 338 дней. Вот и готовы исходные таблицы, по которым с точностью до 10 градусов можно посчитать как вращать панелями.
Привлеките распределенные вычисления, как это делают всякие seti@home и посчитайте с дискретностью 1 градус, если надо или 0.1 градус.
Мне просто не понятно, почему в наш век технологий и сверхмощных вычислительных мощностей нельзя использовать такой достаточно примитивный подход «в лоб», просто при помощи оверкила.
Я, конечно, по большей части теоретик, но что мешает решать подобные задачи оверкиллом?
Посчитать все возможные положения паналей для всех углов станции относительно солнца (с подходящей дискретизацией), выбирать оптимальные на следующие сутки по полученным таблицам? Ну т.е. сперва все посчитать, чтобы потом быстро решать.
Как мне кажется, мощности, чтобы такое посчитать, вполне существуют.
В крайнем случае сделать распределенно, т.к. уже преценденты есть.
Есть же метод поиска подстроки в строке при помощи конечного автомата.
Там, безусловно, тратится время и память на построение непосредственно автомата, если мне не изменяет память надо М*М операций (М — длина искомой строки), после чего поиск происходит линейно.
Т.е. общая сложность, если не считать дополнительные расходы по памяти, получается М*М + N.
Вроде регэкспы работают именно так?
Как я помню, это очень выгодный вариант поиска в двух случаях:
1. М << N.
2. Он легко адаптируется к поиску К подстрок в строке N, почти без дополнительных телодвижений (усложняется лишь этап построения автомата).
Поправьте, если я не прав, могу написать подробнее, если кому-то интересно.
Самому пришлось как-то искать порядка 50ти фиксированных и известных заранее подстрок в большом потоке, и именно это решение для меня оказалось оптимальным, т.к. однажды просчитав автомат я его сохранил для дальнейшего использования.
Я вот чего не понимаю: это просто для себя вещь? Запретить самому себе доступ куда-то?
Сменить ДНС на стандартный либо гугловский дело нескольких секунд.
Не проще ли сверху на монитор поставить мотиватор: «Не смотри порнуху сегодня, не смотри...».
А с баннерами, имхо, AdBlock уже давно успешно справился.
Не вспомню точно, что надо было считать, но всего различных вариантов исходных данных было порядка 100 000, из которых только 10 000 не успевало по времени перебором. Решение состояло в таблице для этих 10 000 вариантов, из которой брался правильный ответ, если исходные данные не брались перебором (ограничение по времени на все решения). Таблицу посчитал все тем же перебором где-то за недельку на трех компах, к которым имел доступ.
Алгоритм более быстрый тогда придумать не получилось, а решить хотелось сильно.
Насчет первокурсника и шахмат — Deep Blue, с его всего 200 милионов позиций в секунду победил человека, а там перебор был не на последнем месте.
Теперь если прикинуть, что будем считать с дискретностью 10 градусов станции относительно солнца.
Примерно получается: 36 * 36 * 36 = 46656 положений станции относительно солнца.
Для каждого положения надо найти оптимальное положение солнечных панелей. Это с той же дискретностью
36 * 27 * 27 * 27 * 27 * 9 * 9 * 9 * 9 = 125524238436 вариантов на каждое положение станции.
Всего надо посчитать энергию для 5856458868470016 расположений станции + панелей. Пусть обсчет положения станции равнозначен расчету позиции в шахматах. Это получается что Deep Blue, который явно уже устарел, посчитал бы все это за 338 дней. Вот и готовы исходные таблицы, по которым с точностью до 10 градусов можно посчитать как вращать панелями.
Привлеките распределенные вычисления, как это делают всякие seti@home и посчитайте с дискретностью 1 градус, если надо или 0.1 градус.
Мне просто не понятно, почему в наш век технологий и сверхмощных вычислительных мощностей нельзя использовать такой достаточно примитивный подход «в лоб», просто при помощи оверкила.
Посчитать все возможные положения паналей для всех углов станции относительно солнца (с подходящей дискретизацией), выбирать оптимальные на следующие сутки по полученным таблицам? Ну т.е. сперва все посчитать, чтобы потом быстро решать.
Как мне кажется, мощности, чтобы такое посчитать, вполне существуют.
В крайнем случае сделать распределенно, т.к. уже преценденты есть.
Хотелось бы прочитать, вопрос интересный.
Там, безусловно, тратится время и память на построение непосредственно автомата, если мне не изменяет память надо М*М операций (М — длина искомой строки), после чего поиск происходит линейно.
Т.е. общая сложность, если не считать дополнительные расходы по памяти, получается М*М + N.
Вроде регэкспы работают именно так?
Как я помню, это очень выгодный вариант поиска в двух случаях:
1. М << N.
2. Он легко адаптируется к поиску К подстрок в строке N, почти без дополнительных телодвижений (усложняется лишь этап построения автомата).
Поправьте, если я не прав, могу написать подробнее, если кому-то интересно.
Самому пришлось как-то искать порядка 50ти фиксированных и известных заранее подстрок в большом потоке, и именно это решение для меня оказалось оптимальным, т.к. однажды просчитав автомат я его сохранил для дальнейшего использования.
Сменить ДНС на стандартный либо гугловский дело нескольких секунд.
Не проще ли сверху на монитор поставить мотиватор: «Не смотри порнуху сегодня, не смотри...».
А с баннерами, имхо, AdBlock уже давно успешно справился.
Но если нет, то очень-очень интересно, хочу две.