Анатолий Белкин (anatbel) wrote,
Анатолий Белкин
anatbel

Categories:

О пользе комбинаторной оптимизации

...
Сначала - длинная преамбула. Немного математики, но не пугайтесь.
В те дни, когда в садах Лицея я безмятежно расцветал в стенах Физтеха писал я, стало быть, диплом, довелось мне исследовать поведение систем, описываемых т.н. функционально-взвешенными графами.
Грубо говоря, есть ориентированный граф, каждая дуга (i,j) которого взвешена некоей функцией fij. Если в момент времени t вершине i отвечает значение ai (t), то к следующему моменту от вершины i к вершине j поступает сигнал bj (t+1) = fij (ai (t)).
Выяснилось, что подобный формализм удобен для описания очень многого, подробности здесь не привожу (да и сам их уже плохо помню - все же сорок лет минуло). При довольно общих предположениях на вид взвешивающих функций (типа непрерывности, выпуклости и т.п.) мне удалось тогда продвинуться довольно далеко, построить некую теорию поведения таких систем, включая динамику, асимптотику, особые точки и пр., из чего впоследствии проистекла вполне приличная глава кандидатского диссера.
Но начал я тогда с простейшего частного случая, когда такие функции суть просто константы, коэффициенты усиления. Если в точке i имеем ai (t), то к следующему моменту в вершине j получаем bj (t+1) = kij x ai (t).
Ага, но тогда в графе могут обнаружиться контуры (замкнутые пути обхода), пройдя вдоль которых, можно в исходной точке получить больше, чем было?
Верно, могут. И поиск контура с максимальным итоговым коэффициентом усиления может быть осуществлен методами комбинаторной оптимизации.
Чем я и занялся, придумав очевидный практический смысл такой модели.

Представим себе, что вершинам графа соответствуют мировые валюты (не только главные), а дуги взвешены переводными коэффициентами. Тогда отыщем контур с итоговым коэффициентом больше 1 - и денежки потекут прямо из воздуха, знай крути барабан!
Итак, некоторое время пыхтел я над задачей поиска контура с максимальным усилением в произвольном орграфе и в итоге смастерил алгоритм (методом ветвей и границ, естественно), который при тогдашних вычислительных мощностях (1978 год, БЭСМ-6) вполне пристойно справлялся с графами на 20-25 вершин (это довольно много, ибо сложность задачи растёт экспоненциально).
Был собою горд изрядно. Задачка красивая, решена успешно.
Опубликовался в академическом журнале ЖВМиМФ (не чета всяким нынешним РИНЦам :)).
Но вот с экспресс-обогащением, конечно, окромя фиги с маслом, ничего не вышло (правда, я и не шибко надеялся).
А почему? По многим причинам.

Ну, во-первых, доступа к игре с переводными коэффициентами и к обмене валюты у советского гражданина Белкина быть не могло. Как и самой валюты.
Но это бы ничего, ибо патриот Белкин за весьма скромное авторское вознаграждение (и даже без оного) запросто выдал бы все секреты, явки и пароли родной советской стране. Почему бы и нет, в самом деле?
Во-вторых было серьёзнее. Переход от одной валюты к другой по тем временам занимал немало времени, интернетов никаких не завезли, так что между t и t+1 явно не секунда. Пока гуляешь вдоль длинного контура, коэффициенты могут измениться, и значительно - грош цена твоим расчётам.
Но было и в-третьих, самое подлое.
За обмен берут некую комиссию, реально это приводит к тому, что получается bj (t+1) = kij x ai (t) + cij, где cij - взимаемая комиссия за конвертацию. Алгоритм несложно переделать и под этот случай, но даже в самом выгодном в итоге контуре заметного "привеса" не получается. Запихав реальные цифры (найденные не без труда), увидел я, что никакого профита вообще нет, одни убытки.
В общем, так и должно быть, не так ли?
Конец преамбулы.

И вот пару дней назад от некоего малознакомого (но все же не вовсе не знакомого) "друга" получаю приглашение посетить некий сайт multicashclub.ru, где из моих ничтожных трех баксов ежедневно будут делать десятки тысяч рублей - знай подставляй ладошки и пересыпай в кубышку.
И в спам верный Яндекс это письмо не выкинул. :)
Как вы уже догадываетесь, ребята именно тем, что я выше многословно описал, и занимаются.
Точнее, якобы занимаются.
Потому что таких оборотов быть, конечно, не может.
Но стало мне любопытно. Конечно, "во-первых" давно отменено, доступ к игре на обмене валюты реален.
"Во-вторых" тоже отпало, ибо ныне все это мгновенно.
Но "в-третьих"-то никуда не делось!
Тщательно предохраняясь, посетил этот сайт - кр-расотища. Видеоинструкции, куча отзывов, крутятся картинки и пр.
И просят-то всего 200 рублей.
Совершенно ясно, что ушлые сайтовладельцы просто дурят нашего брата, но что ж так дешево? На 200 рублей особо не разгуляешься.

И стало мне интересно, и решился я на жертву во имя познания добра и зла.
C отдельной специальной карточки (где и лежало всего 200 рублей с копейками) заплатил им лепту малую - допущен!
Пришла куча красивых писем - авторизация, верификация, тирьямпампация...
Все превозмог, жму заветную кнопку "ЗАПУСТИТЬ ОБМЕН"!
И потекло, блин!
Но не ко мне, а на аккаунт мой в их системе. Это важно.
И вот там уже тышшшшшшши!
Жму опять - опять всё заверте!
После третьего "отжима" набежало аж 9826 рублёв. Нажимаю "ВЫВЕСТИ награбленное СРЕДСТВА" - получаю вежливый ответ: "Минимальная сумма вывода 10000 RUB".
Ладно, запускаю новый цикл обмена, а вот там скрыта засада. Извещают, что, дескать, все публичные линии заняты, но мы вам заведем выделенную линию - и всего-то за 890 рублей.
Вот где собака-то порылась! (с)
Разводка оказалась стандартная: сначала лох платит немножко и уже видит, что вот-вот разбогатеет, но за это надо заплатить (и уже побольше). Не сомневаюсь, что это и не последнее предложение заплатить еще и еще.

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

Кстати, за прошедшие пару дней получил я уже два удивлённых письма от шулеров-"банкометов": что ж вы, мол, зашли, а выделенку не берете, не понимаете своего счастья?

Нет, понимаю. И письма с этим счастьем идут теперь самоходом в спам.
=============


P.S. Нет, 200 рублей не жалко. Было любопытно.
Именно потому, что эту проблему я когда-то изучал (см. Преамбулу).
Tags: Из будущих мемуаров, Мысли вслух, Окружающая жизнь
Subscribe

  • Эллиптический сонет

    ..................... . Был трудный бой. Всё нынче, как спросонку... ..................... . ..................... .А. Твардовский Был трудный…

  • Жить!

    Жить! Врачу-реаниматологу госпиталя "Сокольники" Шамилю Алиеву и его коллегам, которым я многим, очень многим обязан Интенсивная…

  • Еще о пунктах А и Б

    На самом деле, про дорогу из пункта А в пункт Б первоначально я написал совсем другое стихотворение. Оно оказалось вовсе не забавным и для конкурса…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 15 comments

  • Эллиптический сонет

    ..................... . Был трудный бой. Всё нынче, как спросонку... ..................... . ..................... .А. Твардовский Был трудный…

  • Жить!

    Жить! Врачу-реаниматологу госпиталя "Сокольники" Шамилю Алиеву и его коллегам, которым я многим, очень многим обязан Интенсивная…

  • Еще о пунктах А и Б

    На самом деле, про дорогу из пункта А в пункт Б первоначально я написал совсем другое стихотворение. Оно оказалось вовсе не забавным и для конкурса…