Comments 56
Очень интересно! Попробую повторить на 3090.
Ожидаемо, не хватает памяти.
Сразу вопрос - почему Беллман, почему не A* (или даже Bidirectional A*)?
Вы не из Huawei? )
(https://career.huawei.ru/rri/)
Беллман значительно медленнее Dijkstra, Dijkstra значительно медленнее A*.
A* значительно медленнее и затратнее по памяти чем Bidirectional A*. (чуть ли не в log меньше памяти и ходов)
Да и с bidirectional A* вы всегда можете нагенерировать кучу отрезков в 3-4-5 точек, и брать уже готовые при поиске. (Для 1 000 точек - типичная задачка для Aurora, вы получите всего около 8 Gb троек, однако сократите количество ходов в 2 раза).
https://www.researchgate.net/figure/Astar-versus-Dijkstra-search_fig6_225733449
Надо будет сделать публикацию )
Мне думается вы перепутали алгоритмы задача коммивояжёра и поиск пути.
Боюсь, что с тройками городов я точно не ошибся ).
А по A*:
Эвристика - минимальная дистанция до ближайшего нового города (если при возвращении назад у нас до ближайшего нового города расстояние меньше, чем проход к новому напрямую - значит эвристика работает).
Единственный минус - каждый раз искать через BFS ближайший новый город )
Как-нибудь сделаю публикацию со всеми наворотами
Вы тут описываете какую-то эвристическую жадность. Этот метод не дает оптимальное решение задачи Коммивояжора.
Все давно решено с нормальной эвристикой (вот это да, оказывается эти алгоритмы взаимозаменяемы)
Ну, это на нобелевскую премию тянет. А еще на филдофскую медаль и несколько мелких призов по миллиону долларов, вроде Millennium Problem Prize от Clay institute.
Там полиномиальное решение NP-полной задачи. P=NP доказано - расходимся!
Другое, более вероятное объяснение заключается в том, что этот алгоритм находит лишь некоторую аппроксимацию оптимального решения. Что, возможно даже, пригодится в некоторых практических задачах, да и аппроксимации NP-полных задач со строгим доказательством точности - весьма интересная и активная тема исследований, но это параллельно обсуждаемой статье.
Сколько сарказма.
Знаете, простой двухсторонний BFS уже значительно облегчает эту задачу (расходимся) )
Вы все еще про коммивояжора? Нет, просветите, пожалуйста, как BFS, путь и двусторонний, вообще хоть как-то применим тут.
Я просто оставлю ссылку на курс тут:
https://habr.com/ru/articles/255285/
Замечание. Алгоритмы — поиск в глубину (DFS), поиск в ширину (BFS), алгоритм Дейкстры (UCS) и А*, очень похожи и отличаются только в некоторых деталях реализации. Таким образом, реализовав DFS, остальные получается из него относительно просто.
Правда, про двухсторонний поиск и снижение числа ходов в 2 раза вам там не расскажут. По второму пункту придется подождать моей публикации.
Я там подробно напишу почему в этой задаче NP = SQRT(NP)/2 (В худшем случае :) )
Ну или 500 ускорителей вместо 1000000 :)
Не надо мне ссылки на статьи по базовым алгоритмам, пожалуйста, давать. Я всю эту базу знаю гораздо лучше вас, поэтому и придераюсь, потому что вы дичь говорите (1).
Да, все эти алгоритмы концептуально похожи, но они не взаимозаменяемы. Так, BFS не работает с графами, где у ребер разные длины (2), что как раз и наш случай.
И, кстати, все перечисленные вами алгоритмы ищут кратчайший путь в графе. Они никак не могут найти кратчайший путь, проходящий через все вершины, что надо в задаче коммивояжора, если только их не применять к некоторому особому графу, но вы про это тоже ничего не сказали. Плюс, BFS даже там не применим.
Поэтому, пожалуйста, или признайтесь, что ошибались, или расскажите мне уже хоть немного подробностей о том, как же BFS применяется к задаче коммивояжора.
Я там подробно напишу почему в этой задаче NP = SQRT(NP)/2
Вам, похоже, точно нужны ссылки на базовые курсы по теории сложности. Хотябы вики прочитайте, что бы понять, какой бред вы только что написали.
(1) может вы просто очень плохо выражаете свои мысли. Есть парочка фраз, которая бы все объяснила, но вы их из себя даже с моими подсказками выдавить не можете.
(2) Есть модификация BFS работающая с ребрами целых неотрицательных длин, ограниченных К за O(KV+E). Но обсуждаемая задача другая.
Так, BFS не работает с графами, где у ребер разные длины
BFS работает со всеми графами (и даже с направленными циклическими, но долго)
если только их не применять к некоторому особому графу
Что? А, в каждый момент Вы можете взять любой из оставшихся городов.
признайтесь, что ошибались, или расскажите мне уже хоть немного подробностей о том, как же BFS применяется к задаче коммивояжёра.
Так вот же у Вас же в публикации этот самый BFS, только с весовой функцией.
Вам, похоже, точно нужны ссылки на базовые курсы по теории сложности. Хотябы вики прочитайте, что бы понять, какой бред вы только что написали.
Как пройдете курс, начинайте развиваться (чтобы к началу учебы в институте не ударить в грязь лицом).
И так далее, и тому подобное )
BFS работает со всеми графами (и даже с направленными циклическими, но долго)
В смысле? Вы предлагаете обходить каждую вершину кучу раз, пока у нее расстояние улучшается? Ну так это не BFS уже, а совершенно другой алгоритм. Полный перебор фактически.
Не надо мне про bi-directional Bfs рассказывать. Я про него знаю. Почитайте ваши ссылки сами, убедитесь, что там нет никакой весовой функции.
Как пройдете курс, начинайте развиваться (чтобы к началу учебы в институте не ударить в грязь лицом).
Ха-ха! Молодой человек, я эти курсы преподавал. У меня, между прочим, уже давно Phd по computer science. Не в шарашке какой-нибудь, а в одном из ведущих западных университетов.
Щекотать ваш синдром Даннинга-Крюгера мне больше не интересно. Досвидания!
Hidden text
При BranchingFactor ~ N (от N до N/2) и N/2 ходов получаем N^(N/2) для каждого из 2-х поисков в ширину.
Итого 2*N^(N/2) для коммивояджера. И делим все на 2 или 4.
Или SQRT(N^N)/2, как и было обещано.
Да вы просто дурак, от вас воняет!
Иди другим дуракам рассказывай какой ты умный!
Еще раз, BFS в чистом виде не применим к задаче коммивояжора. Во-первых, тут есть функия длины, во-вторых, как вы его заставите обойти все вершины по одному разу?
Сначала с этим определитесь, а потом уже подумайте, стоит ли цитировать неприменимые к задаче оценки.
Consistent Admissable Heuristic for TSP and Graph Search.
Да, докажите мне:
1) что вы можете найти решение лучше чем сумма минимальных ходов из каждой вершины графа (Admissable)
2) Вторую часть почитайте внимательнее ( берете минимальный ход - вы удаляете какой-то элемент из суммы - сумма становится меньше. Прибавляете его обратно как Cost Function - сумма остается той же). Если вы случайно измените возможные ходы (и избавитесь от минимальных ходов в других частях суммы) - сумма увеличится. Попробуйте доказать что это не так (Consistent)
Все, это готовая эвристика для TSP и поискам пути по графам. Я могу спокойно делать A* и получать оптимальное(минимальное) решение.
(P.S. ой, кажется на старом аккаунте лайки от астрофизиков, выдвигаемых на нобелевскую премию. Ой вот это прикол! Может, почитаете по теории графов (и алгоритмам поиска путей)? )
Опять, сначала. Вы понимаете, что задача коммивояжора - не задача поиска кратчайшего пути? Там надо все вершины посещать по одному разу. Можно свести эту задачу просто к поиску пути в особом графе и там даже А* даже с такой эвристикой заработает - но вы ни разу так из себя ни одного слова про это сведение не сказали. Без этого обсужать корректность эвристики бесполезно.
Это задача поиска кратчайшего пути.
Проходящего через все точки.
Это учтено в эвристике (алгоритм не будет завершен пока вы не получите H = 0, и это возможно только после обхода всех вершин.
Особый граф\не особый граф (откуда такие определения? :) ) - важно лишь то, что веса положительны. На уровне кода (получение возможных ходов) - да, я просто удалю ходы для уже посещенных нод (и это отражено в эвристике). Все графы получаемые таким образом имеют лишь одно посещение каждой вершины, а так же ацикличны, а после N ходов - содержат замкнутый путь через все вершины (тут надо проработать вопрос возвращения в исходную точку. На ходе N-1 сделать возможным лишь 1 ход - в начальную точку). С этим тоже вполне очевидно - такой ход есть, иначе наша вершина в точке N-1 уже посещена.
Не путайте это с https://ru.wikipedia.org/wiki/Эвристический_алгоритм
Все, моя эвристика обладает обоими свойствами (и я это доказал), следовательно я получу наикратчайшее решение.
Ну, это на нобелевскую премию тянет. А еще на филдофскую медаль и несколько мелких призов по миллиону долларов, вроде Millennium Problem Prize от Clay institute.
Там полиномиальное решение NP-полной задачи. P=NP доказано - расходимся!
Следует помнить, что A* по сложности примерно N+C, где N - наикратчайшее расстояние, C - дополнительно открытые ноды.
Таким образом я получаю для задачи N^N сложность в N+C.
С двухсторонним поиском еще лучше.
Так, BFS не работает с графами, где у ребер разные длины
BFS вообще работает без учета длин ребер :)
BFS\DFS с весовой функцией - это и есть Дейкстра\Белман (послений алгоритм вообще не рассматривают обычно).
Можно свести эту задачу просто к поиску пути в особом графе
Да что за особые графы? Где это в теории графов-то?
Мне непонятно, как алгоритм поиска пути в графе помогает решению задачи коммивояжёра. Если бы вы приложили код решения, то мы могли бы оценить вашу эвристику.
Да он где-то нашел как A* применяют в том же самом графе, в котром работает ДП (одна вершина для каждого состояния, а ребра - все переходы). ДП в этом графе обходит его в топологическом порядке и так считает кратчайший путь в нем. Действительно, можно там гонять и A*. Но только вычисление эвристики делает худшую оценку работы алгоритма в log n раз хуже. Вопрос, обходит ли он в log n раз меньше вершин - остается открытым.
Вот только он похоже вообще не понимает, что там происходит, вставляет ссылки на доказательство, что эвристика подходит A*, вместо того, чтобы просто свести одну задачу к дургой.
Это ваша проблема если вы до сих пор не прошли рекомендуемый курс ).
Увы, для многих становится понятно, что в лучшем случае это (N+1)*N/2 открытых вершин (ну или около 10-100 тысяч для гарантированно наименьшего решения для 141 узла). Ну или решение NP задачи (потому что вычисление описанной эвристики, мягко говоря - не поиск минимальных остовных деревьев)
10-100 тысяч для гарантированно наименьшего решения для 141 узла
Так, вы уже очень близко! Остановитесь и подумайте, как у вас для 141 узла в графе откуда-то 10-100 тысяч вершин?
Это не вершины изначального графа же? Можете себе представить, из какого же графа эти вершины? Сколько их там?
Гражданин, пройдите хотя бы рекомендуемый курс, почитайте про теорию графов.
Если у вас полносвязные (и близкие к ним) ненаправленные графы (и N^N возможных решений) вызывают столько вопросов - это свидетельствует о вашей низкой квалификации в данных вопросах.
"полносвязные (и близкие к ним) ненаправленные графы" не вызывают у меня никаких вопросов. Я отлично понимаю, что O(V^2+E) будет в таких графах лучше чем O((V+E)logV). Если вам эта запись непонятна, почитайте про ассимтотическую сложность. Упомянутые вами курсы тоже эту тему затронут. Пройдите же их сами.
И вместо того, чтобы цеплятся за какие-то отдельные слова в моем тексте, ответьте, таки, на мой вопрос:
"как у вас для 141 узла в графе откуда-то 10-100 тысяч вершин?"
В курсе об этом тоже сказано - обычно это количество вершин во всех возможных вариантах решения на момент, когда оптимальное решение найдено.
Вы удивитесь - но поиск пути в квадрате 10x10 это около 2^100 вариантов решения(возможных путей). A* дает оптимальное (минимальное) решение "просмотрев" менее 1% из возможных вариантов.
Асимптотическую сложность и линейное программирование пока не рассматриваем.
По общим представлениям я получу оптимальное решение за сравнимое время, только на CPU и без 8 гб памяти ).
> обычно это количество вершин во всех возможных вариантах решения на момент, когда оптимальное решение найдено.
У вас очень кривые формулировки. Вариант решения - эйлеров путь. Количество вершин там - N. Это N*(количество варинатов решения)?
Вы удивитесь - но поиск пути в квадрате 10x10 это около 2^100 вариантов решения(возможных путей). A* дает оптимальное (минимальное) решение "просмотрев" менее 1% из возможных вариантов.
Нет не удивлюсь. Вы, похоже, примерно-то понимаете, что A* - это все еще алгоритм поиска кратчайшего пути в графе. Только граф к которому он применяется - это пространство решений, где каждая вершина соответствует пути в исходном графе без самопересечений, а конечная вершина - эйлеровому циклу. Там O(N2^N) вершин. Но словами вы эту простую мысль уже с десяток комментариев выразить никак не можете.
Теперь, вернемся к предудущему вашему предложению: как в этом графе будет работать обход в ширину?
Почитайте про A* (особенно доказательство оптимальности).
Пройдите курс (чтобы представлять, где BFS/DFS/Dijkstra/A*, как они работают и как они связаны). Не волнуйтесь, этот момент "плавает" даже у ресерчеров Huawei.
Какую простую мысль? Вы думаете никто кроме Вас не может прикинуть пространство возможных решений? )
Может, виной тому Особые Графы? )
Ну, это на нобелевскую премию тянет. А еще на филдофскую медаль и несколько мелких призов по миллиону долларов, вроде Millennium Problem Prize от Clay institute.
Там полиномиальное решение NP-полной задачи. P=NP доказано - расходимся!
Другое, более вероятное объяснение заключается в том, что этот алгоритм находит лишь некоторую аппроксимацию оптимального решения. Что, возможно даже, пригодится в некоторых практических задачах, да и аппроксимации NP-полных задач со строгим доказательством точности - весьма интересная и активная тема исследований, но это параллельно обсуждаемой статье.
Вот это да, спасибо, читайте в моем блоге.
Сейчас правлю публикацию.
Почитайте про A* (особенно доказательство оптимальности).
Опять-сначала. Я знаю про A* и доказательство понимаю. Именно поэтому меня так и смущает ваше применение алгоритма поиска кратчайшего пути к задаче о пути коммивояжора без каких либо намеков на сведение одной задачи к другой через конструирование (ха-ха) особого графа (он же пространство решений).
Какую простую мысль? Вы думаете никто кроме Вас не может прикинуть пространство возможных решений? )
По вышим предыдущим комментариям вообще не видно было, что вы хоть какое-то представление об этом имеете.
Например, вот эти ваши слова:
Это учтено в эвристике (алгоритм не будет завершен пока вы не получите H = 0, и это возможно только после обхода всех вершин
Вообще бред же. Алгоритм завершается в конечной вершине, которая соответствует замкнутому пути через все вершины. Ну, потому что A* в графе завершается, когда дойдет до конечной вершины. А не потому что H=0. Но если не иметь представления о том, в каком же графе вы A* запускаите, то примерно такого уровня высказывания и можно ожидать.
Может, виной тому Особые Графы? )
Это я пытался намеками вытащить из вас ключевые слова "пространство решений".
В astarlib(https://pypi.org/project/astar/), например, вывели функцию is_goal_reached , в других источниках (те же курсы) признак завершения поиска - H=0. (да и по определению эвристики - минимально возможная стоимость решения в самом решении должна быть равна 0).
Увы, как и BSF/Дейкстра/A* - методы решения задач оптимизации тоже связаны.
Есть не информированный поиск (простой перебор c IsGoalReached). Есть поиск с оценкой решения. Есть поиск с неотрицательной стоимостью любого действия (тут применим метод ветвей и границ).
Есть поиск решения с эвристикой (A*) - просмотр только тех решений, которые могут дать результат лучше имеющегося.
Ничто не мешает мне использовать A* не как Универсальное Средство для графов и этих, путей, во!(наверное, вы так и читаете), а как один из видов решения задач оптимизации. Это сразу отбрасывает все вопросы о Виде Графа, откуда и как этот граф получается на второй план. (остается только вопрос о том, что все веса должны быть положительны)
Кстати, тот же DreamCoder (очередной решатель SMT) использует не эвристику, а простой фильтр возможных ходов на основе нейросети (и не использует A*)
Ничто не мешает мне использовать A* не как Универсальное Средство для графов и этих, путей
Кроме того, что доказательство корректности работы A* - формулируется в терминах графов. Поэтому, если не представлять себе в каком графе вы его запускаете, можно получить проблемы. Например, можете мне объяснить, почему A* не запустится на задаче, где надо максимизировать, например, GCD всех длин ребер в пути коммивояжора? Ответ прост: нельзя свести задачу к поиску пити в графе. Вернее, там получается функция длины пути не удовлетворяющая некоторым свойствам функции длины, необходимим для работы алгоритма Дейкстры, надстройкой над которым A* и является.
Другой вопрос - Дейкстра\A* и TSP.
C A* все интереснее - не сохраняется никаких Минимальных оценок для узлов (что видимо и вызывает вопросы и путаницу). Все открытые варианты решения помещаются в очередь с приоритетом. Решения заведомо хуже имеющихся (на основе эвристики) не рассматриваются.
Кажется, это было в рекомендуемом курсе.
На выходных выложу пример.
И, A* ближе к методу ветвей и границ, чем к Дейкстре.
Да ладно! Цитата из википедии:
It can be seen as an extension of Dijkstra's algorithm
Ну так википедию до конца дочитайте.
Relations to other algorithms
A* itself is a special case of a generalization of branch and bound.[29]
A* is similar to beam search
В рекомендуемом курсе, кстати, есть ссылка на доказательство этого.
И так, подытожим:
1) A* можно спокойно применять для решения задачи коммивояджера
2) Моя эвристика для A* отвечает всем требованиям, необходимым для нахождения минимального решения (с доказательствами)
3) Следовательно, вы разговариваете с человеком, который уменьшил сложность решения задачи TSP с N^N до N+C (оптимальное решение, а не близкое к оптимальному) :)
Жду от Вас ссылок на конкурсы с призами, в которых я бы мог поучаствовать :)
Следовательно, вы разговариваете с человеком, который уменьшил сложность решения задачи TSP с N^N до N+C (оптимальное решение, а не близкое к оптимальному) :)
Где C= O(N^N). Так что никаких призов.
Да, A* можно решать задачу коммивояжора, но важно отметить, что он не запускается просто на исходном графе. На что я еще десяток комментариев назад намекал. А вы зачем-то копировали свойства эвристики.
Ок, ждем выходных, проверим.
Что-то мне подсказывает, что с указанной эвристикой C будет сильно меньше O(N^N) (A* эффективнее метода ветвей и границ, методом ветвей и границ решают задачу для 40+ городов (40^40)). Да и существующие методы на основе ветвей и границ будут открывать гораздо больше узлов.
будут открывать гораздо больше узлов (одно из свойств A* - за счет использования очереди с приоритетом)
Ну вот, опять вы что-то не то говорите.
Я, конечно, приношу вам извинения. Алгоритм применим, он работает, но у вас куча каких-то заблуждений на его счет или вы просто очень неясно выражаетесь.
Нет, очередь с приоритетом никак не влияет на количество открытых узлов. Очередь с приоритетом - лишь деталь реализации, чтобы вычисления работали побыстрее на шаге "взять вершину с минимальной оценкой". Более того, если использовать симметрию пространства решений для радикального уменьшения количества вершин, то у вас может оказаться очень много ребер ведущих в одни и те же вершины. В этом случае алгоритм без очереди приоритета будет даже быстрее (обработает те же вершины, но вычисления будут легче).
Далее, шаг "выбрать минимальную вершину" тоже не определяет количество посещенных вершин. Вместе со свойствами эвристики (с которыми вы как с писаной торбой носитесь), этот шаг гарантирует что алгоритм просмотрит вершины в топологическом порядке в ДАГе кратчайших путей. Дейкстра вообще обходит вершины в порядке увеличения растояния, а A* обходит приемущественно вершины, лежащие на кратчайшем пути к цели, но в правильном порядке.
А открывает A* горазно меньше узлов из-за корреляции эвристики с точной длиной пути. Не из-за допустимости или консистентности, и тем более не из-за приоритетной очереди.
Вот рассмотрите эвристику H(v)=0. Оценка всегда 0. Она допустима и консистентна. Но алгоритм выраждается в алгоритм дейкстры и обходит все вершины, которые ближе оптимального ответа. Даже если его через приоритетную очередь реализовывать.
Вкратце, если не хотите проходить курс:
Нет, очередь с приоритетом никак не влияет на количество открытых узлов. Далее, шаг "выбрать минимальную вершину" тоже не определяет количество посещенных вершин
Очередь с приоритетом и эвристика позволяют получить более оптимальные границы отсечения ветвей, чем при простом использовании метода ветвей и границ.
Так же позволяет отсекать заведомо менее удачные решения. И открывать только ноды, которые могут дать решение лучше. (В методе ветвей и границ вы не можете не открывать ноды, только потому что H+C>>Cbest, потому что у вас нет никакой оценки (эвристики)).
Нет никакой "корреляции эвристики с точной длиной пути", есть 2 требования (эвристика меньше или равна решению, и монотонность), соблюдение которых гарантирует то, что минимальное решение будет найдено в кратчайшие сроки.
Все рассуждения про При H=0 это дейкстра - немного не верны. A* прекрасно работает с деревом всех возможных решений (а Дейкстра, увы, нет). Поэтому на той же вики и написано - это скорее метод ветвей и границ (ну или в худшем случае Beam Search).
Очередь с приоритетом и эвристика позволяют получить более оптимальные границы отсечения ветвей, чем при простом использовании метода ветвей и границ.
Еще раз, есть реализация без очереди приоритетов! Просто с выбором минимума из массива циклом. 2 требования - они нужны только, чтобы гарантировать, что алгоритм найдет кратчайший путь, а не случайно отсечет его раньше времени.
Нет никакой "корреляции эвристики с точной длиной пути", есть 2 требования ... гарантирует то, что минимальное решение будет найдено в кратчайшие сроки.
Евристика, везде равная 0 - отлично отвечает обоим требованиям. Но кратчайшее решение будет найдено вообще не в кратчайшие сроки. Как так?
да, могут быть различные реализации (с архивом можно пролететь уже на лабиринте. Даже миллион-другой возможных решений - это уже секунда на выбор минимального элемента).
Эвристика =0 - вы не получите значительного отсечения возможных решений (жадный поиск с эвристикой и просто жадный поиск - разные вещи. Как правило, жадный поиск с эвристикой дает первое приближение границ лучше или такое же, как и просто жадный поиск).
Так же с H=0 вы не получите отсечения множества возможных решений без раскрытия нод (все выродится в Beam Search). Зачем раскрывать ноды, если H<=минимальному пути из данного узла, а C+H уже много больше Cmin? Тут метод ветвей и границ опять в проигрыше.
За счет этих свойств алгоритма A* обычно и говорят, что он снижает все сложность с NP до N+C (много отсекается за счет первого прогона, в дальнейшем отсечение возможных вариантов идет с учетом эвристической оценки).
Вы об этом хотели узнать? Это все есть в курсе )
Ну, это на нобелевскую премию тянет. А еще на филдофскую медаль и несколько мелких призов по миллиону долларов, вроде Millennium Problem Prize от Clay institute.
Ну а теперь перейдем к актуальным вопросам - где ссылки на различные конкурсы?
*с массивом
Кстати, как бонус - я получил эвристику для поиска наикратчайшего пути во всех графах :)
да, могут быть различные реализации (с архивом можно пролететь уже на лабиринте
Зависит от "лабиринта". Реализация с массивом может быть даже быстрее, ибо с приоритетной очередью будет O((V+E) logV) операций, а с массивом O(V^2+E). Тут V - это количество раскрытых вершин, а E - количество просмотренных ребер. В некоторых графах E ~ V^2. Это будет, например, если простарснство решений очень симметрично.
Так же с H=0 вы не получите отсечения
Да! Да! Это именно то, о чем я вам и говорю. H=0 - отвратительнейшая эвристика. Но она удовлетворяет обоим условиям! Значит, эти условия - это не то, что обеспечивает отсечение лишних вершин. Как я и говорил.
С другой стороны, если у вас есть волшебный оракул, который вам выдает абсолютно точную оценку оставшегося пути - то A* раскроет только вершины на кратчайшихпутях, отсекая вообще все лишнее.
Ровно, как я и сказал - отсечение происходит из-за кореляции оценки оставшегося пути с настоящей его длиной. Не из-за допустимости и согласованности эвристики. И не из-за приоритетной очереди.
что он снижает все сложность с NP до N+C
Почитайте курс про теорию сложности. Вы сейчас такую глупость сказали.
Ну а теперь перейдем к актуальным вопросам - где ссылки на различные конкурсы?
Поскольку вы так криво выражались, то, даже не смотря на все мои намеки и наводящие вопросы, выглядело так, будто вы предлагаете как-то запускать A* в изначальном графе, где всего N вершин. А не в пространстве решений, где вершин O(N^N). Что доказало бы P=NP. Если вам эта тема интересна, то начните хотя бы с википедии.
Так я вам написал, что у меня - волшебный оракул, с доказательством волшебности и на порядки лучше, чем MinimumSpanningTree. И мой алгоритм на порядки лучше, чем применяемый метод ветвей и границ.
И благодаря этому я отсеку большую часть ветвей уже после N шагов. И получу сложность в N+C.
И простой поиск пути в квадрате 10x10 - это 2^100 возможных решений. Можете посмотреть гиф еще раз (за конечное время :) )
вы так криво выражались
А, да, с N=50 при открытии 0.02 ветвей я получаю худшую сложность в N^(50*0.02)=N. Точнее,
т.е. нолики в графе Error вот этой таблице (до 100 точно):
И, да, в этой задаче я могу использовать даже не Bidirectional A*, а, скажем хитрый поиск из N/10 начальных точек.
Так я вам написал, что у меня - волшебный оракул, с доказательством волшебности и на порядки лучше
Так, т.е. вы согласны, что H=0 плохая эвристика, даже несмотря на ее допустимость и согласованность? И что много чего отсекается именно из-за корреляции эвристики с точной длинной оставшегося пути?
А, да, с N=50 при открытии 0.02 ветвей я получаю худшую сложность в N^(50*0.02)=N. Точнее,
Во-первых. вы N=50 там получаете 50. При конкретных N какие-то от них зависящие оценки смысла не несут особо.
Во-вторых, Лол. Вы там множитель не туда воткнули. В "точнее" уже правильно написали. Ну раскроете вы не N^N, А (N/50)^N. Конечно быстрее, но все еще экспоненциально. А главное, вы эту оценку в 0.02 еще докажите (вы же только допустимость и консистентность эвристики доказываете).
И простой поиск пути в квадрате 10x10 - это 2^100 возможных решений.
Нет, потому что каждую из 100 вершин надо раскрывать максимум один раз. Так что тут будет 100 открытых вершин. Вот тут как раз надо применять A* дейкстру, или что вам угодно, именно как алгоритм над графом.
Про H=0 и другие рассуждения про большой branching factor - давайте переформулируем вопрос.
Через какое максимальное количество неверных ходов эвристика полностью "забракует" неверное решение?
При таком подходе к анализу сложности становится более-менее очевидно, что это количество ходов не равно N (много меньше). Что дает нам новую оценку в N+N^T, где T - максимальное количество ходов, при котором любое неверное решение будет отсечено.
Это 3 требуемое свойство эвристики - она должны быть не меньше, чем Log(актуальное решение) (иначе мы рискуем получить отсечения пространства решений уже ближе к "листьям" нашего дерева возможных решений). Наша эвристика практически совпадает с решением.
Ага, третье свойство вылезло. Эвристика должна быть не больше точного значения пути, но, вот оказывается, не сильно меньше. Т.е, как я и говорил - коррелировать с точным значением.
Ну а итог-то какой?
Правильно, обычно говорят, что это означает что ваша задача решена наиболее эффективным способом из известных.
Hidden text
И ничто не мешает мне выбирать шаги из 2-3 и более точек.
Тогда я получаю N*(N-1)*(N-2)+1 возможных ходов для 3 точек (+1 - пропуск хода). Но у меня катастрофически уменьшается T (вероятность грубого промаха возрастает в 3 раза для всех N^3 вариантов) (а следовательно, мой алгоритм становится эффективнее за счет повышения нагрузки при открытии новых нод).
Это учтено в эвристике (алгоритм не будет завершен пока вы не получите H = 0, и это возможно только после обхода всех вершин
Бред. Вы вообще понятия не имеете, что говорите. Какой-то бессмысленный набор слов. Вроде ссылки на правильные слова даете, про допустимость эвристики, но вы их видимо, где-то скопировали вообще не понимя о чем они.
Эвристика в А* только влияет на скорость работы, позволяя алгоритму просматривать меньшее количество вершин, из-за того, что вершины просматриваются преемущественно в сторону известного конца. Она никак не может заставить алгоритм обойти все вершины.
Потом, вот эта эвристика - она же назачается каждой вершине, правда? Это функция от одной вершины. Вас не смущает, что ваша эвристика строит остовное дерево среди непосещенных пока вершин? Какие вершины непосещенные для данной вершины v?
Все графы получаемые таким образом имеют лишь одно посещение каждой вершины, а так же ацикличны,
Стоп. Вы там какие-то графы строите? Или вы хотели сказать про пути?
Следует помнить, что A* по сложности примерно N+C, где N - наикратчайшее расстояние, C - дополнительно открытые ноды.
Таким образом я получаю для задачи N^N сложность в N+C.
Ага. А теперь вопрос, как в графе из N вершин алгоритм открвает N^N нод? Может, там есть какой-то другой граф, в котором 2^N * N вершин? (Ну почитайте же хоть одну ссылку, которую сами даете!)
Эвристика в А* только влияет на скорость работы, позволяя алгоритму просматривать меньшее количество вершин, из-за того, что вершины просматриваются преемущественно в сторону известного конца
Эвристика - оценка наиболее эффективного возможного решения из данной точки.
У эвристик есть 2 основные характеристики:
1) приемлемость (эвристика всегда меньше или равна актуальному решению с этой нодой) https://en.wikipedia.org/wiki/Admissible_heuristic
2) и монотонность (https://en.wikipedia.org/wiki/Consistent_heuristic)
Эти 2 свойства позволяют говорить, что в любом графе будет найдено оптимальное (минимальное) решение. (И что значительная часть возможных решений будет отсечена).
В A* нет никакого "вершины просматриваются преемущественно в сторону известного конца". Если вам лень вникать в эту сложную математику - вершины просматриваются в сторону наиболее эффективного решения (на основе PriorityQueue по стоимости).
https://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif
То же самое по остальным "Емким, адекватным" замечаниям ).
Почитайте уже про теорию графов и алгоритмы, слушать ваши изречения про Особые Графы и их топологические порядки (а так же про остовные деревья, и оценки возможных решений).
Ждите, на неделе может закончу публикацию в Medium. Кстати TSP-lib посмотрите, там давно в 2000 точек ушли )
У эвристик есть 2 основные характеристики
Опять вы цитируете то, чего непонимаете.
Да, чтобы А* работал нужны эти 2 свойства оценки в вершине. Как это опровергает мои слова? Какое это вообще имеет отношение к обсуждению?
"преемущественно в сторону известного конца" и "вершины просматриваются в сторону наиболее эффективного решения" - не вижу разницы. Эффективное решение - в смысле кратчайшей длины пути (помните еще, что А* - это алгоритм поиска кратчайшего пути на графе?). Кратчайшие пути - в сторону конца и есть.
на основе PriorityQueue по стоимости).
Решили для убедительности каких-то умных на ваш взляд слов процитировать? Это деталь реализации, ни на логику аргумента ни на его правилность не влияющую вообще. Более того, в некоторых графах использовать приоритетную очередь вообще противопоказано, от этого алгоритм работает в log n раз медленнее (подсказака: в плотных графах).
Почитайте уже про теорию графов и алгоритмы, слушать ваши изречения про
Особые Графы и их топологические порядки (а так же про остовные деревья,
и оценки возможных решений).
Я знаю про теорию графы и алгоритмы. Я их преподавал, когда получал свое PHD по computer science (которую уже давно получил). Именно поэтому мне ваш эффект даннинга-крюгера так в глаза бросается.
Беллман тут упоминается лишь в как один из основателей идеи Динамического Программирования. Алгоритм Беллмана тут вообще никаким боком. Как и A* - прочитайте хотя бы первый абзац в статье.
В python есть модуль array, который работает чуть иначе, чем листы
Коммивояжер на GPU