05.04.2017

Теория шести рукопожатий

Вы наверное слышали об идее что цепочки из шести человек, в среднем, достаточно чтобы связать вас с любым человеком на земле. Интересно также, возможно ли любого человека на земле связать с любым разумным существом во вселенной и какова длина этой цепочки. Но этот вопрос мы оставим на потом, и вернемся к границам земного шара.

Итак, в 1967 году американский ученый Стэнли Милгрэм провел эксперимент, который, вкратце, выглядел следующим образом: были выбраны пары городов, начальный и целевой, которые находились далеко друг от друга не только географически, но и социально. В начальный город, случайным людям, разослали письма с информацией об эксперименте и контакте персоны из целевого города. Если человек получивший письмо знал эту персону лично, то он должен был переслать письмо напрямую. В противном случае письмо необходимо было переслать тому, кто по мнению текущего держателя письма мог с большей вероятностью знать целевой контакт. Также присутствовал механизм для отслеживания длины цепочки людей, через которых проходило письмо прежде чем попасть к персоне в целевом городе. Средняя длина цепочки была равна шести.

В 2001 году Дункан Уоттс повторил вышеупомянутый эксперимент на современный манер. В качестве пакета для информации использовались электронные письма. Он получил такой же результат в виде средней длины цепочки равной шести.

Поразительно то, что шесть человек это не так уж и много. Это 0.00000008% от населения земли, которое примерно равно 7,3 миллиарда человек. Шесть человек можно посадить в ладу шестерку и устроить круиз по подмосковью. Но, как ни феноменально, этого может быть достаточно чтобы связать вас с любой, на первый взгляд самой недоступной, персоной.

Графы

Перед тем как мы приступим к рассмотрению возможного объяснения этого феномена нам необходимо познакомится с математическими объектами — графами, и с некоторыми из их свойств.

Граф это множество вершин и множество ребер, которые соединяют эти вершины. В графическом виде граф можно представить следующим образом:

У нас есть три вершины: A, B, C, и два ребра соединяющие их: AB, BC.

Может кто помнит такой вид развлечения из детства: дают набор точек и путем их правильного соединения получалась картинка какого нибудь котика. Набор точек это множество вершин, и по задаче мы рисовали к ним ребра. Граф в действии. Довольно продвинуто для детей, не находите? Так же я уже описывал такой объект как деревья, которые являются частным случаем графов.

Путь

Как видно из нашего рисунка некоторые ребра непосредственно связаны друг с другом. В нашем предыдущем примере из узла A есть ребро в узел B. Представим все ребра графа как дороги для автомобилей. Ну а там где есть дороги возможно и путешествие! Из A мы можем попасть в B, а из B мы можем попасть в C. Следовательно из A мы можем попасть в C, с промежуточной остановке в B.

Такое путешествие, а формально последовательность ребер через которые мы проходим, мы назовем путем. Длину последовательности ребер в пути будем считать длинной пути.

Итак, если мы из A хотим попасть в C, то нам необходимо преодолеть путь (AB, BC). Мы проходим два ребра, следовательно длина пути равна двум.

K-соседи

Для анализа путей вида A → C с промежуточной остановкой в B введем понятие k-соседей.

Вершина B является k-соседом вершине A если:

  1. Из вершины А есть путь в вершину B
  2. Его длина равна k
  3. Это кратчайший путь для двух данных вершин

Рассмотрим пример:

Из узла A в узел C мы можем попасть двумя путями: напрямую через ребро AC, или с промежуточной остановкой в B. Данные пути, соответственно, мы можем записать следующим образом (AC), (AB, BC). Каким же соседом C является для A? У нас есть два пути, длины этих путей равны 1 и 2 соответственно. Но для того чтобы полностью соответствовать нашему определению нам необходимо выбрать наименее короткий путь, следовательно C является 1-соседом вершине A.

Клика

Если из каждой вершины графа есть путь к любую другую вершину, то такой граф мы называем связанным.

В случае если не все вершины связаны между собой, но какое то подмножество вершин все же полностью связано, то это подмножество называется кликой графа.

Возьмем, к примеру, следующий граф:

В этом графе вершины A, B, C образуют клику, потому что у нас есть ребра из каждой вершины в каждую, а именно AB, AC, BC.

Сила

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

Приведем пример. В качестве вершин представим города, а в качестве ребер дороги между ними. Это называется дорожной сетью. Почему слово сеть заменило слово граф? Я, поверхностно просмотрев сеть интернет, так и не нашел ответа. Есть некая тенденция сетями называть объекты которые относятся к реальному миру, а графами объекты относящиеся к математическому. А может кому то не нравится благородство происхождения?

Так, не отвлекаемся. Представим себе гипотетическую дорожную сеть между четырьмя городами России:

Изображение схематично, не имеет общего с реальным положением дел

Используя то, что мы уже знаем о графах, проведем вычисления над этим графом. Если мы возьмем Москву как отправную точку нашего путешествия, то Санкт-Петербург, Воронеж, и Ярославль являются 1-соседями Москвы. Архангельск и Волгоград 2-соседями. Также города Москва, Ярославль, Санкт-Петербург образуют клику.

На этом мы не остановимся. Мы, также, можем вычислять кратчайшие пути между городами. Скажем, перед нами стоит задача попасть из Архангельска в Ярославль. Кратчайшим путем будет Архангельск — Санкт-Петербург — Ярославль, а не Архангельск — Санкт-Петербург — Москва — Ярославль.

Еще такой пример. Представим что мы проектируем дорожную сеть. Если на дороге из Москвы в Санкт-Петербург произойдет затор, то мы все же сможем попасть из Москвы в Архангельск через путь Москва — Ярославль — Санкт-Петербург — Архангельск. Но если произойдет затор Москва — Воронеж, то мы не сможем попасть из Воронежа и Волгограда в Санкт-Петербург. Москва является узким местом в нашей дорожной сети. Мы можем это исправить проведя дорогу между Воронежем и Ярославлем.

Звучит довольно тривиально, но переведем наши задачи в масштаб городских улиц. Скажем у нас 3 500 улиц с множеством перекрестков, на каждой из улиц разный параметр загруженности и следовательно время прохождения. Ответ на вопрос «Как быстрее попасть из пункта А в пункт Б» уже не столь тривиален. Сложность выявление узких мест в дорожной сети может стать настоящим кошмаром. Но если мы перекладываем нашу проблему на графы, то мы можем использовать алгоритмы для решения этих задач, а следовательно и компьютеры. Вот это уже звучит более интересно, не так ли?

Решение

Теперь мы полностью готовы рассмотреть наш изначальный вопрос. Для этого мы сконструируем модель социальной сети человечества.

Первое предположение: каждый человек обладает определенным кругом знакомств. У нас есть друзья, и, обычно, каждый наш друг знает другого нашего друга. Таким образом мы формируем некую клику в социальной сети, обозначим ее буквой C.

Второе предположение: у человека есть случайные знакомые не входящие в его круг знакомств. Скажем, с кем то мы учились в школе в параллельных классах или познакомились в детском лагере летом. Обозначим их буквой R. У каждого из таких случайных знакомых есть своя клика друзей, у людей из этой клики есть свои случайные знакомые и так далее. Скажем у нас есть 12 человек, в каждой клике по 3 человека, у половины по одному случайному знакомому. Социальная сеть будет выглядеть следующим образом:

Давайте посмотрим на k-соседей для A1 в нашей социальной сети. 1-соседи состоят из людей в клике С (вершины B1, C1), и произвольного друга R (вершина A2). 2-соседи состоят из произвольных знакомых людей из нашей клики (CR), и друзей из клики нашего произвольного знакомого (RC). Мы не включаем друзей клики из нашей клики (CC) потому что это теже люди что и сама клика C. В общем случае мы не включаем цепочки в которых C идет два раза подряд. Ну а с 3-соседей довольно затруднительно описать словами, поэтому просто перечислю в виде обозначений: CRR, CRC, RRR, RCR, RRC.

Я знаю вам не терпится это посчитать:

1-соседи: C + R = 2 + 1 = 3
2-соседи: CR + RC + RR = 2×1 + 1×2 + 1×0 = 4
3-соседи: CRR + CRC + RCR + RRC + RRR = 2×1×0 + 2×1×2 + 1×2×0 + 1×0×0 + 1×0×0 = 4

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

Получается что 3 рукопожатия это максимум что нам понадобится для того чтобы войти в контакт с любым человеком из этой сети.

Расширим масштаб нашей сети до 140 человек в клике и 10 случайных знакомых. Посчитаем сколько человек мы можем достать используя 6 рукопожатий:

1-соседи: C + R = 140 + 10 = 150
2-соседи: CR + RC + RR = 140×10 + 10×140 + 10×10 = 2 900
3-соседи: CRR + CRC + RCR + RRC + RRR = 140×10×10 + 140×10×140 + 10×140×10 + 10×10×140 + 10×10×10 = 239 000
4-соседи: CRRC + CRRR + CRCR + RCRC + RCRR + RRCR + RRRC + RRRR = 6 450 000
5-соседи: CRRCR + CRRRC + CRRRR + CRCRC + CRCRR + RCRCR + RCRRC + RCRRR + RRCRC + RRCRR + RRRCR + RRRRC + RRRRR = 399 100 000
6-соседи: CRRCRC + CRRCRR + CRRRCR + CRRRRC + CRRRRR + CRCRCR + CRCRRC + CRCRRR + RCRCRC + RCRCRR + RCRRCR + RCRRRC + RCRRRR + RRCRCR + RRCRRC + RRCRRR = 13 021 000 000

Тринадцать миллиардов. Впечатляет! Это почти в два раза больше чем население земли.

Так откуда возникает столь интересный феномен? Он возникает из структуры нашей сети, а именно из того что у нас есть клики друзей и случайные знакомые. Структура же возникает из того, как каждый элемент сети создает связи с другими элементами. Для объяснения теории шести рукопожатий мы предполагали что у людей есть клика близких знакомых и у каждой такой клики есть связь, некий мост, в другую клику. Вообще, такие графы называются забавным названием «Мир тесен», и что самое удивительное не только социальные сети проявляют свойства подобных графов.

Интересно наблюдать за тем как растет число контактов с ростом числа рукопожатий. Если 1-соседей у нас 150, то 2-соседей уже 2900, а 3-соседей уже 239 000. Это население довольно крупного города. Это может натолкнуть на мысль, что более слабые связи могут дать нам больше, потому что в них участвует большее количество людей. Именно эту идею представляет американский социолог Марк Грановеттер в статье «Сила слабых связей».

Конечно, это не полностью описывает то, как обстоят дела настоящем мире. Это всего лишь игрушечная модель. Но в отличии от анализа реального положения дел, со всеми его деталями, наша модель позволяет нам получить понимание того, почему теория шести рукопожатий имеет место быть.

10.03.2017

Курс «Модельное мышление»

Для того чтобы понять что такое модельное мышление для начала разберемся с моделями. Возьмем определение из Википедии:

Модель (фр. modèle, от лат. modulus — «мера, аналог, образец») — это система, исследование которой служит средством для получения информации о другой системе; представление некоторого реального процесса, устройства или концепции.

Найдем что то более интуитивное для этого определения. Предположим перед нами есть некая сложная и серьезная проблема из реального мира со множеством «двигающихся частей»: переменных, сущностей, связей. Наша задача ее лучше понять или решить. Возьмем, к примеру, распространение слухов в социальной среде. Скажем, если вы проговоритесь одному вашему другу что вы любите соленые торты, то как быстро об этой весточке будет знать каждый ваш друг и еще полгорода в придачу? Неделя, день, пару часов, или может вообще ничего дальше него так и не уйдет? Можно попытаться решить эту проблему со всеми свистелками: спросить у друга расскажет ли он кому нибудь, спросить у тех кому он расскажет кому они расскажут и так далее. Бум, и голова по всей комнате.

Мы можем пойти более простым путем, но нам придется добавить немного размышлений. Можно представить наших друзей, их друзей, и друзей их друзей в виде социальной сети. Каждый узел будет человеком, а связь между узлами означает связь между людьми. Также мы можем добавить меру болтливости: предположить, что каждый из людей распространяет слухи с некоторой вероятностью.

Moreno Sociogram 2nd Grade.png

Кружки представляют людей, а линии связывают их знакомством. Буквы в кружках можно расценивать как инициалы имен. Автор Martin Grandjean, собственная работа, CC BY-SA 4.0, ссылка

Все просто. Наша модель готова. С ее помощью мы можем изучать нашу проблему более точно, нежели на основе предположений. Мы можем менять параметры и смотреть как будет меняться ситуация в зависимости от того сколько людей знакомы с друг другом, или насколько они болтливы. И вне зависимости от того что вам больше по душе: мой неловкий пример, или определение из вики, этот стиль мышления таит в себе огромный потенциал.

Так что же такое модельное мышление? Собственно это и есть использование моделей для изучения и решения реальных проблем. Причем не обязательно одну модель для одной проблемы. Мы можем использовать множество моделей для рассмотрения одной проблемы, или же одну модель для изучения множества вопросов. Это следствие того, что наши модели это абстракции реальных проблем. В нашем примере человек перестает быть индивидуумом, со своими желаниями и эмоциями, а становится лишь точкой в социальной сети, и этой точке без разницы чем она является. Используя ту же модель мы можем анализировать проблему распространения сигнала в компьютерной сети, в которой есть точки отказа. Модели плодовиты, и это мощь!

В чем магия? В Одиссеи Гомера был такой сюжет (из Википедии):

Прожив у Цирцеи год, Одиссей отправляется дальше, мимо острова сирен, влекущих своим чарующим пением моряков на гибель. Своим гребцам он затыкает уши воском, сам, полный любопытства, приказывает привязать себя к мачте и слушает. Так они минуют угрозу.

Вот хитрец! И волки сыты и овцы целы (в быту я более интересную версию использую). Так, а какое отношение это имеет к нашим моделям? Наши модели привязывают нас к мачте логики, которая в свою очередь помогает нам более эффективно исследовать проблему. Логика направляет нас в наших исследованиях и открывает для нас те свойства проблемы, которые не может открыть мышление «здравым смыслом». Все это помогает нам более точно мыслить, а как результат мы можем принимать более рациональные решения и улучшить нашу жизнь до невиданных высот.

Собственно, курс

Со всем этим великолепием нам поможет ознакомиться замечательный курс «Модельное мышление». Он состоит из десяти недель. После каждой пятой недели вас ждет небольшой экзамен в виде теста. Каждая неделя разбита на 2 модуля и содержит проверочный тест в конце. Широта охватываемых тем и количество моделей которую покрывает курс просто нереальная. Среди них такие вопросы:

  • Почему в американских городах большая сегрегация?
  • Как принять грамотное решение в ситуациях неопределенности?
  • Как предсказать победителя на выборах президента?
  • Как и почему расчет экономика?
  • Что такое процессы Маркова и функция Ляпунова?
  • Как можно представить культуру в виде модели?
  • Почему работает теория семи рукопожатий?
  • Что такое мудрость толпы?

И это очень как далеко не все, подчеркну еще раз: далеко не все темы. Огромное число моделей, и как мы говорили выше их можно использовать и в других проблемах, вплоть до бытовых. А если и этого мало к каждой неделе еще прилагаются материалы для чтения: научные статьи или отдельные главы книг. На закуску у нас программа НэтЛого в которой можно запустить компьютерную симуляцию модели и воочию наблюдать ее работу и менять ее параметры. Безграничные возможности!

Каждый модуль курса самодостаточен и ну очень интересный. Обычно в процессе столь долгого курса под конец интерес очень сильно падает, и это превращается в какую то каторгу. Но не в этом случае.

Обилие матана пугаться не стоит, достаточно простой школьной алгебры. В процессе вы ознакомитесь с теорией игр, автоматов, вероятности, плюс немного статистики. Но это все великолепно и интересно объясняется.

Как мы говорили выше курс на широкую ногу, затрагиваемых тем очень много. В связи с этим он не раскрывает все во всех деталях, но каждый модуль служит хорошим приглашением и мотивацией для дальнейшего самостоятельного исследования.

В заключении скажу что пройти этот курс очень рекомендую я. 10/10. Это один из тех редких курсов который сможет поменять то как вы видите и думаете о мире.

27.02.2017

Представление проблем

