|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 24 Mar 2002 00:12:50
To : Anton Kuznetsov
Subject : Ышо раз задачка
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый Anton! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Anton Kuznetsov и Alexander Shmidt! Что за "Ышо раз задачка", а
где же яйца?!
AS>> Hайти минимаьный (по "длине") путь в графе, который проходит по
AS>> всем вершинам и начинается в строго фиксированной вершине
AS>> (заканчивается - где угодно).
AK> Вроде оно же динамически решается - для каждой вершины хранишь
AK> длину(путь), который начинается в твое любимой вершине, а
AK> закончивается в данной. При добавлении новой вершины выбираешь min для
AK> всех i от 1 до того что уже обработали (то что хранится в вершине i +
AK> ребро от i до новой)...
Привет, Однофамилец! :)
Идея твоя поначалу показалась настолько гениальной, что я, даже несмотря на
позднее время, начал ее реализовывать.
Hа практике оказалось, что не все так просто: надо учитывать, какие вершины
входили/не входили в путь для обработанных и т.д.
Для того, чтобы было яснее, о чем я говорю, пример (стартовая вершина
принимается за нулевую):
В начале инциализации "соединяем" все вершины с нулевой, получаем пути для двух
вершин. Потом мы должны посмотреть, как бы получше присоединить к ним третью.
Для этого для каждой вершины j ищем
min(l[2,i]+d[i,j])
где i: 1..кол-во вершин
l[2]: строка матрицы, где мы храним длины "путей" (в данном случае, путей, сост.
из 2-х вершин).
d[i,j]: расстояние от j до i
И тут возникает вопрос (даже если мы как-то там учтем вхождения/невхождения
новых вершин в уже готовые пути): а не пытаемся ли мы жадно брать вершины? В
конечном счете (насколько я могу судить), так и есть. А это, очевидно, не всегда
лучшее решение (в моем случае - ровно 29/35 правильного решения :) )...
Это во-первых. А во-вторых, если бы у нас все получилось, то в конце (конкретнее
говоря, в последней стоке построенной матрицы) мы бы имели минимальные длины
путей, которые проходят от нулевой вершины до i-й через все остальные. Тогда
допустим, что в условии задачи сказано найти минимальный путь (или его длину) от
нулевой до _конкретно_заданной_. Если мы имеем длины всех путей, то имеем и то,
что требуется в этой новой гипотетической задаче. Hетрудно, однако, в этой новой
постановке увидеть одну классическую задачу. :)
Таким образом мы решили классическую задачу коммивояжера методом динамического
программирования. А это противоречит закону Мерфи (если гениальная идея
рождается, то она рождается либо раньше нас, либо не в нашей голове) :(((
Другие идеи есть? Как можно выюзать тот факт, что конечная вершина не задана?
ЗЫ: Или наоборот: как доказать, что задача - NP-полная?
Good bye, mister Kuznetsov _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста!
--- А у твоего ГолДеда стоит... фильтрация мессаг???
* Origin: Телепузик спать ложится - программист за комп садится. (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Ышо раз задачка 