Как стать автором
Обновить
24
0

Пользователь

Отправить сообщение
но зато это стандарт, а не велосипед.
видимо, о for_each Вы не слышали…

прощай, vnaz… это явно хабро-самоубийство…
а я ведь еще помню Ваш пост про MVC… но тогда не получилось…
Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
Простите за нескромный вопрос, но какое у Вас образование?
Возможно, в разных сферах разные базовые понятия…

1) Я никогда и не отрицал этого, я утверждал лишь про приближенные решения

2) Без эвристики — да, будет найдено верное решение. С эвристикой — нет, не всегда.

По поводу нескольких точек — Вы не правы. Прошу ссылку подтверждающую Ваши слова.
Ради примера — приближенный МВиГ на данных одной крупной компании дал ответ только спустя 8 дней 23 часа 47 минут на кластере из 512 Intel XEON и 4000 Gb оперативки.
Поверьте, компании готовы платить огромные деньги за то, чтобы получить хотя бы приближенные решения. Потому что на тех объемах данных, что у них есть, точное решение посчитать невозможно. В посте приведены алгоритмы, различные существующие. Ремарка про один граф относится к подбору констант, это всегда определяется данными и только ими. Нельзя их угадать заранее для любого графа.
Так что, подытожу.

Рекомендую Вам прочитать Кормена(главы про основы вычислительной сложности), книжку-методичку от MIT по алгоритмам приближенного решения NP-тяжелых задач(к сожалению, она так и не вышла, валяется в сети в виде презентации), и пересесть на более подходящий для таких целей язык(раз уж он Вас ограничивает), потому что на маленьких размерностях Вы никогда не увидите ничего интересного.
задача стояла конкретно для одного графа.
понятно, что на разных графах будут разные результаты, разный подбор эвристик, констант в алгоритмах и т.д.
в любом случае ни один из этих алгоритмов не дает верное решение. только близкое к нему. и на другом графе будут, возможно, другие результаты. однако жадина+метод ветвей и границ наиболее оптимален, т.к. никогда не будет худшим.а у простой жадины он точно всегда выиграет. единственное — когда-то может повезти, и чистый МВиГ посчитается быстро и выиграет.


Первый мой комментарий к моему посту. Так что идеально удовлетворяет.
Поймите же, наконец, что алгоритм с экспоненцальной сложностью не интересен — уже есть такой же по сложности — полный перебор.

Точного решения NP-трудных задач за хотя бы полиномиальное время на текущий момент не существует в природе.

А за нахождение такого алгоритма даже существует специальная премия с нехилым денежным бонусом.

Ваши графики ничего не говорят о сложности — слишком маленькие данные. Это как знаете, в окрестности 0 и x, x^2, x^4 и т.д. тоже почти одно и то же, на первый взгляд.
А x на отрезке [0,1] так вообще самый «большой». А вот потом все ровно наоборот.
Мой алгоритм не нуждался в исправлениях, у него другие цели.

Он работает на огромных данных за адекватное время и не упирается в оперативку.

Ваш же алгоритм будет работать столько, что до Пекина пешком можно успеть… Раз 200
Ответов может быть несколько, да. И такое бывает.

Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
Понятно. Да, это отличная задача для мотивации разобраться с алгоритмами работы с матрицами, памятью и т.д. Я сам когда-то с этого же приблизительно начинал. Тогда вопрос снят.

Поймите, я Вас не критикую, я пытаюсь указать на моменты, которые Вы не заметили.

К сожалению, вот этот случай, когда стоимости равны, может «увести» алгоритм в ветку, в которой на следующих шагах все гораздо хуже, чем если бы мы пошли в другую равную. Такая ситуация уникальна и возникает редко. Но в огромных графах даже почти нулевая вероятность может проявиться — и тогда Ваш алгоритм даст сильно неверный ответ.

Так что нельзя говорить, что он 100% корректен — бывают случаи, когда может «не получиться»

Как раз-таки нет, никакого противоречия. «Не меньше» не значит «больше». Может быть «равно». А если минимальная стоимость равна, то следовательно, ответ может быть и там.

Говорю же, не лезьте в теорию, у нас разные уровни подготовки.
Так что, как это ни грустно признавать, Ваш алгоритм не строго корректен и экспоненциален.

Так что Вы сделали то, что никому не нужно.

Людям нужна либо строгая корректность(минимальный процент людей, в основном, из науки + у них обычно не слишком большая размерность, кластера за пару недель справляются) либо время работы(95% заинтересованных лиц — им нужен достаточно точный ответ, однако размерности данных зашкаливают).

Типичный пример — задача составления расписаний. Алгоритмы там те же, что и коммивояжер. Только коммивояжер не слишком интересен практически, а вот расписания интересны.

Реальная задача — расписание в РЖД. Представляете, сколько там станций и сколько составов? Алгоритм с экспоненциальной сложностью даст ответ, в лучшем случае, в следующем тысячелетии.
Я лишь предлагал алгоритм приближенного решения задачи. Потому что при больших размерностях получить точный ответ нельзя — надо ждать столетия вычислений.

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

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

Проблема в том, что на больших, очень больших графах разница в штрафах между ветвями становится очень маленькой, и подобная эвристика может «увести» алгоритм в ветку, которая кажется чуть-чуть совсем хуже, но зато путь на 1 ребро больше.

На маленьких графах такого не случается. А на больших — редко, но метко.
Пути решения различны, я в одном из своих постов предлагал хранить неплохие ветки в памяти подольше, чтобы иметь возможность к ним «откатываться»
Эвристические алгоритмы в общем случае уже не всегда гарантируют точный ответ.

Грамотно написанный МВиГ без эвристик дает верный ответ, только тогда он не сильно отличается от полного перебора.

МВиГ c эвристиками не дает гарантированного верного ответа.

Поверьте, на С++ в 8Гб можно засунуть гораздо больше, чем в php ;)
Эвристичность тут в том, что желание двигаться в глубину — это наше желание, разработчиков, чтобы получить ответ. Это требование наше, а не задачи. Требование задачи — минимальный путь, только и всего. Это все и портит, грубо говоря, мы вносим в алгоритм то, что ему может помешать.

Про оперативку.
Дело в используемом языкe. На С++ я обсчитывал графы по 1000 вершин на ноутбуке с 8Гб оперативной памяти. 500 вершин — за глаза хватало 4Гб.
Попробуйте язык без сборщика мусора, если это в Ваших силах, конечно, и оперативки будет хватать.
upd. кстати абзац про эвристику в Вашем посте был дословно скопирован из моего поста, было бы неплохо это указывать, но это так, ремарка.

Информация

В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Работает в
Зарегистрирован
Активность