Блог пользователя RodionGork

Бинарный поиск с "золотым сечением"
Автор RodionGork, 13 лет назад, По-русски

Провёл опрос среди коллег и учеников. Посмеялся.

Часто, рассказывая о бинарном поиске (дихотомии) авторы, преподаватели, учителя, менторы и тьюторы упоминают что существует вариант при котором отрезок поиска делится не пополам а в отношении "золотого сечения". Правда не припомню, чтобы они объясняли в каких случаях и зачем это нужно.

А вы знаете?

Можете просто ответить - знаете или нет. Объяснение я хотел под катом привести, но он как-то не очень работает.

Однако если вы не знаете объяснения - попробуйте догадаться. Пожалуй стоит намекнуть что область применения - поиск не по массиву значений (вспомните когда ещё нужен двоичный поиск).

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
А объяснение можно посмотреть здесь, в предыдущей правке.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В данной правке же всё равно троичный поиск рассматривается, а тема поднята про бинарный поиск. В нём золотое сечение как-то может пригодиться?
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Поправляю, то, что вы описали, редко называют бинарным поиском. Больше всего он похож на тернарный поиск, но все-таки это отдельный алгоритм. Кстати, вот и ссылка на википедию.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      М-м-м... Справедливо... Названия "тернарный" в отношении поисков минимума первый раз слышу. Если продолжить вашу мысль, получается что и "бинарный" поиск минимума является "тернарным" хотя и с сильно вырожденной средней частью...

      Хотя тернарный поиск при делении на 3 очевидно не даёт выигрыша в количестве вычислений функции.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Бин.поиск применяется для нахождения чего-либо на (строго) монотонной функции.

        Тернарный поиск применяется для нахождение экстремума в унимодальной функции (имеющей ровно 1 максимум/минимум).
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Продифференцировав получим монотонную функцию:)
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А если у нас не функция, а просто массив чисел? Как вы его продифференцируете?
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              Очень просто - будем брать разность между соседними элементами.
              → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится
            Массив-то можно “продифференцировать”, получив массив конечных разностей.

            Но часто бывает так, что функция задана в виде, не предполагающем дифференцирования, или просто продифференцировать сложнее, чем сделать тернарный поиск.
            → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Бинарный поиск, в котором сильно вырожденная средняя часть (из одного элемента) по сути бинарным поиском не является.

        Бинарный поиск - это поиск, в котором интервал делится на две части и область поиска сокращается до одного из двух интервалов деления. То есть в цикле должна быть одна инструкция if с переходом к одному из двух возможных случаев. 

        Если вы в алгоритме "бинарного поиска" отдельно анализируйте медианный элемент, интервал до медианного элемента, интервал после медианного элемента, то есть используется минимум две инструкции if, то это неправильная реализация бинарного поиска.

        Алгоритм поиска экстремума функции называется тернарным поиском, т.к. отрезок делится на три части и рассматривается три случая.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Да вроде все правильно!
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Знаю. Более того, знаю, что для массива значений его применять тоже можно (хотя это редко дает выигрыш).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    Для массива? Как применять? Теперь ваша очередь вести просветработу ;-)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да также, только с округлением. Просто стоит обратить внимание, что нам необязательно искать на действительной оси. Можно и на целых числах искать (если помнить про одинаковые числа).
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Знаю. Более того, был удивлен, когда узнал, что у нас в ВУЗе некоторым он попадается в качестве задания на лабораторную работу.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Одна из фишек нормально написанного "золотого сечения" это то, что на каждом шаге выполняется только одно вычисление функции, вместо двух (как в тернарном поиске (хотя у нас в ВУЗе препод его называл двоичным)). И сходится он чуток быстрее.

Но у него есть недостаток - у него может слишком быстро расти погрешность из-за того, что в вычислениях используется вычисление квадратного корня.

В общем делая лабы по этим алгоритмам я для себя решил, что "зотолое сечение" нафиг не сдалось.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "И сходится он чуток быстрее."
    Вроде ровно в два раза быстрее..)
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      Нет, не ровно в два. Каждый новый отрезок в ~1.618 раз короче предыдущего (против 1.5 у тернарного), так что чуть быстрее, чем в два. Примерно, в 2.16 2.37, если я ничего не перепутал таки перепутал.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Откуда взялось число 2.16? :)

        Почему не 1.1868...?

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я сейчас не очень соображаю. Я рассуждал так. Отрезок сходится в 1,618/1,5=1,08 раз быстрее. При этом мы вычисляем одну точку, а не две, поэтому еще в два раза быстрее. Всего 2.16. Я не прав?
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +13 Проголосовать: не нравится

            Мне почему-то кажется, что сходится он в раза быстрее.

            Соответственно, в  ≈ 2.3736 раза меньше вычислений.



            → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Это какая погрешность при этом растёт? Погрешность выбора новой точки по X? Но она ж не влияет ни на что. Нам главное точку выбрать - а то что он будет немного в стороне от идеала - не важно...

    И обратим внимание что мы точку находим без вычисления квадратного корня вообще! Просто как отношение!
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -17 Проголосовать: не нравится
    А по поводу того что "золотое сечение" на фиг не сдалось - согласен на 80% т.к. гораздо лучше применить поиск минимума с помощью приближения функции параболой... Хотя и при нём можно точки золотым сечением выбрать. ;-)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Помнится мне, что там "рекомендовалось" делать шаги длинной = возврастающие степени двойки. Так же там можно чуток запариться с выпуклостью точек, да и вывод формулы для вершины параболы по 3-ем точкам вообще не сахар на олимпиаде. В общем я бы придерживался тернарного поиска и не парился.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну как сказать... Несложно прикинуть что для точности 1e-6 тернарный поиск сойдётся примерно за 20 итераций а параболический за 3-5...

        Для олимпиады имело бы смысл, ха-ха, составить задачу так чтобы медленные поиски вылетали по TLE...
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          В этом году, на региональном этапе РОИ, была задача, в которой обычный тернарный поиск не проходил по времени))
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          А можно поподробнее про параболический поиск? Единственное что я нашел это статья на википедии, в которой только словесное описание того что он делает. И в ней написано что этот поиск не всегда сходится. Подозреваю, имелось ввиду что-то другое.
          → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

А кат здесь служит только для обрезки блогпоста, чтобы в блоге он выглядел короче.

А спойлеров здесь пока ещё нет. Кстати, кто хочет их - согласитесь с идеей пожалуйста.

UPD. Интересно, что в этом сообщении не понравилось.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Знаю. Я знаю что золотое сечение в тернарном поиске преподают в обычных курсах программирования в разных ВУЗах, не обязательно в профильных.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Знаю.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У нас даже на методах оптимизации это рассказывали... Кстати это таки тернарный поиск, а не бинарный, и основан он на общем методе деления отрезка на три части (поэтому то и тернарный), причём есть ещё куча разных способов деления отрезка на три части (золотое сечение, равные части, Фибоначчи и пр.).
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
where i can solve problems in ternary search?!
→ Ответить