Алгоритмы. Часть 1.1. Динамические соединения.

04.04.14

Разработка - Работа с интерфейсом

Конспект первой лекции из свежего курса Принстонского университета США за 2014 год.
Вольный перевод с английского с реализацией примеров на 1С.
Курс в целом достаточно интересный и полезный для общего развития.
Перевел и адаптировал только первую лекцию (в 1 части 11 лекций, 2 часть - еще не завершена преподавателями).
Первоисточник на английском - https://www.coursera.org/course/algs4partI.
Если сообщество посчитает материал полезным - займусь переводом следующих лекций (но это довольно трудоемко).
Enjoy! :)

Скачать файлы

Наименование Файл Версия Размер
Выгрузка информационной базы с примерами
.dt 279,44Kb
25
.dt 279,44Kb 25 Скачать

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

«Я считаю, что разница между плохим и хорошим программистом в том – считает ли он свой код или структуры данных более важными. Плохой программист заботится о коде. Хороший программист – о структуре данных и их взаимосвязях».
Линус Торвальдс

«Алгоритмы + структуры данных = программы».
Никлаус Вирт

 

Зачем изучать алгоритмы?

  1. Они имеют очень широкое распространение и влияние.
  2. Имеют глубокие корни и предоставляют широкие возможности.
  3. Помогают решить проблемы, которые не могут быть решены иным путем.
  4. Помогают стать хорошим программистом.
  5. Они могут раскрыть секреты жизни и вселенной.
  6. Для саморазвития, интеллектуальной стимуляции и хорошего заработка.

Лекция 1. Соединение-поиск.

Порядок преподнесения материала в лекциях:

  1. Сформулировать проблему/задачу.
  2. Найти алгоритм решения
  3. Достаточно ли он быстр? Достаточно ли памяти?
  4. Если нет – понять почему.
  5. Найти пути оптимизации.
  6. Повторить пока не будем удовлетворены результатом.

Так называемый Научный метод

Динамические соединения.

Допустим мы имеем массив из N объектов, а также 2 команды:
1. Процедура Объединить – создает соединение между двумя объектами.
2. Функция ОбъектыСоединены – проверяет наличие пути, который объединяет 2 объекта.

 

Пример задачи: существует ли путь, соединяющий точки p и q?
(поиск конкретного пути в данной лекции не рассматривается!)

Будем считать, что тезис «объект p соединен с объектом q» включает в себя следующие утверждения:

  • p соединен с p, т.е. объединен сам с собой;
  • если p соединен с q, то q соединен c p;
  • если p соединен с q и q соединен с r, то p соединен с r.

Коллекция соединенных объектов – перечень всех объектов, объединенных в единую сеть.

Таким образом, операция проверки наличия пути между объектами сводится к проверке принадлежности 2 объектов одной коллекции. А операция объединения объектов – к объединению двух коллекций.

 

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

1 методика. Быстрый поиск.

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

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

Например:

представлены 3 коллекции:

  • 0, 5 и 6 – коллекция с индексом 0
  • 1, 2 и 7 – коллекция с индексом 1
  • 3, 4, 8 и 9 – коллекция с индексом 8

Логика работы операций:

ОбъектыСоединены(p, q) – проверить равенство идентификаторов у элементов с индексами p и q. Если идентификаторы равны – объекты соединены, иначе – нет.

Объединить(p, q) – объединить 2 коллекции – заменить у всех элементов идентификаторы q на p.

Например, выполним объединение объектов 6 и 1 (помимо 6 необходимо переподчинить объекты 0 и 5, т.к. они были связаны с 6):

И сразу видим проблему – пришлось изменить идентификаторы у большого числа объектов.

Затраты. Число операций чтения и записи для массива размером N:

Алгоритм

Инициализация

Объединение

Проверка соединения объектов

Быстрый поиск

N

N

1

 

При этом операция объединения слишком затратная. Она требует N^2 доступов к массиву для выполнения последовательности из N команд для N объектов.

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