На протяжении возможности долгой и беззаботной жизни, которую нам предоставляет современный мир, мы сталкиваемся с множеством проблем. Некоторые из них довольно простые, симметрично, некоторые довольно сложные. Это свойство можно измерить, скажем, по количеству минимального времени которое необходимо потратить для решения проблемы. Под минимальным временем я имею ввиду такое количество времени, которое бы затратил лучший из лучших для решения данной проблемы. Это вполне объективно. Но есть и еще одна сторона монеты: как каждый из нас «видит» данную проблему. Назовем это представлением. Грубо говоря кто то ищет правосудия в суде сквозь логические аргументы, а кто то сквозь огнестрельные:

Игра

Обернем это в математическую обертку для того чтобы посмотреть на это в действии. Рассмотрим игру «В сумме 15» со следующими правилами:

Есть два игрока и карты с номерами с 1 по 9. Игроки берут карты по очереди, начиная с первого игрока. Побеждает тот игрок у которого на руках 3 карты, которые в сумме дают 15.

Предположим что у игрока на руках карты 9 3 5 4 2. Он побеждает потому что 9 + 4 + 2 = 15.

Что мы можем сказать о данной игре? Она может оказаться простой или сложной (наподобие тех в которых тебя облапошивают уличные мошенники). Для того чтобы это понять проведем тестовый матч. В левом углу воображаемого ринга Алиса в роли игрока № 1, в правом Боб в роли игрока № 2.

Стол
Алиса
Боб

Нажмите чтобы проиграть демо

Как мы условились первое право выбора карты за Алисой. Она берет четверку. Боб думает что это странный выбор и берет пятерку. Ход переходит Алисе. Она делает еще более странный ход и берет шестерку. Боб впадает в сомнения. Тут две возможности: либо Алиса хитрая, либо она не понимает сути игры. Боб берет восьмерку. Алиса с победоносным видом берет двойку. Боб включает арифметику и производит расчеты. Если он не возьмет девятку то Алиса победит (4 + 2 + 9 = 15). Но если он не возьмет семерку то Алиса так же победит (6 + 2 + 7 = 15). Взять он может только одну карту. Боб оказался в ловушке и с грохотом продул.

Игра не такая простая как хотелось. Если ее решать в лоб то можно взять все тройки карт которые в сумме дают 15 и следить какие карты взял противник. Вот все возможные комбинации:

  • 2 + 7 + 6
  • 2 + 5 + 8
  • 9 + 5 + 1
  • 4 + 3 + 8
  • 4 + 5 + 6

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

Магия

Вернемся к нашим комбинациям. Я их перетасовал немножко чтобы запутать ваc, но теперь приведем все в порядок:

15 15 15
2 7 6 15
9 5 1 15
4 3 8 15
15 15

Как видно из таблицы выше эти числа можно организовать в очень интересную структуру, которая имеет замечательное название «Магический квадрат». Каждая строка, столбец и диагональ в сумме дают 15. Это число называется «Магическим числом». Итого у нас есть по три числа в группе (строка, столбец, диагональ), каждая тройка этих чисел в сумме дает 15. Ах, да это же наша изначальная проблема. Но та часть, которая мне нравится больше всего, все еще впереди. Представим игру Алисы и Боба используя магический квадрат:

15 15 15
2 7 6 15
9 5 1 15
4 3 8 15
15 15

Не выглядит ли это как что то до боли знакомое? Мы поочередно ходим, выбирая по одной клетке, для того чтобы собрать строку, столбец или диагональ. Cтарые знакомые крестики-нолики подойдут под это описание. То что мы сейчас сделали это сконструировали представление для нашей начальной игры, которое, возможно, поможет нам играть более эффективно. Мы можем играть в крестики-нолики используя представление которое описанно в наших начальных правилах, можем играть в нашу начальную игру используя представление крестиков-ноликов, но являются ли эти две проблемы идентичными вопрос оставлю открытым.

Итог

Что же у нас получилось? Для начала посмотрим на ингредиенты. У нас есть проблема в виде игры решение которой в том виде в котором она нам представлена, через правила, может быть весьма запутанным или даже невозможным. В таких случаях мы можем попробовать сконструировать представление которое описывает нашу проблему по другому, оголяет ее структуру, делая решение простым и очевидным. Все это конечно ведет к прибыли и успеху.

Развивая эту идею можно прийти к интересному размышлению: разные представления ведут к разным решениям. Скажем вы хотите пообщаться с людьми, что переведем как выпить. Рассмотрим два решения: позвать много людей, чем больше тем лучше, или же посидеть тихонько с друзьями, чем ближе тем лучше. Можно это изобразить как количество и качество. Сначала пойдем количественным путем. Мы позвали кучу людей, но все знают чем это обычно оборачивается: вы оказываетесь в кругу в котором большинство берут идиоты. Ваша оценка 4/10. Если мы пойдем другим путем то мы душевно посидим на 10/10. Итак у нас есть 4/10 и 10/10. Первый случай нам принес меньше прибыли, это субоптимальное решение. Второй путь нас приводит к оптимальному решению. Первое представление полностью блокирует оптимальное решение потому что мы мыслим в категории количества. Проблема может быть в том что разные представления включают в себя разное количество частей объективной проблемы. Ну в общем я тут не могу представить ответа, так что оставляю это так.

04.03.2015

Парадоксы Зенона

Бесконечность интересная и таинственная вещь. Но совершенно не понятно может ли наш мозг понять и принять ее? Я уже рассказывал вам о бесконечном отеле Гильберта и мне все это кажется чем-то ненатуральным, чьей то безумной фантазией. Но бесконечность может быть гораздо ближе к реальности, чем закрома нашего разума. Предлагаю вашему внимаю два парадокса о движении, которые сформулировал Зенон Элейский где то в 5 веке до нашей эры.

Чтобы по-настоящему насладится этими парадоксами, надо знать, что рациональные числа обладают свойством плотности. Оно говорит нам следующее: между двумя неравными рациональными числами всегда можно найти рациональное число которое меньше большего числа и больше меньшего. То есть: ∀(a,b ∈ Q)∃(m ∈ Q): a<b ⇒ a<m<b. Это свойство позволяет нам говорить о том, что между вещественными числами 0 и 1 существует бесконечное число рациональных чисел (½, ⅓, ¼, ⅕, ..., ∞). Доказательство.

Гонка Ахиллеса и черепахи

Устроим небольшое воображаемое соревнование. На стартовой линии стоит греческий герой Ахиллес, воин и атлет, символ скорости и силы своего времени. И черепаха. Что? Черепаха? Бред, как черепаха может соревноваться с Ахиллесом? Я думаю, вы бы не стали возражать, если бы мы дали черепахе фору в 100 метров для того, чтобы Ахиллесу пришлось хотя бы немного размять свои мышцы перед триумфальной победой. Предположим, что в целом нашим спортсменам надо преодолеть дистанцию в 1000 метров.

Кстати, на кого вы бы поставили ¤ в этой математической гонке?

Судья взводит стартовый пистолет. На старт, внимание, бдыщь!

Для того, чтобы Ахиллесу обогнать черепаху, ему необходимо сначала ее догнать. Пока Ахиллес бежит 100 метров форы черепаха пробегает еще 10. Черепаха вновь впереди Ахиллеса, он вновь бросается ее догонять и пробегает еще 10 метров. В это время черепаха проползает еще 1 метр. Этот процесс может продолжаться до бесконечности, в которой Ахиллес так и не догонит черепаху.

Проиграли ставку? Но это ничего, ведь деньги у нас не настоящие (в отличии от банков ☺).

Википедия дает данную формулировку этого парадокса:

Допустим, Ахиллес бежит в десять раз быстрее, чем черепаха, и находится позади неё на расстоянии в тысячу шагов. За то время, за которое Ахиллес пробежит это расстояние, черепаха в ту же сторону проползёт сто шагов. Когда Ахиллес пробежит сто шагов, черепаха проползёт ещё десять шагов, и так далее. Процесс будет продолжаться до бесконечности, Ахиллес так никогда и не догонит черепаху.

Представить такую гонку на компьютере нет возможности. Как думаете, почему? Потому что компьютер не может делить бесконечно, так как у нас нет бесконечной памяти, чтобы хранить числа произвольной длинны. Благодаря этим свойствам Ахиллес и черепаха в компьютерной гонке все же окажутся в одной точке. Но, несмотря на это, ее смысл мы можем представить так:

