Здравствуйте, Stanky, Вы писали:

>> Есть ли способы оценить длинну этого самого наименьшего пути, не находя
>> сам путь?
>>
S>А можно как-то поконкретней?

Конечно можно

Вот реализовал я алгоритм какой-нибудь для нахождения этого наименьшего пути и теперь неплохо было бы знать на сколько он хуже идеального...

_>Вот реализовал я алгоритм какой-нибудь для нахождения этого наименьшего пути и теперь неплохо было бы знать на сколько он хуже идеального...


Всмысле длиннее

> Вот реализовал я алгоритм какой-нибудь для нахождения этого наименьшего
> пути и теперь неплохо было бы знать на сколько он хуже идеального...
>
Наверное я не выспался, так как вообще не понимаю тебя!!!
Кто хуже? Какого идеального?

Здравствуйте, Stanky, Вы писали:

>> Вот реализовал я алгоритм какой-нибудь для нахождения этого наименьшего
>> пути и теперь неплохо было бы знать на сколько он хуже идеального...
>>
S>Наверное я не выспался, так как вообще не понимаю тебя!!!
S>Кто хуже? Какого идеального?

Я сам невыспался.

Чтобы знать на сколько путь найденный каким-либо приближённым алгоритмом длиннее идеального наименьшего пути мне надо знать длинну идеального пути(самого короткого из всех возможных) пути.
Вот и хочется узнать есть ли способы узнать длинну этого самого короткого пути

> Вот и хочется узнать есть ли способы узнать длинну этого самого
> короткого пути
>
Метод Дейкстры!!!

Здравствуйте, Stanky, Вы писали:

>> Вот и хочется узнать есть ли способы узнать длинну этого самого
>> короткого пути
>>
S>Метод Дейкстры!!!



Для 10 000 не проходит

> Для 10 000 не проходит
>
А конкретней?

Здравствуйте, Stanky, Вы писали:

>> Для 10 000 не проходит
>>
S>А конкретней?

Ему памяти нехватает.
Кушает 400 Мб и ещё просит

> Ему памяти нехватает.
> Кушает 400 Мб и ещё просит
>
А ты думал массив из воздуха браться будет?
Ну даже 400 метров не так уж и много — у нас в распоряжении почти 2ГБ!!! Я создавал массивы и 16384 * 16384!!!
А реально ли нужен массив 10000 * 10000? Например если граф неориентированный, то можно получить экономию в 2 раза, если массив сильно разреженый, то так же можно исхитриться!!!

Здравствуйте, Stanky, Вы писали:


S>А ты думал массив из воздуха браться будет?

Я ж понимаю

S>Ну даже 400 метров не так уж и много — у нас в распоряжении почти 2ГБ!!! Я создавал массивы и 16384 * 16384!!!
S>А реально ли нужен массив 10000 * 10000? Например если граф неориентированный, то можно получить экономию в 2 раза, если массив сильно разреженый, то так же можно исхитриться!!!

Дело в том что в этом моём графе получается что все вершины соеденины со всеми

> Дело в том что в этом моём графе получается что все вершины соеденины
> со всеми
>
Ну и в чём проблема-то?
Кстати ты так и не ответил: граф ориентированный?

Здравствуйте, Stanky, Вы писали:

>> Дело в том что в этом моём графе получается что все вершины соеденины
>> со всеми
>>
S>Ну и в чём проблема-то?
S>Кстати ты так и не ответил: граф ориентированный?

похоже что он направленый, у него все рёбра ориентированы

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

> и т.к. все вершины связаны со всеми то алгоритм Дейкстры выдаёт путь от
> выршины к вершине напрямую, без захода во все остальные.
>
Нафига он тогда такой красивый нужен?
Ты вообще програмулину, что я тебе кинул запускал?
Там всё очень наглядно можно посмотреть!!!

Например имеем (в хорошем смысле) матрицу стоимости:

    0   1   2   3   4
0  -1  10  20  -1  90
1  -1  -1  30  -1  -1
2  -1  -1  -1  20  50
3  -1  -1  -1  -1   5
4  -1  -1  -1  -1  -1

В строке хранятся расстояния от вершины с номером строки до вершины с номером столбца, -1 — означает, что вершина недостижима!!!
Например: расстояние от 0-й вершины, до 1-й равно 10, а вот из 1-й в 0-ю попасть нельзя (-1)!!!
Ну дык вот, алгоритм Дейкстры для данной матрицы стоимости выдаст такой результат (идём от 0-й ко всем остальным):