Грубый пример: процессор выполняет 10^9 операций в секунду, для доступа к 10^9 объектам в памяти требуется 1 секунда. Но для выполнения 10^9 команд объединения по алгоритму быстрого поиска потребуется более 10^18 операций. Более 30 лет компьютерного времени.
Можно взять компьютер в 10 раз более производительный, но в 10 раз большая задача будет решаться в 10 раз медленнее!

Реализация в 1С:

См. обработку «БыстрыйПоиск»

2 методика. Быстрое объединение.

Алгоритм, который обеспечит максимально быстрое объединение двух объектов.

В этом случае изменим схему хранения связей - в значениях массива будут храниться индексы ближайших связанных объектов: id[i] это родитель для i.
А для вычисления корня потребуется рекурсия id[id[id[...id[i]...]]]

Логика работы операций:

ОбъектыСоединены(p, q) – проверить что элементы с индексами p и q имеют один и тот же корень.

Объединить(p, q) – добавить корневой элемент первой коллекции к корневому элементу второй коллекции.

Например, выполним объединение объектов 3 и 5:

Затраты. Число операций чтения и записи для массива размером N:

Алгоритм

Инициализация

Объединение

Проверка соединения объектов

Быстрый поиск

N

N

1

Быстрое объединение (худший вариант)

N

N

N

 

Дефекты быстрого поиска:

  • Объединение слишком затратно
  • Деревья плоские, но слишком затратно поддерживать их таковыми

Дефекты быстрого объединения:

  • Деревья бывают очень высокими
  • Поиск слишком затратен.

Реализация в 1С:

См. обработку «БыстроеОбъединение»

 

Первое улучшение. Оценка веса.

Быстрое объединение с оценкой веса деревьев:

  1. Изменить предыдущий алгоритм там, чтобы избегать высоких деревьев.
  2. В отдельной структуре хранить размеры каждого дерева
  3. При объединении деревьев всегда присоединять малое дерево к корню большого (метрика рассчитывается исходя из числа узлов в дереве).

Пример результатов работы обоих методов:

Скорость выполнения операций объединения и проверки соединения в данном случае пропорциональна длине веток. Длина веток при этом не превосходит lg N.

Затраты. Число операций чтения и записи для массива размером N:

Алгоритм

Инициализация

Объединение

Проверка соединения объектов

Быстрый поиск

N

N

1

Быстрое объединение

N

N

N

Быстрое объединение с оценкой веса

N

lg N

lg N

 

Реализация в 1С:

См. обработку «БыстроеОбъединениеСОценкойВеса»

Второе улучшение. Сжатие пути.

Быстрое объединение со сжатием пути:

  1. При каждом вычислении корня выполним привязку всех глубоко вложенных объектов к корню.
  2. Это потребует только 1 дополнительную строку кода!

Например, для данного дерева при вычислении корня для объекта номер 9 будет выполнен перенос объектов 9, 6 и 3 к верхнему уровню.

Исходное дерево:

Результат:

На практике – нет причин не использовать этот метод. Он позволяет поддерживать дерево плоским.

Реализация в 1С:

См. обработку «БыстроеОбъединениеСоСжатиемПути»

Финальный вариант. Быстрое объединение с оценкой веса и сжатием пути.

Утверждение (Hopcroft-Ulman, Tarjan): начиная с пустой структуры данных любая последовательность операций объединения-поиска M для N объектов потребует =< c ( N + M lg* N ) числа доступов к массиву.

Где ln*N:

Итог.

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

Алгоритм

Максимальное время выполнения (максимальное число доступов к массиву)

Быстрый поиск

M N

Быстрое объединение

M N

Быстрое объединение с оценкой веса

N + M log N

Быстрое объединение со сжатием пути

N + M log N

Быстрое объединение с оценкой веса и сжатием пути

N + M lg* N

Где M – число операций объединения и проверки соединения для массива из N-объектов.

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

Графики времени выполнения алгоритмов в 1С.
Все 5 вариантов:

Без 1 и 2 варианта:

Пример применения алгоритма – вычисление проницаемости структуры.

Модель для множества физических систем:

  1. Фигура размером N*N из объектов
  2. Каждый объект является либо открытым (проницаемым) с вероятностью p, либо закрытым (непроницаемым) с вероятностью 1-p.
  3. Система проницаема только в том случае, если любой объект из верхнего ряда соединен с любым объектом из нижнего ряда

Зависимость проницаемости структуры от вероятности проницаемости каждого объекта (p).

При большом числе N теория гарантирует наличие четкого порога p*, при котором:

  • если p > p* - структура почти наверняка проницаема
  • если p < p* - структура почти наверняка непроницаема.

p* получено путем симуляции на больших массивах данных и не доказано математически:

Симуляция по методу Монте-Карло для вычисления p*.

http://ru.wikipedia.org/wiki/%CC%E5%F2%EE%E4_%CC%EE%ED%F2%E5-%CA%E0%F0%EB%EE

  1. Создать структуру N*N из закрытых клеток.
  2. Последовательно и случайно открывать закрытые клетки до тех пор, пока верхний ряд не будет соединен с нижним рядом.
  3. Процент открытых клеток даст значение p*

Применение алгоритма динамических соединений для определения проницаемости структуры.

1)      Создать структуру N*N и последовательно определить для каждой клетки элемент в массиве:

2)      Выполнить объединение соседних открытых клеток:

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

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

Во вложенной конфигурации 1С приведена реализация данного подхода.


P.S. - если обнаружите нестыковки, ошибки - пишите в комментариях, я поправлю.

См. также

Богатый редактор картинок, хранимых в базе, с возможностью РИСОВАНИЯ. Редактор внешних файлов картинок. Объект, расширяющий возможности работы с картинками из встроенного языка (Три в одном) + Обработка «Стандартизация картинок»

Работа с интерфейсом Рабочее место Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Платные (руб)

Обработка предназначена для редактирования картинок в режиме «Предприятие», с возможностью РИСОВАТЬ на них. Поддерживается работа как в обычных формах (толстый клиент) так и на управляемых формах (тонкий клиент). Обработка позволяет редактировать как картинки, хранимые в базе, так и графические файлы с диска на файловой системе. Помимо базовых функций (изменение размеров, преобразование формата, обрезание картинки, повороты и т.п.) – редактор имеет богатый набор инструментов для рисования. Доступна функция вставки изображения из буфера обмена. Также обработка может быть использована из встроенного языка как объект для редактирования картинок. Объект может быть использован: на стороне клиента, на стороне сервера, из внешнего соединения. Данная обработка будет особенно полезна тем, кто вносит картинки в базу (изображения номенклатуры, фотографии физических лиц и т.п.). Функционал реализуется с использованием JavaScript и бесплатного ПО ImageMagick (без использования внешних компонент).

6000 руб.

16.01.2015    61698    43    59    

80

[Расширения] Динамическое управление видимостью и доступностью элементов форм (УФ) (8.3.6+)

Работа с интерфейсом Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Платные (руб)

Механизм «Динамическое управление доступом к элементам форм объектов 1С8» предназначен для обеспечения возможности оперативного управления видимостью и доступностью элементов форм документов и справочников продуктов фирмы «1С» «1С:Предприятие 8». Решение универсальное, встраивается в любую конфигурацию с минимальными доработками, что позволяет без проблем обновлять типовые решения.

5000 руб.

14.01.2016    54313    16    21    

42

Управление дашбордами

Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

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

2400 руб.

29.06.2020    16623    21    4    

35

Новогоднее оформление для 1С

Работа с интерфейсом Платформа 1С v8.3 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Зарплата и Управление Персоналом 3.x 1С:Управление нашей фирмой 3.0 Бесплатно (free)

Добавьте новогоднего настроения! Расширение создает декорацию в виде гирлянды на некоторых формах объектов.

27.12.2023    10563    745    elcoan    45    

106

Конструктор HTML, CSS и javascript

Инструментарий разработчика Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

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

2 стартмани

10.04.2023    9484    150    acces969    31    

115

Модель состояния для MVC

Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

"MVC плохо применима в 1С" - познакомьтесь с моделью состояния и, возможно, ваше мнение поменяется! Представленное решение является эволюционным развитием идеи реализации MVC для 1С. В новой версии добавлены DSL для описания модели состояния, а также параметризация свойств параметров и элементов формы.

1 стартмани

05.07.2022    3577    kalyaka    2    

27

Табло очереди заказов на экран телевизора

WEB-интеграция Работа с интерфейсом Платформа 1С v8.3 1С:Розница 2 Платные (руб)

Связка из веб-приложения и расширения для 1С: Розница 2.3.

3600 руб.

29.04.2022    12010    1    5    

10
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. botokash 389 04.04.14 11:55 Сейчас в теме
Очень полезно! Спасибо автору за перевод, надеюсь на продолжение.
2. slazzy 42 04.04.14 12:07 Сейчас в теме
Это не просто полезно, это просто архиполезно. С огромным удовольствием прочитаю продолжение. Давно хочу заняться изучением алгоритмов, тк это логичное развитие программиста...но что-то погряз в изучении типовых. А тут такая возможность.

Спасибо :)
Leon75; 1cmailru; +2 Ответить
3. Mi4man 173 04.04.14 13:28 Сейчас в теме
Спасибо автору!
Ну очень интересно!
Будем ждать продолжений!
4. fishca 1254 04.04.14 16:07 Сейчас в теме
Спасибо, статья очень полезная!
5. ksvd 04.04.14 16:10 Сейчас в теме
Конечно материал очень полезный. Спасибо
6. gaglo 04.04.14 17:12 Сейчас в теме
Большое спасибо! Надеюсь на продолжение, хотя понимаю, что труд огромный.
7. Патриот 449 04.04.14 17:19 Сейчас в теме
(0), спасибо! Небольшая поправка - "Система проницаема только в том случае, если любой объект из верхнего ряда соединен с любым объектом из нижнего ряда" заменить на "Система проницаема только в том случае, если существует такой объект из верхнего ряда, который соединен с одним из объектов из нижнего ряда".
Т.е. надо поменять квантор всеобщности, на квантор существования (если вы понимаете о чём я =)). Либо пример "проницаемой системы" неверен, потому как есть объекты нижнего ряда, которые не соединены с объектами верхнего ряда (что противоречит данному определению "проницаемости").
DrAku1a; ColaKola; Aleksey.Bochkov; +3 Ответить
8. утюгчеловек 38 05.04.14 13:32 Сейчас в теме
Готовящимся в аттестации по платформе на заметку.
Вероятно, можно попробовать использовать алгоритм при решении задач из "1С: Специалист" с формулировками типа:
"У некоторых товаров могут быть аналоги – другие позиции номенклатуры с теми же потребительскими свойствами и ценой, причем таких аналогов у товара может быть несколько. Считается, что если «Товар1» имеет аналог «Товар2», а «Товар2» имеет аналог «Товар3», то «Товар3» также является аналогом «Товар1»"
Выглядит несложно.

Я думал решить через матрицу связности, но перспектива каждый раз при вычислении связности несколько раз перемножать матрицы, взамен
Возврат Корень(й1) = Корень(й2)

меня теперь не прельщает.
9. утюгчеловек 38 05.04.14 15:35 Сейчас в теме
(8) ошибся в предыдущем своем псто. Такой подход предполагает что "если p связан с q, то q связан с p", - это в общем случае не является истиной
10. davdykin 25 05.04.14 17:15 Сейчас в теме
Если можно расскажите, вкратце как проходит обучение в коурсера, и если можно "исходники" статьи, чтобы понять насколько сложна для понимания версия без перевода. Просто давно интересуюсь подобным образованием, но слабое знание английского останавливает :).
DrAku1a; ColaKola; +2 Ответить
11. утюгчеловек 38 06.04.14 10:26 Сейчас в теме
(10) davdykin,
там просто всё. Курс не рассчитан на "шибко англоязычных", сложные слова можно подсмотреть, но в основном всё понятно по контексту. Я спокойно переводил со словарем, прошел, учась в универе, два года назад, Machine Learning и Model Thinking с большим удовольствием.

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

13. davdykin 25 06.04.14 20:57 Сейчас в теме
(11) утюгчеловек, Спасибо большое, возможно ваша информация поможет решиться послушать курс.

Честно говоря после прочтения статьи осталось несколько вопросов, если не сложно, кто все понял до конца поясните:

1. Сжатие пути. Насколько я понял из кода, через некоторое количество итераций мы получим не деревья а обычный массив, т.е. картинку которую мы видели в 1, т.к. в процедуре поиска корня не анализируется насколько глубокое дерево и стоит ли его перекидывать к корню?
2.
Утверждение (Hopcroft-Ulman, Tarjan): начиная с пустой структуры данных любая последовательность операций объединения-поиска M для N объектов потребует =< c ( N + M lg* N )
- в курсе рассказывается как получили данное уравнение, или, как любил говорить мой учитель по вышке "Нетрудно видеть", когда писал ответ следом за условием задачи?
3. Из
Графики времени выполнения алгоритмов в 1С.
как-то совсем не видно сильного преимущества 5 алгоритма над 1-ым, не говоря уже о разнице в 30 лет и 6 секунд
Последний вариант позволяет сократить время решения задачи с 30 лет до 6 секунд.
. В 1С даже хорошие алгоритмы работают плохо? :)
12. DoctorRoza 06.04.14 16:48 Сейчас в теме
Хороший материал, как раз для недопрограммистов 1С-ников! :)
barelpro; +1 Ответить
14. -fox- 07.04.14 09:14 Сейчас в теме
Очень жалею что так наглядно, просто и интересно в нашем институте не рассказывали лекций. Спасибо! Статья просто супер!
15. msirkizyuk 09.04.14 07:48 Сейчас в теме
Большое Вам спасибо! Объём проделанной работы впечатляет.
16. m0r0z 09.04.14 09:18 Сейчас в теме
Спасибо за лекцию.
Все очень подробно рассказано.
Есть повод подучить алгоритмы.
17. rasswet 82 09.04.14 16:23 Сейчас в теме
здорово, всё очень наглядно и хорошо описано, в детали не вникал. Но по первому впечатлению всё очень доходчиво.
18. izidakg 170 09.04.14 18:24 Сейчас в теме
именно так и должны делаться все учебные материалы
терпения автору - учить программированию бывает сложнее самого программирования
19. ildarovich 7846 11.04.14 08:38 Сейчас в теме
В статье "Наш ответ американским лекторам" приведено гораздо более быстрое решение той же задачи на 1С
agrustny; ivanitland; Aleksey.Bochkov; +3 Ответить
20. Aleksey.Bochkov 3659 11.04.14 23:47 Сейчас в теме
(19) ildarovich,
в качестве оправдания :) - я пытался максимально сохранить соответствие примеров кода на java и 1С.
Если примеры будут использовать какие-либо специфичные объекты от 1С, то это получится слегка однобоко и неприменимо к другим языкам программирования.
В последующих лекциях будет аналогичная ситуация.
21. ildarovich 7846 13.04.14 15:40 Сейчас в теме
(20) и сама лекция и Ваша интерпретация выше всяких похвал. И я бы очень хотел, чтобы мое решение выглядело не как критика или замечание, а как дополнение к лекции, сделанное мелким шрифтом и нужное тем, кто решит применить результаты сразу на практике. А способ подачи своего решения и задиристое название статьи-спойлера - это просто юмор и способ привлечь к решению внимание.
С другой стороны, я сам долгое время думал, что все алгоритмы давно открыты. Пока не узнал, что алгоритм Боурера-Мура (быстрого поиска подстроки в строке) был открыт аж в 1984 году, когда люди уже лет 30 решали такие задачи. Из этого я сделал вывод, что алгоритмика не закостенела, что можно ждать новых открытий и искать новые решения.
23. адуырщдв 28 14.04.14 12:24 Сейчас в теме
(21) ildarovich,
Да не то слово! Я, к примеру сам был в шоке когда узнал, что алгоритм Патерсона был придуман только в 1981 году! А это ведь азы computer science!
22. адуырщдв 28 14.04.14 12:18 Сейчас в теме
"Быстрое объединение с оценкой веса" в английской литературе звучит как weighted quick-union, что в нашей литературе переводят как "Взвешенное быстрое объединение". А где взвешенное быстрое объединение с делением пополам (weighted quick-union with path compression by halving)? :) Непроходят чтоль такое в принстоне? :) Ладно я шучу, как сжать путь любой программист придумает кучу методов, если он не очередной "гугл копипаст говнокодер".
24. chmv 16.04.14 08:53 Сейчас в теме
Колосальная работа. Только не понятно, зачем?
mafia; agrustny; адуырщдв; +3 Ответить
25. Патриот 449 21.04.14 13:56 Сейчас в теме
(24) chmv, если после прочтения всей статьи остался вопрос - "зачем она написана", то это печально. Вам, я думаю, эта статья незачем. С таким же успехом можно зайти на любую страницу, с темой не представляющей конкретно для вас интереса (например самолётостроения, или вышивки бисером, или бокса, да чего угодно! Если сказать языком теории множеств, то - универсальное множество минус узкий круг ваших интересов) и спрашивать, зачем она была написана. Но я всё же постараюсь кратенько обрисовать, зачем. Для саморазвития как программист, для развлечения и отвлечения от монотонной работы, может быть и куча других причин. Судя по популярности этой статьи, каждый, кто поставил под ней плюс, извлёк некую ценность из статьи для себя. Если же вы имели ввиду конкретную прикладную ценность для решения задач программистом, который забрёл на этот форум, то таковая имеется. Во-первых, эти алгоритмы могут пригодиться если специалист хочет расширить круг используемых языков, выйдя за рамки 1С, во-вторых статья демонстрирует возможность реализации на 1С стандартных алгоритмов. Наконец, и конкретно в автоматизации бизнеса на 1С встречаются задачи, где необходим поиск оптимального пути (например у моего коллеги была задача, где необходимо было найти наиболее удачный путь денежной транзакции через несколько подразделений одного предприятия в зависимости от набора ограничений - пришлось учить старые добрые алгоритмы).
27. ЧИА 169 22.11.14 09:03 Сейчас в теме
(24) chmv,
Колосальная работа. Только не понятно, зачем?


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

