Алгоритм: планирование Путешествия
Флажок не фактический <input> (это скрыто). Это сделано для того, чтобы стилизовать его последовательно кросс-браузер, кросс-устройство, что в настоящее время невозможно для <input type="checkbox">.
Вместо этого используется псевдоэлемент ::before из <label>.
Поэтому вы должны поместить пользовательский класс в оболочку (custom-control-right в приведенном ниже примере) и добавить немного CSS, который переопределяет значение по умолчанию:
div.custom-control-right {
padding-right: 24px;
padding-left: 0;
margin-left: 16px;
margin-right: 0;
}
div.custom-control-right .custom-control-label::before,
div.custom-control-right .custom-control-label::after{
right: -1.5rem;
left: initial;
}<link href="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/4.1.3/css/bootstrap.min.css" rel="stylesheet"/>
<div style="margin:20px;">
<div class="custom-control custom-checkbox custom-control-inline custom-control-right">
<input type="checkbox" id="location" value="location" name="custom1" class="custom-control-input">
<label class="custom-control-label" for="location"> Option 1</label>
</div>
<div class="custom-control custom-checkbox custom-control-inline custom-control-right">
<input type="checkbox" id="location2" value="location2" name="custom2" class="custom-control-input">
<label class="custom-control-label" for="location2"> Option 2</label>
</div>
</div> Примечание: вы можете заменить селектор div.custom-control-right на .custom-control-right, если этот код анализируется после , вы загружаете Bootstrap CSS. Однако в SO связанные ресурсы загружаются после кода на панели CSS, и мне пришлось переквалифицировать селектор, чтобы он работал.
4 ответа
Оптимизация колонии муравьев, кажется, самое известное решение этого. Обратите внимание, что это - проблема NP, на самом деле даже полная NP проблема. Это означает, что "легко" проверить решение, являющееся корректным, но "трудно" найти его. Единственный способ найти "оптимальное" решение состоял бы в том, чтобы попробовать все возможные решения, сравнить результаты и взять лучший. Конечно, это не приемлемо, если Вы хотите решить его в течение соответствующего времени.
Алгоритмы ACO найдут хорошее решение, близко к оптимуму. Я говорю близко как AFAIK, он не может гарантировать, что всегда нашел лучший. Могли бы существовать лучшие решения. Однако часто не необходимо для реального нахождения лучшего решения возможным, решение, которое просто "очень хорошо", добьется цели, и здесь ACO точно, что Вы ищете. Это может найти решение в интервалах разумного срока, и решение будет хорошо наверняка.
В Вашем случае необходимо изменить его немного. Обычно это будет только пытаться найти краткий маршрут, только принимая путь во внимание. В Вашем случае это должно взять Ваше рабочее окно, резервирование и время, проведенное на местоположении во внимание. Но это просто модификации, "как муравьи перемещаются", основной алгоритм остается таким же и будет все еще работать то же.
Существует большая работа над этой проблемой. Это идет различными именами
- коммивояжер (составление маршрутов транспортных средств) проблема с окнами времени и отношениями предшествования.
- Проблема вывоза и доставки.
Существует хост исследования в области этой проблемы, большого количества ее в Журналах Исследования операций. Эта проблема в целом, NP-трудная, таким образом, общее точное решение проблемы, поскольку Вы описали проблему, не практично, но могли бы быть хорошие, точные или приближенные решения Вашей определенной проблемы. Лучший алгоритм будет функцией Ваших данных.
- Насколько большой Ваш набор данных. Если "n" относительно маленький (30-100) затем, точное решение с математическим программированием, вероятно, возможно.
- Насколько трудный окна времени и отношения предшествования. Если количество возможных местоположений для посещения в каком-либо окне времени является небольшим, то решение как динамическое программирование возможно.
- Если Вы не можете найти особый случай, то Вы, вероятно, хотите объединить эвристический алгоритм конструкции с постпроцессором локального поиска. Простая альтернатива является так называемой эвристикой СХВАТЫВАНИЯ, где Вы
- возьмите существующую эвристику конструкции,
- рандомизируйте то, так, чтобы несколько выполнений дали Вам несколько решений,
- выполните рандомизированную версию многократно
- возьмите лучшее решение, которое заканчивается.
Это - проблема коммивояжера с модификацией, добавляющей рабочее ограничение окна..., что означает, что решение этой проблемы будет еще более трудно найти, чем стандартная проблема коммивояжера.
У меня есть несколько подходов, которые работают прилично для предоставления приближенных решений.
- Генетические алгоритмы
- Запрещенный поиск
- Рандомизированный алгоритм (Например, случайное блуждание)
Я не знаю, относится ли к Вашей проблеме, первое, что пришло на ум я говорю, что она не делает, но динамическое программирование может иногда использоваться на тяжелых проблемах.