Какова ожидаемая длина кратчайшего гамильтонова пути в случайно выбранных точках плоской сетки?

$k$ различных точек выбираются случайным образом из сетки . (Очевидно, что и является заданным постоянным числом.) Из этих точек строится полный взвешенный граф таким образом, чтобы вес ребра между вершиной и вершиной равнялся манхэттенскому расстоянию двух вершин в исходной сетке. , $p\times q$ $k\leq p\times q$ $k$ $i$ $j$

Я ищу эффективный способ вычисления ожидаемой длины кратчайшего (минимального общего веса) гамильтонова пути, проходящего через эти узлов. Точнее, следующие наивные подходы нежелательны: $k$

$\bullet$ Вычисление точной длины пути для всех комбинаций k узлов и получение ожидаемой длины.

$\bullet$ Расчет приблизительной длины пути для всех комбинаций k узлов с использованием базовой эвристики использования минимального остовного дерева, которая дает ошибку до 50%. (Лучшая эвристика с меньшим количеством ошибок может быть полезна)

graph-theory co.combinatorics planar-graphs hamiltonian-paths Джавад
источник

В настоящее время нет надежды на эффективный алгоритм, поскольку невзвешенная задача о гамильтоновом пути на плоской сетке является NP-полной.

Мухаммед Аль-Туркистани

Когда вы говорите о гамильтоновом пути, вы думаете о гамильтоновом пути с наименьшим весом (иначе говоря, проблема коммивояжера)?

a3nm

@ MohammadAl-Turkistany твердость HAM PATH не обязательно является препятствием, так как ОП просто оценка случайных точек.

Суреш Венкат

@ a3nm да, и я исправил это.

Суреш Венкат

Что плохого в вычислении точной длины обхода для многих случайных выборок из точек и в определении ожидаемого значения и стандартного отклонения? Насколько большим вам нужно ?

k

$k$

k, p, q

$k, p, q$

Питер Шор

Ответы:

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

L \approx (p q k)^{1 / 2} f (k / p q) + (p + q) g (k / p q) .

$L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$

Теперь вы можете использовать эксперименты над задачами меньшего размера, чтобы выяснить, что такое и . Во-первых, чтобы оценить , вы хотите провести эксперименты на выборке без границы: самый простой способ сделать это - использовать сетку с левой стороной, соединенной справа и сверху вниз, образуя тор. Чтобы оценить , вы можете использовать эксперименты на сетке . $f$ $g$ $f$ $p\times p$ $g$ $p \times q$

Для оценки вам нужно решить (точно или приблизительно) относительно большие TSP, поскольку чем больше те, которые вы используете для оценки, тем лучше будут ваши результаты. Вы можете использовать эвристику с точностью до нескольких процентов или точный код TSP. Смотрите здесь для хорошей эвристики. Решатель Concorde TSP Билла Кука найдет точный оптимум для достаточно больших экземпляров (это лучший из доступных кодов TSP) и может быть использован бесплатно для академических исследований.

Питер Шор
источник

Используя терминологию из TSPLIB , я искал SOP, а не TSP. Умножение рассчитанного для TSP, на дает верхнюю оценку для SOP. К сожалению, Concorde TSP solver не обрабатывает SOP, и я не смог найти SOL solver онлайн.

E [L]

$E[L]$

(k - 1) / k

$(k-1)/k$

Джавад

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

E [L]

$E[L]$

L

$L$

L

$L$

E [L]

$E[L]$

k

$k$

E [L]

$E[L]$

Джавад

Я тоже не совсем понял причину коэффициента . Почему это не должно быть ? Как изменяется эта аппроксимационная формулировка для меньших значений и ?

k^{2}

$k^2$

k^{2} / (p q)

$k^2/(pq)$

p

$p$

q

$q$

Джавад

@ Джавад: Хороший вопрос. Я был неправ, потому что я как-то думал о баллах, когда писал свой ответ. Коэффициент основан на моем предположении, что сетка имеет ребра единичной длины, поэтому вся область имеет размер . Среднее ребро должно иметь длину , и существует ребер, поэтому, если вы хотите, чтобы оставался примерно постоянным, первый член должен быть .

k^{2}

$k^2$

p \times q

$p\times q$

p \times q

$p \times q$

θ (\sqrt{p q / k})

$\theta(\sqrt{pq/k})$

k

$k$

f

$f$

\sqrt{p q k} f (k / p q)

$\sqrt{pqk} f(k/pq)$

Питер Шор

Для разница между длиной TSP и длиной SOP должна быть почти незначительной.

k \approx 10^{6}

$k \approx 10^6$

Питер Шор