в применении к 1с - если что-то тормозит, не обязательно апгрейдить сервера, можно и запросы переписать, или над регистрами поработать
неоднократно изменение 1 запроса в типовых конфигурациях ускоряло проведение документа с 15-40 минут до 0.1-0.3с
26. agrustny 19 22.04.14 11:07 Сейчас в теме
Позабавило:
5. Они могут раскрыть секреты жизни и вселенной.
6. Для саморазвития, интеллектуальной стимуляции и хорошего заработка.
Не переводили бы Вы такую дурь ;) - взяли бы лучше хорошую книжку какую-нибудь из прошлого века 19xx
Java - это немножко для другого...
(упрек по поводу выбору гнилого источника, к реализации на 1С - вопросов нет, т.к. это уже для забавы)
28. NN2P 414 18.04.17 11:56 Сейчас в теме
Статья отличная.

Прошу простить мое буквоедство и откорректировать:

"...потребует =< c ( N + M lg* N ) числа доступов к массиву.

Где ln*N:.."

на
"...потребует =< c ( N + M lg N * N ) числа доступов к массиву.

Где lg*N:..
"
29. Aleksey.Bochkov 3659 20.04.17 19:30 Сейчас в теме
(28) Насколько я понимаю текущий вариант является правильным.
Meaning of lg * N in Algorithmic Analysis
Итерированный логарифм
30. NN2P 414 20.04.17 21:12 Сейчас в теме
(29)
Итерированный логарифм
Ого, прошу прощения. Спасибо за просвещение.
31. pvlunegov 157 07.11.17 23:28 Сейчас в теме
Взял вашу конфигурацию, на ее основе сделал алгоритм построения дерева путей при тыке мышью на ячейке.
Дерево путей сделал визуальное отображение в виде красных ячеек на месте белых ячеек (свободные).
Коричневые ячейки - препятствие.
Должен заметить что мой алгоритм очень ущербен и на данный момент при размере веток дерева >5 1с уходит в долгий расчет более чем на час.
При размере веток дерева Путей <=5 считается в пределах нормы.

Как я понимаю, после каждого шага расчета (у меня 1 шаг расчета = увеличение всех веток дерева на 1) необходимо уплощать дерево (уменьшать количество листьев, увеличивать количество веток).
Алгоритм уплощения надо додумать.
Думаю, при верном построении алгоритма удастся создать полное дерево связности.

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

См. рисунок
Прикрепленные файлы:
32. pvlunegov 157 07.11.17 23:37 Сейчас в теме
Как вариант упрощения алгоритма можно взять предложенный в игровой индустрии так называемый "Муравьиный поиск".
Попробую реализовать его для уменьшения количества вычислений.
В данном алгоритме необходимо реализовать распараллерирование вычислений. Каждый "Муравей" есть отдельный процесс производящий вычисление пути и помечающий его в дерево.
Соседние муравьи "Видят" проложенный собратом путь и не идут по нему.
Таким образом можно запустить несколько параллельных процессов обсчета дерева пути.
Кроме того, в прикладном значении алгоритм важен прежде всего для вычисления кратчайшего пути между 2 точками.
Это можно использовать в муравьином алгоритме.
Например, вычислять "РАсстояние" до целевой точки в каждой точке пути и таким образом вычислять "Рейтинг" каждой точки.
Муравей, при выборе следующей точки для обсчета из соседних, выбирает точку с наибольшим рейтингом.
Таким образом, сокращается радиус поиска и количество вычислений.

Еще одно упрощение задачи - муравей, первый нашедший путь будет считаться выигравшим гонку.
Все поиски завершаются и выбирается данный путь (Может и не самый лучший) - таким образом будет реализация алгоритма поиска первого попавшегося пути (возможно не самого кратчайшего), зато с минимальными затратами времени.
33. pvlunegov 157 07.11.17 23:45 Сейчас в теме
(32) Должен заметить особые случаи муравьиного алгоритма.
Если муравей прошел какой то тропой, не самой оптимальной. Его собрат "наткнулся" на след муравья.
Должен ли он пересекать его путь?
Варианты:
1. Муравьи не пересекают свои пути поиска
- В этом случае необходимо реализовывать "жадный" вариант поиска - искать все возможные соседние пути без пропусков
- Только после исчерпания всех соседних клеток искать другие
- Минусы - медленная прогрессия поиска, топтание на месте, тупики обхода, возвращение в исходные точки.
- Реализовать поиск быстрый поиск по рейтингу пути тяжело
2. Муравьи пересекают пути собратьев. Но делать это нежелательно.
Чтобы уменьшить это явление, уменьшать рейтинг тех клеток, которые прошел собрат.
Муравей пересечет путь собрата при острой необходимости (когда другие варианты менее желательны)
- Действует алгоритм поиска пути по рейтингу
- Более быстрый поиск, обход тупиков и слепых пятен.

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

Займусь данным вопросом, о результатах отпишусь.

Всем спасибо за внимание.
Оставьте свое сообщение