Нахождение минимального покрытия интервала с подынтервалами
Использовал serveo и ngrok и застрял с ngrok. Я верю им, когда они говорят, что это безопасно, но я также добавил дополнительные уровни безопасности на свой хост-компьютер, который выдает SSH, усилив конфигурацию SSH и открыв минимальные порты, необходимые в iptables. Например, я ограничил входящий трафик SSH только из моей локальной подсети. Я сделал это, потому что, узнав о ngrok, я обнаружил в сети (забыл, где), что есть шанс, что кто-то сможет определить IP-адрес хост-машины.
3 ответа
Жадный алгоритм, запускающийся в a или b всегда, дает оптимальное решение.
Доказательство: считайте набор Sa всех подынтервалов, покрывающих a. Очевидно, один из них должен принадлежать оптимальному решению. Если мы заменяем его подынтервалом (amax, bmax) от Sa, правильная конечная точка которого bmax максимальна в Sa (достигает дальше всего направо), остающийся открытый интервал (bmax, b) будет подмножеством остающегося интервала от оптимального решения, таким образом, это сможет быть покрыто без большего количества подынтервалов, чем аналогичный открытый интервал от оптимального решения. Поэтому решение, созданное из (amax, bmax) и оптимальное решение для остающегося интервала (bmax, b), также будет оптимально.
Так, только запустите в a и многократно выберите интервал, достигающий самого далекого права (и покрывающий конец предыдущего интервала), повторитесь, пока Вы не поразите b. Я полагаю, что выбор следующего интервала может быть сделан в журнале (n) при хранении интервалов в увеличенном дереве интервала.
Походит на динамическое программирование.
Вот иллюстрация алгоритма (предположите, что интервалы находятся в списке, отсортированном по времени окончания):
//works backwards from the end
int minCard(int current, int must_end_after)
{
if (current < 0)
if (must_end_after == 0)
return 0; //no more intervals needed
else
return infinity; //doesn't cover (a,b)
if (intervals[current].end < must_end_after)
return infinity; //doesn't cover (a,b)
return min( 1 + minCard(current - 1, intervals[current].start),
minCard(current - 1, must_end_after) );
//include current interval or not?
}
Но это должно также включить кэширование (memoisation).
Вы имеете в виду так, чтобы подынтервалы все еще наложились таким способом, который (a, b) остается полностью покрытым во всех точках?
Возможно, разделяя сами подынтервалы на базисные блоки, связанные с тем, куда они произошли из, таким образом, можно перечислить опции для каждого интервала базисного блока, составляющего другие регионы, покрытые подынтервалом также. Затем можно использовать поиск на основе каждого подподынтервала и по крайней мере быть уверены, что никакие разрывы не оставляют.
Затем должен был бы искать.. эффективно.. это было бы более твердо.
Мог устранить любой набор интервалов, которые полностью покрыты другим набором меньшего числа и работы проблема после предварительной обработки.
Не был бы минимальное для целого быть минимальным по крайней мере для одной половины? Я не уверен.
Найденный ссылкой на журнал, но не мог считать его.:(
Это было бы проблемой набора удара и было бы NP_hard в целом.
Не мог считать это ни один, но похож на противоположный вид проблемы.
Не мог считать его, но другой соединяется, который упоминает, что разделил интервалы.
Вот доступная ссылка на Рандомизированных Алгоритмах для проблем GeometricOptimization.
Страница 35 этого PDF имеет жадный алгоритм.
Страница 11 Karp (1972) упоминает установленный на удар и цитируется много.
Результат Google. Исследование было забавой, но я должен пойти теперь.