Метка «полный перебор»

Около месяца назад я наткнулся на форму приглашения друзей через почту и/или номер мобильного телефона (который в добровольно-принудительном порядке требуют при регистрации). Я не долго думаю вставил в форму 1500 случайных номеров, по 500 в каждом формате (89*********, +79*********, 9*********). Поле «Сообщение» оставил пустым. На следующее утро меня ждал сюрприз: пара десятков новых диалогов, в которых я начинал разговор с сообщения «Optional message». Не долго думая я отправил отчет через форму на Facebook. Но после недельного ожидания и повторного отчета мне пришёл ответ: «This is not a bug. It's a core Facebook feature.».
Читать полностью »

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

Есть мнения, что задача коммивояжёра может формулироваться ещё двумя способами:
1. Необходимо обнаружить кратчайший гамильтонов цикл.
2. Необходимо обнаружить кратчайший путь, начинающийся в заданном узле.

Однако обе эти формулировки при ближайшем рассмотрении оказываются частными случаями первоначальной формулировки.
Формулировка 1 подразумевает, что входным узлом может быть любой узел, а выходным — один из ближайших к нему. Что требует полного перебора всех ближайших узлов к произвольно выбранному узлу.
Формулировка 2 подразумевает, что входной узел задан, а выходным узлом может быть любой. Что требует полного перебора всех выходных узлов с последующим выбором кратчайшего пути из всех кратчайших.
Поэтому мы остановимся на первоначальной формулировке, и будем решать задачу в общем виде.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js