0 -> 1 = 10    //Здесь напрямую
0 -> 2 = 20    //Здесь напрямую
0 -> 3 = 40    //Здесь 0 -> 2 -> 3
0 -> 4 = 45    //Здесь 0 -> 2 -> 3 -> 4

Привет

_>Помогите советом, если кто-нибудь сталкивался...

_>Необходимо найти минимальный путь соединяющий данную точку со всеми остальными, которых порядка 10 000.
_>Точки заданы кординатами на плоскости

Во избежании дальнейшей путанницы автору предагается четко описать стоящую перед ним задачу. Очень желательно с примерами.

Здравствуйте, gid_vvp, Вы писали:

_>про задачу коммивояжера знаю, но интересует именно задача с таким огромным чилом пунктов.

от увеличения количества пунктов задача коммивояжера ну никак не становится другой задачей.

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

по поводу оценки приближенного решения — никак только сравнивать с другими же приближенными. точного решения задачи коммивояжера для 10000 пунктов ты не найдешь никогда

Здравствуйте, bipka, Вы писали:

B>от увеличения количества пунктов задача коммивояжера ну никак не становится другой задачей.

Полностью согласен

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

Да всё идёт к нему: генетическому алгоритму...
Может есть ещё варианты?

Попробую сформулировать чётко:
1. На плоскости расположено 10000 точек, их расположение задано координатами (в декартовой системе координат)
2. Необходимо, начиная с некоторой наперёд заданной точки, обойти всё 10000 точек таким образом, чтобы путь оказался наименьшим.

B>по поводу оценки приближенного решения — никак

Жаль, конечно...
Но в алгоритме Литла, помоему, как-то оценивается минимальный путь...
Вот и хотелось бы узнать на сколько точно это и возможно ли вообще?
Хотя Вы уже ответели что нет.
Может кто-нибудь ещё скажет?

B>только сравнивать с другими же приближенными. точного решения задачи коммивояжера для 10000 пунктов ты не найдешь никогда

Думаю ближаешее время этого не сделает никто

Здравствуйте, Den Raskovalov, Вы писали:

DR>Во избежании дальнейшей путанницы автору предагается четко описать стоящую перед ним задачу. Очень желательно с примерами.

вот тут сформулировал точнее:
Re[2]: поиск минимального пути

Автор: gid_vvp
Дата: 10.01.05

Хотя Вы и так всё правильно поняли

Здравствуйте, Stanky, Вы писали:

S>Нафига он тогда такой красивый нужен?
S>Ты вообще програмулину, что я тебе кинул запускал?
S>Там всё очень наглядно можно посмотреть!!!

Спасибо за помощь, я разобрался в этом алгоритме.

Здравствуйте, gid_vvp, Вы писали:

_>Да всё идёт к нему: генетическому алгоритму...
_>Может есть ещё варианты?
на самом деле, если сравнивать с другими алгоритмами, ГА дает весьма неплохой результат, особенно если время критично.
_>Попробую сформулировать чётко:
_>1. На плоскости расположено 10000 точек, их расположение задано координатами (в декартовой системе координат)
_>2. Необходимо, начиная с некоторой наперёд заданной точки, обойти всё 10000 точек таким образом, чтобы путь оказался наименьшим.
ну тогда и нет разницы, с какой именно точки обходить
_>Но в алгоритме Литла, помоему, как-то оценивается минимальный путь...
_>Вот и хотелось бы узнать на сколько точно это и возможно ли вообще?
имхо — только реализовать несколько алгоритмов и сравнивать. сам я давно хочу написать развернутую статью по сравнению алгоритмов для решения задачи коммивояжера, причем я очень надеюсь, что ГА там будет одним из лучщих
но все времени не хватает
_>Хотя Вы уже ответели что нет.
_>Может кто-нибудь ещё скажет?
емэйл дай. пришлю свою древнюю дурацкую статью (на 2м курсе писал про решение TSP ГА. кое чем может поможет при реализации

Здравствуйте, bipka, Вы писали:

B>имхо — только реализовать несколько алгоритмов и сравнивать. сам я давно хочу написать развернутую статью по сравнению алгоритмов для решения задачи коммивояжера, причем я очень надеюсь, что ГА там будет одним из лучщих
B>но все времени не хватает

Надеюсь пару штук реализую.

B>емэйл дай. пришлю свою древнюю дурацкую статью (на 2м курсе писал про решение TSP ГА. кое чем может поможет при реализации

gid_vvp{at}tut.by
вместо {at} @

Спасибо.