Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
Ради примера — приближенный МВиГ на данных одной крупной компании дал ответ только спустя 8 дней 23 часа 47 минут на кластере из 512 Intel XEON и 4000 Gb оперативки.
Поверьте, компании готовы платить огромные деньги за то, чтобы получить хотя бы приближенные решения. Потому что на тех объемах данных, что у них есть, точное решение посчитать невозможно. В посте приведены алгоритмы, различные существующие. Ремарка про один граф относится к подбору констант, это всегда определяется данными и только ими. Нельзя их угадать заранее для любого графа.
Рекомендую Вам прочитать Кормена(главы про основы вычислительной сложности), книжку-методичку от MIT по алгоритмам приближенного решения NP-тяжелых задач(к сожалению, она так и не вышла, валяется в сети в виде презентации), и пересесть на более подходящий для таких целей язык(раз уж он Вас ограничивает), потому что на маленьких размерностях Вы никогда не увидите ничего интересного.
задача стояла конкретно для одного графа.
понятно, что на разных графах будут разные результаты, разный подбор эвристик, констант в алгоритмах и т.д.
в любом случае ни один из этих алгоритмов не дает верное решение. только близкое к нему. и на другом графе будут, возможно, другие результаты. однако жадина+метод ветвей и границ наиболее оптимален, т.к. никогда не будет худшим.а у простой жадины он точно всегда выиграет. единственное — когда-то может повезти, и чистый МВиГ посчитается быстро и выиграет.
Первый мой комментарий к моему посту. Так что идеально удовлетворяет.
Поймите же, наконец, что алгоритм с экспоненцальной сложностью не интересен — уже есть такой же по сложности — полный перебор.
Точного решения NP-трудных задач за хотя бы полиномиальное время на текущий момент не существует в природе.
А за нахождение такого алгоритма даже существует специальная премия с нехилым денежным бонусом.
Ваши графики ничего не говорят о сложности — слишком маленькие данные. Это как знаете, в окрестности 0 и x, x^2, x^4 и т.д. тоже почти одно и то же, на первый взгляд.
А x на отрезке [0,1] так вообще самый «большой». А вот потом все ровно наоборот.
Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
Понятно. Да, это отличная задача для мотивации разобраться с алгоритмами работы с матрицами, памятью и т.д. Я сам когда-то с этого же приблизительно начинал. Тогда вопрос снят.
Поймите, я Вас не критикую, я пытаюсь указать на моменты, которые Вы не заметили.
К сожалению, вот этот случай, когда стоимости равны, может «увести» алгоритм в ветку, в которой на следующих шагах все гораздо хуже, чем если бы мы пошли в другую равную. Такая ситуация уникальна и возникает редко. Но в огромных графах даже почти нулевая вероятность может проявиться — и тогда Ваш алгоритм даст сильно неверный ответ.
Так что нельзя говорить, что он 100% корректен — бывают случаи, когда может «не получиться»
Как раз-таки нет, никакого противоречия. «Не меньше» не значит «больше». Может быть «равно». А если минимальная стоимость равна, то следовательно, ответ может быть и там.
Говорю же, не лезьте в теорию, у нас разные уровни подготовки.
Так что, как это ни грустно признавать, Ваш алгоритм не строго корректен и экспоненциален.
Так что Вы сделали то, что никому не нужно.
Людям нужна либо строгая корректность(минимальный процент людей, в основном, из науки + у них обычно не слишком большая размерность, кластера за пару недель справляются) либо время работы(95% заинтересованных лиц — им нужен достаточно точный ответ, однако размерности данных зашкаливают).
Типичный пример — задача составления расписаний. Алгоритмы там те же, что и коммивояжер. Только коммивояжер не слишком интересен практически, а вот расписания интересны.
Реальная задача — расписание в РЖД. Представляете, сколько там станций и сколько составов? Алгоритм с экспоненциальной сложностью даст ответ, в лучшем случае, в следующем тысячелетии.
Я лишь предлагал алгоритм приближенного решения задачи. Потому что при больших размерностях получить точный ответ нельзя — надо ждать столетия вычислений.
Ваш алгоритм, к сожалению, тоже экспоненциален, так что на больших данных ждать его придется очень долго.
И, к сожалению, он теряет свойство корректности. Потому что даже при равных минимальных границах выбор пути в котором размерность меньше, не означает, что оптимальное решение не может лежать в другом пути.
Проблема в том, что на больших, очень больших графах разница в штрафах между ветвями становится очень маленькой, и подобная эвристика может «увести» алгоритм в ветку, которая кажется чуть-чуть совсем хуже, но зато путь на 1 ребро больше.
На маленьких графах такого не случается. А на больших — редко, но метко.
Пути решения различны, я в одном из своих постов предлагал хранить неплохие ветки в памяти подольше, чтобы иметь возможность к ним «откатываться»
Эвристичность тут в том, что желание двигаться в глубину — это наше желание, разработчиков, чтобы получить ответ. Это требование наше, а не задачи. Требование задачи — минимальный путь, только и всего. Это все и портит, грубо говоря, мы вносим в алгоритм то, что ему может помешать.
Про оперативку.
Дело в используемом языкe. На С++ я обсчитывал графы по 1000 вершин на ноутбуке с 8Гб оперативной памяти. 500 вершин — за глаза хватало 4Гб.
Попробуйте язык без сборщика мусора, если это в Ваших силах, конечно, и оперативки будет хватать.
а я ведь еще помню Ваш пост про MVC… но тогда не получилось…
Возможно, в разных сферах разные базовые понятия…
1) Я никогда и не отрицал этого, я утверждал лишь про приближенные решения
2) Без эвристики — да, будет найдено верное решение. С эвристикой — нет, не всегда.
По поводу нескольких точек — Вы не правы. Прошу ссылку подтверждающую Ваши слова.
Рекомендую Вам прочитать Кормена(главы про основы вычислительной сложности), книжку-методичку от 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Гб.
Попробуйте язык без сборщика мусора, если это в Ваших силах, конечно, и оперативки будет хватать.