Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.

Пытаясь запрограммировать алгоритм Литтла (частный случай метода ветвей и границ), я понял, что в рунете крайне трудно найти его правильное описание понятным языком и разобранную программную реализацию. Однако имеющиеся в изобилии описания обманчиво правдоподобны на данных малого размера и с трудом проверяются без визуализации.

Предыстория

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

• Открытый исходный код
• Реал тайм рендеринг мира в игровом движке
• Поддержка основных платформ (mobile, web, desktop)
• Желательно C# как основной язык разработки

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

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

Ладно, хватит завлекалок. Пора удариться в математику.

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

Для простоты, будем рассматривать 2D случай, частицы круглые, радиус частиц у всех одинаковый.

Содержание

1. Обзор алгоритмов
1.1. Полный перебор
1.2. Sweep & Prune
1.3. Регулярная сеть
2. Некоторые оптимизации
2.1. Sweep & Prune
2.2. Регулярная сеть
3. Сравнение скорости выполнения
4. Приложение (программа и исходный код)
5. Заключение

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

Что это ?

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

Иногда полезно представить граф в графической форме, так чтобы была видна структура. Можно привести десятки примеров, где это может пригодиться: визуализация иерархии классов и пакетов исходного кода какой-нибудь программы, визуализация социального графа (тот же Twitter или Facebook) или графа цитирования (какие публикации на кого ссылаются) и т.д. Но вот незадача: количество ребер в графе зачастую настолько велико, что нарисованный граф просто невозможно разобрать. Взгляните на эту картинку:



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

Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Под катом очень-очень много текста, т.к. рассказывается один из вариантов решения данной задачи «в картинках» для тех, кто мало знаком с графами. Листинг прилагается.

Недавно на Хабре была статья, посвященная алгоритмам на графах. С позволения автора, мой первый хабратопик продолжит цикл.

Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.

Это шестая, заключительная часть из серии Hg Init: Учебное пособие по Mercurial от Джоэля Спольски (Joel Spolsky). Предыдущие части:

• «Переобучение для пользователей Subversion»
• «Основы Mercurial»
• «Привыкаем работать в команде»
• «Исправляем ошибки»
• «Процесс слияния»

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

Часть 6. Архитектура репозиториев

Наш рецепт становится все лучше:

Это третья часть из серии Hg Init: Учебное пособие по Mercurial от Джоэля Спольски (Joel Spolsky). Предыдущие части:

• «Переобучение для пользователей Subversion»
• «Основы Mercurial»

Одно из преимуществ использования Mercurial — возможность работать командой над одним кодом. Mercurial позволяет каждому работать независимо и помогает объединять сделанные изменения.

Часть 3. Привыкаем работать в команде

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

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

Вопросы конкурентного доступа к реляционным базам данных встают практически перед любыми разработчиками прикладного программного обеспечения и не только перед ними. Результатом такой востребованности этой области является наличие большого количества созданных архитектурных паттернов. Это позволяет успешно справляться с большой сложностью разработки таких программ. Ниже пойдёт речь о таких рецептах, а также механизмах на которых базируется их реализация. Повествование будет иллюстрироваться примерами кода на Java, но большинство материала не привязано к языку. Цель статьи — описать проблемы конкурентного доступа к реляционным базам данных, в качестве введения в предмет, а не полноценного охвата темы.

У вас никогда не возникало ощущения, что в языке X, на котором вы в данный момент программируете чего-то не хватает? Какой-нибудь небольшой, но приятной плюшки, которая может и не сделала бы вашу жизнь абсолютно счастливой, но определенно добавила бы немало радостных моментов. И вот вы с черной завистью посматриваете на язык Y, в котором эта штуковина есть, грустно вздыхаете и тайком льете по ночам слезы бессилия в любимую подушку. Бывало?

1. Для чего эта статья?

Желание получить возможности Git на Windows платформе материализовало стремление повозиться с разными схемами настройки.

2. Осознание

Нужно осознать, что придется использовать программы Cygwin,SSH,GitExtenstions,Git,Gitolite

Cygwin — это программа, которая эмулирует окружение Linux.У нее есть свое черное окно, выглядящее и работающие как окно терминала Linux.
MsysGit — это программа для эмуляции git окружения, но без ssh сервера, поэтому мы не будем использовать на сервере репозитариев. Используем только для клиентов репозитария.
SSH — это программа для использования ssh подключений из ssh клиентов, доступная для всех операционных систем.
SSH сервер — это программа принимающая подключения от ssh клиентов.
Git — это набор программ, включая сам git, для работы с репозиториями файлов.
Gitolite — это программа, обертывающая git, и реализующая функции управления репозитариями: управление пользователями, их доступом и т.п.
GitExtensions — это программа для windows, обертывающая функционал как git, так прилагающегося набора программ в GUI, который также, встраивается в среду разработки Visual Studio 05/08/10.