1000 метров
И так до бесконечности.

Давайте сделаем еще одну визуализацию. Для этого мне понадобятся ваши руки. Расставьте их на расстоянии одного метра. Правая рука стоит не подвижно, а левая начинает движение к ней. Но не плавное, сначала левая рука приближается к правой на половину начального расстояния, то есть на 50 сантиметров. Потом на половину полученного расстояния, то есть на 25 сантиметров, потом на половину этого и так далее. До бесконечности. Забавно, да? Вы только что завершили бесконечный процесс своим хлопком.

Еще одна хорошая визуализация, которую опять же нельзя по настоящему представить на компьютере, это построение квадрата из бесконечного числа прямоугольников. Берем квадрат, скажем, 100 на 100 единиц измерения, делим его пополам, одну половину делим еще раз на две равные части, еще одну полученную половину делим пополам. И так далее, до бесконечности. Да, наш конечный квадрат состоит из бесконечного числа меньших прямоугольников:

Так о чем это? О бесконечном процессе и его конечном завершении. Как же Ахиллесу удается настичь и обогнать черепаху в этой нелегкой гонке? Почему наши руки сходятся в хлопке, завершая процесс у которого нет финального шага? И еще: как конечный кусок материи может состоять из бесконечного числа частиц, как в случае с нашим квадратом?

Дихотомия

Дихотомия в переводе с греческого значит «Деление пополам», именно так Аристотель назвал этот парадокс Зенона.

Давайте представим что мы решили прогуляться в парк. Парк находится от нас в 100 метрах. Для того, чтобы пройти 100 метров, надо сначала пройти 50 метров. А для того, чтобы пройти 50 метров, нам надо пройти 25 метров. Вы уже поняли к чему я клоню? Да, к бесконечности процесса деления этого расстояния. Движение невозможно!

Есть забавная выдержка в которой противник Зенона, чтобы доказать обратное, начал просто ходить перед ним:

Еще как-то, защищая того же учителя, утверждавшего, что сущее неподвижно, он выдвинул пять эпихейрем в пользу того, что сущее неподвижно. Антисфен-киник, который не смог на них возразить, встал и стал ходить, полагая, что доказательство делом сильнее всякого возражения словом.

Википедия дает нам такую формулировку этого парадокса:

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

Представим это визуально:

100 метров
или подождем еще минутку?

Как мы видим, этот парадокс похож на парадокс Ахиллеса и черепахи, только в отличии от последнего, у него отсутствует точка старта — что и делает невозможность совершить шаг.

Заключение

Данные парадоксы обсуждаются уже более 2000 лет, и, как говорит нам Википедия, научное сообщество до сих по не пришло к общему мнению о сущности парадоксов. Мне нравятся эти парадоксы тем, что они, при достаточном погружении в их суть, задают интересные вопросы, которые, как мне кажется, уходят корнями во что-то очень базовое:

  • Как бесконечное действие может завершиться?
  • Есть ли конечная мера у времени и пространства, или его можно делить до бесконечности?
  • Если время можно делить бесконечное число раз, тогда как быть с такими вот парадоксами?
  • Если пространство бесконечно, то как конечные предметы могут состоять из бесконечного числа частиц?
  • Как физический процесс за конечное время принимает бесконечное множество значений?

Я говорю с позиции профана и в этих вещах не разбираюсь, если у вас есть ответы на эти вопросы, я бы очень хотел прочитать о них в комментариях к посту. Или, возможно, у вас возник тоже какой-то интересный вопрос?

В качестве бонуса интересное видео по теме:

14.05.2014
архивирован

Понимание русских

Вчера начался замечательный и своевременный курс «Понимание русских: контекст межкультурной коммуникации» от Высшей школы экономики. Надеюсь курс прольет свет и даст ответы на вопросы на которые у меня, как у русского, нет ответа, а так же прибавит понимания окружающей действительности.

Перевод описания со страницы курса:

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

Целью курса является предоставление студентам широкого обзора базовых принципов которые руководят прошлыми, настоящими и будущими взаимодействиями между Россией и западом, сфокусированными на культуру и национальную психологию русских и западных европейцев.

15.01.2014

Задача о n-ферзях

В это статье мы на примере шахматной проблемы n-ферзей рассмотрим как соединить наши знания о рекурсивных функциях и представлении данных в виде деревьев для решения сложных проблем. Если вы не читали предыдущие статьи (рекурсия, деревья) то советую их изучить перед продолжением чтения этой статьи. Для решения задачи мы так же изучим еще пару интересных трюков: как с помощью рекурсии создавать деревья и как в них искать данные методом поиска с возвратом. Я надеюсь, что я заинтриговал вас. Приступим.

Постановка задачи

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

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

Ферзь ходит по красным клеткам

Приведем пример почти решенной задачи для доски 4 на 4. Попробуйте сами закончить это решение кликнув на нужной ячейке:

Кликните на клетку где должен стоять ферзь

А вот одно из возможных решений для доски 8 на 8:

Задача не такая простая, как может показаться. К примеру, общее число расположения ферзей на доске 8 на 8 равняется 4 426 165 368. Разумеется, человек не будет решать эту задачу за счет простого перебора, но в любом случае при возрастании доски сложность увеличивается во много раз, и тут нам на помощь приходит компьютер.

Анализ проблемы

Разберем нашу проблему на составляющие.

Первое что приходит на ум при разборе любой шахматной проблемы это шахматная доска. Поскольку наша доска квадратная, она имеет только один параметр, который отвечает за высоту и ширину — назовем его размерность и обозначим n. Доска с размерностью n=8 имеет высоту и ширину в 8 клеток. Всего на данной доске 8×8=64 клетки:

n
n

Каждая клетка имеет координаты вида ряд:столбец. Она может быть пустой, или на ней может находится ферзь.

Ферзь атакует другого ферзя если они находятся на одном ряду, или на одной колонке, или на одной из диагоналей (слева-направо, справа-налево).

атак(x,y)⇔(ряд(x)=ряд(y))⊕(кол(x)=кол(y))⊕(диа_лп(x)=диа_лп(y))⊕(диа_пл(x)=диа_пл(y))

Решением является доска, которая удовлетворяет следующим условиям:

  1. Количество установленных на доске ферзей равно размерности доски.
  2. Ни один ферзь не атакует другого.

решена(доска)⇔(колво_ферзей=n)∧∀x.¬∃y.атак(x,y)

Алгоритм решения

Самое сложное при решении любой проблемы, а тем более незнакомой, это сделать первый шаг. Не пытайтесь объять незнакомую проблему разом, первый шаг должен быть максимально простым.

Мы начинаем с пустой доски. Представьте себе доску с минимальной размерностью. n=1? Нет, слишком тривиально. n=2? Вот этот вариант нам подходит.

Взглянем еще раз на условие решения: на доске должно находиться n ферзей и ни один ферзь не должен атаковать другого. Начнем с первой части этого условия: надо поставить n фигурок. Как мы это сделаем?

Маленький шаг для человека, большой шаг для решения проблемы. Поставим ферзя в клетку с рядом 1 и колонкой 1 (1:1):

Поскольку у нас размерность доски n=2, то по условию нам остается поставить всего одну фигурку. Поставим ее в первую свободную клетку:

Посмотрим на условие еще раз. Две фигурки есть, следовательно, первую часть условия мы удовлетворили. Вторая часть условия гласит, что ни одна фигурка не должна атаковать другую. Напомню, что ферзь атакует по своему ряду, колонке или диагоналям. Получается, что вторую часть условия мы не удовлетворили — наш первый ферзь атакует второго, так как они находятся на одном ряду:

Но не будем унывать, уберем второго ферзя с доски и поставим его в клетку 2:1. Теперь первый ферзь атакует второго ферзя по вертикали:

Опять уберем его и поставим в оставшуюся клетку, которую мы не попробовали — 2:2. Но и тут наш воинственный первый ферзь не дает соседу покоя атакуя его по диагонали:

Все ли варианты мы попробовали? Нет, еще можно переставить самого первого ферзя из клетки 1:1 на клетку 1:2 и попробовать решить с этой начальной позицией. Если и так не получится, то можно попробовать еще клетки 2:1 и 2:2 в качестве начальной позиции. Для доски с размерностью n=2 уже по этим вариантам можно заключить что решения не существует, но если мы посмотрим на решение для доски с размерностью n=8, которое мы приводили выше, то заметим, что там первая клетку свободна, следовательно менять позицию первого установленного ферзя имеет смысл.

Наша попытка не увенчалась успехом в виде решения задачи, но мы получили нечто большее — алгоритм. И, если с него скинуть частные детали, то его можно будет применить для решения задачи с любой размерностью доски. Давайте немного формализуем то, что мы описали выше. Для большей наглядности и простоты предположим, что размерность доски больше единицы:

  1. Начинаем с пустой доски.
  2. Ставим фигурку в первую свободную клетку:
    1. Если фигурка атакует другую, тогда переставляем ее на следующую свободную клетку:
      1. Если больше нет не попробованных клеток, тогда возвращаемся к предыдущей установленной фигурке и переставляем ее:
        1. Но если текущая фигурка является начальной, тогда предыдущей быть не может, следовательно задача не имеет решения.
    2. Если количество фигурок равно размерности доски тогда данная доска является решением.
    3. Если количество фигурок меньше размерности доски тогда берем еще одну фигурку и возвращаемся к пункту 2.

Из описания алгоритма плохо видно, но в процессе он генерирует дерево. Каждый раз когда мы ставим фигурку в свободную клетку на доске мы производим от нее потомка. От этого потомка, при наличии свободных клеток на нем, мы можем произвести еще одного потомка и так далее. Таким образом из пустой доски в начале работы алгоритма у нас вырастает дерево. В виде таких деревьев очень удобно представлять игры с последовательными ходами. Как я отмечал в предыдущей статье такие деревья анализируют компьютерные алгоритмы чтобы обыгрывать людей.

Еще одна важная деталь этого алгоритма это то, что он использует метод поиска с возвратом. Каждый раз устанавливая новую фигурку мы стараемся найти такую позицию, при которой она не будет атаковать другие фигурки. Если на данной доске такую установку сделать невозможно тогда мы возвращаемся на шаг назад и переставляем предыдущую установленную фигурку. Таким образом мы пробуем все возможные комбинации фигур на доске и пытаемся найти решение данной проблемы.

Представим это визуально:

Нажмите чтобы проиграть демо

Решение

В процессе анализа проблемы мы выделили три типа данных: доска, клетка, фигура. При этом доска состоит из клеток, а фигурки устанавливаются на клетки. Доска с расставленными фигурками так же является решением задачи. Получается, что доска это наш основной тип данных. Давайте подумаем как нам его удобно представить в программе.

Самое очевидное это представить доску в виде матрицы размером n строк, в каждой строке n элементов. Но это можно сделать проще: в виде одного плоского массива n×n элементов. Каждый элемент этого массива представляет собой клетку. Клетка может иметь два состояния: пустая, с фигурой. Давайте условимся что пустая клетка будет представляться булевой константой false, а клетка с фигурой будет представляется булевой константой true. Для простоты давайте называть такие данные не массив а Board. Давайте попробуем представить доску с размерностью n=4, и решение для этой доски:

/** B представляет пустую клетку
  * @type {CellState}
  */
var B = false;

/** Q представляет клетку с ферзем
  * @type {CellState}
  */
var Q = true;

/** Пустая доска с размерностью n=4
  * @type {Board}
  */
var n4emptBrd = [B, B, B, B,
                 B, B, B, B,
                 B, B, B, B,
                 B, B, B, B];

/** Решение для доски с размерностью 4
  * @type {Board}
  */
var n4solBrd = [B, Q, B, B,
                B, B, B, Q,
                Q, B, B, B,
                B, B, Q, B];

Комментарии сверху это JSDoc. Если вы не знакомы с этой штукой то не пугайтесь, она используется для создания документации и просто чтобы было легче разобраться в коде. В процессе написания программ я этим активно пользуюсь и это приносит свои плоды в виде менее запутанного кода. Но, если хотите, можете это отбросить.

Каждый раз вручную создавать доску в виде большого массива не удобно. Поэтому нам бы не помешала функция которая делала бы это за нас. Назовем ее createEmptyBoard. Реализовать ее просто: создаем пустой массив и заполняем его пустыми значениями n×n раз:

/** Создает пустую доску n*n элементов
  * @param  {Natural} n Размерность доски
  * @return {Board}
  */
function createEmptyBoard(n){
  var b = [];
  for(var i=0;i<n*n;i++){ b.push(B); }
  return b;
}
// Тесты для функции createEmptyBoard
(function(){
  console.log("Тест1:", createEmptyBoard(4).length==16);
})();

Под каждой функцией будем писать небольшие тесты, которые помогут нам убедится в работоспособности нашей программы.

Все приготовления закончены и мы можем приступать к функции которая будет решать проблему n-ферзей. Это уже задачка посложнее. Для начала давайте подумаем что должна принимать и возвращать эта функция. По нашему алгоритму она принимает пустую доску и возвращает доску с решением. А если решения нету, как у доски с размерностью 2? Мы не обговорили этот момент при проектировании алгоритма, так что пусть это будет false.

Создать такую функцию за один присест очень сложно, так что давайте опять подумаем о простом шаге который приблизил бы нас к реализации этой функции. Очень хороший выбор для этого шага — написание тестов. К предыдущей функции мы писали тесты после ее реализации, но для сложных функций очень хорошо писать тесты перед написанием самой функции. Во многих случаях это поможет вам лучше разобраться в проблеме и уменьшит время тестирования функции.

Самый тривиальный случай для этой задачи это n=1. Тот самый, который мы проигнорировали при проектировании алгоритма. Решением для этой доски будет доска с одной клеткой, в которой установлен ферзь. Для доски с размерностью n=2 решения нету, мы это узнали при проектировании алгоритма. А для доски с размерностью n=4 мы уже записали решение в коде чуть выше.

Для того чтобы наши тесты сразу начали приносить пользу нам надо написать заглушку для функции. Кстати, мы забыли ее назвать, пусть она называется solve. Заглушка должна возвращать значение которая реальная функция может вернуть, поэтому пусть это будет false. Перенесем в код то, о чем мы сейчас рассуждали:

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску
  *                         Иначе false
  */
function solve(b){ return false; } // заглушка

(function(){
  console.log("Тест2:",
    solve(createEmptyBoard(1)).toString()==[Q].toString());

  console.log("Тест3:", solve(createEmptyBoard(2))==false);

  console.log("Тест4:",
    solve(createEmptyBoard(4)).toString()==n4solBrd.toString());
})();

Шаги вроде написания тестов до реализации функции, описания ее интерфейса и предназначения в комментариях ведут к большему пониманию проблемы. Пользуйтесь этими трюками при создании сложных функций.

Теперь самое время подумать над наполнением функции. В процессе разработки алгоритма мы заметили что он генерирует данные с древовидной структурой. Из предыдущей статьи мы научились мастерски обрабатывать такие данные используя функции со взаимной рекурсией. Напоминаю, для того чтобы обработать древовидные данные нам надо создать две функции. Одна из них оперирует над узлом дерева, который в контексте этой проблемы представляет собой доску, с установленными фигурками или без них. Вторая оперирует над потомками данной доски, которые мы получаем устанавливая фигурки в свободные клетки на данной доске. Первую назовем solveBrd, а вторую solveChilds. Обе эти функции вложим в нашу функцию solve с помощью замыкания, так же закомментируем заглушку за ненадобностью:

// function solve(b){return false}; // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){

  }

  // Ищет решения для списка потомков
  // @param {array of Board} lob
  // @return {Board | false}
  function solveChilds(lob){

  }

  return solveBrd(b);
}

Про замыкания можно почитать в Википедии.

Функция solveBrd принимает доску, которая может поступить из функции solve или из функции solveChilds, потому что мы используем взаимную рекурсию. Поскольку доска поступающая из solveChilds содержит в себе фигурки логично было бы узнать является ли она решением. Поэтому давайте пожелаем чтобы у нас была функция isSolved, которая принимает доску и возвращает true если доска является решением. Если поступившая в функцию solveBrd доска является решением задачи тогда ее надо вернуть, и функция solve завершит свою работу. В противном случае поочередно, для каждой свободной клетки на данной доске, надо поставить фигурку. Из получившегося массива досок надо удалить не валидные доски, так как обрабатывать их и их потомков не имеет смысла потому что они не могут содержать решения. Не валидной является доска на которой одна фигурка атакует другую. Давайте представим процесс формирования данных досок, у не валидных досок красный фон:

