2.

Мой ответ Jonny.

Hello, Jonny!

На этом мои знания английского почти заканчиваются.:-((

Мне было весьма приятно получить от Вас пространный комм. Жаль, что Вы не оставили обратного адреса, ссылки на сайт или хотя бы временный почтовый ящик. Поэтому отвечаю здесь, у себя в гостевой. Признаться, она плохо организована, но я не умею на narod.ru сделать лучше.

Ваше замечание о моём "немодном" ныне программировании точно соответствует истине. Я действительно отстал, и тому есть свои причины. Живу я, как Вы точно заметили, "не в городе", а в гетто, куда переселился провести остаток жизни. Долгое время говорил всем и считал сам, что не доживу до 2000 года. Задолго до этой отметки мне давали протянуть ещё 9-10 месяцев...

У меня был длительный период времени, когда я был отстранён от программирования, от компьютера, и вообще от умственной работы - я был слеп. После того, как мне вернули зрение, я обнаружил, что программирование сильно скакнуло вперёд, вся жизнь внезапно изменилась. По моей стране прокатилась перестройка, да и самой страны, в которой я худо-бедно приспособился жить, уже не было. Что я успел сделать, так это приобрести пиратский CBuilder5 и освоить его. В начале 80-х меня называли лучшим программистом в городе. Никаких результатов, кроме навыков, от того времени не осталось. Моя лучшая программа была написана ещё тогда, но она фактически и не работала, хотя нужда в ней была преогромная, пока у предприятия были заказы. Оказалось, что у аэрокосмического объединения не нашлось средств на оплату кондиционирования машинного зала, и самую мощную в городе ЭВМ просто продали армянам на драгметаллы.:-((

В 2004 году знакомый сисадмин (А.Духовской, ему посвящены два моих стихотворения) нашёл для меня заказ. Нужно было для пивоваренной фирмы, где он работал, сделать "транспортную задачу", как он выразился. Конечно, это была не транспортная задача. Но заказ был интересным, и я его выполнил. Это та самая программа "BestRoutes", выполняющая развозку пива по городу и его окрестностям. Я рассчитывал поживиться свеженьким транслятором, н-ну типа взять похранить, но оказалось, что на фирме, которая отщипывает от себя крупный кусок в бюджет губернии, ВООБЩЕ нет никакого транслятора! Сисадмины изредка пользуются Perl-ом, а немногочисленные иные каким-то продвинутым вариантом FoxPro, работающим исключительно с таблицами Excel. Пришлось привести свой BCB5 и устанавливать у них. Конечные пользователи и операторы дали моей программе оценку "блеск". А Вы пишете - "немодно".:-)) Они лучше просто не видели.

BestRoutes значительно сложнее отдельной TSP. Фактически это задача о нескольких коммивояжёрах, число которых неизвестно, да ещё попутно нужно решать "задачу о рюкзаке", а перед нужно определить зону выгрузки каждого грузовика. Мне повезло, что вершин в отдельном обходе было немного, и я справился некоторой модификацией перебора. И сам алгоритм выдаёт решения, приближающиеся к оптимальным. На фирме мне дали ссылку в интернете на статью об этой задаче, точного английского названия я уже и не помню, но запомнил, что никто даже не пытался найти точное решение полной проблемы. Слишком сложно, да и кому нужно тратить компьютерное время на точное решение, если можно найти быстро приближённое, мало чем уступающее оптимальному.

А после завершения проекта BestRoutes меня хватил азарт. Да не может же быть, чтобы для такой просто формулируемой задачи, как TSP, не смогли придумать эффективного алгоритма. Я начал его конструировать, и нашёл. Я был отрезан от библиотек, от научного общения, интернет у меня тоже был хиленький, не по карману большие трафики. Осталось от прежних времён несколько книг по математике, куда я и не заглядывал много лет, и вот - пригодились. Книга "Компьютерная оптимизация", перевод книги "COMBINATORIAL OPTIMIZATION", была выпущена в 1985 году. Если учесть те несколько лет, в течении которых она писалась, переводилась и дважды издавалась, в оригинале и в переводе, то ясно, что информация в ней существенно отстала. Но упоминание о Хэлде и Карпе там было, и небольшое описание их главного результата, чуть поболе аннотации. Так что с (Held&Karp HK 1970) я знаком, хотя оригинала не читал и точных формулировок теорем не знаю. (Их формулы, которые встретились в той книге, куда сложнее моих, между прочим). Не совпадают они! Свою "статью" о TSP я показывал и другим ещё до того, как опубликовать её в интернете. Была у меня встреча с одним профессионалом, доктором наук, как раз по TSP специализирующимся. Я попытался объяснить ему свой достаточный признак оптимальности, но он стал мне рассказывать, как можно быстро эту задачу TSP решить. Скорее всего, объяснял мне неразумному последние достижения. Я попытался несколько раз вставить словечко, что мои алгоритмы работают несколько по-другому, но разговора, увы, не получилось. Прошло полтора года, полагаю, что он так и не дочитал мой "огромный" труд до конца. Напоследок доктор с гордостью показал последний сборник статей, в создании которого принимала участие его лаборатория. Я прочитал заголовки работ, кое-где аннотации. Запомнились "асимптотически оптимальный алгоритм решения TSP", начало формулировки одной теоремы "В предположении единственности оптимального обхода...", да ещё введение полуцелых длин рёбер. Я понял, что в то время я опережал данную лабораторию. "Асимптотически оптимальный" алгоритм мне не нужен, так как я имею достаточные признаки точного оптимального решения. Возможная неединственность оптимального обхода для меня вообще не проблема, устраняется она, кстати(!); до полуцелых длин рёбер я к тому времени догадался сам, хотя после понял, что использовать их необязательно. Jonny, полагаю, что ты неправ, когда пытаешься спасти неравенство треугольника в задаче TSP. Мои алгоритмы работают не так, как у Хэлда и Карпа, хотя я не имею точных формулировок, только косвенные. Хитрость состоит в том, что я ВООБЩЕ не вычисляю суммарную стоимость никаких обходов, ни оптимальных, ни близких к ним. Почти никогда. Поэтому у меня нет никаких процентов близости к истинному результату. Для индивидуальной задачи TSP я строю замыкание семейства эквивалентных задач, далее, имея достаточные признаки оптимальности и теорему о достижимости одного из них в построенном классе эквивалентности, я всего лишь с помощью итераций, но не перебора и не ветвлений, получаю другую задачу с построенным оптимальным обходом. Остаётся только суммировать стоимости рёбер в первоначальной задаче, - оптимум гарантирован.

Теорема о достижимости достаточного признака оптимальности доказывается в полпинка, но она неконструктивна. Поэтому у меня нет знания об асимптотике числа итераций. Вот здесь термин "асимптотика" уже на своём месте. Моих знаний недостаточно, чтобы её вычислить, да я и желанием делать это не горю. Рассчитывал я присоседиться-скооперироваться с той лабораторией. Типа, я пишу алгоритмы, вы доказываете теоремы, но - не получилось ничего из этой затеи.

Почему я не хочу заниматься асимптотикой скорости получения результата - да вот почему. Симплекс-алгоритм, придуманный для задачи ЛП в 20-х годах прошлого века, работал и сейчас великолепно работает. Редко встречающееся зацикливание математики побороли, построив антициклины. С превеликим трудом удалось придумать экспоненциальные контрпримеры для задачи ЛП, с которыми симплекс-алгоритм не смог бы справиться. Я подозреваю, что симплекс-алгоритм полиномиален в среднем, как быстрая сортировка, к примеру. Или быстрое преобразование Фурье, поскольку подавляющее большинство натуральных чисел N, размерностей массива, не являются ни простыми числами, ни числами, имеющими малое число простых делителей. Если мои подозрения верны, то TSP фактически решена. Осталось лишь превратить алгоритмы на бумаге в программы для компьютера.

А вот эдесь уже начинаются серьёзные проблемы, у меня. Мне уже за 60. За годы вынужденного отлучения от программирования мозг отдохнул, часть его у меня, та, которая придумывает, осталась свежей. А вот та часть, от которой зависит реализация замысла, барахлит. Производительность черепашья, память никудышна. Плюс масса других болячек. Медленный комп. Почти нет интернета. У меня в заделе 4 проекта в программировании, и ещё пятый недавно проклюнулся, к коему даже не приступал. TSP среди них всех - самый младший. По правде, мне эта задача уже неинтересна. Иногда навещает вдохновение, бросаю всё, переключаюсь на стихи. Меня в интернете, вообще-то, считают Поэтом. Да ещё новые ноты откуда-то появляются, чужую музыку аранжировать научился, кажется.:-))

До осени прошлого года у меня около 20 месяцев не было домашнего интернета. Были жгучие проблемы со здоровьем и финансами. Редко-редко забегал в интернет-кафе, когда оказия заносила в город. Теперь - интернет есть, но хилый, повторяю. Раньше я искал информацию об TSP, но как-то мазал мимо той, о которой Вы упомянули. Знаю числа вершин рекордных задач, но нигде точной постановки этих задач так и не нашёл. Мне фактически нужен список длин рёбер, и всё, но он ни разу так и не встретился. Хотя бы для козырной задачи обхода столиц штатов США. Может, это от того, что я слабоват в английском, быстро читать и переводить хотя бы заголовки страниц не могу, сохранять весь сайт так и не научился, а вызывать словари для перевода - накладно, счётчик у провайдера тикает и тикает.:-((

Jonny, ты пишешь, что опередил меня. Искренне рад твоим успехам. Только должен заявить, что я остановился на цифре 50 вершин всего лишь потому, что моя уже старенькая программа тестирования задач TSP работает только в пошаговом режиме. Я и с сотней вершин работал, с напрягом, конечно, оттого что пытался после каждого шага перерисовать экран. Настоящую "боевую" я разрабатываю, но работа тормозится постоянно. Планирую варианты Tiny-8, Small-40, Medium(2000-9000), Large>Medium, Huge>Large, Vast>Huge, с разными алгоритмами. Цифры - это максимальное число вершин, точные значения будут вычислены позже. Возможно, от простого переборного варианта Tiny я откажусь. К Large, Huge и Vast приступлю, только если заимею более мощное железо.

А вот планарный вариант или, что почти что то же, вариант на сфере, планирую делать. Число вершин - не ограничено. Придумал серьёзное упрощение этих задач.

Что касается выражения "постепенное добавление весов", то это выдумка исключительно Ваша. Мои итерации более изощрённые. Градиентным методом не пользуюсь, многомерное пространство вершин (оно и не пространство вовсе) так хитро устроено, что термин градиент и приладить-то некуда. Вдобавок, аналога принципиальной проблемы HK-границы у меня просто нет! В моей формуле граница точная и достижимая. Если бы ещё знать число итераций, чтобы добраться до границы.

Спасибо за информацию, когда появится возможность, пошарю в гугле, но лучше, если бы Вы оставили несколько ключевых ссылок.

Индийскую работу от 2002 года я читал. Но никак с ней не пересекаюсь. А ещё я зря потратил время на штудировании статьи Мирона Тельпиза. Он утверждал, что P versus NP. Утверждение мне понравилось, а вот доказательства я так и не увидел.

А статья про ЦЛП - так себе, только устарелое вступление к черновику темы. Вероятно, я её удалю. На самом деле я не хотел убивать TSP. Пусть здравствует! Мне нужно было всего лишь привлечь внимание и заманить такого посетителя, как Вы! Я теперь почти абсолютно уверен, что на правильном пути. Дойти бы его...

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

Этот адрес должен знать каждый - http://chillugy.narod.ru/

1.

Получен первый отклик на статью I KILL TSP от Jonny, пространный и проблемный.
Jonny

Извините, что отписываюсь не на форуме, он почему-то не добавляет мои сообщения :/ Алгоритм придуманный вами конечно же давно и хорошо известен. Оценка нижней границы разработана Хэлдом и Карпом 1970 (Held&Karp HK) является золотым стандартом для TSP. Я сам балуюсь математикой с программированием и тоже сам додумался до схожего алгоритма, однако мне повезло больше (я надеюсь, а время покажет). Отклонение нижней границы от оптимума в HK ~1%, что совсем не плохо. На гугле много иностранной литературы по границе HK. В частности основная теорема (которую можно доказать на пальцах) об эквивалентности идеальной (речь идет о стратегии улучшения) границе HK решению ЛП релаксации ЦЛП постановки коммивояжера. Что касается стратегий улучшения (постепенного добавления весов), то это вопрос вторичный и обычно здесь используется метод улучшения по градиенту (литературы вобщем-то полно). Отдельное спасибо за простоту и доходчивость текста "статей", что называется пожалели читателя :) Что касается преобразования общих графов в графы, на которых выполняется неравенство треугольника , то здесь не все так просто (имхо). Ведь кратчайший остов+[ребро для замыкания] в этом случае могут быть больше чем кратчайший тур коммивояжера, а знчит HK - граница уже не подходит. Могу ошибаться, но по-моему это принципиальная проблема для HK -границы. Я тоже написал свою программу планирования развозочных маршрутов, но пока еще мир не готов ее увидеть. Удивило, что вы пользуетесь стандартными компонентами билдера для работы с данными, прямо как "не в городе живете". Для придания товарного вида программам рекомендую освоить компоненты EhLib (золотой стандарт для билдера). Кстати, по-поводу экспериментов на ЗКМ, существует специальная библиотека задач-тестов называется TSPLIB95 (золотой стандарт), если хотите и дальше продолжать в этом направлении обязательно ознакомтесь. Задачки на 50 точек -семечки, нужно решать хотябы 150, чтобы писать I kill ... Стихи забавны, поэма прямо как богема, хотя лично я никогда не понимал, чем уж так красивы стихи и поэмы. Я люблю пейзажи, красивые алгоритмы, шутки и анектоды (эти хитросплетения нескольких смыслов всегда очень красивы), ну а стихи - для меня это нечто среднее между красивым пейзажем и красивой шуткой (игрой слов) в результате получается "ни то ни се а так пустяк" примерно как женский спорт ;)). В целом подобного рода сайты я называю "творческими кладезями", в том смысле, что человек выкладывает на них самое хорошее чем жил 30 лет. Да и по поводу теста чисел на простоту с логарифмической сложностью, готов ли ваш алгоритм? В 2002 состоялась сенсация, Индийские математики вписали себя в историю, создав алгоритм с логарифмической сложностью. Хотя на практике он разумеется проигрывает рандомизированным тестам, основанным на малой теореме Ферма. Статьи по ЦЛП по-возможности прочту позже, надеюсь они написанны в непринужденном - летнем стиле как и все ваши поэмы ;))) За музыку респект, надо будет заценить.