коммивояжёр

From

Ilya Rogov (2:5030/1334.1024)

To

Stanislav Shwartsman

Date

2003-01-11T01:43:28Z

Area

RU.ALGORITHMS

    Привет тебе, Stanislav, с того света от Ильи.

 Давным-давно, 10 Jan 03 09:07, когда земля была ещё тёпленькая
 и по ней бегали мамонты, Stanislav Shwartsman и Ilya Rogov говорили про коммивояжёр:

 IR>>   Кто-нибудь слышал о НЕРЕКУРСИВНОМ решении задачи сабжа ? Я
 IR>> подчёркиваю - НЕРЕКУРСИВНОМ. Ведь всякую рекурсивный алгоритм
 IR>> можно преобразовать в аналогичный итерационный. Или я не прав ?
 SS>  В связи с тем, что сабж задача NP-полная, искать ее оптимальное
 SS>  решение даже "почти полным перебором" уже практически бессмысленно.
 SS>  Для решения таких задач используются приближенные алгоритмы, которые
 SS>  вместо "почти полного перебора" предлагают "почти оптимальное
 SS> решение" зато за приемлемое время. И вот они-то как раз чаще всего НЕ
 SS> рекурсивны :)

   Дело в том, что я хочу проверить работу как раз именно такого алгоритма. Я ведь не буду на глазик считать наикратчайший путь в графе даже из 5 вершин. А хочется проверить, скажем для 10-15. Время пока есть, посижу часик перед монитором, потерплю ...

                                                        Ilya Rogov
... Бредить помогали вопли моих соседей
---
 * Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)