Что мы видим? Трёх солдат, вероятно, Первой мировой войны, очевидно, уже вкусивших «прелестей» той ужасной эпохи. Они стоят обнявшись, на них одна форма, в их взглядах — общая мечта о победе. Но всего-то двадцать лет спустя один из них, заразив своей извращённой философией миллионы соотечественников, поставит под ружьё половину человечества, останется в памяти потомков самым страшным чудовищем XX века. Второй из троицы тоже прославится идеями, но вопреки бывшему товарищу, как самый яркий борец за мир своего времени — и, возможно, целого столетия.
Вопрос, который не даёт покоя многим, видевшим этот снимок, заключается в том, правда ли изображённые на нём люди те, на кого они похожи.
Касательно одного сомнений нет, мы знаем его личность наверняка. Собственно, благодаря ему снимок (есть более качественные, но обрезанные понизу версии) и стал знаменит. Крайний справа — тяжёлый взгляд, усы, фанатичная выправка — не кто иной как Адольф Гитлер, с примостившимся у его ног любимым псом Фукслем. А человек, которого он обнимает, очень похож на Эриха Пауля Ремарка, более известного как Эрих Мария Ремарк. Он молод по сравнению со своим сослуживцем, ему меньше двадцати и на фронте он в лучшем случае месяц — и это хорошо соотносится с архивными данными: Эриху, в отличие от Адольфа, и впрямь довелось попасть на войну рано и послужить недолго.....
Рассмотрим облако из конечного числа точек. Возьмем шпагу и проткнем его насквозь. Какое-то число точек нанижется на шпагу. Спрашивается, минимум сколько раз надо протыкать облако шпагой, чтобы нанизать его полностью?
Это случай классической задачи о покрытии. Имеется конечное множество точек и некоторая совокупность его подмножеств. Требуется покрыть это множество, использовав минимальное количество указанных подмножеств. В нашем случае совокупность подмножеств состоит из отрезков. Если решать эту задачу с помощью жадного алгоритма, который на каждом шаге выбирает подмножество, покрывающее максимальное число точек, то решение, как известно, не всегда минимально, чему имеется стандартный контрпример с 5 подмножествами.
А в случае со шпагой, т.е. с отрезками, такой пример можно придумать? Конечно, не обязательно с 5 подмножествами. ))
В Интернете уже существуют большие проблемы с защитой своего профиля и данных, но исследователи из Университетского колледжа Лондона решили, что всем надо поволноваться еще больше. Они создали новый софт, который может в совершенстве копировать любой почерк — как живого человека, так и мертвого — так что теперь подделать подпись или записку сможет каждый.
Раньше попытки скопировать чей-то почерк были довольно неудачны. Непосредственно сами буквы были довольно похожи, но соединялись они совершенно искусственно, и подлог был виден с первого взгляда. Новый алгоритм, созданный доктором Томом Хайнсом, доктором Уазеном Мас Аода, доктором Гэбриэлом Бростоу и другие учеными-компьютерщиками, повторяет все особенности почерка отдельного человека, включая толщину букв, их соединение, а также вертикальное и горизонтальное расположение. Результат выглядит так, словно написан от руки, буква за буквой, так как различные знаки отличаются от слова к слову.
Алгоритму требуется по крайней мере параграф написанного от руки текста, после чего он в совершенстве воспроизводит любой почерк. Есть применения для этой технологии, которые не касаются подделки подписей, контрактов или рецептов. Он может позволить людям, пораженным инсультом, или же тем, кто потерял способность писать, генерировать вполне разборчивые записки. Ну и в принципе новый алгоритм может разбирать неразборчивый почерк, а также оцифровывать рукописные тексты.
Математики из Сент-Эндрюсского университета в Шотландии обещают любому, кто справится с «задачей о восьми ферзях» в более общем виде, предложив для неё программное решение, миллион долларов. Программа должна расставить на доске 1000 на 1000 клеток тысячу ферзей, которые не бьют друг друга, и не потратить на это годы. Тому, у кого получится, считают исследователи, подвластна задача практически любой сложности.
В частном виде задача, которую придумали ещё в 1850 году, звучит просто: нужно расставить на обычной шахматной доске восемь королев таким образом, чтобы ни одна из них не била другую.
Она имеет много решений, хотя бы одно из которых интуитивно может найти почти любой человек, который знает шахматные правила. Несколько сложнее написать код, который будет решать такую задачу. Но и это вполне по силам даже начинающему программисту, который знает хотя бы QBasic.
Даже в общем виде, для доски любого размера, хоть миллион на миллион с миллионом ферзей программа не будет громоздкой. Нью-Йоркский математик Пол Батлер, например, предложил элегантное решение длиной ровно в один твит: 140 символов.
Проблема в том, что для решения «задачи восьми ферзей» даже на доске с диагональю в тысячу клеток такой программе понадобится мощный компьютер и долгие, долгие годы работы. По условиям челленджа, программа-победитель должна решить задачу «тысячи ферзей» за приемлемое время. До сих пор с этим не справилась ни одна лаборатория и ни один суперкомпьютер, хотя пробовали многие. Организаторы челленджа считают, что программе, которая справится, по силам будут самые сложные, на данный момент нерешаемые, задачи в области шифрования.
Почему обязательно годы?
Почему бы не найти решение на 1-й же минуте!
Ведь не требуется найти ВСЕ решения.
Методом Монте-Карло. Если повезет, конечно.
Помолиться и найти. Или все-таки требуются все??
На доске 1000*1000 с 1000 ферзей очевидно и одно решение не находится в приемлемое время.
The team found that once the chess board reached 1000 squares by 1000, computer progams could no longer cope with the vast number of options and sunk into a potentially eternal struggle akin to the fictional “super computer” Deep Thought in Douglas Adams’ Hitchhiker’s Guide to the Galaxy, which took seven and a half million years to provide an answer to the meaning of everything.
Задача вроде не компьютерная, но как решить ее без компьютера, я не знаю. (Удивляюсь могучим школьникам.) Поэтому помещаю ее в эту ветку (Владимирович, думаю, одобрит). Рис. 9 я пока отрезал.
На компьютере найти решение не очень сложно. Я за 1000 попыток нашел 4 штуки, в т.ч. указанное.
Приведу еще одно, нарисованное мною от руки, как смог. В принципе можно было бы и на стенку повесить. ))
Все они - эти змейки - имеют начало и конец. Понятно, что замкнутых змеек, см. условие, не существует.
Все они - эти змейки - имеют начало и конец. Понятно, что замкнутых змеек, см. условие, не существует.
Возникает вопрос, а можно ли хотя бы одну из этих змеек замкнуть, т.е. закрасить еще одну, 43-ю, клетку так, чтобы она была соседкой только первой и последней закрашенным клеткам? А если нельзя, то какова максимальная длина змейки, которую замкнуть можно?
Нетрудно найти, и даже вручную, такую змейку из 39 клеток, так что после замыкания в ней будет 40 клеток. А вот длиннее ее мне найти не удалось. И скорее всего, можно доказать, что это и есть максимум.
Змейки одинаковой длины, замкнутые или нет, могут отличаться, например, по количеству изломов ("коленок") k.
Ниже я изобразил пару змеек длиной 42 клетки с k = 26 и 19.
Правда, не могу сказать, самая изломанная и самая неизломанная змейки это или нет.
Чтобы найти змейки из 42 клеток (по максимуму), я сделал 1 000 000 случайных экспериментов (за час с лишним компьютерного времени), каждый из которых насчитывал 64 случайные змейки (по числу стартовых клеток). И всего я нашел 45 змеек, различающихся оконечными клетками (их две, и они взаимозаменяемы), не учитывая, однако, что некоторые змейки суть одно и то же (симметричны друг другу). Вернее, это не столько змейки, сколько представители классов змеек, где классы различаются только оконечностями входящих в них змеек. То, что я нашел не все возможные классы, видно на следующей доске, в ячейках которой я подсчитывал одновременно старты и финиши этих (45) змеек. Видно, что не всё на ней симметрично.
Чтобы найти змейки из 42 клеток (по максимуму), я сделал 1 000 000 случайных экспериментов (за час с лишним компьютерного времени), каждый из которых насчитывал 64 случайные змейки (по числу стартовых клеток). И всего я нашел 45 змеек, различающихся оконечными клетками (их две, и они взаимозаменяемы), не учитывая, однако, что некоторые змейки суть одно и то же (симметричны друг другу). Вернее, это не столько змейки, сколько представители классов змеек, где классы различаются только оконечностями входящих в них змеек. То, что я нашел не все возможные классы, видно на следующей доске, в ячейках которой я подсчитывал одновременно старты и финиши этих (45) змеек. Видно, что не всё на ней симметрично.
Сумма всех чисел, понятно, равна 45х2 = 90.
Разобьем доску двумя осями на четыре равных квадранта. Понятно, что для нахождения ВСЕХ классов змеек длиной 42 клетки достаточно найти все классы, змейки которых начинаются в 1-м квадранте (но можно взять и любой другой), а все остальные классы получить зеркальным отражением относительно осей. Времени потребуется в 4 раза меньше, чем для всей доски. Миллиона экспериментов в 1-м квадранте мне чуточку не хватило (зато, для сравнения и контроля, во 2-м квадранте хватило). Картина (в 1-м квадранте полная) получилась следующая.
Всего насчитывается 22 класса змеек (т.е. 22 класса эквивалентности по оконечным точкам) или, вместе с зеркальными отражениями, 48 классов, а не 45, как процитировано выше. Других нет, они невероятны.
Не сразу, но наконец-то я нашел все решения этой задачи. Если змейка стартует в одной клетке и финиширует в другой, то добавим в обе клетки по единичке. Тогда все решения (змейки длиной 42 клетки), стартующие в 1-м квадранте, произведут следующую суммарную картину.
Т.е. 16 змеек финишируют в 1-м квадранте, где и стартовали, 92 змейки финишируют в 3-м квадранте и по 4 змейки финишируют во 2-м и в 4-м квадрантах, итого 116 змеек-решений. Всего же будет 116х4 = 464 решения. Если же не различать старт и финиш змейки, то решений будет 464/2 = 232. А если еще и не различать змейки и их зеркальные отражения, то решений будет и вовсе 16/2 + 92 + 4 + 4 = 108 штук. Вроде так.
Да, забыл сказать, что рассмотреть пришлось более 50 млн случайных змеек, чтобы отфильтровать эти 108.
Заметил одну закономерность в рассматриваемой задаче. Перенумеруем все клетки доски по вертикали и горизонтали: i = 0, ..., 7 и j = 0, ..., 7 и введем расстояние (манхеттенское) между клетками (i, j) и (i', j'): d = |i - i'| + |j - j'|. В принципе d = 0, 1, 2, ..., 13 или 14, но не в случае стартовой и финишной клеток решения задачи, какое решение ни возьми: здесь d = 3, 5, 7, 9 или 11.
не хватает случая вспучивания доски, изменения ее кривизны, потока риччи и метрик шахматных клеток
1. Исходную задачу я не придумал, а взял из сборника олимпиадных задач. Про ее решение написано, что найти его не так-то просто. Компьютер же позволяет найти не просто какое-то решение, но ВСЕ решения! И их довольно много, так что найти требуемое вполне реально и вручную. Опять же множество решений, любое, так и просится (!) рассмотреть на нем какую-нибудь задачу оптимизации.
2. Манхеттенская метрика, хоть и не уникальна в этом отношении, но является целочисленной при целочисленных координатах, самое оно для точности.
3. Приведите свою алгоритмическую задачку, БОЛЕЕ ВСЕМ ИНТЕРЕСНУЮ, но заведомо посильную для персонального компьютера.
Смотрите, какое художество получилось, все-таки речь в задаче идет о художнике.
Пояснение. Из каждой клетки стартует какое-то количество змеек максимальной длины 40, 41 или 42 клетки, будем считать эти змейки красными, зелеными и синими соответственно. С другой стороны, эти змейки где-то финишируют. Суммарное количество змеек, стартующих из данной клетки, и змеек, финиширующих в ней, в соответствии с их цветом обозначим R, G, B, всего R + G + B = S змеек, а относительное их количество, т.е. R/S, G/S, B/S, обозначим r, g, b. Рассматривая теперь каждую клетку, будем считать эти r, g, b ее барицентрическими координатами в стандартном цветовом треугольнике. В цвет точки с этими координатами клетка и окрашена.
Нюанс: зеленые и красные змейки никогда в чисто зеленых (#00FF00) и чисто красных (#FF0000) клетках не финишируют, но всегда стартуют (а синие, разумеется, никогда в них не финишируют, поэтому число B всегда четное). Другими словами, по сравнению с предыдущей картиной изменился цвет только синих клеток - в них добавились зеленый и красный цвета, в основном зеленый, а красный - лишь в предугловые пары.
