Оптимизация планирования доставки грузов. Алгоритм кластеризации k-means (метод K-средних).

Публикация № 444787

Разработка - Математика и алгоритмы

логистика маршрут оптимизация карта OpenStreetMap

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

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

Признак, по которому мы собираем одни предметы в одну группу, а другие в другую, называется метрикой. Грубо говоря, метрика – это просто способ отделить один предмет от другого. Самый распространненый вариант – это когда метрикой является расстояние.
Кластеризация (деление на кластеры) может быть и немного другой. Например, если поставить задачу разделить все вещи на четыре кучи (кластера), то при этом наверняка игрушки попадут в одну кучу с книжками или карандашами, т.е перемешаются. Такой метод называется алгоритм кластеризации К-средних, то есть мы заранее задаем количество кластеров, а алгоритм сам разделяет объекты на это количество.

Описание алгоритма кластеризации "для чайников"

Описание  алгоритма кластеризации

Пример работы алгоритма
 

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

В данном случае мы будем работать с точками на плоскости размером 20 на 20 (не важно даже каких единиц).  Например, дано 50 точек, расположенных случайным образом. Нужно распределить эти точки по кластерам алгоритмом К-средних (или K-means).

Действуем так:

Сначала случайным образом выставляем на этой же плоскости несколько центров кластеров, например 4. Центр кластера называется центроидом. Без начального положения центроидов не удастся запустить алгоритм (увидите, почему). Как их расставить – дело ваше, можно самостоятельно вводить координаты, можно применить еще какой-нибудь алгоритм. Далее начинается вычисление кластеров в цикле. Делается это так:

    1. Сначала мы «привязываем» каждую точку к тому центроиду, к которому она ближе, т.к. центроид является центром кластера, то можно сказать, что мы относим каждую точку к тому кластеру, к центру которого она ближе.
    2. Когда все точки привязаны и ни одна от нас не убежала, нужно пересчитать координаты центроидов. Для этого мысленно вписываем весь кластер в прямоугольник и ставим центроид туда, где пересекутся его диагонали (в середину, короче). Квадратики – это центры кластеров. Линии от точек до центров нужны просто для наглядности, чтобы сразу видеть, к какому центру принадлежит точка.
      рисунок 6 
    3. Повторяем для нового центра действия с шага 1 до тех пор, пока центроиды не перестанут менять своего положения. Если они перестали менять положение, значит алгоритм сошелся и мы теперь крутые перцы. Кстати, как правило алгоритм сходится где-то за 2-6 итераций. Но в теории возможно, что алгоритм не сойдется вообще, поэтому на всякий случай нужно включить в него «защиту» – прервать его после например 30 итераций. Это гарантирует, что программа не зависнет.

 

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

Описание алгоритма кластеризации

Для выборки данных, содержащей n записей (объектов), задается число кластеров k , которое должно быть сформировано. Затем алгоритм разбивает все объекты выборки на k разделов (k < n), которые и представляют собой кластеры. 

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

1. Случайным образом выбирается k записей исходной выборки, которые будут служить начальными центрами кластеров μ. Такие начальные точки, из которых потом «вырастает» кластер, часто называют «семенами» (от англ. seeds – семена, посевы). Каждая такая запись будет представлять собой своего рода «эмбрион» кластера, состоящий только из одного элемента.

2. Для каждого центройда формула5 вычислить расстояния формула6 до всех точек формула4

формула7

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

  • Евклидово расстояние или метрика L2

формула17

где формула18 - наборы (векторы) значений признаков двух записей.

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

  • Расстояние Манхэттена (англ.: Manhattan distance) или метрика L1

 формула19

Фактически это кратчайшее расстояние между двумя точками, пройденное по линиям, параллельным осям координатной системы (см рис. ниже).

 рисунок 5

Преимущество метрики L1 заключается в том, что ее использование позволяет снизить влияние аномальных значений на работу алгоритмов. Кластеры, построенные на основе расстояния Манхэттена, стремятся к кубической форме. Иногда расстояние Манхэттена называют «расстояние городских кварталов» (англ.: city-block distance), из-за ассоциаций, возникающих с прямоугольными формами застройки, которая характерна для современных городов.


3. Сформировать кластеры, для каждого центройда формула5 из множества Х отобрать подмножество точек Хк с минимальным расстоянием до  формула5
 формула8
Пример.  Для лучшего понимания методики воспользуемся геометрической интерпретацией определения, к какому из центров кластеров ближе всего расположена та или иная запись. Границей между двумя кластерами является точка, равноудаленная от четырех центров. Из геометрии известно, что множество точек, равноудаленных от двух точек A и B, будут образовывать прямую, перпендикулярную отрезку AB и пересекающую его по середине. Принцип поиска границ будущих кластеров поясняется с помощью рисунке. Для простоты рассматривается 2-мерный случай, когда пространство признаков содержит всего два измерения (X1,X2). Пусть на первом шаге были отобраны три точки A, B и C. Тогда линия 1, проходящая перпендикулярно отрезку AB через его середину, будет состоять из точек, равноудаленных от точек A и B. Аналогично строится прямая 2 для точек A и C, а также прямая 3 для точек B и C. 

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

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

рисунок 1

4. Вычислить новые центроиды как среднее всех точек кластера Хк
формула9
где формула10 - количество точек в кластере К
Например, если в кластер вошли три записи с наборами признаков формула12, то координаты его центроида будут рассчитываться следующим образом:
формула13
Затем старый центр кластера смещается в его центроид. На рисунке центры тяжести кластеров представлены в виде крестиков.
рисунок 2
Таким образом, центроиды становятся новыми центрами кластеров для следующей итерации.

Шаги 3 и 4 повторяются до тех пор, пока выполнение алгоритма не будет прервано либо не будет выполнено условие в соответствии с некоторым критерием сходимости. 

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

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

формула14

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

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

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

Также можно рассмотреть функцию оценки Q качества работы кластеризатора
формула11
 где с - количество кластеров, di - среднее внутрикластерное расстояние, d0 - среднее межкластерное расстояние
Для получения наилучшего результата можно несколько раз выполнить алгоритм кластеризации после чего выбрать результат с наименьшим значением Q.
 рисунок 3
рисунок 4

Свою популярность алгоритм k-means приобрел благодаря следующим свойствам.

Во-первых, это умеренные вычислительные затраты, которые растут линейно с увеличением числа записей исходной выборки данных. Вычислительная сложность алгоритма определяется как k *n *l , где k – число кластеров, n – число записей и l – число итераций. Поскольку k и l заданы, то вычислительные затраты возрастают пропорционально числу записей исходного множества.

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

 

Пример работы алгоритма k-means

Пусть имеется набор из 8 точек данных в двумерном пространстве, из которого требуется получить два кластера. Значения точек приведены в табл. 1 и на рис. 5.

 рисунок 7

Шаг 1. 
Определим число кластеров, на которое требуется разбить исходное множество k=2.

Шаг 2.
Случайным образом выберем две точки, которые будут начальными центрами кластеров. Пусть это будут точки m1=(1;1) и m2=(2;1). На рис. 5 они закрашены черным цветом

Шаг 3. 

Проход 1.
Для каждой точки определим к ней ближайший центр кластера с помощью расстояния Евклида. В табл. 2 представлены вычисленные с помощью формулы формула17 расстояния между центрами кластеров m1=(1;1), m2=(2;1) и каждой точкой исходного множества, а также указано, к какому кластеру принадлежит та или иная точка.
 
 Таблица 2

Таким образом, кластер 1 содержит точки A, E, G, а кластер 2 – точки B, C, D, F, H. Как только определятся члены кластеров, может быть рассчитана сумма квадратичных ошибок:

 формула20

Шаг 4. 

Проход 1.

Для каждого кластера вычисляется его центроид, и центр кластера перемещается в него.

Центроид для кластера 1:  [(1+1+1)/3, (3+2+1)/3] = (1; 2). 

Центроид для кластера 2: [(3 + 4 + 5 + 4 + 2)/5, (3 + 3 + 3 + 2 + 1)/5] = (3,6; 2,4).

Расположение кластеров и центроидов после первого прохода алгоритма представлено на рис. 6.

рисунок 9

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

Шаг 3.

Проход 2.

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

 Таблица 4

Относительно большое изменение m2 привело к тому, что запись H оказалась ближе к центру m1, что автоматически сделало ее членом кластера 1. Все остальные записи остались в тех же кластерах, что и на предыдущем проходе алгоритма. Таким образом, кластер 1 будет A, E, G, H, а кластер 2 – B, C, D, F. Новая сумма квадратов ошибок составит:

формула21

,что показывает уменьшение ошибки относительно начального состояния центров кластеров (которая на первом проходе составляла 36). Это говорит об улучшении качества кластеризации,т.е. более высокую «кучность» объектов относительно центра кластера.

Шаг 4.

Проход 2.

Для каждого кластера вновь вычисляется его центроид, и центр кластера перемещается в него.

Новый центроид для 1-го кластера:  [(1+1+1+2)/4, (3+2+1+1)/4]=(1.25, 1.75).

Центроид для кластера 2: [(3 + 4 + 5 + 4)/4, (3 + 3 + 2 + 4)/4] = (4, 2.75).

Расположение кластеров и центроидов после второго прохода алгоритма представлено на рис. 7.

 рисунок 10

По сравнению предыдущим проходом центры кластеров изменились незначительно.

Шаг 3.

Проход 3.

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

Таблица 5

 

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

формула22

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

Шаг 4.

Проход 3.

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

 
Итоговое распределение на кластеры смотрите на рис. 7.
 
Итак, в этой статье  было показано, КАК ПОЛУЧИТЬ ОПТИМАЛЬНЫЕ МАРШРУТЫ ДЛЯ ЗАДАННОГО КОЛИЧЕСТВА А/ТРАНСПОРТА из указанного места отгрузки, при этом грузоподъемность транспорта не принималась во внимание. 
 
В следущей статье "Метод Кларка-Райта. Оптимальное планирование маршрутов грузоперевозок"  будет показано КАК УЗНАТЬ КОЛИЧЕСТВО НЕОБХОДИМОГО А/ТРАНСПОРТА С УЧЕТОМ ЕГО ГРУЗОПОДЪЕМНОСТИ ДЛЯ ФОРМИРОВАНИЯ ОПТИМАЛЬНЫХ МАРШРУТОВ.
 
 

Описанный метод используется в программе "Простое формирование маршрутов. Работа с картой. Расчет оптимальных вариантов доставки" 

 

Специальные предложения

Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. V.Nikonov 119 10.02.16 14:39 Сейчас в теме
Есть встроенная в 1с8 Функция Кластеризации. Я всё никак не дождусь хорошего (практического) примера использования данной функции. Начал было сам двигаться, да не хватило свободного времени и заинтересованности заказчика...
В базе УТ10 хранились в виде свойств географические координаты... Там ещё эпопея была с Широтой/Долготой Торговой точки с форматом Число(14, 11) проблема была - решили. Отображение точек на карте получали...
Оставалось сделать кластеризацию по Координатам и Типам торговых точек (СвойствоОбъектов) обсчитать... И на выходе получить оптимизированный График доставки...
Леонов Александр; +1 Ответить
2. kapustinag 10.02.16 15:29 Сейчас в теме
(0) Он интерактивный, то есть повторяется несколько раз, пока не «сойдется».

Думаю, не "интерактивный", а "ИТЕРАТИВНЫЙ". Чаще употребляется "ИТЕРАЦИОННЫЙ".
cleaner_it; +1 Ответить
3. mi1man 240 10.02.16 15:51 Сейчас в теме
(2) kapustinag, спасибо .. поправил
Оставьте свое сообщение

См. также

Автоматические и управляемые блокировки применительно к типовым конфигурациям 1С Промо

Математика и алгоритмы Практика программирования v8 v8::blocking 1cv8.cf Бесплатно (free)

Основные принципы работы с режимами автоматических и управляемых блокировок в 1С Предприятие 8. Теория и применение в типовых конфигурациях: БП, УТ, ЕРП

10.11.2018    34638    ids79    40    

Партионный учет по двум количественным показателям

Математика и алгоритмы Учет ТМЦ v8 1cv8.cf Оптовая торговля, дистрибуция, логистика Россия УУ Бесплатно (free)

Особенности учета партионной системы при наличии двух количественных показателей.

26.03.2020    3345    lastcontra    4    

Treemapping — способ визуализации данных древовидной структуры. Карта-схема дерева

Математика и алгоритмы Работа с интерфейсом v8 1cv8.cf Бесплатно (free)

Предлагается ознакомиться с редким способом графического представления иерархических данных. Приводится алгоритм формирования и пример реализации.

18.02.2020    4775    randomus    18    

[После]Новогодние задачи

Практика программирования Математика и алгоритмы v8 Бесплатно (free)

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

30.12.2019    3054    Alxby    23    

Как работает серверный вызов в 1С Промо

Математика и алгоритмы v8::УФ Бесплатно (free)

Клиент-серверная архитектура заложена в платформе изначально — со времен «1С:Предприятие 8.0». Однако при разработке на 8.0 и 8.1 о разделении кода на клиентскую и серверную часть можно было не заботиться, поскольку на клиенте (на толстом клиенте) был доступен тот же функционал, что и на сервере. Всё изменилось с выходом платформы «1С:Предприятие 8.2», когда появился тонкий клиент. Теперь на клиенте доступен один функционал, на сервере — другой. Клиент и сервер «общаются» между собой с помощью серверного вызова. Конечно, это усложнило процесс разработки, но с другой стороны – можно создавать более оптимальные (быстрые) решения, поскольку все сложные задачи выполняются на сервере.

18.11.2017    55807    pahich    82    

Регистры бухгалтерии. Общая информация

Практика программирования Математика и алгоритмы v8 v8::БУ БУ Бесплатно (free)

Общая информация о внутреннем устройстве регистров бухгалтерии.

05.09.2019    28114    YPermitin    24    

"Хочу универсально!" [Часть 1]

Математика и алгоритмы Практика программирования Разработка v8 1cv8.cf Бесплатно (free)

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

02.09.2019    9808    SeiOkami    35    

Иерархия без "В ИЕРАРХИИ"

Математика и алгоритмы v8 Бесплатно (free)