В корпоративе придется выделить ресурсы для хостинга SSH службы, дисковое пространство для размещения репозитариев.
Человека, который будет обслуживать SSH сервер, доступ к репозиторию.
Научить пользователей использовать аналоги функций для взаимодействия с их старыми система контроля версий через GitExtensions.
Предложить им некоторые схемы работы, которые позволяет достичь Git.

UPD: 05.08.2011
UPD: 30.01.2012

Перевод статьи Vincent Driessen: A successful Git branching model

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



В качестве инструмента управления версиями всего исходного кода она использует Git.

Распределенные системы контроля версий (DVCS) постепенно замещают собой централизованные. Если вы еще не используете одну из них — самое время попробовать.

В статье я постараюсь показать, как можно быстро начать экспериментировать с git, используя сайт github.com.

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

“Не стоит следовать некоторой идиоме только потому, что так делают все или так где-то написано”

Мысли автора статьи во время чтения и рефакторинга чужого кода

Ни для кого не будет секретом, что платформа .NET поддерживает автоматическое управление памятью. Это значит, что если вы создадите объект с помощью ключевого слова new, то вам не нужно будет самостоятельно заботиться о его освобождении. Сборщик мусора определит «достижимость» объекта, и если на объект не осталось корневых ссылок, то он будет освобожден. Однако, как только речь заходит о ресурсах, таких как сокет, буфер неуправляемой памяти, дескриптор операционной системы и т.д., то сборщик мусора, по большому счету, умывает руки и весь головняк по работе с такими ресурсами ложится на плечи разработчика.

А как же финализаторы? – спросите вы. Ну, да, есть такое дело, финализаторы действительно предназначены для освобождения ресурсов, но проблема в том, что время их вызова не детерминировано, а это значит, что никто не знает, когда они будут вызваны и будут ли вызваны вообще. Да и порядок вызова финализаторов не определен, поэтому при вызове финализатора некоторые «части» вашего объекта уже могут быть «разрушены», поскольку их финализаторы уже были вызваны. В общем, финализаторы – они-то есть, но это скорее «страховочный трос», а не нормальное средство управления ресурсами.

На прошедшей недавно конференции Build кроме уже широко освещенной и обсужденной презентации Windows 8, Metro UI и WinRT было еще немало интересного. В том числе, Дон Сайм и его команда представили developer preview новой, третьей по счету, версии языка программирования F#, который является частью developer preview Visual Studio 11 (и, кстати, уже может быть опробована вами по ссылке).

Ёще один интересный пост от Jimmy Bogard, посвященный cозданию форм для глубоко вложенных View Model в ASP.NET MVC. Несмотря на то, что в нём постоянно идёт отсылка к ASP.NET MVC 2, информация актуальна и для 3-ей версии. Под хабракатом оригинальный пост в вольном переводе.

Недавно пакетный менеджер NuGet для платформы .NET получил очередное обновление до версии 1.5. Ниже перечислены нововведения в новой версии.

Шаблоны проектов с предустановленными пакетами NuGet

Во время создания нового проекта ASP.NET MVC 3 библиотеки jQuery, включенные в шаблон проекта добавляются в проект в качестве пакетов NuGet. Шаблон проекта ASP.NET MVC 3 содержит набор пакетов NuGet, которые устанавливаются каждый раз, когда на базе шаблона создается новый проект. Эта возможность включать пакеты NuGet в шаблоны проектов Visual Studio теперь является встроенной функцией NuGet, что позволяет использовать ее любому типу проекта.

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

В текущее время появляется всё больше high-load проектов оперирующие колоссальным объемом данных. И уже нельзя обойтись классической реляционной моделью хранения этой информации. Всё более популярными становятся NoSQL базы данных (NoSQL — обозначает Not only SQL). Одной из таких баз данных является MongoDB, которая уже заслужила внимание к себе таких компаний как Disney, craiglist, foursquare. К тому же тут неоднократно писали о ней:
NoSQL, используя MongoDB, NoRM и ASP.NET MVC
Шардинг MongoDB на пальцах
Репликация MongoDB на пальцах

Это еще одна статья о работе с MongoDb в среде .net.

Что потребуется:
1. Скачайте (http://www.mongodb.org/downloads), распакуйте и запустите mongod (это сервер)
2. Драйвер (https://github.com/mongodb/mongo-csharp-driver/downloads)
3. Поехали