Содействие - исключение из 3-го закона Ньютона.

Амальгама

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Амальгама » Reductor Sapiens » Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое


Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое

Сообщений 481 страница 510 из 868

481

#p91022,Лукомор написал(а):

Максимальный запретный, надо полагать?
Или максимальный разрешенный?

Любой. Но в нашей схеме ищем максимальный разрешенный построением пути через все точки с изъяитием одной.

0

482

Вот еще раз.
N точек связанные оптическими каналами с задержками пропорциональными длинам участков.
Если подать световой сигнал на любую входную точку, то на всех N-1 выходных точках, можно получить N-1 быстрейших сигналов (по переднему фронту) и cтолько же длиннейших (по заднему фронту). Промежуточные теряем, и черт с ними. Наибольший из N вариантов отыскивается элементарно.

Построить полный путь для максимального по времени сигнала двоичным поиском с временем log(N-1) - дело техники, но нас интересует кратчайший через все точки.
С учетом замечания Лукомора, этот искомый путь будет либо длиннее бОльшего запретного, либо меньше его. Все запретные пути короче минимум на 1 точку. Короче не по длине, а по количеству точек.

Тогда удаляем из TSP схемы по одной точке и находим сначала N конечных точек с максимиальным временем, а затем N максимальных маршрутов в N укороченных на точку схемах. Как выше написано, эта тривиальная процедура займет
N+Nlog(N-1) тактов.

А теперь возвращаем точку N-1 способами в найденный максимальный путь и повторяем N раз для всех их, за время N(N-1). В полном пути сигнал пройдет с единственным временем, которое будет либо меньше либо больше максимального запретного.

И, наконец. осталось найти в этом списке кратчайший путь двоичным поиском за logN

Отредактировано Шарпер (2018-09-11 16:17:59)

0

483

#p91022,Лукомор написал(а):

Максимальный запретный, надо полагать?
Или максимальный разрешенный?

Фишка - максимальный запрещенный путь для TSP из N точек, будет равен максимальному разрешенному пути для TSP с изъятой точкой.

0

484

#p91025,Шарпер написал(а):

Фишка - максимальный запрещенный путь для TSP из N точек, будет равен максимальному разрешенному пути для TSP с изъятой точкой.

Классно!
А зачем мы ищем  максимальный путь, если мы должны найти минимальный путь?

0

485

#p91026,Лукомор написал(а):

А зачем мы ищем  максимальный путь, если мы должны найти минимальный путь?

Для того, чтобы отсеять запретные.

0

486

Мы же максимальные ищем на укороченных на точку картах, как разрешенные и строим для них пути

0

487

Все. Нашел ошибку. Подтвердите

0

488

#p91029,Шарпер написал(а):

Все. Нашел ошибку. Подтвердите

А? Что? Кто здесь?!
Кто у кого что нашел?! http://www.kolobok.us/smiles/user/Mauridia_44.gif

0

489

#p91031,Лукомор написал(а):

Кто у кого что нашел?! http://www.kolobok.us/smiles/user/Mauridia_44.gif

Я у себя. Возврат точки к укороченному полному пути предопределяет не N вариантов, а до хрена вставок. Но слава богу, они нам не нужны. Соединим эту точку со всеми N-1 точками построенного пути и двоичным поиском найдем новый минимальный полный путь опять за log (N-1) шагов.

И тогда будет N+Nlog(N-1)!+Nlog(N-1)+logN
Вполне полиномиально. Мне так кааца.

Отредактировано Шарпер (2018-09-11 19:17:18)

0

490

Ключевое слово:"Кааца"... http://www.kolobok.us/smiles/standart/smile3.gif

0

491

#p91033,Лукомор написал(а):

Ключевое слово:"Кааца"...

Ну, я уповаю, что Ваш незамыленный взгляд найдет ошибку
Или давай делить будущий миллион от Клея  http://www.kolobok.us/smiles/artists/just_cuz/JC_gimmefive.gif

0

492

#p91033,Лукомор написал(а):

Ключевое слово:"Кааца"

Это эстонская фамилия. Все знают Тоомаса Абраамовича Кааца.

+1

493

0

494

#p91034,Шарпер написал(а):

Или давай делить будущий миллион от Клея

Я тебе его дарю целиком и полностью!  http://www.kolobok.us/smiles/light_skin/hi.gif

Отредактировано Лукомор (2018-09-11 20:28:35)

0

495

#p91028,Шарпер написал(а):

Мы же максимальные ищем на укороченных на точку картах

Не мы, а вы! (с)

0

496

#p91046,Лукомор написал(а):

Я тебе его дарю целиком и полностью!

Свою долю отдай Доктору. Он принадлежит моему клану и я должен блюсти его интерес.  http://www.kolobok.us/smiles/personal/to_keep_order.gif