Говорится о том, как эффективно представлять иерархию в СУБД, как получать и использовать эти представления при решении задач в запросной технике. Уточняются и дополняются запросы из статьи "Уровни, глубина, прародители, циклы и аналоги запросом" [https://infostart.ru/public/160707/].

22.08.2019    12331    ildarovich    19    

Будни автоматизации или "мне нужна программка для 3D упаковки" Промо

Практика программирования Математика и алгоритмы Оптовая торговля Оптовая торговля v8 1cv8.cf УУ Бесплатно (free)

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

24.03.2014    45264    ildarovich    116    

EnterpriseData – часть 3. Загрузка данных, идентификация объектов

Практика программирования Математика и алгоритмы Перенос данных из 1C8 в 1C8 Разработка v8 v8::УФ 1cv8.cf Бесплатно (free)

Основные этапы загрузки данных через EnterpriseData. Идентификация объектов загружаемых полностью и по ссылке. Приведены схемы процессов загрузки данных. Описание основных операций и обработчиков. Перечень процедур БСП, используемых при загрузке данных, структура «КомпонентыОбмена».

22.08.2019    14875    ids79    8    

Обработчики событий при записи объектов. Зачем и что за чем?

Математика и алгоритмы v8 Бесплатно (free)

Программисту, имеющему немного опыта на платформе 1С 8.3, бывает сложно разобраться: ПередЗаписью, ПриЗаписи, ПослеЗаписи, на сервере, на клиенте, в модуле формы, в модуле объекта.... Эта шпаргалка была создана в процессе обучения и реального опыта с целью разложить всё по полочкам, чтобы было четкое понимание в каком случае какой обработчик нужно использовать и в какой последовательности они запускаются при записи и проведении документов. Данная статья будет полезна в большей степени начинающим разработчикам. Но и опытным позволит освежить информацию, упорядочить её.

25.07.2019    49834    AlbinaAAA    28    

Как проводятся документы в типовых конфигурациях от 1С

Математика и алгоритмы Практика программирования Разработка v8::ОУ ERP2 УТ11 Россия УУ Бесплатно (free)

В свое время, когда только начинал шаги в 1С и изучал, как проводятся документы в конфигурациях на платформе 1С по книге "Разработка управляемого интерфейса" (Хрусталева Е.Ю.), и там были представлены примеры совсем далекие от того, как сейчас проводятся документы в современных конфигурациях от 1С.

24.07.2019    27341    skv_79    35    

Приемы обработки больших данных в 1С Промо

Универсальные обработки Математика и алгоритмы Перенос данных из 1C8 в 1C8 v8 1cv8.cf Бесплатно (free)

Рассказ об эффективных приемах организации обработок больших объемов данных на платформе 1С

07.08.2015    67045    tormozit    27    

FizzBuzz на 1С. Чем короче, тем веселее. Варианты принимаются...

Практика программирования Математика и алгоритмы Разработка v8 Бесплатно (free)

Мне было скучно, я не мог себя заставить написать ничего полезного. И читал статью на Хабре. Потом я читал комментарии, а потом... нет я не ушел смотреть котиков на ютюбе. Я решил сделать несколько решений задачки FizzBuzz на 1С, с целью "чем короче, тем лучше". Прошу сильно не пинать, это просто развлечение для вечера.

24.07.2019    5430    vandalsvq    16    

Управление качеством кода

Математика и алгоритмы Рефакторинг и качество кода v8 Бесплатно (free)

О SonarQube, АПК, EDT. Какие преимущества дает их использование. Для каких команд подходит.

22.07.2019    16392    Stepa86    33    

Что делает "В ИЕРАРХИИ" в запросе?

Математика и алгоритмы v8 Бесплатно (free)

Описание действий платформы 1С при использовании конструкции "В ИЕРАРХИИ" в запросах.

16.07.2019    26282    YPermitin    34    

XDTO - это просто Промо

Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

С появлением платформы 8.1 фирма “1С” представила механизм, носящий интригующее название XML Data Transfer Objects или, если коротко - XDTO. По традиции, документирование механизма составлял тот, кто хорошо разбирался в вопросе, а стало быть опустил “и так понятные” с его точки зрения моменты. Целью данной статьи (или цикла статей, как получится) стало желание поделиться накопленным опытом. Мне кажется, многие неочевидные вещи в механизме XDTO необходимо осветить получше.

24.12.2012    293621    Evil Beaver    173    

Создание отчетов с помощью СКД - основные понятия и элементы

Практика программирования Математика и алгоритмы v8 v8::СКД Бесплатно (free)

Основные принципы работы СКД. Понятия схемы компоновки и макета компоновки. Описание основных элементов схемы компоновки: наборы данных, поля, вычисляемые поля, ресурсы, параметры.

25.06.2019    52108    ids79    25    

Реализуем Стек, Очередь и Приоритетную очередь в 1С

Практика программирования Математика и алгоритмы v8 1cv8.cf Россия Бесплатно (free)

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

24.06.2019    14095    RonX01    65    

Почему вообще работает мой запрос? или Ещё раз о планах запросов

Математика и алгоритмы Практика программирования Разработка v8::Запросы Бесплатно (free)

Другие статьи на эту тему объясняют, что такое план выполнения запроса, но не рассказывают о том, как его получить. Эта заметка призвана заполнить этот пробел. Её цель - популяризировать общедоступные инструменты получения плана запроса среди разработчиков, которые ещё не начали их использовать.

10.06.2019    9368    DataReducer    12    

Самоучитель языка запросов 1С. Промо

Практика программирования Решение задач на 1С:Специалист Математика и алгоритмы v8 v8::Запросы Бесплатно (free)

Сервис для изучения запросов 1С: "Консоль изучения запросов 1С:Предприятие 8". Теперь и с конструктором запросов!

07.05.2013    109950    bpc222    327    

Организация хранения промежуточных данных

Математика и алгоритмы v8 Бесплатно (free)

Организация хранения промежуточных данных в процедуре сверки.

29.05.2019    4202    scientes    1    

Вычисление 200 тысяч знаков числа pi

Математика и алгоритмы v8 Россия Бесплатно (free)

В статье рассматриваются возможности платформы выполнять сверхточные вычисления без использования сложных алгоритмов и внешних компонент на примере вычисления числа pi.

28.05.2019    7887    Oleg_nsk    96    

Регистры накопления. Виртуальные таблицы. Часть №1: Обороты

Практика программирования Математика и алгоритмы Разработка v8 1cv8.cf Бесплатно (free)

Описание работы платформы 1С:Предприятие 8.2 с виртуальной таблицей "Обороты" регистров накопления.

20.05.2019    27295    YPermitin    7    

Решение транспортной задачи запросом Промо

Математика и алгоритмы v8 Бесплатно (free)

Списание по двум последовательностям партий запросом (без программной обработки)

1 стартмани

30.04.2014    35019    bforce    22    

Даем названия переменным: как префиксы экономят наше время

Практика программирования Математика и алгоритмы Разработка v8 Бесплатно (free)

Понятные названия переменных экономят время и силы разработчика : в начале, когда мы даём названия переменным, в процессе развития разработки, когда мы "на лету" понимаем назначение той или иной переменной, в конце, когда мы передаём разработку на поддержку других программистов, сами переходя к новым разработкам

06.05.2019    6927    Designer1C    81    

Заметки по SQL: Срез последних - аналог запроса

Математика и алгоритмы Практика программирования v8 1cv8.cf Россия Бесплатно (free)

В статье описывается создание среза последних данных средствами классического языка запросов. Причем метод построения запроса был разработан еще во времена, когда автор работал с СУБД Oracle 9i и программировал на PL SQL. Основная идея заключается преобразовании запроса с подзапросом, в запрос без подзапроса (в примерах описывается преобразование до двух вложенных подзапросов). Запросы тестировались на реальных базах данных. Платформа - 1С:Предприятие 8.3 (8.3.10.2561).

15.01.2019    11690    IVC_goal    7    

Парсер запросов 1С. Часть 1: Введение, разбор математических выражений Промо

Математика и алгоритмы v8 Бесплатно (free)

Рано или поздно становится скучно решать типичные задачи, для которых придумана 1С. Голова пухнет от бухгалтерских терминов и очередных "хотелок" пользователей. Именно в такие моменты хочется гордо поднять голову, воскликнуть "Но я же программист!" и заняться чем-то интересным. В цикле статей я постараюсь доступно описать, как устроены парсеры в целом и на примере парсера языка запросов 1С. Требования к навыкам читающего: основы языка 1С, основы алгоритмизации.

1 стартмани

04.12.2013    30713    juntatalor    49    

Многопоточное восстановление последовательностей

Производительность и оптимизация (HighLoad) Практика программирования Математика и алгоритмы Универсальные функции v8 Бесплатно (free)

Универсальный алгоритм многопоточного фонового восстановления любой последовательности.

05.12.2018    13195    _ASZ_    33    

Основные понятия и механизмы оптимизации клиент-серверного взаимодействия в 1C

Математика и алгоритмы Практика программирования v8 Россия Бесплатно (free)

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

23.08.2018    38423    Rain88    46    

Теорема номер тринадцать

Математика и алгоритмы v8 Бесплатно (free)

Использование математических методов для языка запросов.

15.03.2018    12111    vasilev2015    24    

Сервис для изучения методов платформы 1С:Предприятие 8. Бесплатно! Промо

Практика программирования Решение задач на 1С:Специалист Математика и алгоритмы v8 Бесплатно (free)

Бесплатный ON-Line сервис изучения методов платформы 1С:Предприятие 8. Подготовка к аттестации 1С:Специалист on-line! Тестовые задания по различным видам учета! Подсказки для оптимального решения!

27.06.2013    50034    bpc222    52    

"Взлом" теста "1С:Профессионал" методом машинного обучения

Практика программирования Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

Нейронные сети – не единственная модель, реализующая принципы машинного обучения. Есть еще байесовская модель, которая математически строже и определеннее, поскольку построена на надежном фундаменте теории вероятностей. Применению байесовского вывода к решению интересной теоретической задачи и посвящена данная статья. Слово "взлом" в заголовке использовано для привлечения внимания. Речь идет исключительно о математическом методе, показанном на примере знакомой всем задачи. 

12.03.2018    19162    ildarovich    19    

Введение в CI для 1С

Математика и алгоритмы v8 Россия Бесплатно (free)

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

21.11.2017    23654    real_MaxA    22    

#Область ВНЕШНИЕ_ВЫЗОВЫ или MVC в 1С, библиотечность и упрощение интеграции кода

Практика программирования Математика и алгоритмы Универсальные функции v8 Бесплатно (free)

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

12.10.2017    17942    for_sale    58    

v8: Концепция минимального изменения конфигурации для легкого обновления Промо

Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

"Лучше день потерять потом за пять минут долететь" ((с) "Крылья, ноги и хвосты") или как сделать так чтобы обновление конфигурации проходило с минимальными трудозатратами.

28.01.2013    38102    MarSeN    57    

Пишем игру Минер. Обработка событий ActiveX в 1С

Практика программирования Математика и алгоритмы v8 Россия Бесплатно (free)

Пример демонстрирует обработку событий генерируемых компонентой ActiveX в 1С.

29.05.2017    14774    user621724_Dimav1979    12    

Как я доступ на kb.1c.ru получал

Решение задач на 1С:Специалист Математика и алгоритмы v8 Россия Бесплатно (free)

kb.1c - база знаний по технологическим вопросам крупных внедрений и не только. В этой базе знаний собираются методики и решения технологических проблем эксплуатации 1с, check-list'ы и инструкции по настройке ПО на серверах. Какие-то из размещенных статей дублируются на ИТС. Когда я искал пути получения доступа к нему я столкнулся с проблемой: мало кто доподлинно знает как получить доступ к нему, не работая у франчайзи 1с. Я опишу путь, который прошёл я, как физическое лицо.

01.05.2017    26240    ikekoval    34    

Улучшение стандарта "Структура модуля"

Математика и алгоритмы v8 1cv8.cf Россия Бесплатно (free)

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

26.03.2017    14441    o.nikolaev    23    

Пример выбора несколько обработчиков событий записи объекта для решения одной задачи Промо

Математика и алгоритмы v8 Бесплатно (free)

Данная публикация предназначена для начинающих разработчиков и является продолжением статьи "Обработчики событий при записи объектов. Зачем и что за чем?" (ссылка далее). Содержит пример использования несколько обработчиков событий для решения одной задачи и объясняется почему выбраны именно они.

27.09.2012    194770    AlbinaAAA    65    

"Распределение в запросе" или "избавляемся от перебора"

Математика и алгоритмы Универсальные функции v8 1cv8.cf Россия Бесплатно (free)

Хороший перебор - это отсутствие перебора. Рассмотрим пример замены полного перебора запросом.

16.12.2016    33855    alexandersh    48    

Планы обмена. Квитировать или гарантировать?

Практика программирования Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

Планы обмена предлагают использовать две стратегии удаления обработанных изменений: квитирование и гарантированная доставка сообщений. Как сделать правильный выбор?

12.12.2016    17275    zhichkin    9    

Некоторые принципы оптимизации запросов 1С (+SQL)

Математика и алгоритмы v8 Бесплатно (free)

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

17.11.2016    10814    ture    40    

Альтернативные способы работы с XML. Часть 2: Введение в xPath или запросы к XML Промо

Обмен через XML Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

В предыдущей статье "Введение в DOM или объектная модель документа" было описано понятие объектной модели документа (DOM), раскрыты плюсы и минусы использования модели при разборе файлов XML, приведено сравнение с построчным последовательным разбором. Были представлены варианты выборки данных с помощью объекта 1С ДокументDOM. Теперь настало время познакомить читателей с самым, на мой взгляд, интересным способом извлечения данных из XML - при помощи языка запросов xPath.

09.08.2012    42155    1cspecialist    13    

Использование git для доработки типовых конфигураций 1С

Математика и алгоритмы v8 Беларусь Украина Россия Бесплатно (free)

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

11.10.2016    207427    pumbaE    31    

Оптимизация запросов 1С:Предприятие – от теории к практике

Практика программирования Математика и алгоритмы v8 Бесплатно (free)

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

07.10.2016    38097    bpc222    20    

Регистры сведений 1С. Как это устроено.

Математика и алгоритмы v8 Бесплатно (free)

Основная идея публикации - собрать в одном месте информацию о внутреннем устройстве такой абстрактной сущности, как "Регистр сведений 1С" и ответить на ряд вопросов: Что происходит при записи регистра в различных режимах? Что такое на самом деле "СрезПервых" и "СрезПоследних"? Как оптимально выбрать структуру регистра? Это та информация, владея которой, начинаешь лучше понимать как это работает и как правильно использовать регистры сведений.

05.08.2016    187239    Sergey.Noskov    156    

От Hello world - к защите конфигураций за 1 минуту Промо

Защита и шифрование Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

Вы всегда хотели но боялись создать COM объект? Тогда мы идем к вам! С обычным блокнотом, где будем программировать на c#, и таймером ...

19.05.2012    34945    O-Planet    130    

Переводим расширения на 8.3.8. Памятка.

Практика программирования Математика и алгоритмы v8 Россия Бесплатно (free)

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

29.07.2016    47277    mrXoxot    12    

Подобие Объектно-ориентированного программирования в 1С (ПООПс)

Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

Статья для тех кто знаком с ООП и опустил руки.

24.07.2016    12558    adam26    54