Нажмите чтобы проиграть демо

Функцию которая создает массив потомков данной доски и вырезает из него несостоятельные варианты назовем nextBoards. И наконец реализуем все это в виде кода:

function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {arrayof: Board} lob
  function solveChilds(lob){

  }

  return solveBrd(b);
}

И заглушки для нереализованных функций isSolved и nextBoard:

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
// !!!
function isSolved(b){ return false; } // Заглушка

/** Создает массив потомков данной доски
  * Все несостоятельные доски вырезаются
  * @param  {Board} b
  * @return {array of Board}
  */
// !!!
function nextBoards(b){ return []; } // Заглушка

Комментарием // !!! я оставил отметку что функция еще не реализована. Так же мы написали для этих функций заглушки, они позволяют нам иметь в любой момент времени работоспособную программу.

Для того чтобы закончить функцию solve нам осталось поработать над функцией solveChilds. Это классическая рекурсивная функция, которая принимает массив и обрабатывает каждый элемент. Напомню, для того чтобы написать хорошую рекурсивную функцию нам надо поработать над тремя составляющими: базовым случаем, рекурсивным случаем, доказательством того что рекурсивный случай приведет к базовому.

Функция solveChilds очень похожа на функцию map, которую мы реализовали в статье о рекурсии. Она так же принимает массив и обрабатывает каждый элемент. Поэтому базовым случаем, как и в функции map, у нас будет пустой массив. А теперь подумаем что мы вернем в базовом случае. Поскольку функция solveChilds возвращается из solveBrd, которая в свою очередь возвращается из solve, получается что наша функция должна возвращать доску или false. Если мы достигли случая когда в solveChilds передается пустой массив значит у доски нету потомков в которых можно искать решения. Следовательно мы возвращаем false в базовом случае.

В рекурсивном случае нам необходимо узнать имеет ли первая доска в данном массиве потомков решение. Для этого мы передадим первую доску в функцию solveBrd, а не в isSolved. Потому что функция solveBrd будет искать решение не только в переданной доске, но и в ее потомках. Вызывая из функции solveChilds функцию solveBrd мы создаем цикл взаимной рекурсии. Если в первой доске нету решения тогда нам необходимо обработать следующую доску в данном массиве. Для этого уберем первую доску из массива потомков и с полученным массивом рекурсивно вызовем функцию solveChilds.

Вот и все, с функцией solve мы закончили. Эту функцию сложно объяснить на словах, поэтому давайте выразим ее в коде:

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску
  *                         Иначе false
  */
// function solve(b){return false}; // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {array of Board} lob
  // @return {Board | false}
  function solveChilds(lob){
    if(lob.length==0){
      return false; // базовый случай
    }else{
      // рекурсивный случай
      var first = lob[0];
      var rest  = lob.slice(1,lob.length);
      var tryBrd = solveBrd(first);
      if(tryBrd!=false){
        return tryBrd;
      }else{
        return solveChilds(rest);
      }
    }
  }

  return solveBrd(b);
}

У нас еще остались две нереализованные функции: isSolved и nextBoards. Давайте начнем с nextBoards. Она принимает доску и возвращает массив потомков этой доски. Этот массив формируется путем установки одной фигурки во все свободные клетки доски. Еще он должен содержать доски в которых ни один ферзь не атакует другого.

Получается что эта функция должна выполнять сразу два действия: заполнять пустые клетки на доске и фильтровать получившийся список. Давайте разделим эту функцию на две функции. Первая будет заполнять клетки на доске и возвращать массив получившихся досок. Назовем ее fillBlanks. Вторая будет фильтровать получившийся список, оставляя только валидные доски. Ее назовем keepOnlyValid. Поскольку наша функция nextBoards является просто комбинацией двух функций напишем к ней простой тест, который проверяет что комбинация этих функций возвращает тоже, что и nextBoards. Реализуем функцию nextBoards и заглушки для fillBlanks и keepOnlyValid:

/** Создает массив потомков данной доски
  * Все не валидные доски вырезаются
  * @param  {Board} b
  * @return {array.}
  */
  // function nextBoards(b){ return []; } // Заглушка
  function nextBoards(b){
  return keepOnlyValid(fillBlanks(b));
  }

  // Тесты для nextBoards
  (function(){
  console.log("Тест5:", (function(){
  var nb = nextBoards(createEmptyBoard(1));
  var fn = keepOnlyValid(fillBlanks(createEmptyBoard(1)));

  return nb.toString()==fn.toString();
  })());
  })();


  /** Создает массив досок в которых в каждой пустой клетке
  исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array of Board}
  */
  // !!!
  function fillBlanks(b){ return []; } // заглушка

  /** Фильтрует массив досок оставляя только те доски
  в которых ни одна фигурка не атакует другую
  * @param  {array of Board} lob
  * @return {array of Board}
  */
  // !!!
  function keepOnlyValid(lob){ return []; } // заглушка

Напишем функцию fillBlanks. Она довольно сложная, поэтому лучше начать с тестов. Самый простой случай это пустая доска с размерностью n=1. В этом случае наша функция должна вернуть массив который содержит одну доску, в единственной клетке которой должен стоять ферзь. Если мы передадим этой функции доску с размерностью n=1 в клетке которой стоит ферзь, тогда наша функция должна вернуть пустой массив. Если мы передадим функции пустую доску с размерностью n=2 тогда она должна вернуть нам четыре доски: в первой доске ферзь стоит в клетке 1:1, во второй в 1:2, в третьей в 2:1, в четвертой в 2:2. Я думаю нам хватит столько тестов, реализуем их:

// Тесты для fillBlanks
(function(){
  console.log(
    "Тест6:",
    (function(){
      var x = fillBlanks(createEmptyBoard(1));
      return x.length==1 && x[0][0]==Q;
    })());
  console.log("Тест7:", fillBlanks([Q]).length==0);
  console.log(
    "Тест8:",
    (function(){
      var x = fillBlanks(createEmptyBoard(2));
      return x.length==4 &&
        x[0].toString()==[Q,B,B,B].toString() &&
        x[1].toString()==[B,Q,B,B].toString() &&
        x[2].toString()==[B,B,Q,B].toString() &&
        x[3].toString()==[B,B,B,Q].toString()
    })());
})();

Тесты стали немножечко сложнее, но не пугайтесь — функция будет простой. Нам надо пройтись по всем клеткам данной доски, если клетка не содержит фигурку тогда надо ее поставить туда, а данную доску сохранить в результирующем массиве. Если клетка занята тогда мы просто ее игнорируем.

Для удобства так же давайте реализуем функцию которая принимает доску, координаты клетки (ряд и колонку) и значение клетки. В результате функция возвращает доску с установленным значением на клетке с данными координатами. Назовем ее fillSquare.

Реализуем функцию fillBlanks:

/** Создает массив досок в которых в каждой пустой клетке
    исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array of Board}
  */
// function fillBlanks(b){ return []; } // заглушка
function fillBlanks(b){
  // @param {Board}   brd Итерируемая доска
  // @param {Natural} pos Позиция
  function iter(brd, pos){
    if(brd.length==0){
      return []; // базовый случай
    }else{
      var first = brd[0];
      var rest  = brd.slice(1,brd.length);
      if(first!=Q){
        return [fillSquare(b, pos, Q)].concat(iter(rest, pos+1));
      }else{
        return iter(rest, pos+1);
      }
    }
  }

  var clone = b.slice(0, b.length); // Клонируем доску
  return iter(clone, 0);
}

И функцию fillSquare:

/** Ставит на доску в данную позицию данное значение
  * @param {Board}   b Доска
  * @param {Natural} p Позиция
  * @param {Q | B}   v Ферзь или пустая?
  */
function fillSquare(b,p,v){
  var clone = b.slice(0, b.length);
  clone[p]=v;
  return clone;
}

// Тесты для функции fillSquare
(function(){
  console.log("Тест9:",
    fillSquare([B],0,Q).toString()==[Q].toString());
})();

Перейдем к функции keepOnlyValid. Она принимает массив досок и возвращает только те, на которых ни одна фигурка не атакует другую. Получается наша функция выполняет сразу два действия: фильтрует и проверяет на валидность.

Для первого действия в Яваскрипте уже есть встроенная функция filter. Она вызывается у массива и принимает в качестве параметра функцию. В эту функцию поочередно передается каждый элемент данного массива и если она возвращает true то этот элемент будет в результирующем массиве.

Теперь подумаем о второй части нашей функции — проверки валидности доски. Для того чтобы доска считалась валидной ни одна фигурка не должна атаковать другую. Нам надо пробежаться по всем фигуркам на доске и проверить не атакует ли она другую. Фигурка может атаковать по горизонтали, вертикали и диагонали. Довольно сложная логика и она нам пригодится еще в функции isSolved, поэтому для нее напишем отдельную функцию, назовем ее isValid.

Начнем с написания тестов:

(function(){
  console.log("Тест10:",
    keepOnlyValid([[B]]).toString()==[[B]].toString());

  console.log("Тест11:",
    keepOnlyValid([[Q]]).toString()==[[Q]].toString());

  console.log("Тест12:", function(){
    var lob = [
      [Q,Q,B,B],
      [B,Q,Q,B],
      [B,Q,B,Q]
    ];
    return keepOnlyValid(lob).length==0;
  }());
})();

В первых двух тестах передаем валидные доски и проверяем что они вернулись в результате. В последнем передаем список не валидных досок и проверяем что вернулся пустой массив. Перейдем к реализации самой функции и заглушки для функции isValid:

/** Фильтрует массив досок оставляя только те доски
    в которых ни одна фигурка не атакует другую
  * @param  {array of Board} lob
  * @return {array of Board}
  */
//function keepOnlyValid(lob){ return []; } // заглушка
function keepOnlyValid(lob){
  return lob.filter(function(b){ return isValid(b); });
}


/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
function isValid(b){ return false; }

Наша функция вызывает у переданного массива досок функцию filter и передает ей в качестве параметра функцию, которая возвращает значение isValid для каждой доски. Не забываем закомментировать заглушку для keepOnlyValid.

Последняя и самая сложная функция на нашем пути — isValid. Посмотрим на заглушку которую мы написали выше. Наша функция принимает доску и возвращает true если она валидна, в противном случае false. Для того чтобы узнать валидна ли наша доска мы должны пробежаться по каждой фигурке и посмотреть атакует ли она другую. Фигурка может атаковать по горизонтали, диагонали и вертикали. Начнем с написания тестов для всех этих случаев:

// Тесты для функции isValid
(function(){
  // Не валидна если фигурки на одной горизонтали
  console.log("Тест13:", isValid([Q,Q,
                                  B,B])==false);
  // Не валидна если фигурки на одной вертикали
  console.log("Тест14:", isValid([Q,B,
                                  Q,B])==false);
  // Не валидна если фигурки на одной диагонали
  console.log("Тест15:", isValid([Q,B,
                                  B,Q])==false);
  console.log("Тест16:", isValid([B,Q,
                                  Q,B])==false);
  // Валидные доски
  console.log("Тест17:", isValid([Q])==true);
  console.log("Тест18:", isValid(n4emptBrd)==true);
  console.log("Тест19:", isValid(n4solBrd)==true);
})();

Для того чтобы определить атакует ли фигурка другую фигурку нам понадобятся три функции которые выясняли бы что фигурка не атакует по горизонтали, вертикали и диагоали. Назовем их notAttackByHorizontal, notAttackByVertical, notAttackByDiagonal.

Для каждой из этих функций нам важно две вещи: позиция первой фигурки и позиция второй фигурки. Если ряд нашей фигурки совпадает с рядом другой фигурки значит она ее атакует по горизонтали. Если столбец нашей фигурки совпадает со столбцом другой фигурки то она ее атакует по вертикали.

С диагональю немножечко посложнее. Посмотрим на пример:

3 3 6 6

(3−6)÷(3−6)=−1; |−1|=1

Если мы разницу ряда первой фигурки и второй фигурки разделим на разницу их колонок и получим 1 в абсолютном значении тогда они атакуют друг друга по диагонали. Тут надо быть осторожным и проверять атаку по диагонали только после проверки атаки по горизонтали и вертикали, потому что если колонки совпадут тогда мы получим деление на ноль.

И, наконец, для того чтобы определить что фигурка не атакует никакую из других фигурок мы напишем рекурсивную функцию notAttackOthers. Она будет принимать позицию фигурки и массив позиций остальных фигурок и поочередно, используя три функции которые мы описали выше, проверять не атакует ли переданная фигурка кого либо из переданного списка.

Напишем заглушки для этих функций и вложим их внутрь isValid используя замыкание:

function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByHorizontal(pos1, pos2){} // заглушка

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByVertical(pos1, pos2){} // заглушка

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByDiagonal(pos1, pos2){} // заглушка

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  // !!!
  function notAttackOthers(thisPos, othersPos){} // заглушка
}

Поскольку мы имеем дело с плоским массивом нам понадобятся еще две вспомогательные функции которые определяют колонку и столбец по позиции в массиве и размерности доски. Назовем их posToRow и posToCol. Они будут принимать позицию фигурки в массиве и саму доску для определение ее размерности.

Для того чтобы определить ряд нам нужно разделить позицию на размерность доски и результат округлить в меньшую сторону. Для того чтобы определить колонку мы возьмем остаток от деления позиции на размерность доски. А для того чтобы определить размерность доски возьмем квадратный корень из количества клеток, которые она содержит. Реализуем эти вспомогательные функции:

/** Считает размерность доски исходя из количества элементов
  * @param  {Board}   Доска
  * @return {Natural} Размерность доски
  */
function getBoardSize(board){
  return Math.sqrt(board.length);
}

// Тесты для функции getBoardSize
(function(){
  console.log("Тест20:", getBoardSize(n4emptBrd)==4);
})();

/** Переводит позицию фигурки в строку
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Строка на которой стоит фигурка. Zero-base
  */
function posToRow(pos, board){
  // Тут важно округлить в меньшую сторону
  return Math.floor(pos/getBoardSize(board));
}

// Тесты для функции posToRow
(function(){
  console.log("Тест21:", posToRow(1, n4emptBrd)==0);
})();

/** Переводит позицию фигурки в столбец
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Колонка на которой стоит фигурка. Zero-base
  */
function posToCol(pos, board){
  return pos%getBoardSize(board);
}

// Тесты для функции posToCol
(function(){
  console.log("Тест22:", posToCol(5, n4emptBrd)==1);
})();

Вернемся к нашим функциям проверки атаки. Алгоритм для функции проверки атак мы описали выше. А в функции notAttackOthers мы, используя рекурсию, поочередно проверим атакует ли фигурка другие фигурки из переданного массива позиций используя функции проверки атак. Если фигурка атакует какую-либо другую тогда наша функция вернет false. Реализуем их:

function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }
}

Теперь нам надо каким-то образом получить массив позиций всех фигурок на доске и определить что ни одна фигурка на доске не атакует другую.

Начнем с получения массива. Для этого напишем небольшую рекурсивную функцию которая будет проходить по всей доске и сохранять в результирующем массиве позиции фигурок, которые она встретит. Эта функция будет похожа на функцию map, которую мы реализовывали в посте про рекурсию, так что базовый и рекурсивный случай у нее такой же. Назовем ее getFiguresPos. Приступим к реализации:

/** Возвращает массив со всеми позициями фигурок на доске
  * @param  {Integer} curPos Текущая позиция
  * @param  {Board}  board  Доска
  * @return {array of Integer}
  */
function getFiguresPos(curPos, board){
  if(board.length==0){
    return [];
  }else{
    var first = board[0];
    var rest  = board.slice(1, board.length);
    if(first==Q){
      return [curPos].concat(getFiguresPos(curPos+1, rest));
    }else{
      return getFiguresPos(curPos+1, rest);
    }
  }
}

Мы уже близко к развязке. Нам осталось придумать способ как убедится что ни одна фигурка не атакует другую. Давайте подумаем, поскольку все фигурки у нас одинаковые то если одна не атакует ни какую другую, то и никакая другая не может атаковать ее. То есть, если мы проверили одну фигурку с координатами всех других фигурок, то другие фигурки проверять с координатой этой фигурки смысла не имеет. Получается, что мы можем очень удобно организовать данную функцию, давайте назовем ее checkFigures, в рекурсивном стиле:

  1. Берем первую фигурку из маcсива позиций.
  2. Проверяем не атакует ли она позиции в оставшийся части массива используя функцию notAttackOthers.
  3. Рекурсивно вызываем эту же функцию, но с массивом уже без первого элемента.
  4. Возвращаем результаты рекурсивного вызова и вызова функции notAttackOthers объединенные логическим оператором И.

Базовый случай у нас это пустой массив, возвращаем true. В противном случае мы проверяем не атакует ли эта фигурка кого-то еще и рекурсивно вызываем эту же функцию для проверки оставшегося массива. Звучит запутанно, но на деле все просто:

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array of Integer} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

Финальный штрих в функции isValid: вызываем функцию checkFigures с массивом позиций который нам отдает функция getFiguresPos и возвращаем результат. Вот полный вид функции isValid:

/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
//function isValid(b){ return false; }
function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array of Integer} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

  return checkFigures(getFiguresPos(0, b));
}

Вот мы и подобрались к развязке этой истории. У нас осталось не доделана только функция isSolved. Возвращаемся к условию: решением является доска на которой находится количество фигурок равное ее размерности и ни одна фигурка не атакует другую. Для проверки атак у нас уже есть функция isValid, а для проверки количества фигурок на доске можем использовать длинну массива, который возвращает функция getFiguresPos. Наша функция тогда принимает вид:

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
//function isSolved(b){ return false; } // Заглушка
function isSolved(b){
  return isValid(b) && getFiguresPos(0, b).length==getBoardSize(b);
}

(function(){
  console.log("Тест23:", isSolved(n4emptBrd)==false);
  console.log("Тест24:", isSolved(n4solBrd)==true);
})();

Вот и все, если вы подошли к написанию кода с должным вниманием и аккуратностью после запуска программы все тесты должны показывать true, что является признаком того что наша программа работает как и задумывалось. Полная версия исходного кода программы находится в репозитории на Гитхабе.

Запустим поиск для доски с размерностью 4:

  solve(createEmptyBoard(4));

У меня возвращается вот такой массив:

  [false,true,false,false,
   false,false,false,true,
   true,false,false,false,
   false,false,true,false]

Да, это решение. Попробуем поискать решение для доски с размерностью 2, функция должна вернуть false так как для этой доски нет решения:

  solve(createEmptyBoard(2));
  // > false

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

// Тест производительности,
// @param {Natural} startSizeOfBoard Начальный размер доски
// @param {Natural} endSizeOfBoard   Конечный размер доски
// @return {true} Тест закончился
function benchmark(startSizeOfBoard, maxSizeOfBoard){
  if(startSizeOfBoard>maxSizeOfBoard){
    return true;
  }else{
    console.log("Считаем для доски с размерностью:",
      startSizeOfBoard);

    var startTime = Date.now();
    var solution  = solve(createEmptyBoard(startSizeOfBoard));
    var endTime   = Date.now();

    console.log("Решение:", solution.toString());

    console.log("Затраченное время:",
      endTime - startTime, "миллисекунд");

    return benchmark(startSizeOfBoard+1, maxSizeOfBoard);
  }
}

В первый параметр этого теста надо передать интересующий начальный размер доски, во второй конечный размер доски. Тест поищет решение для досок размерность которых находится между переданным начальным размером и конечным. Начальный и конечный размер включены в этот интервал. Он так же посчитает время в миллисекундах, которое он затратил на этот поиск.

Вот мои результаты для досок от 1 до 9 на компьютере МакБук Эйр (1.8 гигагерц «Intel core i5», 4 гигабайта ОЗУ):

benchmark(1,9);

Создавая такие тесты и строя графики на основе их данных мы можем узнать много интересного о задаче и алгоритме. Например, почему для поиска решения для доски с размерностью n=6 тратится 442 миллисекунды, а для доски с размерностью n=7 всего 5? Посмотрим на найденные решения:

Ага, решение доски с размерностью n=7 лежит прямо в первой ветке дерева, потому что ферзь стоит прямо в самой первой клетке. А вот с доской с размерность n=6 нам не повезло и алгоритму пришлось раскрывать больше ветвей дерева. Получается что с ростом размерности доски скорость поиска в нашем алгоритме не будет расти линейно, а что было бы если бы стояла задача найти все возможные решения? Подумайте над этим.

Так же в этих решениях содержится еще одна интересная закономерность: решение доски на 6 клеток как бы вложено в решение доски на 7 клеток. Иначе говоря если мы уберем первую строку и первый столбец из решения доски на 7 элементов мы получим решение для доски на 6 элементов. Забавно, я это заметил уже только когда делал визуализацию.

Заключение

Как мы видим по тестам производительности наш алгоритм не самый быстрый в мире и не позволяет получить ответ по щелчку пальцев. Но что у него не отнять так это то, что он отлично показывает силу деревьев и рекурсии.

С помощью деревьев мы организовали простую и эффективную структуру для хранения наших данных, а рекурсия помогла нам удобно организовать их обработку. Что мне нравится в этой парочке так это то, как одно очень красиво ложится на другое. Как будто это одно и тоже, просто представленное с другого ракурса.

А о методах ускорения поиска по деревьям поговорим в следующих статьях.

13.01.2014
архивирован

Большие идеи в великие компании

Приглашаю вас окунуться в мир капитализма и стартапов вместе со мной, опытным индивидуальным предпринимателем, и курсом «Разработка инновационных идей для новых компаний: первый шаг в предпринимательство» от Мэрилендского университета. Это, конечно, не так интересно, как наше любимое программирование или наука, но все же в обществе, где предприниматели — это новые рок-звезды ☺, эти знания могут быть полезными.

Перевод описания со страницы курса:

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

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

09.12.2013
архивирован

107 лет со дня рождения Грейс Хоппер

9 декабря 1906 года родилась одна из пионеров компьютерной науки, контр-адмирал флота США Грейс Хоппер. Грейс писала программы для одной из первых крупных американских вычислительных машин Марк 1, развила идею машинно-независимых языков программирования в своем языке «Флоу-Матик», который потом стал основой для языка Кобол, и популяризировала то слово, которое снится в самых ужасных кошмарах большинству программистов — дебагинг. Причем один из первых багов имел не логический, а вполне себе физический смысл:

Биографию лучше расскажет Википедия, а я хочу отметить что Грейс обладает отличным чувством юмора, смотрите сами:

лайк
05.12.2013

Социальная экспансия

Сегодня я начинаю свой план социальной экспансии с открытия группы в Вконтакте, страницы в Фейсбуке, канала в Серфингберде, Твиттера, и аккаунта с крутыми технократическими Кобами.

На этих ресурсах не только ссылки на посты из этого блога, но и куча интересного материала который не умещается сюда. Вступайте и подписывайтесь.

Еще одно незаметное изменение — у блога сменился домен с ch-ms.ru на forallx.ru.

Ну и главная мантра интернета: лайк, шейк, репост.

лайк
02.12.2013
архивирован

Учимся разрабатывать приложения для Андроида

К сожалению пока только телефонного. Но все же хочу сообщить вам, что сегодня начинается интересный курс «Креативность, серьезность и увлекательная научность приложений для Андроида» от Иллинойсского университета. Курс подходит даже для людей которые не знакомы с компьютерной наукой и программированием. Для дополнительной мотивации можете ознакомится с тем сколько получают андроид и ява разработчики.

Перевод описания со страницы курса:

Этот курс дружественен новичкам и является восхитительным введением в компьютерную науку и программирование приложений для смартфонов и планшетных компьютеров на базе Андроида. Никакого опыта программирования не требуется. Проходя этот курс вы получите удовольствие от создавания приложений для современных мобильных устройств, таких как планшетный компьютер Нексус.

Вы будете использовать инструменты которые используют разработчики под систему Андроид и создадите полноценные и полезные приложения. Мы так же представим фундаментальные принципы компьютерной науки и идеи программирования которые питают современные смартфоны и планшетные компьютеры.