Здравствуйте. Есть исходная таблица "События"(табличная часть документа). Нужно составить из этих событий расписание таким образом, чтобы можно было посетить как можно больше событий(от его начала и до конца). Подскажите, пожалуйста куда нужно копать или ,может какой-нибудь алгоритм для решения этой задачи.
Прикладываю скриншот исходной таблицы и таблицы результатов.
Прикладываю скриншот исходной таблицы и таблицы результатов.
Прикрепленные файлы:
По теме из базы знаний
- Понимание и использование параллелизма в SQL Server
- Дополнение к УПП 1.3 для ведения миграционного учета и печати форм заявлений в органы ФМС
- COVID-19: подробная аналитика в одном приложении
- А вы как стали программистом?
- OKR как методология личной и профессиональной эффективности: развивай себя как Google
Найденные решения
(14) Доработал алгоритм, чтобы проход был максимально линейным, но как его полноценно протестировать - непонятно.
У Вас очень странный набор записей, где их больше 10000. Много совпадающих и очень близких длительностей для каждого времени начала.
Если убрать повторяющиеся, то остается меньше тысячи, и скорость работы приемлемая, а в итогах по траектории записей меньше 10.
Но повторюсь - для уверенности надо хорошо потестировать.
У Вас очень странный набор записей, где их больше 10000. Много совпадающих и очень близких длительностей для каждого времени начала.
Если убрать повторяющиеся, то остается меньше тысячи, и скорость работы приемлемая, а в итогах по траектории записей меньше 10.
Но повторюсь - для уверенности надо хорошо потестировать.
&НаСервере
Процедура СформироватьОтчетНаСервере()
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ РАЗЛИЧНЫЕ
| СобытияСписокСобытий.ВремяНачала КАК ВремяНачала,
| СобытияСписокСобытий.Длительность КАК Длительность
|ИЗ
| Документ.События.СписокСобытий КАК СобытияСписокСобытий
|ГДЕ
| СобытияСписокСобытий.Ссылка = &Ссылка
|
|УПОРЯДОЧИТЬ ПО
| ВремяНачала";
Запрос.УстановитьПараметр("Ссылка", ВыбранныйДокумент.Ссылка);
РезультатЗапроса = Запрос.Выполнить();
Если РезультатЗапроса.Пустой() Тогда
Возврат;
КонецЕсли;
ТЗ = Запрос.Выполнить().Выгрузить();
ТЗ.Колонки.Добавить("КолВоПосещений");
ТЗ.Колонки.Добавить("НомерПредшественника");
ТЗ[0].КолВоПосещений = 1;
ТЗ[0].НомерПредшественника = -1;
ИндексСтрокиСМаксимальнымПосещением = 0;
Для Счетчик = 1 По ТЗ.Количество()-1 Цикл
ТЗ[Счетчик].КолВоПосещений = 1;
ТЗ[Счетчик].НомерПредшественника = -1; // заглушка, чтобы не опускаться глубже
ВложенныйСчетчик = Счетчик-1;
Пока ВложенныйСчетчик >= 0 ЦИКЛ
ТекСтрока = ТЗ[ВложенныйСчетчик];
Если ТЗ[Счетчик].ВремяНачала >= ТекСтрока.ВремяНачала + ТекСтрока.Длительность*60 Тогда
ТЗ[Счетчик].НомерПредшественника = ВложенныйСчетчик;
ТЗ[Счетчик].КолВоПосещений = ТекСтрока.КолВоПосещений + 1;
Если ТЗ[ИндексСтрокиСМаксимальнымПосещением].КолВоПосещений <= ТЗ[Счетчик].КолВоПосещений Тогда
ИндексСтрокиСМаксимальнымПосещением = Счетчик;
КонецЕсли;
Прервать;
КонецЕсли;
ВложенныйСчетчик = ВложенныйСчетчик - 1;
КонецЦикла;
КонецЦикла;
//обратным ходом восстанавливаем последовательность к элементу с максимальным кол-вом посещений
ОптимальнаяТраектория = Новый Массив;
ОптимальнаяТраектория.Добавить(ИндексСтрокиСМаксимальнымПосещением);
ТекущийИндекс = ИндексСтрокиСМаксимальнымПосещением;
Пока ТЗ[ТекущийИндекс].НомерПредшественника >= 0 Цикл
ОптимальнаяТраектория.Вставить(0, ТЗ[ТекущийИндекс].НомерПредшественника);
ТекущийИндекс = ТЗ[ТекущийИндекс].НомерПредшественника;
КонецЦикла;
Для каждого Элемент Из ОптимальнаяТраектория Цикл
Сообщить("Время: " + ТЗ[Элемент].ВремяНачала + ", длительность: " + ТЗ[Элемент].Длительность);
КонецЦикла;
КонецПроцедуры ПоказатьОстальные ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
(3) Навсидку, примерно так (делал на коленке, можно оптимизировать, конечно)
&НаСервере
Процедура ОптимальныеСобытия()
ТЗ = Новый ТаблицаЗначений;
ТЗ.Колонки.Добавить("ВремяНачала", Новый ОписаниеТипов("Дата",,,Новый КвалификаторыДаты(ЧастиДаты.Время)));
ТЗ.Колонки.Добавить("ДлительностьВМинутах");
ЗаполнениеТаблицыСобытий(ТЗ);
ТЗ.Сортировать("ВремяНачала");
СписокНаибольшихЗначений = Новый СписокЗначений;
// в значение записываем максимум посещений для данной точки, в представление - оптимальную траекторию
СписокНаибольшихЗначений.Добавить(1, "0"); // в первую точку можно попасть только одним способом из предшественника с индексом 0
Для Счетчик = 1 По ТЗ.Количество()-1 Цикл
КолВоМаксПосещений = 1; // посещение текущей точки
Для ВложенныйСчетчик = 0 По Счетчик-1 Цикл
Если ТЗ[Счетчик].ВремяНачала >= ТЗ[ВложенныйСчетчик].ВремяНачала + ТЗ[ВложенныйСчетчик].ДлительностьВМинутах*60 Тогда
Если СписокНаибольшихЗначений[ВложенныйСчетчик].Значение + 1 > КолВоМаксПосещений Тогда
КолВоМаксПосещений = СписокНаибольшихЗначений[ВложенныйСчетчик].Значение + 1;
ОптимальныйПредшественник = ВложенныйСчетчик;
КонецЕсли;
КонецЕсли
КонецЦикла;
// добавляем в массив оптимальную траекторую для данной точки
Если КолВоМаксПосещений >1 Тогда
Траектория = СписокНаибольшихЗначений[ОптимальныйПредшественник].Представление + "," + Счетчик;
Иначе
Траектория = Строка(Счетчик);
КонецЕсли;
СписокНаибольшихЗначений.Добавить(КолВоМаксПосещений, Траектория);
КонецЦикла;
СписокНаибольшихЗначений.СортироватьПоЗначению(НаправлениеСортировки.Убыв);
ОптимальнаяТраектория = СтрРазделить(СписокНаибольшихЗначений[0].Представление, ",");
Для каждого Элемент Из ОптимальнаяТраектория Цикл
Сообщить("Время: " + ТЗ[Число(Элемент)].ВремяНачала + ", длительность: " + ТЗ[Число(Элемент)].ДлительностьВМинутах);
КонецЦикла;
КонецПроцедуры Показать
Фактически, задача про все варианты выбранных мероприятий без пересечений. Таких вариантов <= чем 2^К, где К - количество вариантов. Самый простой метод - это битовое значение. Количество бит = количество событий. Бит = 1 - идем, бит = 0 - не идем. Дальше тест на допустимость, что события не пересекаются. Дальше поиск варианта, где полезного времени больше, чем в других вариантах (таких вариантов может быть несколько). Ну и всяческие эвристики можно сюда нагнетать, если охота. Но для 20-ти событий - это цикл от единицы до миллиона с чем-то - не сильно то и много даже для 1С.
(10) Не совсем уверен в этом коде, попробуйте потестировать на маленьких выборках на верность.
Если работает правильно, попробуйте на больших (количество вложенных итераций должно существенно сократиться), и в замере производительности гляньте, где больше всего съедается времени.
Подозреваю, что на сортировках таблиц и СтрРазделить
Если работает правильно, попробуйте на больших (количество вложенных итераций должно существенно сократиться), и в замере производительности гляньте, где больше всего съедается времени.
Подозреваю, что на сортировках таблиц и СтрРазделить
&НаСервере
Процедура ОптимальныеСобытияРеф()
ТЗ = Новый ТаблицаЗначений;
ТЗ.Колонки.Добавить("ВремяНачала", Новый ОписаниеТипов("Дата",,,Новый КвалификаторыДаты(ЧастиДаты.Время)));
ТЗ.Колонки.Добавить("ДлительностьВМинутах");
ЗаполнениеТаблицыСобытий(ТЗ);
ТЗ.Сортировать("ВремяНачала");
ТаблицаМаксимумов = Новый ТаблицаЗначений;
ТаблицаМаксимумов.Колонки.Добавить("ВремяОкончания");
ТаблицаМаксимумов.Колонки.Добавить("КолВоПосещений");
ТаблицаМаксимумов.Колонки.Добавить("Траектория");
Максимум = ТаблицаМаксимумов.Добавить();
Максимум.ВремяОкончания = ТЗ[0].ВремяНачала + ТЗ[0].ДлительностьВМинутах*60;
Максимум.КолВоПосещений = 1;
Максимум.Траектория = "0";
Для Счетчик = 1 По ТЗ.Количество()-1 Цикл
КолВоПосещений = 1;
Траектория = Строка(Счетчик);
ВложенныйСчетчик = ТаблицаМаксимумов.Количество() - 1;
Пока ВложенныйСчетчик >= 0 ЦИКЛ
ТекМаксимум = ТаблицаМаксимумов[ВложенныйСчетчик];
Если ТЗ[Счетчик].ВремяНачала >= ТекМаксимум.ВремяОкончания Тогда
КолВоПосещений = ТекМаксимум.КолВоПосещений + 1;
Траектория = ТекМаксимум.Траектория + "," + Счетчик;
Прервать;
КонецЕсли;
ВложенныйСчетчик = ВложенныйСчетчик - 1;
КонецЦикла;
НовыйМаксимум = ТаблицаМаксимумов.Добавить();
НовыйМаксимум.ВремяОкончания = ТЗ[Счетчик].ВремяНачала + ТЗ[Счетчик].ДлительностьВМинутах*60;
НовыйМаксимум.КолВоПосещений = КолВоПосещений;
НовыйМаксимум.Траектория = Траектория;
КонецЦикла;
ТаблицаМаксимумов.Сортировать("КолВоПосещений убыв");
ОптимальнаяТраектория = СтрРазделить(ТаблицаМаксимумов[0].Траектория, ",");
Для каждого Элемент Из ОптимальнаяТраектория Цикл
Сообщить("Время: " + ТЗ[Число(Элемент)].ВремяНачала + ", длительность: " + ТЗ[Число(Элемент)].ДлительностьВМинутах);
КонецЦикла;
КонецПроцедуры
Показать
(14) Доработал алгоритм, чтобы проход был максимально линейным, но как его полноценно протестировать - непонятно.
У Вас очень странный набор записей, где их больше 10000. Много совпадающих и очень близких длительностей для каждого времени начала.
Если убрать повторяющиеся, то остается меньше тысячи, и скорость работы приемлемая, а в итогах по траектории записей меньше 10.
Но повторюсь - для уверенности надо хорошо потестировать.
У Вас очень странный набор записей, где их больше 10000. Много совпадающих и очень близких длительностей для каждого времени начала.
Если убрать повторяющиеся, то остается меньше тысячи, и скорость работы приемлемая, а в итогах по траектории записей меньше 10.
Но повторюсь - для уверенности надо хорошо потестировать.
&НаСервере
Процедура СформироватьОтчетНаСервере()
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ РАЗЛИЧНЫЕ
| СобытияСписокСобытий.ВремяНачала КАК ВремяНачала,
| СобытияСписокСобытий.Длительность КАК Длительность
|ИЗ
| Документ.События.СписокСобытий КАК СобытияСписокСобытий
|ГДЕ
| СобытияСписокСобытий.Ссылка = &Ссылка
|
|УПОРЯДОЧИТЬ ПО
| ВремяНачала";
Запрос.УстановитьПараметр("Ссылка", ВыбранныйДокумент.Ссылка);
РезультатЗапроса = Запрос.Выполнить();
Если РезультатЗапроса.Пустой() Тогда
Возврат;
КонецЕсли;
ТЗ = Запрос.Выполнить().Выгрузить();
ТЗ.Колонки.Добавить("КолВоПосещений");
ТЗ.Колонки.Добавить("НомерПредшественника");
ТЗ[0].КолВоПосещений = 1;
ТЗ[0].НомерПредшественника = -1;
ИндексСтрокиСМаксимальнымПосещением = 0;
Для Счетчик = 1 По ТЗ.Количество()-1 Цикл
ТЗ[Счетчик].КолВоПосещений = 1;
ТЗ[Счетчик].НомерПредшественника = -1; // заглушка, чтобы не опускаться глубже
ВложенныйСчетчик = Счетчик-1;
Пока ВложенныйСчетчик >= 0 ЦИКЛ
ТекСтрока = ТЗ[ВложенныйСчетчик];
Если ТЗ[Счетчик].ВремяНачала >= ТекСтрока.ВремяНачала + ТекСтрока.Длительность*60 Тогда
ТЗ[Счетчик].НомерПредшественника = ВложенныйСчетчик;
ТЗ[Счетчик].КолВоПосещений = ТекСтрока.КолВоПосещений + 1;
Если ТЗ[ИндексСтрокиСМаксимальнымПосещением].КолВоПосещений <= ТЗ[Счетчик].КолВоПосещений Тогда
ИндексСтрокиСМаксимальнымПосещением = Счетчик;
КонецЕсли;
Прервать;
КонецЕсли;
ВложенныйСчетчик = ВложенныйСчетчик - 1;
КонецЦикла;
КонецЦикла;
//обратным ходом восстанавливаем последовательность к элементу с максимальным кол-вом посещений
ОптимальнаяТраектория = Новый Массив;
ОптимальнаяТраектория.Добавить(ИндексСтрокиСМаксимальнымПосещением);
ТекущийИндекс = ИндексСтрокиСМаксимальнымПосещением;
Пока ТЗ[ТекущийИндекс].НомерПредшественника >= 0 Цикл
ОптимальнаяТраектория.Вставить(0, ТЗ[ТекущийИндекс].НомерПредшественника);
ТекущийИндекс = ТЗ[ТекущийИндекс].НомерПредшественника;
КонецЦикла;
Для каждого Элемент Из ОптимальнаяТраектория Цикл
Сообщить("Время: " + ТЗ[Элемент].ВремяНачала + ", длительность: " + ТЗ[Элемент].Длительность);
КонецЦикла;
КонецПроцедуры Показать
(22) Если все равно, какое событие посетить из начинающихся в один момент и с одинаковой длительностью, то в первом запросе это получать не нужно. Лучше после формирования конечной оптимальной цепочки Время/Длительность присоединить к ней данные по Тема/НомерСтроки из любой записи исходной таблицы с таким же Временем и Длительностью.
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот