Сообщение Re[5]: Время черепахи от 02.07.2015 13:45
Изменено 02.07.2015 14:36 Somescout
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Somescout, Вы писали:
S>>Условие что при d>0, N<=200 намекает на полный перебор.
К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
Если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.
К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.
Возможно.
К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.
---------
Насчёт поиска и сортировки... есть идея, но описывать полный алгоритм текстом мучение, поэтому образно:
1) Вычтем из всех моментов времени время подхода черепахи:
t'[i] = t[i]-(x[i]/Vmax)
2) Очевидно, что для каждого t'[i], максимальное количество элементов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
К>Здравствуйте, Somescout, Вы писали:
S>>Условие что при d>0, N<=200 намекает на полный перебор.
К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
Если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.
К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.
Возможно.
К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.
---------
Насчёт поиска и сортировки... есть идея, но описывать полный алгоритм текстом мучение, поэтому образно:
1) Вычтем из всех моментов времени время подхода черепахи:
t'[i] = t[i]-(x[i]/Vmax)
2) Очевидно, что для каждого t'[i], максимальное количество элементов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Somescout, Вы писали:
S>>Условие что при d>0, N<=200 намекает на полный перебор.
К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
Если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.
К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.
Возможно.
К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.
---------
Насчёт поиска и сортировки... есть идея, но описывать полный алгоритм текстом мучение, поэтому образно:
1) Вычтем из всех моментов времени время подхода черепахи:
t'[i] = t[i]-(x[i]/Vmax)
2) Очевидно, что для каждого t'[i], максимальное количество элементов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
К>Здравствуйте, Somescout, Вы писали:
S>>Условие что при d>0, N<=200 намекает на полный перебор.
К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
Если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.
К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.
Возможно.
К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.
---------
Насчёт поиска и сортировки... есть идея, но описывать полный алгоритм текстом мучение, поэтому образно:
1) Вычтем из всех моментов времени время подхода черепахи:
t'[i] = t[i]-(x[i]/Vmax)
2) Очевидно, что для каждого t'[i], максимальное количество элементов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.