#p91047,Лукомор написал(а):

Не мы, а вы! (с)

И что неправильно? Провеотье дейьвия с логарифмами штоле. я не помню наверняка.

0

497

#p91047,Лукомор написал(а):

Не мы, а вы!

Все сам, все сам... Эх!

Ошибки конечно! Странно что вы их не видите.

0

498

#p91050,Шарпер написал(а):

ровеотье дейьвия с логарифмами штоле. я не помню наверняка.

Чтобы я проверил, подскажи пожалуйста, по какому основанию ты берешь логарифм, и факториал ты берешь от (N-1),
или, не дай бог, от Log(N-1)?

0

499

#p91072,Лукомор написал(а):

Чтобы я проверил, подскажи пожалуйста, по какому основанию ты берешь логарифм, и факториал ты берешь от (N-1),

По 2. Двоичеый же поиск. А log2N это для двоичного поиска

Отредактировано Шарпер (2018-09-12 06:22:17)

0

500

Ощибка в том, что я прохлопал все наиментшие мусорные и проиежуточные до наибольших.

0

501

#p91050,Шарпер написал(а):

Свою долю отдай Доктору. Он принадлежит моему клану и я должен блюсти его интерес.

То-есть ты свою долю отдашь Инкви, я правильно понял?
Осталось только придумать подходящее название нашему благотворительному фонду!  http://www.kolobok.us/smiles/light_skin/yahoo.gif

0

502

#p91075,Лукомор написал(а):

То-есть ты свою долю отдашь Инкви, я правильно понял?

Не. Без квантов он меня послал далеко...

0

503

Лукомор
Короче. мы легко можем найти все minmax для всех N укороченных на точку карт. Наш искомый может расположиться где угодно внутри и вне диапазона

0

504

Какие св-ва есть у минимального пути с пропущенной точкой? Ьо, что это единственный минимальный мусорный для полного пути с возвращенной точкой - возврат точки в карту не даст ни олного мусорного, а только разрешенные. В них будет кратчаший искомый?

0

505

#p91075,Лукомор написал(а):

подходящее название нашему благотворительному фонду

Так вариантов всего два. Либо "Лукопер", либо "Бегемор", но я затрудняюсь выбрать из них лучший.

+3

506

#p91078,Шарпер написал(а):

Какие св-ва есть у минимального пути с пропущенной точкой? Ьо, что это единственный минимальный мусорный для полного пути с возвращенной точкой - возврат точки в карту не даст ни олного мусорного, а только разрешенные. В них будет кратчаший искомый?

Зачем всё изобретать заново? В шахматных алгоритмах давно и очень качественно реализован, что характерно, минимаксный перебор. Можно оттуда взять нужный кусок и получить ответы на эти и последующие вопросы.
Ведь обход путей - это тоже своего рода шахматная партия, где каждый ход порождает новую позицию и новое множество допустимых ходов. Соответственно, в каждом узле дерева перебора есть его "вес" или набор весов, ЕМНИП, эта фигня уже называется взвешенными графами.
*с сомнением*
Да только будете ли это читать. Там длинно, скучно и почти без картинок.

0

507

#p91079,DoctorLector написал(а):

Так вариантов всего два. Либо "Лукопер", либо "Бегемор", но я затрудняюсь выбрать из них лучший.

Тогда уж Шармор. Для своих можно просто Шарм.
А учитывая твое участие, Др.Шарм.
http://www.kolobok.us/smiles/light_skin/good.gif

+1

508

#p91079,DoctorLector написал(а):

я затрудняюсь выбрать из них лучший.

Уже не актуально.
Титульный  спонсор с темы  благотворительности уже плавно съехал... http://www.kolobok.us/smiles/light_skin/yahoo.gif

0

509

#p91025,Шарпер написал(а):

Фишка - максимальный запрещенный путь для TSP из N точек, будет равен максимальному разрешенному пути для TSP с изъятой точкой.

Извиняюсь, что лезу с уточнениями раньше 20-ой страницы. Под точкой понимается город или путь? Если город, то его нельзя исключать из поиска, потому как в правильном решении должны присутствовать все города. Иначе получается преобразование исходной задачи к некоторой другой задаче, не тождественной исходной.

0

510

#p91081,Zagar написал(а):

А учитывая твое участие, Др.Шарм

При чём тут я? Я не организатор фонда, а всего лишь скромный получатель полумиллиона долларов. Фонды не называют именами спонсируемых.

#p91083,Лукомор написал(а):

Титульный  спонсор с темы  благотворительности уже плавно съехал

Как так? Мне уже под заказ шьют рюкзак для денег. Только не новыми купюрами и чтоб номера не подряд, договорились?

0


Вы здесь » Амальгама » Reductor Sapiens » Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое